In the spirit of the ProcJam2014 (that unfortunately I have to skip because of a ton of academic duties :<) I’m presenting to you a simple algorithm to generate maps: the cellular automata generator. In particular, cellular automata are very well suited for cave-like environment and, in general, natural maps. It works both in 2D than in 3D and can be easily implemented in no more than 20 minutes.

From the theoretical point of view, a cellular automata is a discrete model that consist in a regular grid of cells. Each cell can have a finite number of states (usually two: on and off). On top of this grid, a system of rules is built to control the evolution of the cells. The rule are usually simple and local: this means that each rule decide on the state of a single cell just on the basis of a limited set of cells (the neighborhood) located around the cell of interest. No rule on the global state of the grid can exist! For instance “the total number of cell in the on state is less than X” is NOT a local rule.

There are a huge amount of theoretical work on cellular automata. The good news is that you have to know nothing about that to use them! Let’s see an example.

In the small applet above you can see the algorithm at work. First we start with a completely random map in which each cell is initialized randomly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function randomMap(randomAmount) {
	for (var r=0;r<height;r++) {
		map[r] = new Array();
		for (var c=0;c<width; c++) {
			if(isOnBorder(r,c)) {
				map[r][c] = 1;
			} else {
				var mapMiddle = (height / 2);
				if (r == mapMiddle)
                {
                    map[r][c] = 0;
                } else{
					if (Math.floor((Math.random() * 101)) < randomAmount) {
						map[r][c] = 1;
					} else {
						map[r][c] = 0;
					}
				}
			}
		}
	}
}

In the applet above, I have set the amount of initially “wall” cells to 40%. There is no reason for this number, it is just an empirical number. If you look better the map, you can see an empty column at the center of the map. Also in this case, there is no technical reason: I’ve just seen that with an empty line in the center of the map I usually get better results.

Then, you can press the “Evolve” button. The evolve button starts the cellular automata evolution algorithm. This is really simple. For each cell I check the following rules.

• If the cell is a wall: if the number of walls around that cell is greater than 3, the cell remains a wall. Otherwise it becomes empty.
• If the cell is empty: if the number of walls around that cell is greater than 5 or the number of walls in a range of two step from that cell is less than 2, the cell becomes a wall. Otherwise it remains empty.

As usual, the code is better than thousand words.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function cellularLogic(r,c,clean) {
	var numWalls = countAround(r, c, 1, 1);
    var numWalls2 = countAround(r, c, 2, 2);

    if (isWall(r,c))
    {
        if (numWalls >= 3)
        {
            return 1;
        }
        return 0;
    }
    else
    {
        if (!clean) {
            if (numWalls >= 5 || numWalls2 <= 2) {
                return 1;
            }
        } else {
            if (numWalls >= 5) {
                return 1;
            }
        }
    }
    return 0;
}

Because these rules leave some single-wall in the empty spaces, there is another rule that can be used to “clean” the map. You can see the effect of this second rule with the “Clean” button.

As you can see, the result of this algorithm is amazing1 and it is so easy to implement! There must be a flaw! Well, there is. Cellular automata algorithm are powerfull but are really difficult to control. There is really low control on the shape and features of the map. Moreover, this algorithm is extremely sensible to rule and parameter variations. Changing the initial randomness, or a single element of the evolution rule can have an huge impact on the final result. For this reason, this algorithm is suitable only in that situations in which the completely randomness of the level is a desired features. In other cases (or if you want an “artificial” environment or dungeon) there are other algorithms that are recommended.

The full javascript code can be found here. There is also a C++ implementation on my GitHub account here.

I hope you enjoy this!