Dungeons Without End
Random Dungeon Generators and My Experiments with Them
I’ve built a lot of little games over the years. It started with a version of Monopoly for my high school senior project that I called Joenopoly. It was built in Visual Basic 6, I believe, and I had a form with code-behind that I used for all of the gaming elements. This was my first large project, my first real “game”, although it was written, for the most part, in a very non-elegant way. It lacked loops and didn’t look like anything I’d ever write today. But it worked. And it impressed. The impression upon others’ faces impressed me further, and this encouraged me to continue building games.
Over the years, one kind of element in a game fascinated me more than any other: the random dungeon. Older generations referred to games about random dungeons as roguelikes, and nowadays, the roguelite genre thrives. I never played roguelikes, and I suspect I probably wouldn’t enjoy them very much. It was never really about the gameplay part of the random dungeon for me. It was the way they were built. My Joenopoly worked because it considered every case, every possibility, every kind of scenario that might happen, and the code handled it. In my mind, building working software meant thinking out every use case and planning ahead. But enter the random dungeon. How do we implement that? I was fascinated.
So I sought out the answer. The world opened before my eyes as I researched: there was an entire universe called Procedural Content Generation. PCG, for short. I thought to myself, the world doesn’t need any more games: it just needs the perfect PCG game. That was naive, admittedly. I think few still strive for that kind of game, and it’s fascinating on its own. But the piece that caught most of my attention was how PCG can be used to implement random dungeons. And there are some very good answers.
Play First, Read After
But before we get into those, and the heart of this article, I want you to play first, and read after. Click on the dungeon below, and then move Pot with the arrow keys or WASD. Pot can only see so far down the corridors and hallways of the dungeon, so you’ll have to explore. Bring Pot to the Flame, an allegory for our Philosopher’s Pot work, and the dungeon will be fully illuminated in celebration, and a new dungeon generated. Experiment with the tuning parameters to see how they impact the dungeon generation. And try different algorithms altogether.
Tune the generator
My blend. Cut the map up like a BSP tree, and fill each piece with a room, a cave, or a little maze. Rough up the rooms with a noisy automaton, then join every cut back together.
Turning a knob builds a new dungeon and opens the map. Press M to go back to the fog.
If you get lost, M shows the whole map, and N rolls a fresh dungeon. Pick a bigger size and the view pans along with Pot. Or press B, sit back, and let the believable AI find the Flame for you.
How I Got Here
I really first got into dungeon generators around 2010. I had just completed my Master’s degree in Computer Science, and it was time to start thinking more seriously about my doctoral degree. Believable AI was at the front of my initiatives, seeking ways to build games with AI computer components that were believable, in the “could that be a human?” sense, and in a Turing-test way. I wanted to build the kind of Turing test game where we could eventually have computer players that fooled humans into thinking they were playing other humans.
In 2011, I wrote what I called AiMazed, a dungeon generator in Lua with little cars that navigated randomly generated dungeons in search of stairways to the next level. There were crystals you could pick up to earn points, and a timer. You were pitted against a computer component, armed with a basic solver and a pacer to make you think it was another human player. Neither of you could see the whole map. The computer player kept a list of what I called “darkways” - the spots where a hall ran off into the dark - and whenever it ran out of new hall to follow, it headed for the nearest one to see what was there.
My first real question to myself was: maybe the thing that clues a user into believable behavior is how the computer player chooses to turn at different junctions and intersections within the dungeon. So I surveyed 200 random internet people for their answers to a questionnaire asking just that. The statistics I got back were not 50-50 as expected, but clearly biased in a certain way. I applied those weights to AiMazed, and I had my project. Those same weights steer the Believable AI button in the demo above: the Pot explores on its own, turning at every fork by the odds those 200 people gave me, and pausing now and then, the way people do.
Mind you, that project didn’t really go anywhere. It was a cool little thought experiment with some real data. But it had no conclusions to really draw from. Nothing too awe-inspiring or quite deserving of the PhD program. And 200 answers to the survey wasn’t by any means a “lot of” data. My path took me elsewhere, but my heart will always have a special place for random dungeon generation. And I want to write on some of those landmark algorithms that enamored me along the way.
Mazes vs Dungeons
Two concepts emerged in dungeon generators: a maze and a dungeon. The difference is pretty soft, or semantic. A maze is more like one of those line-art puzzles you find in a book at the store. Something to do while on the airplane. Those mazes have a critical engineering problem, though: the walls don’t really exist. They are only lines that separate one cell from another. Dungeons, on the other hand, are different in that the walls definitely exist as places you cannot go, because each one is a wall tile. Classic games, like Zelda, feature dungeons because the walls are real places in the game. I can’t tell you a game with mazes in them, and this distinction is probably a pretty good reason why, although you probably can find some. After all, the concept isn’t that difficult to implement, mind you.
I choose to live in the world where walls are real. Dungeons. But that said, mazes can still exist as dungeons. The trick is to give every line a tile of its own. Each cell of the maze becomes a floor tile, and each line between two cells becomes a tile, too: rock if the line is still there, floor if it was knocked down. That’s how every maze in the demo above becomes a dungeon.
Another key characteristic of mazes is that there are no rooms, only corridors. Rooms are sections of walkable dungeon that are more than one cell wide and tall. So we have our first real tunable parameter: the number of rooms, and the largest allowable size of those rooms. A maze has no rooms, and a dungeon might have some rooms.
Loops and dead ends are another important aspect of dungeons. These add more depth to the character of a dungeon. A dungeon that has too many loops might not be that much of a maze at all, if every path eventually takes you where you need to go anyway. And a dungeon with too many dead ends might be too frustrating.
The Algorithms
I investigated four approaches to random dungeon generation. I started with mazes: the basic recursive backtracker, where all points are connected by one and only one path. This is your typical puzzle-book maze. Super basic, but not that entertaining. Certainly not that replayable. Then I looked at Jamis Buck, who had built his own algorithm. His was an approach that had tendencies, but those tendencies made the generated dungeon feel like it had more character. Then: something interesting - cellular automata. Something that happens in real life, transcribed into a tool to build dungeons. And lastly, the binary space partitioning algorithm, known as the BSP tree, my favorite of the bundle, in terms of both the algorithm itself and the dungeons it generated.
In the spring of 2012, I put all four side by side in a little Java testbed, with a dropdown to pick between them. The algorithm picker in the demo above is that dropdown, reborn.
The Recursive Backtracker
The original one that everyone is familiar with, if you think about it. The name is fancier than the output. The foundation is that all cells in the maze are connected by only one path. It works fairly simply, and as an algorithm, it’s a great one to study if you’re interested in algorithms in general. Pick a random cell in the grid. Then pick a neighbor you haven’t visited. These two are now connected. You basically keep going like that until everything is visited. So you need to track a list of who is visited, and the path that got you here, and if this sounds a lot like a depth-first traversal, you’re on the right track. It has O(n) complexity, where n is the number of cells in the grid: every cell gets visited once, and each one only ever checks its four neighbors.
The funner way of imagining this is exploring a cave with a ball of string. You dive in as deep as you can, and when you hit a dead end, you backtrack until you find additional options. By the time you’re done, you’ve created some art with the string: the branches of a tree.
There are some tunable aspects of the recursively backtracked dungeon. You can control how many “straight runs” there are, and how many dead ends there are that “loop”. The pure maze has both set to zero, but you can add loops and a little character by increasing either one.
Jamis Buck’s Dungeon
Jamis Buck wrote about mazes, and in fact, it’s how I started learning anything at all about dungeon generation. His blog describes exactly how the algorithm works, and it’s the recipe I used for AiMazed in 2011. It’s basically another kind of maze generator, a cousin of what’s called the growing tree algorithm, but with some extra steps.
Think about it this way: you’re digging your way out. Pick a random cell and dig. Keep going straight, and roll the dice every step. Say at 5% odds, you’ll turn a random way. Keep this low for longer hallways and high for a twisty mess. When your digger hits a wall or a place it’s already been, pick a new random cell it’s already dug and repeat. Once every cell has been dug, it’s a perfect maze again.
Algorithmically, it’s a bit slower than the recursive backtracker: about O(n log n). Near the end, the digger wastes a lot of jumps hunting for the last few undug cells, sort of like filling the last few spots in a sticker album. Then Buck describes the sparsify operation, in which every dead end gets filled back in, over and over. Do that once and the tips of the branches fall off. Do it a dozen times and whole wings go solid, leaving a few winding halls with rock between them. Each pass is one more sweep over the grid.
But like with the recursive backtracker, dead ends are hardly any fun. So we can add loops, just like with the backtracker, to add that kind of character: some of the dead ends that are left keep digging instead, turning now and then, until they break into another hall. And straight paths are also less fun. A dungeon is one with rooms, not just halls. So the algorithm also adds rooms as the last step. Each room gets a random size and goes wherever it would touch the fewest hallways, sort of like finding the quiet corner of a crowded restaurant. Then it’s hollowed out, and one of its walls digs outward until it meets a hall, so no room is sealed off.
Every round, AiMazed rolled those knobs, too: how many times to sparsify, how often a dead end became a loop, and how many rooms to place and how big, with smaller rooms when the halls were thick. Pick Jamis Buck’s dungeon in the demo and they’re all there. Set the dead-end trims, the loops, and the rooms to zero and you’ll see the raw perfect maze. Push the corridor turns all the way up and the long halls collapse into a twisty mess. “Roll the knobs” does what the 2011 game did between rounds.
And then there was the safety net. Once the dungeon was built, the game dropped in the player, the key, and the stairs at random, and checked for a path to each. If there wasn’t one, it threw the whole dungeon away and built another. Computers are fast. Rolling again was cheaper than being clever, and the demo above still works the same way.
Cellular Automata
Cellular automata are used for more open, marshy, open-world landscapes. Mazes look built. Sometimes you want a dungeon that looks like nature dug it, a cave, and for that the trick is a cellular automaton. It’s the same family of rules as Conway’s Game of Life. Erosion is the term I think of. The iterative application of rules in cellular automata feels just like erosion.
Flip a coin for every tile: rock or floor, with a bit under half of them rock. It looks like TV static. Then make a pass where every tile looks at itself and its eight neighbors. If five or more of those nine are rock, it becomes rock; otherwise, it becomes floor. “Five of nine” is a fractional requirement: when five or more of the block of nine meet the criteria, the rule applies. Run that four or five times, and the static wears down into smooth, lumpy caverns.
The catch is that coin flips don’t care about the Pot. You’ll often get one big cave and a handful of little pockets cut off from it. So after the passes, a flood fill finds each separate cave, keeps the biggest, and fills in the rest, or digs a tunnel to join them. Pick cellular automata in the demo, set the smoothing passes to zero to see the static before it settles, and switch on the tunnels to join the lost pockets instead of filling them in.
My 2012 version looked much farther afield. Every tile counted its neighbors three tiles out in every direction, 48 of them, which grows big, blobby open spaces rather than twisty caves.
BSP Tree
This one feels the most like a dungeon to me. I love the approach the algorithm takes. Split a room in half, and recurse into each half. It’s used for a dungeon full of only rooms, and you’re left with a hallway to multiple rooms. Not a maze, per se, but interesting as a random hotel of sorts.
BSP stands for binary space partitioning. Take the whole map and cut it in two, across or down, at a random spot. Then cut each half in two, and each of those, until the pieces are about room-sized. Those cuts form a tree, with the whole map at the top and the little pieces at the leaves. Put a room somewhere inside each leaf. Then walk back up the tree, and at every branch, run a corridor between the two halves it split apart.
What I like about BSP is that the promise every dungeon has to keep, that the Pot can always reach the Flame, comes for free. Every split gets joined back together on the way up, so every room connects to every other room by construction. No flood fill, no rolling again. With no extra corridors, the BSP dungeon is a tree, just like the perfect maze: one way between any two rooms. Add a few, and loops appear.
My 2012 version did one more thing before joining the rooms: it ran a single pass of a cellular automaton over them, to rough up their edges, so they looked dug instead of built. That was the start of blending.
Putting It All Together
This isn’t really “Joe’s Algorithm,” the way the playable demo up top labels it. It’s just an amalgamation of all the algorithms here so far. I suppose it is Joe’s Algorithm, but I hardly recognize it as anything so significant to be worthy of that title.
It cuts up the map like a BSP tree. Each piece becomes a room, a cave, or a little backtracker maze, by the mix you set. The rooms get roughed up by a noisy rule borrowed from the Krall Dungeon, a fifth choice in that 2012 dropdown that grew little square rooms into lumpy ones. Then it walks back up the tree and joins every cut, BSP style, so the promise holds.
What I love about it is the character. You can have parts of the dungeon that have significantly different character than other parts: a cave world in this segment, and a long, winding tunnel maze in another. That variety is the spice of life, ultimately, and the kind of flavor that makes a dungeon “interesting”. It’s the same thought as the Philosopher’s Pot offering a way to preserve your sense of self while using AI, so that you don’t lose your precious self. That’s the part that makes the world interesting.
Keeping the Promise
Each of these generators has its own personality. The backtracker has its long, winding halls. Jamis Buck’s dungeon has its straight runs and its dead ends to trim. The cave has its lumps and its lost pockets. The BSP dungeon has its tidy rooms, one per leaf. But underneath, they all answer to the same little game: somewhere in the dark there’s a Flame, and the Pot has to be able to get there.
Sometimes that promise comes for free, as with BSP. Sometimes you check for it afterward, with a flood fill. And sometimes you just roll the dice again until it holds. That one is the least clever of the three, and it’s the one I trusted in 2011. I rather like it still. In software, it’s a pretty good rule well beyond dungeons: guarantee it by construction when you can, check it when you can’t, and don’t be too proud to throw the work away and start over.
What’s Next
In closing, I studied these algorithms to gain insight about gaming, algorithms, and dungeon generation where it intersects with PCG. I wanted to be able to contribute something significant in the world of human-believable AI. But I also wanted to stay close to my heart with gaming, too. I plan to expand the game of the maze, as playable above, into something larger, something more competitive, with a competitive mode and an adventure mode. I started doing something like this called Qubey’s Deep Dungeon once, but my time and energy were ultimately scooped up in other things. Now I think what comes next is a return to that kind of game, and we’ll see where we end up.
Anyway, that’s it for now. Now, go help Pot find Flame a few more times.