Dungeon Generation

Posted on Jun 3, 2020

While creating the game Unexpect Orcs, we needed a way to generate the dungeon levels. We had a look at some existing methods, for example Bob Nystrom’s brilliant method where he connects rooms with mazes.
For the most part we found that, while these generators were good, they didn’t really suit what we were after, We wanted to keep the rooms of our dungeons separated by corridors to keep that cramped feeling, but it didn’t make sense to use that whoever was building these dungeons would make the routes between rooms so indirect, so we decided to address that and make our own generator!

Example output from our dungeon generator

We initially implement a fairly basic algorthim; Randomly place n rooms and then randomly connect them to each other with “L” shaped corridors. While this certainly works, and was enough to get the ball rolling on the project, it left a bit to be desired. As you can see, a lot of the rooms end up merged together because the corridors are placed along the walls separating them. There are also a lot of loops and open areas that are just about as illogical as the windy corridors we were trying to avoid.

Our first try at generating a dungeon using L shaped corridors to connect rooms

This article detials the final method that was used for generating the Cellar Dungeon in Unexpected Orcs. The method is made to be pretty versatile and can generate a a wide variety of dungeons with completely different feels. It’s currently under-utilised in the game, but hopefully this article will demonstrate its usefullness.

The generation can be broken down into three main steps:

  1. Place rooms
  2. Connect rooms
  3. Fill with tiles

Step 1: Placing rooms

The placement of the rooms is the most difficult step in this algorithm, this is where all the magic happens and is what gives the dungeons their feel. After completing this step you are left with something like the image below. Each numbered box represents a room and each red line shows how they are linked together.

To get to this stage, the generator needs a bit of information. Firstly it takes a few room prefabs (hand built rooms made with our custom level builder), these being the spawn and boss rooms, as well as a list of other rooms that can be used in between. Along with these rooms, the generator is also given information about the maximum number of rooms, how close rooms can be to each other as well as the “spread” of the dungeon.
The spread dictates how new rooms branch out from the spawn room. It is essentially the angle (in raidians) that corridors can branch in, in a +/- direction (therefore the effective spread is twice the angle given here). For example, a spread of PI will allow the dungeon to grow in all directions, while a spread of PI/4 will produce a dungeon that only grows in a right-angled wedge.

To start off the generation, the spawn room is set as the initial room from which all other rooms are placed and a random direction is chosen to be the overall “direction” of the dungeon.
With those starting conditions, the rest of the room placement can begin.

The placements are made by choosing a random, already placed room (at first this will be the spawn room as it’s the only room that has been placed). We also randomly pick a new room prefab from the supplied list to be placed. A random angle is also determined, using the range of the dungeon’s direction +/- the spread. The new room’s distance from the placed room is chosen at random between the minimum and maximum room closeness. If the chosen placement of the room results in a collision with already placed rooms, the placment is discarded and retried.

During this process, the “depth” of each room is stored, that is the number of corridors needed to be travelled in order to get to the spawn room (for example: in the image above, room 8 would have a depth of 3). It is also important to keep track of which rooms connect with which other rooms, this will allow us to generate the corridors later.

Here is some pseudo code for the above:

function placeRooms(spanwRoom, bossRoom, rooms, maxRooms, maxDist, minDist, spread) {
    placedRooms = [spawnRoom]
    direction = random(2 * PI)

    while(placedRooms.length < maxRooms) {
        baseRoom = random(placedRooms)

        newRoom = random(rooms)

        angle = direction + random(-spread, spread)
        distance = random(minDist, maxDist)

        //puts the newRoom into the correct tile coordinates
        newRoom = placeNewRoom(newRoom, baseRoom, angle, distance)

        if(!newRoom.collides(placedRooms)) {
            // new room doesn't interfere with any placed rooms, place the new room
            newRoom.depth = baseRoom.depth + 1
            placedRooms.add(newRoom)
            connect(newRoom, baseRoom)
        }
    }
}

Once the maximum number of rooms has been placed, we can finally place the boss room. There are many ways this could be done, the way I decided to implement this was to place it using the previous method but instead of using a random room to connect it to, I used the “deepest” room in the dungeon. I’m not entirely happy with this, but I will talk more about this when discussing the short comings of this approach in the conclusion.

By following these steps, you end up with a situation that looks like the image above. At this point, only the location of the rooms is known, and which room connects to which. The next step is to turn those theoretical connections into actual corridors.


Step 2: Creating corridors

This step is relatively straight forward compared to the previous one, we already know which rooms need to be connected and we know where those rooms are placed. All we need to figure out is which actual tiles to take to get there. If that sounds like a pathfinding problem to you, you’d be absolutely right!

Specifically, I use the A* pathfinding algorithm and this is for a number of reasons.

Firstly, A* finds the shortest path (if it exists) between the start and the goal nodes. Both the Depth-First-Search, and the Breadth-First-Search algorithms will find a path, but not necessarily the shortest path. For dungeons that are supposed to human-made (well… depending on your game, not human, maybe dwarves? Orcs?..), I personally think it makes more sense to have direct corridors rather than a labyrinth, that’s why I want the shortest path.

Since we are on a grid system and we know both the starting location and where we want to end up, A* also has an advantage over Dijkstra’s algorithm. A* is basically a modified Dijkstra’s that allows us to bias our pathfinding in the direction of goal which should, in most cases, give us a speed boost. In this use case I doubt that it helps much since the search area is pretty small, but it’s trivial to go from Dijkstra’s to A* so why not? (If you’re wondering, I used manhattan distance as the heuristic which takes barely any computational power).

So now that we’ve got our search algorithm sorted, we just need to run it! For each connection between rooms we find the shortest path between their centres. In order to do this, we need to be able to interperate which positions are traversable. This is a pretty simple check; Are we in the wall of a room that isn’t the start room or the goal room? If the answer is yes, then it’s not a valid tile to traverse.

We personally don’t worry about pathfinding arround other corridors as we think this leads to desirable behaviour. When we ignore the other corridors, it opens up the possibility of corridors with intersections as well as corridors that are more than 1 tile wide (Both of these can be seen in this example, there is split corridors between rooms 0, 1, and 2. There is a 2-wide corridor leaving room 10 on the left).

Thats it! Corridors done and dusted. What we’re left with is the positions of the rooms and the corridors, now it’s time to turn them into tiles!


Step 3: Filling in the tiles

We now have the location of all the tiles that make up our dungeon, but we need to translate that into a tile map.

This is the easiest step, we’re on the home straight! We start off with a tile map that fits the dimensions of the dungeon (we know these from by tracking the min/max coordinates when placing rooms and corridors), and fill it with a generic WALL tile.

We then loop through all the rooms in the dungeon and copy their tiles into the tile map. Once the rooms are in, we follow each corridor and place generic FLOOR tiles to fill them in.

The final step to the whole process is applying the dungeon’s “tileset”. This is essentially a palette of tiles that is used to replace the WALL and FLOOR tiles with something a bit more thematic. With the way our tilesets are set up, we can have variation in which tiles are used which helps to break up repeating patterns and make the evironment a bit more interesting.

A bonus of this is that by using the generic wall and floor tiles in the prefabs definition, we can have rooms that can be re-used across dungeons with different themes.

The final result of the generation can be seen here:

You’ll note that the rooms look terrible and not much fun to play. While I’d like to use the excuse that they were only test rooms, my lack of artistic talent is also partly to blame.


Wrapping it up

This is by no means a perfect dungeon generator, and depending on your goals it might not even be a good one, but it allows us to get a wide variety of dungeons by just tweaking a few parameters.

There are some things that still need some work. As I mentioned in the first step, boss room placement is not ideal. One issue with it is that it is possible to end up in a situation where there is no space for the boss room around the deepest room, putting us into an endless loop. The way we deal with this at the moment is to try inceasing the distance the boss room is allowed to be from the deepest room but this is a bandaid fix more than anything, definitely not a polished solution. Ideally we will try and place around the deepest room a fixed number of times before trying the next deepest, until we can place the boss room. Another problem is that you might not want the boss room to always be the deepest one. There is almost certainly a better metric to determine the best boss room placement, but while we are trying to figure that out, depth will be adequate.

There are also some features that I would like to add to this generator in the future:

  • Room prefabs that are able to specify door locations instead of using the centre of the room for pathfinding.
  • Rotation and reflection of rooms to allow for more variety.
  • Introduce “cycles” into the room graph so that dead-ends are reduced and there is more choice in which path to take. This is sort of achieved by allowing corridors to cross one another, but there is no control with this method and the loops always occur within corridors and never rooms.

If you made it to the end, thank you! I hope you enjoyed it and maybe even found it useful. If you have any questions or suggestions feel free to get in touch!