Generating caverns with cellular automata

In this article, I’ll be discussing how to generate neat-looking fully connected caves using cellular automata. This algorithm builds off of another algorithm which can be found here. As noted, the linked algorithm is incomplete and cannot be used for generating dungeons that are suitable for a real roguelike. This article is about the method I used to make that algorithm workable.

First off, the basic algorithm:

To begin, let’s take a look at basic algorithm behind generating nice-looking cave levels with cellular automata:

1. Scatter wall blocks across the level at a 30-40% saturation level (I've found that 39% is ideal).

2. Iterate through all the tiles on the map four times: 
  - For each tile in each iteration, set the tile to be floor.
  - Then, calculate the number of wall tiles within both one square of the original tile (these are neighbors) and two squares (these tiles are nearby). Store these numbers.
  - If the number of neighbors for the tile is greater than or equal to 5, or there are less than two wall tiles nearby, set this tile to be a wall.
  - If it is not a wall already, leave this tile as a floor tile. 3. Iterate through all the tiles on the map three more times:
  - For each tile in each iteration, set the tile to be floor.
  - Calculate the number of wall tiles within both one square of the original tile.
  - If this tile has five or more neighboring walls, make it a wall. Otherwise, leave it as a floor tile.

The issue with cellular automata is…

…the caves generated with the cellular automata technique are often unconnected. Since many roguelikes depend on all parts of a level being accessible, this is usually a bad thing. So, clearly, we need a way to drop the disconnected regions or otherwise ignore them. The best way to do this is with a flood fill algorithm. A flood fill algorithm is able to find all the nodes connected to each other that aren’t delimited by another type of node. In graphics applications, this is usually used to find regions of similar color.

In our algorithm, the flood fill algorithm will be used to find all the regions of the cave that are comprised of purely floor tiles–in other words, all the caverns (unconnected or not) on the map. Once we have a list of the caverns, we can select the largest cavern–this will be the main cavern. We can then simply drop the other patches, as they are small unconnected regions that are precisely what we don’t want.

Flood fill algorithm in Javascript:

Here’s how I managed the flood fill algorithm and subsequent cavern managing in Javascript:

// this variable will be used to store the various unconnected caverns 
var caverns = [];

// begin looping through the map
for (var x = 1; x < this.size.x; x++) {
for (var y = 1; y < this.size.y; y++) {
var cavern = [];
var totalCavern = [];

if (this.data[x][y].type != "dirty floor") { // we've already been over this tile or it is already part of a cavern,
// no need to check it
continue;
}

cavern.push(this.data[x][y]);
totalCavern.push(this.data[x][y]);

while (cavern.length > 0) {
var n = cavern.pop();

if (n.type == "dirty floor") { // set a flag on the tile indicating it has already been checked
n.setType("floor");

for (var i = 0; i < 8; i++) {
var curTile = this.data[n.position.x + x_array[i]][n.position.y + y_array[i]];
if (curTile.type == "dirty floor") {
cavern.push(curTile);
totalCavern.push(curTile);
}
}
}
}

// add this cavern
caverns.push(totalCavern);

// sort the caverns
caverns.sort(function (a, b) {
return (b.length - a.length);
});
}
}

// remove the largest cavern, as it is the main cavern
caverns.shift();

// now that we've got the unconnected caverns, change their tile type
if (caverns.length > 0) {
for (var i = 0; i < caverns.length; i++) {
for (var j = 0; j < caverns[i].length; j++) {
caverns[i][j].setType("wall");
}
}
}

As you can see, I loop through all the tiles. First, I check to see if I’ve already been over the tile; if so, I pass it on. If I haven’t, I go through that tile and search its neighbors, too. Eventually, I’ve searched all the tiles on the map and sorted them into the various caverns to which they belong. Once I’ve done that, I sort the caverns by size, from largest to smallest, and pick out the one with the most tiles in it (in other words, the biggest cavern). This is the main cavern, so we can get rid of or ignore the rest. I personally chose to get rid of my unconnected caverns, but it’s possible to connect them or just ignore them for the rest of the dungeon generation code–it’s up to you really.

In finis…

If you’ve read this far, you’re at least slightly intrigued by the cellular automata/flood fill cave generation algorithm–good! Hopefully you’ll have as much fun playing around with it as I did. As you can see, the Javascript code I included above makes heavy use of some external data-managing structures, such as a map data structure and a tile structure as well; I’ll be writing more articles about how I handle the map and tile stuff later. As always, thanks for the read, and if I made any mistakes during this article or if any of my code can be improved, please let me know!

2 thoughts on “Generating caverns with cellular automata”

  1. Hey, you might not remember me, but I’m RylandAlmanza from #rgrd a long time ago. I was the one that was also making my roguelike in Javascript (and then HaXe, and now back to Javascript.) Could you send me an email? I have a few questions if that’s ok. :)

Leave a Reply

Your email address will not be published. Required fields are marked *