Simulating a sequence of events concurrently subject to a happened-before partial order

Question

I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time.

I have a logic part that calculate those actions for each turn, and than pass it to the game engine to animate. This is the list of action that I currently supporting:

• perform attack
• perform miss
• perform taking damage
• perform dying
• perform moving

If I animate all the actions at once than it look messy:

Unit A attacks unit B, while unit B is not even there, it went to attack unit C

If I animate all the actions one by one, than it looks lame

Unit A attacks unit B, the other 18 units is just stand and waiting for the unknown...

How can I find what actions I can perform in parallel?

For now my best solution, is to wait for unit to finish attacking before attacking it, it cover many scenarios but it still got halls.

Unit A attacks unit B, unit C waiting for A to finish attacking in order to attack him. Unit D attacks and kill unit C.

Edit based on D.W answer:

This solution cover most of the cases but, I found a hall in it.

Think about the next scenario

A attacks B, B attacks C, C attacks D

Because each of those action has a dependency on the prevues one, your algorithm would suggest to break it in to 3 sequences.

• A attacks B
• B attacks C
• C attacks D

How ever I would like to break it in to, two sequences:

• A attacks B, C attack D
• B attacks C

I want to use your algorithm solution iff B kills C.

Answer 1

Try identifying all dependencies between actions, then build a DAG that represents the dependencies: each vertex is an action, each edge is a dependency between two actions. From this you can identify how to perform the maximum number of actions in parallel. Basically, the algorithm is:

1. Find all the sources. Perform all of those actions at once.

2. Delete all of those sources, and the edges going out of them.

3. Go back to step 1.

A source is a vertex with in-degree zero, i.e., with no edges entering into it. In your context, it will be an action all of whose dependencies have been satisfied.

For instance, if action 1 must occur before action 2, which must occur before action 4, and action 3 must occur before action 4, the resulting order you get using this algorithm is: first actions 1 + 3 are performed (because they are the two sources); then action 2; then action 4.