I am building a strategy game where multiple units(5 - 20) is fighting each othe

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.