Cave levels in games are fun to play. When designed well, they, like real caves, ignite our desire to explore the unknown. They can be dangerous and rewarding. But, designing anything by hand takes time and effort; oftentimes a lot. Is there a faster way to make good-quality caves? Ones that look natural, but where they are different enough to keep things interesting? Yes. Yes there is: We can use the computer to help us! Computers good at doing things quickly and don't mind doing tedious calculations over and over and over and over...
To generate our caves, we're going to use a collection of computational models called Cellular Automata to help us. The recipe we're going to use to build our caves is:
Each square in our grid is a cell. A cell can either be a wall or a space. We're going look at each cell in the grid and randomly decide, with a certain probability, if that cell will be a wall or a space. Here's a snippet of the code:
// create a grid of cells
var numberOfRows = 100;
var numberOfColumns = 100;
var gridOfCells = [];
// loop through and randomly assign a cell to be either a wall (1) or a space (0)
var wallProbability = 0.5;
for (var row = 0; row < numberOfRows; row++) {
gridOfCells[row] = [];
for (var col = 0; col < numberOfColumns; col++) {
// determine whether the cell will be a wall or a space
var state = Math.random() >= wallProbability ? 0 : 1;
// update this cell's state
gridOfCells[row][col] = state;
}
}
Now that we have the grid, let's see what this looks like. I chose to color the walls a dark gray (#333) and open spaces white (#fff). Try adjusting the probability using the slider. Note that probabilities are between 0 and 1, but you can also think of it as choosing between 0% and 100% of the cells to be walls. Click the Randomize Walls button to re-randomize the cells.
How are we going to use these cells to create caves?
We're going to let the cells make decisions by talking with their neighbors. You see, cells are quite social. Each one is part of a Moore neighborhood, which consists of a cell and the 8 cells surrounding it. To create our cave, each cell must choose whether to become a wall or a space by taking into consideration the states of itself and its neighbors. It does so using a rule. We're going to use a variation of the majority rule to guide our cells in making a cave. Here are the specifics of the rule (in code):
// Apply this function on each cell in the grid and put the nextState values into a different grid.
// It's important to not overwrite any cell values until all nextState values have been calculated.
function getNextState(row, col) {
var cellRow = row;
var cellCol = col;
var cellState = gridOfCells[cellRow][cellCol];
// 1. Get this cell's neighbor locations in the grid
var neighbors = [];
// loop through the set of 3x3 cells centered on this cell
for (var r = -1; r < 2; r++) {
for (var c = -1; c < 2; c++) {
var neighborRow = cellRow + r;
var neighborCol = cellCol + c;
if (neighborRow === cellRow && neighborCol === cellCol){
// this is the center cell - ignore
}
else {
// this is a neighbor - add to array
var n = { row: row, col: col };
neighbors.push(n);
}
}
}
// 2. Count how many neighbors are walls
var wallCount = 0;
for (var i = 0; i < neighbors.length; i++) {
var neighborLoc = neighbors[i];
// check to see if the neighbor location exists (i.e. is on the grid)
if (neighborLoc.row >= 0 && neighborLoc.row < numberOfRows &&
neighborLoc.col >= 0 && neighborLoc.col < numberOfColumns) {
var neighborState = gridOfCells[neighborLoc.row][neighborLoc.col];
if (neighborState === 1) wallCount++;
}
else {
// the location doesn't exist
// since we want the edges and corners to be (mostly) made of walls,
// assume this neighbor was a wall and add 1 to the wall count
wallCount++
}
}
// 3. Use the majority vote rule (variation) to decide this cell's next state
var nextState = null;
if (cellState === 0) {
// the cell is currently a space
if (wallCount >= 5) {
nextState = 1;
}
else {
nextState = 0;
}
}
else {
// the cell is currently a wall
if (wallCount >= 4) {
nextState = 1;
}
else {
nextState = 0;
}
}
return nextState;
}
Let's take a look at how this works in action. I've reduced the number of cells on the grid to make it easier to see the neighborhoods. Hover over any cell to see it's Moore neighborhood. You can see it in orange on the grid itself, as well as in the top left Cell Info box. Click on the Apply Rule button to watch the cells change based on the rule stated above. Continue clicking and you'll start to see some cave-like structures appear.
Of course, since the number of cells was reduced, it doesn't look very nice. Now that you have a good idea of what a Moore neighborhood looks like, we can increase the number of cells. Let's take a look at a 100 x 100 grid of cells.
Our caves already look nice even after a few iterations of our rules, but that doesn't mean there aren't problems. Depending on the probability you chose, you might get caves that are too open, or too closed. Or, even when you do get a nice balance of open and interesting, the cave has multiple isolated areas that cannot be accessed by the player. How can we deal with these issues?
There are many different ways and they depend on your goal. If you want to procedurally generate levels from the game, long after making it, then you'll want to use algorithmic ways of checking and fixing problem areas. For more details on this method, check out these pages:
I oftentimes like to think of this algorithmic generation as being a starting point for a person. People are good at designing things for other people. Computers are good at exploring very large design spaces and generating combinations that people may not have thought of. I think we make a good team. We can ask computers to find different designs and then we can evaluate and build off those designs to make something really special.
One of the simplest ways of doing this is through editing. While a computer is generating the cave using the rules of Cellular Automata, we can edit in-between, or after, or even before. We can make changes that connect areas, or even completely redesign an area. Of course, the point was to minimize effort while producing something interesting, so if you find yourself doing too much work, maybe just start over.
You can switch between drawing walls and drawing spaces by clicking the Draw button in the Controls menu. By clicking on a cell, you will change that cell to the color shown on the button. If you click and drag the mouse, you will change all cells that you drag over to the color shown on the button. Everything else works the same. Oh, and if you want to save your cave, press the Save Cave button and follow the instructions.
If you liked the topic, here are a few more sources for you to peruse. If you'd like to know more about how I made this, click the Behind the Scenes link at the top. And, if you want to clone the project, you can go to my GitHub page and check it out! Thanks for reading this!