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

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 3

If you had a central Manager which could receive and emit notifications, you could use an Observer pattern. Every time a turn evolves, the animals notify where they are. The Manager notifies who is there, and they execute their eat() method according to the context. When they are done eating, they notify() the manager, who in turn tells them what to do (e.g. sheep.die())

Answer 4

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 5

Off the top of my head, you might do something like this:

Have a single World object that manages a list of Player objects. The player has the following methods:

Player

• public void takeTurn( World world )
• public boolean isDead()
• public void kill()

When the World instance gets to each player, it asks it if it is dead. If not, it calls the takeTurn method. Or, takeTurn can call isDead() internally and just return if it is. If you kill another player (or yourself), you just call the player's kill method.

Passing in the world to the takeTurn is just in case you need to make a callback to update the state of the world.

Answer 6

One way to do this is:

1. Have the sheep do their actions and record them on the next step.
2. Update the board for the sheeps actions
3. Do each wolf action and record them on the next step.
4. Update the board for the wolf actions.

Two ways two multithread this are:

• Divide the Board into different regions and assign each thread to a region. You'll have problems figuring out how to move it from one region to another.

• The other way could be to break the loop through creatures to different threads. eg

  for(w=THREAD_NUM; w<NUM_OF_WOLVES; w+=NUM_OF_THREADS) { w.doAction(); }

Answer 7

It sounds like you wish to have the world evolve in the same manner every time like Conway's life. In Life, you look at each cell and calculate what the outcome for it would be based on the previous state. If the cell has two neighbors it will live to the next generation, no matter if those neighbors won't be there in the next generation. The original state should be read-only and the rules should work no matter what.

For instance, what if you have two wolves near a sheep, would they both eat it, or just one? If just one, then you need a rule for which one gets to eat the sheep and the other one needs to know that. You could go the opposite way, i.e. look at the sheep, find pick an animal that would eat it. Let's say that you only want one wolf to eat the sheep and you say that the wolf with the lowest 'Y' coordinate gets the sheep, or the lowest 'X' coordinate if there are two wolves with the same 'Y'. If you are processing a wolf you need to make sure there is no other wolf that would eat the sheep first. This could get more confusing because maybe that would has another sheep near it that it would eat, so it wouldn't eat the first one...

The easiest way would be to say that all animals can do their actions no matter what happens to them in the evolution to the next round or what any other animal does. If a sheep is surrounded by three wolves, it will be dead the next round and all wolves will share in the meal. If there is grass next to a sheep, the sheep will eat it even if the sheep is surrounded by wolves. For the wolves, they will all be fed that round because they were next to a sheep.

public class Cell {
    public int CellType = 0; // 0 == empty, 1 == grass, 2 == sheep, 3 == wolf
    public int Feedings = 0;
}

public class World {
public Cell [] Cells = new Cell[100];
public int Rows = 10, Cols = 10;

public Cell GetCell(x, y) {
    if (x < 0 || x >= Cols || y < 0 || y >= Rows) return null;
    if (Cells[y * Cols + x] == null) {
        Cells[y * Cols + x] = new Cell();
    }
    return Cells[y * Cols + x];
}

public World Evolve() {
    World w = new World();
    for (int y = 0; y < Rows; y++) {
        for (int x = 0; x < Cols; x++) {
            HandleCell(w, x, y);
        }
    }
    return w;
}

public void HandleCell(World newWorld, int x, int y) {
    Cell result = newWorld.GetCell(x, y);

    Cell c = GetCell(x, y);
    if (c.CellType == 2) { // sheep
        bool foundWolf = false;
        bool foundGrass = false;

        // code here to find if a wolf or grass are around the sheep

        if (foundWolf) {
            // default cell type is empty, so leave it be (wolf ate me)
        } else {
            result.cellType = 2; // still a sheep here
            if (foundGrass) {
                result.Feedings = c.Feedings + 1; // and he ate!
            } else {
                result.Feedings = c.Feedings; // or not...
            }
        }
    }

    if (c.CellType == 3) { // wolf
        bool foundSheep = false;

        // code here to find if a sheep is around the wolf

        result.CellType = 3;
        if (foundSheep) {
            result.Feedings = c.Feedings + 1; // ate the sheep!
        } else {
            result.Feedings = c.Feedings;
        }
    }
}

Answer 8

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.

Answer 9

Maybe you could do this totally random.

First random example: sheep eats the grass and then the wolf eats the sheep (sheep -> wolf)

Second random example: wolf eats the sheep, because the poor thing was too slow to get to the grass (wolf -> /)

Is the real world deterministic? :)