Procedural Dungeon Generation: Cellular Automata
22 Nov 2016Last time we looked at generating random dungeons for video games using the Drunkard’s Walk algorithm. The Drunkard’s Walk is fun to play with, and often generates cool levels, but it’s also pretty unreliable. That’s not good enough for my purposes: I want to reliably generate big, open, cavelike maps, with lots of space for fastmoving enemies to swarm and surround the player.
To that end, we’ll be using a cellular automaton to generate levels that look like this:
We’re still using a 2D grid to represent our level, but we’ll be using some new vocabulary this time. Each spot on the grid is now a cell. Each cell is either alive or dead. (An alive cell is a cave wall, and a dead cell is empty space where the player can move around freely.)
The algorithm starts by generating a grid of these cells, each of which has a certain chance of being alive.
(def canvasid (atom "canvas1"))
(defn drawgrid
[grid]
(let [canvas (js/document.getElementById @canvasid)
ctx (.getContext canvas "2d")
width (count (first grid))
height (count grid)
canvaswidth (.width canvas)
canvasheight (.height canvas)
cellwidth (/ canvaswidth width)
cellheight (/ canvasheight height)]
(.clearRect ctx 0 0 canvaswidth canvasheight)
(set! (.fillStyle ctx) "#CCC")
(loop [x 0 y 0]
(when (< y height)
(when (= (> grid
(get y)
(get x))
:dead)
(doto ctx
(.beginPath)
(.rect (* x cellwidth) (* y cellheight) cellwidth cellheight)
(.fill)))
(recur (if (identical? (inc x) width) 0 (inc x))
(if (identical? (inc x) width) (inc y) y))))))
(defn highlightneighbors
[grid x y]
(let [canvas (js/document.getElementById @canvasid)
ctx (.getContext canvas "2d")
width (count (first grid))
height (count grid)
canvaswidth (.width canvas)
canvasheight (.height canvas)
cellwidth (/ canvaswidth width)
cellheight (/ canvasheight height)]
(set! (.fillStyle ctx) "#00ff00")
(doto ctx
(.save)
(aset "globalAlpha" 0.3)
(.beginPath)
(.rect (* cellwidth (dec x)) (* cellheight (dec y)) (* 3 cellwidth) cellheight)
(.fill)
(.beginPath)
(.rect (* cellwidth (dec x)) (* cellheight y) cellwidth cellheight)
(.fill)
(.beginPath)
(.rect (* cellwidth (inc x)) (* cellheight y) cellwidth cellheight)
(.fill)
(.beginPath)
(.rect (* cellwidth (dec x)) (* cellheight (inc y)) (* 3 cellwidth) cellheight)
(.fill)
(.restore))))
(defn drawgridhighlighted
[grid x y]
(drawgrid grid)
(highlightneighbors grid x y))
(defn generaterow
[width aliveprobability]
(vec
(take width
(repeatedly #(if (< (rand) aliveprobability)
:alive
:dead)))))
(defn generategrid
[width height aliveprobability]
(vec
(take height
(repeatedly #(generaterow width aliveprobability)))))
(drawgrid (generategrid 50 50 0.5))
As usual, all the code snippets in this article are interactive — try changing that 0.5
to a 0.1
or a 0.99
. You can always focus a snippet and press Ctrl+Enter to rerun it, too!^{1}
The basic idea with cellular automata is that we start with an initial grid like the one we’ve just generated, and then we pretend that its cells are bacteria in a petri dish. We simulate the passage of time, during which cells are born and die.^{2}
The algorithm looks like this:
 If we’ve run the simulation
numiterations
times, we’re done.  For each cell on the grid,
 Calculate the number of its neighbors that are alive.
 If the cell is dead and has at least
birththreshold
alive neighbors, it becomes alive.  If the cell is alive and has at least
survivalthreshold
alive neighbors, it stays alive.  Otherwise, the cell is dead.
 Go back to step 1.
Before we get carried away, let’s consider an edge case we’ll have to deal with: cells on the outskirts of the grid will have some neighbors that are out of bounds!
(defn spotisoffgrid?
[grid x y]
(let [height (count grid)
width (count (first grid))]
(or (< x 0)
(>= x width)
(< y 0)
(>= y height))))
(spotisoffgrid? (generategrid 5 5 0.5) 1 0)
For simplicity, we’ll say that these nonexistent neighbors are considered to be alive. (As a bonus, this rule tends to give our levels nice solid walls around the edges.)
Now let’s write a function that finds a given cell’s neighbors. In addition to the drawgrid
function from last time, I’ve supplied a drawgridhighlighted
function that lets you see what your cell’s neighbors look like.
(defn neighborvalues
[grid x y]
(for [i (range (dec x) (+ x 2))
j (range (dec y) (+ y 2))
; We only care about our *neighbors*.
:when (not= [i j] [x y])]
(if (spotisoffgrid? grid i j)
:alive
(getin grid [j i]))))
; Let's try it out.
(let [grid (generategrid 5 5 0.5)
[x y] [2 2]]
(drawgridhighlighted grid x y)
(neighborvalues grid x y))
Now that we’re able to count how many of our neighbors are alive, let’s figure out how to determine a cell’s new value at each step of the simulation.
(defn newvalueatposition
[grid x y birththreshold survivalthreshold]
(let [cellisalive? (= (getin grid [y x]) :alive)
aliveneighbors (count
(filter #(= % :alive)
(neighborvalues grid x y)))]
(cond
(and cellisalive?
(>= aliveneighbors survivalthreshold)) :alive
(and (not cellisalive?)
(>= aliveneighbors birththreshold)) :alive
:else :dead)))
; Let's try it out.
(let [grid (generategrid 5 5 0.5)
[x y] [2 2]]
(drawgridhighlighted grid x y)
(newvalueatposition grid x y 4 5))
That’s all the groundwork we need — let’s implement the algorithm!
(defn automataiteration
[grid birththreshold survivalthreshold]
(let [height (count grid)
width (count (first grid))]
(loop [newgrid grid
x 0
y 0]
(if (= y height)
; Done!
newgrid
; Otherwise:
(let [newvalue (newvalueatposition
grid
x
y
birththreshold
survivalthreshold)]
(recur (associn newgrid [y x] newvalue)
(if (= (inc x) width) 0 (inc x))
(if (= (inc x) width) (inc y) y)))))))
(defn automata
[width height initialprobability
birththreshold survivalthreshold iterations]
(nth
(iterate
#(automataiteration
%
birththreshold
survivalthreshold)
(generategrid width height initialprobability))
iterations))
(drawgrid
(automata 40 40 0.35 3 5 4))
It… works?
Well, it sure looks like that code is doing something to our grid, but it’s not easy to tell how we can use this to generate a cool cave like the one we saw at the beginning of this article. This problem is one of the most interesting things about procedural level generation — whenever you’re evaluating an algorithm, you’ve got to figure out what its inputs are, and try to develop some understanding of how you can manipulate those inputs to get the type of levels that you want.
I didn’t pop out of the womb with a welldeveloped intuition for how birth and survival thresholds affect the shape of caves generated by a cellular automaton, and so I had some trouble figuring out how to proceed when I got to this point. Like last time, building a little tool helped a lot. Try cranking up the number of iterations!
After playing around with the different options available, I’ve settled on using an initial chance of 0.45
, a survival threshold of 4
, and a birth threshold of 5
. This set of parameters seems to reliably generate the specific kind of open cave areas that I’m interested in. Let’s try our implementation again, using those values:
(drawgrid
(automata 40 40 0.45 5 4 4))
Looks good! Kinda small, though.
The snippet above runs our code on a little 40x40
grid because this implementation of the algorithm is really, really slow, and it takes forever if you run it on e.g. a 100x100
grid. This speed issue is also the reason that these snippets use 4
as their default number of iterations — in real life, I find that a value around 12
makes for smoother caves.
In a future article, we’ll revisit this code and figure out how to make it much faster, and we’ll learn a little bit about ClojureScript in the process.
Wrapping up
I learned about today’s algorithm from Kyzrati’s post on the topic. His implementation is a bit different from ours — he starts by running these birth/survival/death rules on random, individual cells a bunch of times, rather than applying them to all cells on the grid at the same time. He then performs several smoothing passes, in which he applies cellular automata rules to the entire grid at once like we’ve been doing, in order to remove straggling singlecell pillars and cavelets.
I have an implementation that tries to mimic his, and I think I like the results it gives, but I’ve been playing with it for a couple of weeks and frankly I still have no idea what actual effect this runonindividualcellsmanytimes approach has. It does something, and it doesn’t seem to make the levels worse, so I’m keeping it for now. Give it a shot yourself using my visualization tool.
Future work
There’s a lot left to do before these levels are super fun and playable:
 If we generate one of these caves, place the player at one end, and put his goal at the other end, he’ll have to do a ton of backtracking along the way in his search for the exit, and that isn’t very fun. Kyzrati’s solution is to tweak the boundaries of the input grid so that the algorithm generates longer, narrower caves that require less backtracking.
 The algorithm often generates small “island” caves that are completely disconnected from the main cave; I need to write a postprocessing step that detects them and fills them in.
This seems like a good stopping point for now, though. We’ve written some code that generates neato caves! We’ll make it better in future posts.
Further Reading
 Mapgen: Cellular Automata
 The Cellular Automaton Method for Cave Generation
 The Nature of Code: Cellular Automata
 Cellular Automata Method for Generating Random CaveLike Levels
 Generate Random Cave Levels Using Cellular Automata

Can we talk about how crazy this is? How many blogs have you ever seen with interactive code snippets like this? KLIPSE rules. It’s supereasy to use, and it can run python, ruby, javascript, plus other languages too. Give it a shot in your blog! ↩

This algorithm will seem very familiar to you if you’ve ever seen Conway’s Game of Life. ↩