Custom Dungeon Generation

July 2020


Introduction

While creating the game Unexpect Orcs, my team and I needed a way to generate the dungeon levels. 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.
This article detials the method that is currently being 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.

Room Placement

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); 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. A spread of PI (radians) will allow the dungeon to grow in all directions (the effective spread is x2 the given spread as it is used as a +/-, doubling the range), 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, along with a new room from the supplied list to be placed. A semi-random angle is also determined, this is calculated with combination of the dungeon's direction and the spread. The rooms 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)) {
			//collision with an already placed room, try again
			continue
		} else {
			newRoom.depth = baseRoom.depth + 1
			placedRooms.add(newRoom)
			connect(newRoom, baseRoom)
		}
	}
}


Once the maximum number of rooms have 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!

Corridor Placement

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, to do this we need to check there validity. 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 valid.

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 forked corridors as well s 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:

Final Dungeon

You'll note that the rooms look terrible and 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 final solution.
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:


If you made it this far, 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!