So, I play a lot of Dungeon Crawl, and one thing I’m consistently impressed with is the quality of the randomly generated levels: far more advanced than the standard “lots of rectangles connected by elbow corridors” made popular by Rogue and CS201 classes everywhere, they tend to incorporate a wide variety of techniques and approaches to preserve a sense of novelty. 1
The basic algorithm
As you might have guessed from the title of this post, the core of the algorithm comes from an application of cellular automata (also known as The Game of Life). Specifically, the algorithm is the following (imagine, like below, that you have a sixty by forty grid of cells/tiles):
1. set the borders to become walls 2. randomly set a percentage (let's say 40%) of the tiles to be walls 3. for a certain number of evolutions (let's say 5): a. iterate over each cell. b. if a 3x3 grid centered over the cell contains at least five walls, it stays a wall. c. otherwise, it becomes/stays empty. 4. admire your badass cave
The logic here is relatively simple, and you can see the results below (be sure to evolve and reset it yourself!): 3
Now this is actually a pretty neat result considering it’s such a simple algorithm, but there are a few things missing. In particular, I have two complaints:
- Inconsistency: every once and a while we end up with relatively spacious caves, which aren’t objectively terrible or anything but not particularly ideal.
- Some poor little caves get cutoff from the rest of the system.
Getting vaguely fancy
Let’s address the first issue with the most naive possible solution, shall we? If we’re worried about open spaces, it’d behoove us to try and systemically remove open space. So let’s modify the algorithm a little:
1. set the borders to become walls 2. randomly set a percentage (let's say 40%) of the tiles to be walls 3. for a certain number of evolutions (let's say 5): a. iterate over each cell. b. if a 3x3 grid centered over the cell contains at least five walls, it stays a wall. c. if a 3x3 grid center overed the cell contains no walls, it becomes a wall. d. otherwise, it becomes/stays empty. 4. admire your badass cave
And the result, again, is below:
So this tiny tweak gives us a much different result, right? We end up with thinner passages for sure – as any open space with a width of three or more gets swallowed by the next evolution – and the result is something that looks like the handiwork of, say, crazed goblins as opposed to a dragon with too much time on its hands. Unfortunately, the islanded caves is still an issue (if anything, it’s more prominent) and we get a lot of one-tile columns that spot up the place, which looks a little strange.
Let’s opt for a compromise: first we make sure we’ve got something chock-full with corridors, then carve it up and clean it a little. In algorithmic form:
1. set the borders to become walls 2. randomly set a percentage (let's say 40%) of the tiles to be walls 3. for a certain number of evolutions (let's say 3): a. iterate over each cell. b. if a 3x3 grid centered over the cell contains at least five walls, it stays a wall. c. if a 3x3 grid centered over the cell contains exactly two walls, it becomes a wall. d. otherwise, it becomes/stays empty. 4. for a certain number of evolutions (let's say 3): a. iterate over each cell. b. if a 3x3 grid centered over the cell contains at least five walls, it stays a wall. c. otherwise, it becomes/stays empty. 5. admire your badass cave
And the results are below:
Flooding our caves
Well, not perfect. We still have that whole island problem. There are a few obvious solutions to be made here:
- Ignore the damn thing, since caverns collapse all the time
- Fill in the disconnects
- Connect the disconnected caverns
I’m going to opt for the third one for its uncanny ability to provide a local maxima of cavern/evolution, which is a very important metric that I just made up. Our logic here hinges on a couple assumptions:
- if two caverns are connected, then you can move between any space between them freely
- if a given point can be reached by every cavern, then all caverns are connected
So we’re going to use the following basic algorithm:
1. for each distinct cave in the grid: a. set (x,y) to a random point in the cave b. while (x,y) is not equal to the exact center of the grid and (x,y) is not in a separate cave from the original point: i. increment/decrement either x or y such that (x, y) is now closer to the center ii. if (x, y) is a wall, remove it 2. admire your badass cave
Here’s the problem: how do we figure out where our caves are? From a visual standpoint it’s obvious, but since we’re theoretically storing this as a mere two-dimensional array of booleans, we have no way of creating the caves themselves.
1. for each cell in the grid: a. if the cell is a wall, skip b. if the cell has already been assigned to a cavern, skip c. add all the cell's direct neighbors to a queue d. while that queue is not empty, dequeue the first cell and goto 1a. 2. alas, your cave has not changed in badassery
It’s worth noting two things about this approach:
- In this theoretical example, you can travel diagonally, so ‘direct neighbors’ means all eight cardinal directions
- This is crazy inefficient but our use case is a relatively small grid so eh who cares
So we implement the two algorithms above and get the following (hit ‘connect’ to run the floodfill and the random walk):
And that’s it! It’s a handful of pretty basic algorithms that you can combine to do really cool things. There are definitely some weaknesses that can be addressed with special cases (I think the connecting corridors could look way better, and if there isn’t a cavern in the center it might look a little wonky), but it was a lot of fun for me to tinker around with this.
(Thanks to Jake and Sonny for reading a draft of this, and this article for inspiration.)
- Obviously worth noting is that I’m sure this technique has been around for long before Crawl. [return]
- It’s used in Orc and Jelly, if that means anything to you. [return]
- If you’re confused, try fixating on one cell and watching how it changes as you click the ‘evolve’ button. [return]
- You ever notice how the excitement of an algorithm is often in inverse proportion to the excitement of it’s name? Flood fill: sounds awesome, pretty boring logic. Timsort: sounds like an off-brand sleep aid, ends up being awesome. [return]