In my last blog post, we talked about pseudo-random number generation and how that can be used to add a bunch of variety to your games. Today, we are going to go over something a little bit more complicated using the same ideas. We are going to use PRNG to create some random cave-like environments using a programming model called cellular automata. That probably sounds complicated, but it can be quite simple. In the simplest terms, cellular automata is a set of rules that are applied to an individual cell on a grid.

These concepts have been widely discussed, and studied, for many years. This is also a common way to randomly generate maps for roguelike games. If you are already familiar with these concepts, you will probably be familiar with the whole process I am about to cover. As usual, I will be using GameMaker for this example.

Now let's look at how to set up these rules, and generate some caves.

Defining rules

Before we get to defining the rules in code, let's go over the general concept of the generation process. The rules we are going to follow are simple.

First, populate a grid with random walls, then run the following set of rules on each cell in the grid.

1. Check the neighboring cells of each cell on the grid, and see how many of them are also walls.

2. If the cell is a wall, and four or more of its eight neighbors are also walls, it remains a wall.

3. If the cell is not a wall, and five or more of its neighbors are walls, it becomes a wall.

Check out this grid below. Imagine the black squares are walls, and the white squares are empty space. All of the walls have been placed on the grid randomly. Take a look at the wall in the middle of the grid, labeled "one." The red spaces around the middle cell are its neighbors. Using the rules above, we can determine that this cell should not remain a wall. Only two of its neighbors are walls, and in order to remain a wall, it would need four or more neighbors that are walls. Meanwhile, the cell labeled "two" would remain a wall, because it has at least four neighbors that are walls.
 

By checking each cell in a grid, and applying these simple rules, we will be able to generate some cave-like formations.

Random walls

Before we can start generating a bunch of cool caves, we need to do a little bit of set up. The first thing we need to do is define our grid. This means figuring out how big the grid will be, and how big each cell within the grid will be. I’m going with cells that are 16x16 pixels, and the size of the grid will be automatically determined by the size of the room the grid is in. Here is what that looks like.

Initialize grid variables

grid_size = 16;
map_w = room_width / grid_size;
map_h = room_height / grid_size;

map = ds_grid_create(map_w,map_h);

GameMaker has a series of functions relating to grids that I will be using throughout this example. In depth information about ds_grid functions is at the end of this blog. All you really need to know for now is how to create a grid of data, which we are going to store cell information in.

Now that we have our grid we need to prefill it with a bunch of random walls, otherwise we won’t have any cells to check for the actual cave generation.

Place random walls

for(w = 0; w < map_w; w++){
	for(h = 0; h < map_h; h++){
		//fill with a wall a random % of the time
		map_middle = map_h * 0.5;
			
		if(h == map_middle){
			map[w,h] = 0;	
		}else{
			map[w,h] = randomPercent(45);
		}			
	}
}

randomPercent

if(argument[0] >= irandom(100)){
	return 1;
}else{
	return 0;	
}

Surprise! We have two blocks of code, but like I said before, they are both pretty simple. The first block simply loops through the cells in the grid, and based on a 45% chance, will turn that cell into a wall. There is also a check in there to prevent the cell in the center of the room from being a wall. The second block of code is a little function I wrote to return true or false based on a percent chance. This should make about 45% of the cells in the grid into walls. Now we have something to work with!

Cave generation

We have our grid that is about 45% full of walls, and we know what rules we need to follow in order to generate some caves. All we need to do now is check each cell in our grid, and apply our rules.

Make caves

for(w = 0; w <= map_w - 1; w ++){
	for(h = 0; h <= map_h - 1; h ++){
		map[w,h] = placeWallLogic(w,h);
	}		
}

This should look familiar at this point. We are looping through the cells in the grid again, and then with the placeWallLogic script, we apply our rules.

placeWallLogic

///placeWallLogic ( width, height );
startX = argument[0] - 1;
startY = argument[1] - 1;
endX = argument[0] + 1;
endY = argument[1] + 1;

iX = startX;
iY = startY;

var wall_counter = 0;

for(iY = startY; iY <= endY; iY++){
	for(iX = startX; iX <= endX; iX++){
		if(!(iX == argument[0] && iY == argument[1])){
			if(isWall(iX,iY)){
				wall_counter ++;	
			}
		}
	}
}

num_walls = wall_counter;

if(map[argument[0],argument[1]] == 1){
	if(num_walls >= 4){
		return 1;
	}
	if(num_walls < 2){
		return 0;	
	}
}else{
	if(num_walls >= 5){
		return 1;	
	}
}

return 0;

In this block, we check each of the neighbors around a particular cell, check and see if it is a wall using the isWall script, and the cell is changed to a wall accordingly.

isWall

if(map[argument[0],argument[1]] == 1){
	return true;	
}

if(map[argument[0],argument[1]] == 0){
	return false;	
}

The isWall script simply checks to see if a cell is or is not a wall, and returns true or false. Now we have a grid full of data that, once drawn to the screen, should show us a pretty cool randomly generated cave! I wrote a little autotiler script to place tiles based on the cell in the grid.

autotiler

//auto tiler
collisionLayer = layer_create(-1);
tilemapWalls= layer_tilemap_create(collisionLayer,0,0,tiles_collision,room_width,room_height);

for(w = 0; w < map_w; w++){
	for(h = 0; h < map_h; h++){
		if(map[w,h] == 1){
			tilemap_set_at_pixel(tilemapWalls,1,w*grid_size,h*grid_size);	
		}
	}
}

The tile system in GameMaker Studio 2 is a little more complex than the previous version, but its functionally the same. We have to define a tile layer (collisionLayer) and create a tilemap (tilemapWalls) before we can place tiles. Then it's a simple matter of looping through the grid, which you should be a pro at by now, and placing a tile if there is a wall.

Here are a couple of caves I was able to generate. This was using a 16x16 cell, in a room that is 960x960, which means there are 3,600 cells in the room!
 

Additional reading

• GameMaker Studio 2 ds_grids
• GameMaker Studio 2 tiles
• Cellular Automata

Nathan Ranney is the founder of game development studio Gutter Arcade. He's best known for the creation and development of Knight Club, an online indie fighting game.