A dungeon for role-playing games can be conjured out of the æther with just a source of randomness and a few clever algorithms. But how? And why would we want a computer to design our dungeons - doesn’t that take out the fun?
First, let’s address the why. As a game designer, it is immensely advantageous to have game experiences that vary each time you play. It becomes difficult, after all, to empathize with your imagined player if you’ve experienced each level ad infinitum. But replayability is not just a boon for the designer, it’s also one for the player. A game stays fresh much longer when the content varies each time - think of the dungeons of Diablo, or the world maps of Civilization.
So, what are our options for procedurally building a dungeon? Here are three families of methods commonly used: “digging” agents, cellular automata, and binary space partitioning:
“Digging” agents construct a dungeon one room at a time, connecting each nearby to one of the previously constructed rooms. I like to think of this method as being like a digger that successively carves out open space underground.
Cellular automata are systems that can “evolve” a dungeon’s geometry where an element’s value at the next time is a simple function of the value of its neighbors. Cellular automata can produce interesting and varied organic-looking geometry.
Binary space partitioning is an algorithm that recursively splits the map area along an axis just like a Mondrian painting. We can then place rooms in each partition of the space.
As with other types of procedurally generated content, our output has constraints. A dungeon must presumably be fully connected, have a diversity of rooms and environments, and direct the player towards a goal. Some of these constraints relate to the geometry of the dungeon, and others relate more to the items and creatures we place in them and how the user can interact with the environment.
What’s next?
We’ve touched upon a handful of “traditional” algorithms for constructing dungeons, yet we’ve barely scratched the surface. In future articles, I intend to implement these dungeon construction methods and more in Python and C# and integrate them into a dungeon system I’ve been building in an online course: “Unity Procedural Generation: Build Infinite Game Levels”.
We discussed how to generate a dungeon, but not what makes a dungeon fun or challenging. And is this even something we can quantify? I think this topic will intersect with interesting graph theory and graph algorithms. If we can quantify a dungeon “goodness”, then we can apply a wealth of search methods to find a good one.
Finally, I think it’s interesting to revisit these older methods in the age of Generative AI. Can we teach our utility-function-for-dungeon-funness to a foundation model? And can we use foundation models to control dungeon generation via natural language descriptions and images?
Stay tuned, and hope to see you in the next article!