Simulating a sequence of events concurrently subject to a happened-before partial order 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.
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:


Find all the sources.  Perform all of those actions at once.
Delete all of those sources, and the edges going out of them.
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.