Game of life : how to have "entities" to evolve in parallel?

Question

Ok the title is not clear, here is what I mean.

I am programming some kind of game (like the game of life). For example, there are animals (each animal is a Java instance of a class).

All these animals are on a map, and all this "world" evolves each "turn".

These animals can make actions at each turn. Example : a wolf kills a sheep.

But, I have trouble regarding the "way" to make these evolution between states, because the result will depend of the order I loop through the animals.

Example :

• Wolf first : the wolf kill the sheep (then the sheep is dead, so no action)
• Sheep first : the sheep eats some grass and THEN (turn of the wolf) the wolf kills the sheep

How can I solve this problem ?

Multithreading ? (but I will have a lot of animals, like 1000 and even more...). Is there an algorithm, a "way" to do that ?

Thanks

Answer 1

You should model the turns properly, i.e. have every animal take its turn based on the current state of the world, so that the results of the action get updated into the next state of the world, not the current one. I.e.

1. In the current step, the sheep eats some grass, and the wolf kills it.
2. In the next state of the world, there is a content wolf and no sheep (or a sheep carcass - depending on your model).

This way the order of evaluation is not affecting the outcome, which opens up the possibility to e.g. parallelize the execution, preferably using FutureTasks and a ThreadPoolExecutor.

Answer 2

Thread concurrency is not the main issue here. I believe that the right model should be allowing every entity to decide on an action in the current turn. Then, for determining the game state at the next turn you should process the actions, resolving conflicts if needed. You should decide on rules for resolving all kinds of "conflicting" action combinations taken by two different players.

Answer 3

Oh, you don't want to get into multi-threading, things will get even more confusing.

In this case, iterate through all animals and let them choose their action. THEN update the map.

Answer 4

I think it is only possible for entities to evolve in parallel in very simple scenarios (Conway's life as an example) - for your "wolves-sheep-grass" world it's getting more complex the more you think about it:

• Consider a situation with two wolves and one sheep. Wolf One decides to eat the sheep; Wolf Two decides to eat the sheep - how would you decide which one gets the sheep (let's suppose that eating is an atomic operation - wolves can't share their meals). So you still will need to decide on some order so, say Wolf One gets a sheep and Wolf Two gets nothing (which is completely unexpected for the Wolf Two - there was a sheep a second ago, it opens its mouth and - BAM! - there's nothing)

• There are two wolves and two sheep; both sheep "attractiveness" is the same for both wolves, so they choose their prey randomly. Unfortunately, they're choosing the same sheep, Wolf One eats Sheep One, Wolf Two tries to eat Sheep One too but it magically disappears right under its nose. End of turn. In the next turn Sheep Two runs away, Wolf Two starves - which is completely illogical.

So I think simply iterating over the list of Animals and calling a method for each animal which performs an atomic action results in a more logical universe. If you're concerned that animals spawned earlier have unfair advantage over the ones spawned later you may just randomize the list of Animals before each turn - this way, in your example, either Sheep eats some grass and then is getting eaten by the Wolf, or the Wolf eats it before it has a chance to eat any grass. C'est la vie.