Some dungeons are made of rooms with stone walls, while others are more naturally shaped rocky caverns. Naturally, procedurally generating these variegated geometries require different methods. We’ll be tackling organically shaped caverns in this article with a simple but ingenious method called the cellular automaton (Johnson et al., 2010).
Here is the core of the idea: imagine you have a square petri dish divided into tiny squares or cells. Each cell contains a bacterium and can be in either a “dead” or “alive” state. Initially, the cells are in either state at random, independently of each other.
We divide time into discrete steps and a simple rule determines the state of a cell at the next step:
If a cell is alive but it has has 5 or less neighbors who are alive, it dies.
If a cell is dead and it has 3 or more living neighbors, it becomes alive.
Otherwise, the cell remains in its current state.
What we mean by “neighbors” is at our discretion. We’ll define it as the eight immediately surrounding cells. Also, I’ve chosen 4 for the “survival threshold” and 5 for the “birth threshold”, but again this is a parameter we can set.
🤓 Let’s code it up!
We’ll encapsulate our cellular automaton in a Python class. It needs to store the construction parameters, the grid of cell states, as well as an additional buffer for calculating the next time step:
When an object of this class is instantiated, we need to allocate the cell arrays and initialize them. The initial state has independent random values with the flip of a coin:
To count the number of neighboring cells that are alive, we take a slice of the array, and use a simple trick to treat out-of-bounds neighbors as alive:
The following method simulates a single time step of the automaton using the rule we previously described. Notice how the values of the next time step only depend on the previous time step, or rather, we update all of the cell values asynchronously:
Finally, we just need some methods to visualize our “dungeon”:
🧐 Results
Here is some output over 12 time steps:
and the final frame:
The black regions represent rock walls and the white, open space. You should try playing around with the parameters to understand their effect on the cavern geometry.
By changing the random seed you can generate a practically infinite number of dungeons. And by fixing the seed, you can, in effect, store a dungeon in 64-bits!
→ What’s next?
Our cavernous dungeon could use some heuristic improvements over the plain automaton output. There are several disconnected “rooms”, including some that are too small to be practical. A simple post-processing step numbers the “islands,” removing those smaller than a given threshold and joining the larger ones to form a single large cavern.
But, we’ll have to leave that for another day! Hope to see you in the next article 🤠
Resources
My Python implementation (to follow shortly…)
Johnson et al., 2010. Cellular automata for real-time generation of infinite cave levels. PCGames, 2010.