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!

Console-like display in the browser?

I’ve been working for some time on a Roguelike in Javascript. One of the first things I had to do for my Roguelike, of course, was establish some sort of display routine. I could have gone with HTML5’s new <canvas> tag or something similar, but setting up a console-like environment for canvas can get a little involved. So instead, I established a way to use the browser’s native text rendering. Say hello to a simple Javascript class for console-like rendering in the browser: I call it display.js.

So, let’s take a look at the code required initialize a basic 80 by 25 console and draw a few characters with the display class:

// create a display for console-like rendering
display = new Display(new Vector2(80, 25), new Vector2(10, 35), true);

// let's draw the classic @ sign:
display.ch("@", new Vector2(10, 10));

// maybe fake a few walls
for(var x = 0; x<10; x++) {
display.ch("#", new Vector2(x, 0));
}

// let's put a green slime down, too
display.ch("j", new Vector2(15, 15), "green");

Okay, let’s step through this code really quickly. Before we begin, though, I’d like to note the Vector2 class I use here; it’s nothing more than a utility function I use to hold a position with X and Y values (you can grab a copy of it here). So, in the code, the first line initializes the console display. The first variable we pass in to this function call is the size of the display–I use 80 by 25 because that’s a standard console size, but these numbers could be anything you want. The second variable we pass in is the offset of the console from the rest of the page. The third variable we pass in is whether we want this display to open in a new window or not. If you set it to false, the display will simply be written to your HTML page. If it’s set to true, the console will open in a popup window.

The next line calls a function on our newly created console, namely ch. This allows you to display a character on the screen and takes a minimum of two and up to five parameters. In order, these are: the character to display, the position of that character, the color of the character, the opacity of the character, and the background color of the character. Only the character you want to write and the position of that character are required; the others are optional. The color variable accepts a few basic color names as well as hex values. The next few lines do nothing more than demonstrate the various applications of the ch function, which is the only function display.js makes use of.

In finis…

As you can see, the display class isn’t very advanced right now, but it’s been all I’ve needed so far. If you want to download the class, you can grab it here. Quick note, it does make use of jQuery, so make sure you include that in your project before you attempt to use it. As progress on my game continues, this library will likely be updated with more functions as I need them. Thanks for taking a look, and be sure to keep an eye on Hey Javascript for more updates in the near future! (hopefully, I’ll be posting some dungeon generation algorithms in Javascript soon)