Dungeon Generation

As shown in other post, world-maps can be generated in a lot of interesting and creative ways. I decided to focus on generating a dungeon, as I found it both fun and challenging. In this set of post I'll try to show my experimentations on the subject.

After starting a new job, I had to leave my personal projects to focus on my new role in my new company. It may have taken me some time, but I'm back to coding for myself a little bit.

My goal will be (at least in the beginning) to create a man-made dungeon. No natural underground for my first tries.

General Process

This animated image show the construction of our dungeon, step by step. The main idea is to get a free door in a room and try to add another room at this point. If such a room can be added, then the door is no longer free. All doors in the new room are added to the list of free door (except the one lining to the old room, of course)

Grid 

I used a square grid, as I wanted large boxy rooms, long corridors and 90 degree turns. I placed each tile at run time and stored them in a 2D array. Each tile contains a simple character that represent its content. For example, "#" is wall, "=" is door...

Rooms

Each dungeon room is a 2D array of tiles. 

All the rooms are pre-set and stored into individual files. This makes it easier to add or modify them later on. We could also modify the code to generate the rooms.

All rooms loaded from those files are mirrored on the X, Y, X&Y axis, as well as rotated 90° and mirrored again. This allow to generate 8 rooms from a single definition.

So here are a few rooms that we defined :

The orange block are walls and the brown one are doors. Blue are half-height or full-height decorations. Red are joker and can be anything on the map, to allow for non-rectangular rooms.

Room Placement

We start by adding a door on the map. Then, we add it to the "available exit" list in map space (i.e., with their coordinate on map and the kind of door)

The rest of the generation process is an iteration on the following (each step will be described later on)

1. Choose one exit in the "available exit" list
   
2. Choose one room that contains this kind of exit
   
3. Check if the room can be placed, by overlaping the door from the map with the one from the room and checking for inconsistencies (like any other rooms that could be in the way). If the room can not be placed, repeat step 2 while there are room available.
   
4. Put all the doors from the new room in the "available exit" list if they are not already present, or remove them otherwise.
   

Choose the Exit

We have a list containing the available exits and have to choose one. There are three main way to do this.

Random choice

We take one exit at random on the list. Simple, nice and easy.

Depth-First

By taking the last element of the list, we are acting like we follow a path. We take one of the doors from the initial room, add a new room, take one of the door of this new room, add another new room and so on.  If there are no doors in the current room, we can go back to the previous one.

Breadth-first

By taking the first element of the list, we span-out of the initial room : we get (in sequence) all the doors from the initial room, then all the doors from the second room, and so forth.

As you may notice, there are few differences in the result from the different methods.The breadth method has the advantage of looking more "dungeon like", as the last exits will probably be along the further from the initial one (at least in term of number of room to cross).

Choose a room with this kind of exit

For now, we have two kind of exits : horizontal and vertical, both 2-cell wide. So we takes all rooms that contains the exit type we're looking for. Since this is static, we can pre-calculate those lists once.

We could choose a room at random, but we could also sort the list by several factors. For example sorting the room list by increasing room size allows for the biggest room to be chosen, as long as there's enough space. However, this means that bigger rooms will prevail.

My solution is to have two data linked to each room: a sort index data based on size ((XSize+YSize)/10), and a usage counter that increase by one each time the room is placed on the map. We sort the rooms by Sort Index - Usage. 

There is however something to be mindful of: when we increase the usage of a room, we should also increase the usage of all the rooms that comes from the same origin / file. Otherwise, the room will be lower on the list for the next selection, but copies made by mirroring or rotation still are at the top of the list, meaning in the end the chances of selecting duplicate rooms multiples times won't be any lower.

Once this is done, we take the first room of the list, and go down in the list if it can not be placed.

Check if the room can be placed

To check if the room can be placed, we place the door from the map and the one from the room on top of each other, and then we compare both of their tiles.

If the tile is a joker, either on the map or the room, the tile is OK. It's also good if it's an identical tile on both the map and the room. If at least one tiles doesn't correspond, there is no match and we check another door on this room, or another room if we ran out of doors to check.

Here are two room. The right exit has been selected on the first, and we will try to superimpose it with the 2 corresponding exits of the second room.

We start with the right exit of the new room. Superposing it to the exit on the map does not work :

Performing the same operation with the left exit of the room gives a satisfying result, since there are no collisions :

You can check by comparing tiles from the room with the corresponding tiles in the map. If both tiles are identical, or if one of them is a joker, then the tiles are compatibles. If all the tiles are compatibles, then the room can be placed here.

OK, this is a lie. I'm sorry (no I'm not).

Let's have a look at what occurs in the following case. Both doors from the right room's door  can be used to link to the left room: 

 

In one case, apart from the door, there is no collision (all other tile are joker), so it's valid choice :

 

In the other case, we are putting the new room over the old one, but all since all tiles are matching, it's technically also valid. And of course, the tiles are matching, since it's the same room... which means that visually we don't get anything new. Moreover, all non-used doors from the initial room (left one) are now considered  used since they all link to the new room (see lower in this blog about this).

 

To counter this, each time we place a room, we have to store the room Id and it's origin one the map. Before checking a new room, we make sure that this room id was not already placed with the same origin. Otherwise, we are simply duplicating the room, which should be forbidden.

Adding the new doors 

Once we get a valid room, we  get all the doors (in our previous example, left and right doors). For each we check if they are present in the available exit list, in map coordinate.

• If no, this is a new door, and we add it to the list.
• If yes, this mean that a door already exist at this position from a previous room. The fact that our door is at the same position means that the two rooms are linked by this door, and can not be used anymore. We thus remove the exit from the available list.

This methods allows the removal of all used doors, even if they weren't used to place the room. In the following image, after adding the lower-right room, all doors marked with a '-' will be removed from the available list, while the one marked with a + will be added.

Map Cleaning

When we have no more exits available, it's time to clean up the map.

1. replacing all "joker" tiles by "wall" tiles
   
2. removing the door that do not lead to a room
3. removing dead-end corridor (cul-de-sac) 
   

 Step 2 & 3 have to be performed repetitively, till it can't be applied anymore. Removing a door could lead to a corridor becoming a dead end, which would be removed, and so on...

Transform Joker into wall

Any tile of non modified type (i.e. joker)  are transformed into a stone/wall tile. 

Remove non-useful door.

Some exits/door could not be used to create a new room. We have to remove those, as they open onto wall, not empty space. 

• This could be done by adding them to a special list when we checked all rooms and could not place any of them from for a door.

• Another possibility is to perform some sort of pattern matching, and when found, replace the pattern by another one. For example we can replace the first pattern by the second : 

 Remove Cul-de-sac

We can also remove Cul-de-sac in the same way using a pattern to replace another pattern.