Procedurally Generating a Dungeon: Part 2

Introduction

In a previous blog post I wrote about an algorithm I created for procedurrally generating a grid based dungeon. In this system each room had four exits. When each room was processed, it would randomly determine if it had an up, down, left or right exit.

I made the algorithm for a few reasons. Firstly I wanted to do a bit of learning in the procedural generation space. Secondly, I wanted something I could use in game development and game-jams. The algorithm itself would serve as a placeholder for tech demos, before a more tailored algorithm could be added to a game.

Since publishing, I felt that the algorithm was more complex than necessary. Each room being processed was responsible for a bit too much. There were the occasional bug and crashes, despite a rather large amount of unit and integration testing.

I thought I could and should make a more simple algorithm. So, I set of with pen and paper alongside some dice to simulate randomness.

The Algorithm

Pseudocode

Set t = target_room_count;
var grid = generate a t by t 2d array;
var nodes_to_process_queue = [Vector2(0,0)];
var total_rooms = 0;

while total_rooms < t:
    var room_added_on_pass = false;
    for node in nodes_to_process_queue:
        var new_room = nodes_to_process_queue.pop();
        var new_nodes_to_process = new_room._generate_room_exits();
        for node in new_nodes_to_process:
            if node is not in nodes_to_process_queue:
                nodes_to_process_queue.push(node);
        if new_room has exit:
            total_rooms++;
            room_added_on_pass = true;
        if !room_added_on_pass && nodes_to_process_queue.size() == 0:
            var forced_room = _force_new_random_exit(grid)
            if forced_room.is_new_room:
                total_rooms++;
            new_nodes_to_process.push(forced_room.new_nodes_to_process)
shrink grid to be x by y in size, where:
    x is the x coordinate of the rightmost room
    y is the y coordinate of the bottommost room.

    
func _generate_room_exits(grid, room_coords):
    randomly generate right and down exits for room at grid[room_coords.y][room_coords.x]
    return coordinates of adjacent room that exits lead to.

func _force_new_random_exit(grid):
    randomly determine whether to expand rightwards or downwards
    if expand_downward:
        choose random existing room from bottom row
        or choose first room on bottom as default case if no rooms have exits on row

        generate down exit for random room
        return {
            is_new_room: a boolean check for if the chosen room has exits prior to being forced an exit
            new_node_to_process: coords for adjacent room toward exits,
        } 
    else:
        choose random existing room from rightmost column
        or choose first room on right column as default case if no rooms have exits on column

        generate right exit for random room
        return {
            is_new_room: a boolean check for if the chosen room has exits prior to being forced an exit
            new_node_to_process: coords for adjacent room toward exits,
        }

Explanation

As we can see the algorithm still generates a grid based dungeon with room that have four-exits. There are small changes of large consequence.

The largest change is that rooms are no longer responible for generating exits in all four directions. In the previous algorithm rooms were responsible for generating "UP, DOWN, LEFT, RIGHT" exits. Now they are only responsible for "DOWN" and "RIGHT" exits.

This has a major effect on the dungeons that are generated as they would not have a way expand upwards or leftwards, unless an existing path were to join a room from those directions. That is quite the limitation for sure, yet it is a limitation that has had quite a large benefit. By having rooms be responsible for generating only two exits we have removed a lot of tracking that is required. We also now no longer need to check for "valid exits" - defined as exits which do not yet exist and do not have nodes associated with them.

The simplification of the exit generation has also allowed us to remove the previously_processed_room_list. We can do this as rooms are either generating a RIGHT or DOWN exit which once created are never removed. Also paths colliding would not lead to exits being overridden. Say we process node (1,1) twice, due to a room connecting to it from above and to the left, there would be no opportunity for the room to accidentally remove the UP exit or LEFT exit. Once an exit has been set it is not removed, so reprocessing (1,1) would not lead to it removing an existing DOWN exit.

There have also been changes in the case where we run out of rooms to process but we have not yet hit our target room count. This situation occurs when not enough exits are generated, which is more likely to happen when we have a low chance of generating exits.

Previously, we would choose a random room to process. Now we randomly choose whether to expand rightwards or downwards. If we expand rightwards, we choose a random cell on the far-right of the dungeon and add a RIGHT exit; if we expand downwards we choose a random cell on the bottom of the dungeon and add a DOWN exit. Again a more limiting change, but a change that keeps it simple.

An example of a procedurally generated dungeon using the new algorithm.

Closing Thoughts

My previous algorithm for generating 2D grid-based dungeons without corridors felt over-complicated. I concluded I should simplify this algorithm and did that by making new exits be either RIGHT or DOWN, rather than UP, DOWN, LEFT or RIGHT.

This small change limits the shape of the generated dungeon. Yet the benefits of the change has lead to a simpler algorithm that is easier to follow and is less prone to bugs.