When I first hacked together the early version of Dungeons of Freeport, I put together a very quick and dirty method for generating the dungeons. It’s the most common beginner’s one. But the last few weeks, I’ve been deciding which techniques to use for this game’s dungeons.

Before I start going into a bit more information about it, a few caveats:

This is my first Roguelike (or, Roguelike, depending on your perspective), but I’ve been doing proc gen in my games since the very start, really. My first game, TownCraft, used proc gen for every level. Super Death Fortress and its sequel did the same thing. But both used very simple proc gen techniques – just enough to do what I wanted them to, certainly noting that’d turn the head of anyone used to serious Roguelike work.

Secondly? If it’s not obvious already, what techniques (and there are many) to use to generate a dungeon is very subjective. Please don’t take my conclusions in this blog post as some kind of assertion that this is the One True Way. These techniques are what I chose for this specific game based on my needs and, frankly… what I enjoy coding.

I am, however going to talk a bit about different techniques I tried and rejected – and why.

Finally? Most everything I learned to do this came from numerous fantastic articles and talks which can be found online. I will link to all the relevant ones that helped me at the bottom of the article.

Real Basics

While this isn’t intended to be a tutorial of any sorts, as I can’t presume anyone reading this knows what dungeon generation even is (or that they have played a rogue-like before), here is a brief summary of what a procedural dungeon generation system is for, and how it tends to work:

In a classical Roguelike, some number of rooms (or other enclosed spaces) are generated. For the ‘level’ to be complete, they have to be connected with passageways.

In most Roguelikes there needs to be multiple levels you descend into, stairs up and/or down to lower levels need to be placed in rational places, and the dungeon level itself will want to be populated with treasure, monsters, traps, or other things.

The real trick comes in trying to make a space that seems believable – or at least interesting to explore. To accomplish this, a lot of techniques can be used.

The most simple form the kind that pops up in most every ‘make your own Roguelike’ tutorial, is this:

1. Generate a randomly sized room, and place it in a valid place on your map
2. Repeat this process until you have enough rooms (or your dungeon is full)
3. Connect the rooms by taking the centre point of two rooms, and ‘drawing’ a line between the two, either horizontal then vertical, or vertical then horizontal. Any square along this drawn space, if it turns out to be stone, should be carved out
4. Repeat this process until each room is accessible from the start position

Even with a simple system like this, there’s a lot of implementation questions you can ask. For instance…

• How do you determine which places are valid to place a room? The easiest way, if not a very efficient one, is to generate a random room size and position, then just check if it sits in a valid space or not, placing it if so, trying again if not.
• What do you do when passageways take you through another room? This can produce overlapping passages and rooms. That may not be a bad thing, of course. Is THAT an aesthetic you want?
• When determining if all rooms are connected, how do you plan to do that? A path finding room or dijkstra algorithm could help, or you could simply store metadata about which rooms are connected where to determine when you’re ‘done’.

Then, of course, you get questions about the rooms themselves. Generating a random rectangle is easy. But what if you want something more complex? Rooms that are circular, or have a body of water in them? Rooms that have specific shapes and use cases, like finding a kitchen in a goblin lair? Or what about natural cave formations instead of ‘dungeons’ of the sort supposedly created by sentient creatures?

There are many answers to all these questions. Here’s a few techniques I looked into, and what they’re most often used for…

Algorithms

The following algorithms are things I have tried to use (or plan to use) while making DFP, and some general thoughts on why I did or didn’t use them.

BSP Trees

This was the first thing I tried. The basic concept is that you divide your dungeon space into two halves, then keep doing this recursively (randomly deciding whether to divide each space horizontally or vertically), stopping when a space gets to a pre-defined size. Say, the size of an average-sized room.

Having done this, you can then generate a room that will fit within a bottom level node on the tree, and be sure that it won’t overlap with any others.

In practice, this means for larger dungeons you aren’t repeatedly checking spaces only to find a dungeon room won’t fit there. In terms of processing power (and therefore time) required to generate a dungeon, this is good.

I implemented this early on but found that for the size of dungeons I was doing in my game… it didn’t seem to be a huge advantage. There’s a few cases (like if I plan to go with very large dungeons for lower levels in future) where I might use this system, but for now it’s not a part of the DFP dungeon generator code.

Cellular Automata

This system uses an algorithm akin to Conway’s Game of Life, which is helpful when generating naturalistic cave systems. It’s really very neat.

I’ve not implemented this yet, but I plan to – not for full levels, but for natural caves that will exist at the lower levels, connected to mines and the like.

Room Walk / Procedurally Build

This is a system whereby you generate a room (much like the random room placement noted above). However, the difference is where you place it. Rather than simply picking a random spot and seeing if it fits, you ‘walk’ the new room some number of paces in a direction from the last room you placed.

You repeat this process numerous times, and when it fails you go back to a previous room to keep trying – or even pick a random one that’s already placed.

The advantage of this system is that you end up with room positions that are a as close (or far) from each other as you want them to be.

Another advantage is that if you know roughly what other rooms this new one will be close to, you can more easily have your proc gen factor this in when making decisions about just what room to make or how big to make it.

I’ll talk a bit more about how I’ve used this in the next section.

A-star Pathing

A* pathing is one of the most robust and well-used systems to calculate routes between points on a map.

In short, it takes your origin point, gets all adjacent points (and a ‘cost’ to move across them), and begins adding these into a pool recursively, always checking the nodes which have the lowest total cost and seem to be making ‘forward progress’ best on an estimation of the distance, until they either fail, or hit the destination.

This system has numerous advantages, such as that its ‘nodes’ can be anything, so it doesn’t have to work on a 2d grid, and that it will try to minimise how many checks it does to generate a path to the destination.

Dijkstra Maps

Dijkstra maps are another really useful tool. They essentially take an origin point, then based off the ‘cost’ of each node in the map, it will leave you with effectively a heat map showing how many turns (or what cost) it will take to get a given node.

This can sometimes be used effectively in lieu of the above A* algorithm but… I use it alongside the A* method, for some different purposes will be described below.

The Dungeons of Freeport System

Having experimented at least a little with the above systems (and a few experiments of my own), I ended up settling on a combination of procedures that give me the kind of dungeons that I want.

So, a few things about what I want to do with DFP:

• ‘Dungeons’ have specific categories. For instance, they can be a mine (that is, a combination of human constructed rooms & passages likely breaking into natural-seeming caves), a dungeon (human constructed rooms only), a crypt (as before, but with more supernatural enemies, haunted places, etc). This will impact the layout, the difficulty, and what kinds of rooms/spaces appear in a given dungeon.
• Dungeons will be relatively small. Both in terms of the level sizes being single or maybe just double digits in terms of number of rooms, and the number of levels in a dungeon being only a handful. The reason for this is that the core gameplay loop of DFP is ‘single dungeon a day’, with an intended play-time of maybe 10-15 minutes, if that.
• All dungeons are designed to be ‘completable’, but… very likely won’t be. During each delve, the player will, at a certain point, likely have to make the choice of “I am low on supplies and health potions, I am hurt, and my backpack is quite full of loot, do I turn back now while I still can, or risk going deeper?” Not so much ‘permadeath’ in the Rogue sense of the word, but where dying in a dungeon effectively erases the progress and loot you obtained.
• For each player on a given instance, the dungeons available will be the same. That is, each day a certain number of these limited dungeons will be generated of different difficulty levels, and each player on the instance can try one, posting comments, notes, even helping other players (or hindering them).
• The game will focus on some detailed simulated systems. Again, we’re not talking Dwarf Fortress here, but it will track not only light levels and line of sight, but sound propagation (you can sneak up on enemies to sneak attack them, or avoid combat entirely).

What this means is this: I do not want to create huge spaces. I am not creating Dwarf Fortress. I want small, tight, nicely structured dungeons.

So – this is the system I have decided to use…

Step One – Room Generation

Firstly, I generate a room. These are bespoke rooms generated by a system. The game takes all the rooms it knows how to make, and calls a probability function for each one. The probability function factors in things such as:

• What level the dungeon is (some rooms may not appear until deeper into the depths)
• What category the dungeon is (dungeon,mine,crypt,etc)
• What rooms it is close to (some rooms may be much more common near others – like, a larder or storage room near a kitchen, and a kitchen near a dining hall)
• What rooms already exist (some rooms can only exist once in a dungeon, or once in a level)

It generates a weighted probability stat, which is fed in. The program then picks the room.

The room object is generated by the algorithm, so while most rooms have a roughly similar size to others of their type, the layout and precise size may differ slightly (or, a lot depending on the type of room – a kitchen is a kitchen and probably much like each other, but a large storage hall might be varied in shape and contents).

Something else then gets done, which I will talk more about later – valid door positions are picked. For most rooms, this will just be a position to the north, south, west and east on its walls. But for some rooms, we may only want doors on one wall, or have several ones on certain walls.

For instance, the hall shown to the left here has pillars along its west and eastern walls, chairs beside them (the number is based on the width), an altar up front… and only has doors on its north and south walls. However, it has two possible door spaces on each wall, to give the sort of “left and right stage exit” feeling. Its size may vary, and the number of pillars and chairs in it may vary, but fundamentally speaking the basic shape and the unique placement of its doors remains the same.

In addition to the standard human-made rooms shown above, I am also going to use here some cellular automata. For certain types of dungeons, I will want ‘natural’ caves. Most likely in one corner or edge of the map. While not done yet, I plant to have some ‘rooms’ be quite large spaces generated with an automata system. Hopefully this drops into place nicely and does what I want but… we’ll see.

Step Two – Room Placement

If the generated room is the first room, it places it somewhere randomly in the space (and adds a ‘down stairs’ to it). If it is not, it then picks a cardinal direction, and a distance, and places the room there.

Once all the rooms are placed, it moves on to…

Step Three – Door Removal

With all the rooms in place, it now moves over each room to check if any door spaces are bad options.

For instance, if a room has a valid door position on its north wall, but the room is right up against the north edge of the dungeon level, it will remove that door.

This stops doors which will invariably be unable to attach to anything even being checked.

Step Four – Passage Creation & Dungeon Contiguity Checks

Connecting the rooms happens next. The first step is to pick a random room, and another one quite close to it.

The two closest doors to each other on each room are chosen. Then, the A* algorithm runs to try and find a connection between the doors. If it fails, then it will check the other doors until it finds one that connects.

Then, another disconnected room is chosen, and another one right near it. (It will prioritise disconnected rooms, but failing that it will connect to any room it can.)

It’s also worth noting that the A* algorithm carving the passages has a few rules I made to try and create more maze-like dungeons:

1. It can only tunnel through rock that is surrounded by more rock – unless it gets to its destination door. This stops it from accidentally breaking through into rooms it’s not intending to, or pathing too close to the edge of the map, leading a hole to infinity.
2. It prioritises existing passages as ‘cheaper’ than tunnelling through rock, resulting in lots routes between rooms sharing a common passage, rather than a thousand disconnected strands.

At the end of each pass, a check is done to ascertain if the dungeon level is now fully connected.

In the end, I decided to do this using a combination of systems: first, I remember which rooms are ‘connected’ to each other. Once all rooms are connected to at least one other, I run a Dijkstra algorithm, checking to ensure that the centre space in each room has a valid number – that is, it’s connected to the rest of the dungeon.

If that’s not the case, I connect two more rooms.

Once this check passes, it’s time to popular the level with monsters, treasure, and an exit.

Step Five – Metadata, Monsters, Loot and Exits

The exit is the first thing placed in this stage, and it’s done by first running a Dijkstra algorithm on the finished dungeon, and noting the distance of each centre point of a room. Using this technique, I can grab all the rooms that are moderately far away from the start position (but not always the FURTHEST one away) and pick one at random to be our exit, having the next set of stairs in it.

Then, also using the Dijkstra map, I can create secret rooms.

The method for doing this is to find all rooms that have only one door (so they’re a dead end), and do not contain a staircase. I can then replace the door with a secret entrance of some sort – a bit of wall that shows its cracks when you approach it with a torch, for instance.

I can also do this to, say, lock a room and ensure the key for it is hidden somewhere accessible to the player. Having marked those rooms as secret or locked, I can remember that for loot placement time – those places get some fancier loot, for sure.

Placing loot and monsters can use the same system. I can quickly tell how far I am placing certain loot or monsters to the player start, to avoid you appearing right next to the best loot in the level (unless I want it to).

We Have a Dungeon

Almost all of what I’ve descriebd above I’ve now implemented. So hopefully, this will ( as I do some play testing) result in dungeons that fit my specific use-cases for the game.

But hey, even if I have to muck around more and add/remove features? It’s fun as hell to make.

Seriously – make a Roguelike. It’s a blast.

References / Links

A fantastic primer on dungeon generation for Roguelikes is this talk by Herbert Wolverson from Roguelike Celebration 2020. If you want a much more verbose but very accessible talk on this subject, I can’t recommend it enough. https://www.youtube.com/watch?v=TlLIOgWYVpI

Beyond this, I recommend the following:

• Procedural Dungeon Generation – slsdo.github.io
• Dijkstra Maps Visualised
• Using A Cellular Automata Style Rule To Create A Cave System

And, of course – RogueBasin generally.