I'm working on a 2d game similar to Minecraft (Redstone), where certain actions have to be executed in a predefined order every tick. There are multiple "modules" that can each register multiple "actions". I need a way to correctly execute them in order while not messing everything up. Those modules can be made by different developers, so conflicts should be resolved automatically. The number of actions is in the double digits, so no need for performance.
My idea is to use bounds, where you define actions as executing before or after some other action.
Imagine there is one module labeled "1" looking like this, containing 3 actions:
1.A: after START
1.B: after 1.A
1.C: after 1.B
Then you have another module "2" that gets added later:
2.A: after 1.B
In this case I would want the order to be
This is pretty straight forward to understand, but issues quickly come when I have two definitions with the same bounds. Which one should have priority? This is actually the case here, since both 2.A and 1.C have the same bound. I thought about adding "before" bounds to the definition of 1.B and 1.C to basically "push" them further apart, which would make sure that 2.A goes between 1.B and 1.C.
However those are all just informal ideas and I feel like a problem similar to this must already exist somewhere, and I'm just too dumb to find it.
A completely different approach would be to somehow coordinate all those developers to agree on a predefined order, which would require some kind of global registry for those actions, which I don't really want because it complicates simple lightweight scripting. If you have any idea how to do this efficiently without overcomplicating things, I'm also happy with that.
Sounds fun.
I'll ignore modules because they don't seem to affect the core issue. They're just a packaging mechanism.
You have a list of actions, each with "after" and "before" dependencies. The actions must all get executed, one by one, in an order which doesn't violate the dependencies. To keep things general, I'll assume that each action can have zero or more "after" and zero or more "before" dependencies.
I'll also assume that an action doesn't care about any actions which aren't listed among its dependencies or among its dependencies' dependencies etc. So in your example, it shouldn't matter whether you run 1.C before 2.A or 2.A before 1.C, as long as they both execute after 1.B.
One thing that I noticed makes life easier is that if action B has A as its "before" dependency, it's safe to also add B to A's "after" dependencies and vice versa. So once you collect all actions from all developers listing their afters and befores, you can interlink the actions so that all afters have corresponding befores on the other side and vice versa.
Once you have that, you can start your output sequence with any actions which have no "after" dependencies. Then add all actions whose "after" dependencies are all already listed and continue until you're done.
Here's some pseudocode:
type action
{
contains Afters, a set of actions.
(This action must be sequenced after all of its Afters.)
contains Befores, a set of actions.
(This action must be sequenced before all of its Befores.)
}
procedure PreprocessActions
{
Actions is an input parameter, a set of actions to modify.
for each Action in Actions
{
for each Other in Action.Befores
{
add Action to Other.Afters.
}
}
}
procedure OrderForExecution
{
InputActions is an input parameter, a set of actions.
Sequenced is the return value, a list of actions.
set Sequenced to be an empty list.
Unprocessed is a local variable, a set of actions.
fill Unprocessed with copies of actions in InputActions.
execute PreprocessActions on Unprocessed.
(If it's ok to modify the input itself, Unprocessed is not needed and
you can execute PreprocessActions on InputActions directly.)
Processed is a local variable, a set of actions.
set Processed to be an empty set.
while Unprocessed is not empty
{
Next is a local variable, an action.
set Next to be any action from Unprocessed without any afters
or whose afters are all listed in Processed,
but only if there's no Processed actions listing it among their Befores.
if not found, set Next to be any action from Unprocessed without any afters
or whose afters are all listed in Processed.
(If none can be found, throw an exception or error or something.
It's either a circular dependency or conflicting constraints.)
remove Next from Unprocessed.
add Next to Processed.
append Next to the end of Sequenced.
}
}
Sets should be some data structure without duplicates and with quick insertions, removals and lookups. (For instance, .Net's HashSet or C++'s unordered_set.) The output list should be something ordered, with quick appends to the end (for instance, .Net's List or C++'s vector, or just a basic array since size is known up-front). If you wish to keep ordering predictable even for actions which shouldn't care about which runs first, make Unprocessed some sorted dataset with quick removals and sort the elements by module name then action name or something like that (e.g. .Net's SortedSet or C++'s set).
The algorithm should run in quadratic time. There's probably opportunity for optimization there, but you probably won't have enough actions to be worth the effort. Especially since I assume that the list can be precalculated once and then reused millions of times.