.O.
..O Deniz's personal pages
OOO
/home /about

Terrain generation using cellular automata

January 24, 2017

Cellular automata are a nice way of representing natural terrains for game worlds. The idea is that a cell interacts with its neighbor cells changing their content, just as a natural process would do. The method actually stems from biology, where a population interacts with their neighbors either dying due to scarce resources or thriving by multiplying due to enough mates. The algorithm is pretty simple, each cell has a binary state that toggles based on the number of neighbors in a state. E.g if the current cell has more than 4 neighbors that are alive it will die, otherwise it will live. As you iterate the 2x2 matrix of cells an organic pattern starts to emerge which is what we need when imitating a terrain of grass. The cells may have more than 2 states, but I’ve used only too to generate a grass land with 2 types of grass tiles.

    public boolean[][] run(int width, int height, int death, int birth, int runs) {
        boolean[][] map = new boolean[height][width];
        boolean[][] temp = new boolean[height][width];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = Utils.coinFlip();
                temp[i][j] = map[i][j];
            }
        }

        int WIDTH=map[0].length, HEIGHT=map.length;

        for (int k = 0; k < runs; k++) {
            for (int y = 0; y < HEIGHT-1; y++) {
                for (int x = 0; x <WIDTH-1; x++) {
                    int nbs = aliveNeighbors(temp, x, y);
                    if (temp[y][x]) {
                        map[y][x] = nbs >= death;
                    } else {
                        map[y][x] = nbs > birth;
                    }
                }
            }

            //copy generated to temp for the new run
            for (int i = 0; i < map.length; i++) {
                temp[i] = map[i].clone();
            }

        }
        return map;
    }

the death and birth parameter define how many neighboring alive cells trigger a death or a birth. The runs parameter defines how many generations we will process.

   public int aliveNeighbors(boolean[][] map,int x, int y) {
        int count=0, my = map.length, mx = map[0].length;
        for (int i = -1; i <2; i++) {
            for (int j = -1; j < 2; j++) {
                int nx = x + i;
                int ny = y + j;
                if (i == 0 && j == 0) {

                } else if (nx < 0 || ny < 0 || nx > mx || ny > my) {
                    count++;
                } else if (map[ny][nx]) {
                    count++;
                }
            }
        }
        return count;
    }

Here is an example output

Tags: #gamedev