Procedurally Generating a Dungeon

Intro

Today I will to run you through creating procedurally generated layouts of a maps of rooms with up to 4 exits that link to other rooms. That's quite a lot to read everytime, and so throughout this blog post I will refer to it as a "dungeon".

I refer to what we're generating as a dungeon because that's what I had in mind when I was developing this algorithm. It doesn't have to be a dungeon, it could easily be house, a maze or anything else that consists of nodes and up to four links.

When creating this I had in mind something that I could use to procedurally generate the layout of levels in games. This would save me time during the development process, could enhance replayablility and lead me to fine tuning or improving other elements of a game's design.

There could be other uses for this. Though, to be clear, I have written from the perspective of creating a dungeon for players to traverse.

This algorithm generates a 2D-array of nodes or "rooms" that can have up to four exits: up, down, left, right. These rooms then connect to another adjacent room in the direction of the exit.

I will now run you through the process of creating this dungeon, using pseudocode.

Pseudocode

I am choosing to use pseudocode as there are many different programming languages or engines you could use this algorithm in. Having a more generic pseudocode algorithm could help you understand this algorithm at a high level.

The low-level details are not important for you to understand this algorithm and they actually consist of a fair amount of code. The implementation may be quite different depending on where you are implementing this algorithm. 

var target = number;
var dungeon = 2D target by target array.
var room_count = 0
var room_to_process_list = [];
var previously_processed_room = [];
var current_coordinates = {x: 0, y: 0};

while room_count < target:
    coords_to_process = rooms_to_process_list.pop()

    IF coords_to_process IS NOT NULL:
        current_coordinates = coords_to_process

    var room;
    var reprocessing_room = false;

    WHILE coords_to_process does not have valid addable exits:
        coords_to_process = reprocess previously_processed_rooms.pop();
        reprocessing_room = true;
        IF coords_to_process has a valid addable exit:
            room = reprocess_room(coords_to_process):
                randomly generate new valid UP,DOWN,LEFT,RIGHT exits and retain previous exits
    IF reprocessing_room == false:
        room = generate new_room(coords_to_process):
            randomly generate UP,DOWN,LEFT,RIGHT exits
    
    add room to dungeon at the current_coordinates within the dungeon array.
    IF current_coordinates not in previously_processed_rooms:
        add room coordinates to previously_processed_rooms;
    
connect room entrances
remove dead end exits

return dungeon

What this does is it builds a target room count by target room count 2D array, and then whilst enough rooms have not been created it loops through generating rooms, which have up, down, left or right exits.

A key thing to understand in this algorithm, is the concept of a "valid" exit. A valid exit is an exit which does not exist and does not yet have a node associated with it. Let's list three examples to explain this concept:

On each run of the loop, we generate a room. When a room is generated a list of non-processed adjacent rooms, i.e nodes that now have links to the newly created room, are added to the rooms_to_process_list. The next room we process will be a room popped off of this list.

In each iteration of the loop we pop an item off of the rooms_to_process_list. When we pop from the front we do a breadth-first generation and the dungeon tends to fan out, due to us processing rooms that are adjacent to earlier generated rooms first. When we pop from the back we do a depth-first generation, as we process the rooms adjacent to the most recently processed rooms first, which leads to more long chains of rooms.

breadth-first vs. depth-first dungeon examples.
Breadth-first vs depth-first dungeon examples.

On occasion, we will end up in a situation where we try and generate a room but the coordinates we are trying to generate a room for have no addable valid exits. In this scenario, we back-track to a previously processed room that has a valid addable exit and then reprocess that room. Reprocessing is where we add a new valid exit to the room and keep the previous exits.

We continue this process until we have our specified number of rooms.

Once we have our target number of rooms, we knock through the exits. That is, for each exit in each room we ensure that the adjacent room in the direction of the exit has an exit in the opposing direction. For example, if we have a room with a right exit then the room to the right will have a left exit.

We also remove dead ends. Dead ends are exits in a room that do not lead to another room. These exist because we hit the target number of rooms before processing the room with a dead end.

Closing thoughts

Many procedural dungeon generators create corridors or irregular shaped rooms. This algorithm does not handle the creation of corridors or the shapes of the rooms. This algorithm only deals with the rudimentary layout: the coordinates of a room and the adjacent rooms that a room links to. This algorithm is used for the layout but could be plugged into a pipeline that generates corridors or individual room layouts.

This is early in my adventure into procedural generation. It is my second published algorithm for procedural generation. My first - my maze generation npm package - is similar in that it used a 2D array to generate a layout using an up, down, left, right structure for nodes. I would advise looking into my maze generator for inspiration if you were to implement this dungeon generation algorithm.