Best solutions for designing two dimensional world - Game of life

Question

I need to create application which would simulate predator-prey relationship. I can use some framework( ex. repast), but I am wondering about writing application from scratch.

The biggest problem for me is way of representing map with food sources, predators and prey.

Very simple model

I was thinking about two dimensional array of lets say Cell. Cell would have boolean fields predator, food and prey and corresponded setters and getters. Predators and prey would wander around and observe cells in specific radius( range of sight). If predator spots prey it moves toward it. If prey spots predator it moves in opposite direction. Not disturbed prey is wandering until it find source of food.

Moving/Wandering

In this example Animal is goes to Destination point.

   _ _ _ _ _ _      _ _ _ _ _ _                _ _ _ _ _ _
0 |_|_|_|_|_|_|    |_|_|_|_|_|_|              |_|_|_|_|_|_|
1 |_|A|_|_|_|_|    |_|_|_|_|_|_|              |_|_|_|_|_|_|
2 |_|_|x|x|_|_| -> |_|_|A|x|_|_|    . . .     |_|_|_|_|_|_|
3 |_|_|_|_|x|_|    |_|_|_|_|x|_|              |_|_|_|_|_|_|
4 |_|_|_|_|_|D|    |_|_|_|_|_|D|              |_|_|_|_|_|D|
   0 1 2 3 4 5

This walk consumes 5 moves and Animals will have some specific speed( 2 moves/second). In every move one Cell is setting predator to false, and another is setting it to true. With programming it will looks like this( of course there would be method moveTo(x,y)):

Animal animal = new Animal(1,1);
animal.setPosition(2,2);
animal.setPosition(3,2);
animal.setPosition(4,3);
animal.setPosition(5,4);

Observing

Sample predator observation with max range of 3. I have marked observed cells by x. Observation is just simple checking if getPrey() returns true:

   _ _ _ _ _ _ _      _ _ _ _ _ _ _      _ _ _ _ _ _ _          
0 |_|_|_|_|_|_|_|    |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|      
1 |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|    |_|x|x|x|x|x|_|        
2 |_|_|_|x|_|_|_|    |_|_|x|x|x|_|_|    |_|x|x|x|x|x|_| 
3 |_|_|x|A|x|_|_| -> |_|x|x|A|x|x|_| -> |x|x|x|A|x|x|x|       
4 |_|_|_|x|_|_|_|    |_|_|x|x|x|_|_|    |_|x|x|x|x|x|_|
5 |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|    |_|x|x|x|x|x|_|
6 |_|_|_|_|_|_|_|    |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|
   0 1 2 3 4 5 6

The best way would be observing area around with every step( move) but it seems like a lot of computations( checking conditions). Am I correct at this point?

Is this good approach to hold most of data in two dimensional array? I will appreciate any constructive answers.

This is only sample example. In future I would like to add reproduction, mood, inteligence, etc.

Thanks.

EDIT

I forgot to mention scale of the problem.

I think that number of Predators and Prey would be less than 100. But it's only guess. Size of map would be 500x500 or even smaller.

Answer 1

Asking for the best solution always implies an uncomfortable pressure. And in order to properly answer such a question and really give the best solution, one requires a degree of detail in the problem specification that is hard to Conway.. eh.. convey on a Q&A site.

But not only because of the difficulties in answering this question, I'd recommend to model this as an interface in the first place. Assuming you already have a Cell interface, you could represent the World as a

interface World {
    Cell get(int x, int y);
    int getSizeX();
    int getSizeY();
}

Depending on the trade-off between memory consumption and efficiency, you can then offer various implementations. For a "dense" (and very efficient) implementation, you can use arrays:

class ArrayWorld implements World {
    private Cell cells[][] = ...

    @Override
    public Cell get(int x, int y) {
        return cells[x][y];
    }
    ...
}

For a "sparse" (although slightly less efficient) implementation, you might use something like a

class MapWorld implements World {

    // Assuming a class "IntPair" which encapsulates
    // two int values, with proper implementation 
    // of hashCode and equals:
    private Map<IntPair, Cell> map = new HashMap<IntPair, Cell>();

    @Override
    public Cell get(int x, int y) {
        return map.get(new IntPair(x,y));
    }
    ...
}

The neat thing here is that you may easily implement a property of the world that is frequently used in such cellular automata: Namely, a world with a "torus" topology, where the coordinates are "wrapping" at the borders:

class TorusWorld implements World {
    private World delegate = ...

    @Override
    public Cell get(int x, int y) {
        int wrappedX = ((x % getSizeX()) + getSizeX()) % getSizeX();
        int wrappedY = ((y % getSizeY()) + getSizeY()) % getSizeY();
        return delegate.get(wrappedX, wrappedY);
    }
}

This "Torus world" can then be backed by any other implementation of the World interface.

However: You also mentioned an Animal class, so it's not entirely clear what your Cell class should look like: Will the Cell really contain an Animal? Or only a set of flags that show whether the cell contains Food, a Prey or something else? Will it be possible that the Cell contains two things (e.g. a Predator and Food, which probably will not interact)? These are all the questions that should be answered as early as possible, during the specification phase.

Answer 2

This really depends on the size of your matrix and how sparse it is. But a cell model should be fine especially if you have random access to the coordinates (x, y) and do not want to have a huge matrix. For efficient code you could have a look at 'serious' Game of Life implementations:

• What's an efficient implementation of Conway's Game of Life for low memory uses?
• Optimizing Conway's 'Game of Life'

The issue is mainly with memory consumption vs speed (hmmm... as usual).

What you are looking for are cellular automata. Doing those from scratch is interesting and fun.

Answer 3

Your 2d-array approach is always the simplest to implement. Think in advance what the maximum array size will be.

If you have the need to use a huge world with a mixture of dense and sparse life, then there are much better alternatives, but all of them are much more complex.

For dynamic 2d structurees, take a look on quad trees, or even you could mix up a quad tree with your 2d array approach.