1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems to be a question about concurrency, not parallelism. And it's not at all about game theory. I actually think it's mostly a programming question. $\endgroup$ – Raphael Jul 14 '14 at 11:02
  • $\begingroup$ I think you need to spend a bit more time thinking through exactly what are the requirements. Can you frame this as a specific technical question? For instance, are you looking for the actions that occur in each round to form an independent set in the "attacks" graph? Something else? Right now this question is not well-defined enough to answer, so the first step is for you to see if you can articulate the precise requirements. $\endgroup$ – D.W. Jul 14 '14 at 19:05
  • $\begingroup$ @D.W. Hope it is more clear now. $\endgroup$ – Ilya Gazman Jul 14 '14 at 19:33
  • $\begingroup$ @Ilya_Gazman, well, no, this question isn't any more clear -- this question remains exactly the same as it was when I made my comment. My comment was on the latest version (after your edit), and reflects your edit. $\endgroup$ – D.W. Jul 14 '14 at 23:49
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand the algorithm. What are sources? Can you explain your example with the algorithm? $\endgroup$ – Ilya Gazman Jul 14 '14 at 3:07
  • $\begingroup$ @Ilya_Gazman, I've edited my answer to try to clarify that. Sorry about any confusion! $\endgroup$ – D.W. Jul 14 '14 at 17:46
  • $\begingroup$ Wow, now I actually got it. Tnx $\endgroup$ – Ilya Gazman Jul 14 '14 at 17:52
  • $\begingroup$ Found a hall in this solution, please review my edit to the question $\endgroup$ – Ilya Gazman Jul 14 '14 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.