Random dungeon generation

in Game Programming

Last weekend was spent on creating a game in 48 hours for the Ludum Dare. The final results can be found here. In this post I will highlight on of the techniques I used during the game jam: random dungeon generation.

Getting a good random dungeon generator going was a bit of a challenge. There are plenty of scripts out there, but none of them were really suitable for my use case. The main reason for this was that I wanted a dungeon – with loops – not a maze. Maze generation is reasonably simple, but I had to spend quite a bit of time to get a result which I was happy with.

Let’s summarise what we want to achieve in a few explicit requirements: we want to generate a dungeon such that

  1. the amount of dead ends is limited;
  2. the dungeon is reasonably connected: not too densely, but also not too sparsely;
  3. the dungeon has a predictable size;
  4. there are some holes in the dungeon, so it is not one big rectangle.

Altogether, it should turn into something like this:

Generated dungeon

1. Random walks

The atomic technique of many maze generators is the random walk. We start at a tile and just move in a random direction until we encounter another room. A random walk could look like this for example:

Random walk

Or it could look different altogether:

Another random walk

Implementing a random walk is not difficult. Let’s take a look at a random walk method:

IEnumerable<Room> RandomWalk(RoomMap map, Room room)
{
    // Select a random direction.
    var dirMaybe = room.RandomEmptyDirection();
    if (dirMaybe == null)
        return;
    var dir = dirMaybe.Value;

    // Get the coordinates in the new direction.
    var coordinates = room.transform.position + Dir2Vector(dir);

    while (IsContained(coordinates) && map.GetRoomAt(coordinates) == null)
    {
        // Create a new room and connect it.
        var newRoom = CreateRoomAt(coordinates);
        room.Connect(newRoom, dir);

        yield return newRoom;
        room = newRoom;

        // Select a random direction.
        dirMaybe = room.RandomEmptyDirection();
        if (dirMaybe == null)
            break;
        dir = dirMaybe.Value;

        // Get the coordinates in the new direction.
        coordinates = room.transform.position + Dir2Vector(dir);
    }
}

The method calls some helper methods, but I think they should be descriptive enough to make the code understandable. Let’s quickly run through it nevertheless:

First we select a random empty direction on the room. This is to prevent the random path from going backwards and thus creates longer random paths. We then convert the direction to a new set of coordinates and check if the new coordinates are contained in our dungeon bounds and if the tile is empty. If so, we create a new room and repeat the process.

We can easily adapt this algorithm a bit already to make sure we leave holes in our dungeon for a nicer result. I created a ProbabilisticallySurrounded function that takes a potential room position and then returns false with a probability based on the around of rooms surrounding that tile. In my case, if the room is fully surrounded, I return false with 50% probability, and if the room is surrounded on three sides, I return false with 25% probability. In all other cases I return true. We then adapt the while-loop with another condition:

while (IsContained(coordinates) && map.GetRoomAt(coordinates) == null && ProbabilisticallySurrounded(coordinates))

Repetition repetition repetition

Alright, we now have one random path, but that won’t be enough. We want to repeat the random walks to generate a larger dungeon. We can achieve this by keeping track of all the rooms we generate, and try to do a random walk from each of the rooms. The code turns into something like this:

void Generate(RoomMap map, Room start)
{
    // Initialise queue of rooms.
    var roomsToExpandFrom = new Queue<Room>();
    roomsToExpandFrom.Enqueue(start);

    // Continue creating rooms until we run out of rooms.
    while (roomsToExpandFrom.Count > 0)
    {
        var room = roomsToExpandFrom.Dequeue();

        // Perform the random walk, while keeping track of new rooms.
        foreach (var r in RandomWalk(map, room))
            roomsToExpandFrom.Enqueue(r);
    }
}

And the result doesn’t look too bad.

Random walk repeated

There are still a few problems with this though. If you repeat this several times, you will see that the size of the dungeon can differ a lot. I have seen dungeons only half the size of the one above, and dungeons that fill almost every square. We need to normalise this, so I changed the conditions around a bit.

void Generate(RoomMap map, Room start, int amountOfRooms)
{
    // Initialise amount of rooms created to 1 (the start room).
    int roomsCreated = 1;

    // Initialise queue of rooms.
    var roomsToExpandFrom = new Queue<Room>();
    roomsToExpandFrom.Enqueue(start);

    // Continue creating rooms until we have enough.
    while (roomsCreated < amountOfRooms)
    {
        // Make sure we always have rooms queued.
        if (roomsToExpandFrom.Count == 0)
        {
            // Just requeue 20 rooms randomly.
            for (int i = 0; i < 20; i++)
            {
                roomsToExpandFrom.Enqueue(map.RandomRoom());
            }
        }

        // We should always have a room to dequeue now.
        var room = roomsToExpandFrom.Dequeue();

        // Perform the random walk, while keeping track of new rooms.
        foreach (var r in RandomWalk(map, room))
        {
            amountOfRooms++;
            roomsToExpandFrom.Enqueue(r);
        }
    }
}

Instead of just checking if the room queue is empty, we just loop until we have the amount of rooms we want. This means we might run out of rooms to expand from, so we should implement a mechanism that works around this. The code block at the start of the while-loop takes care of this.

The following image shows how there were still enough opportunities to expand, but the algorithm stopped anyway. In other instances, the area will fill up faster and the algorithm will try to fill in gaps to get to the amount of desired rooms.

Room limitation

Connectivity

So we dealt with requirements 3 and 4: we have a dungeon of predictable size and we’re not too unhappy with the shape. The only problem is that the dungeon currently consists of little hallways with dead ends. That is not going to do. After trying different solutions, the easiest solution turned out to be simplest: just find all the rooms with a dead end and connect them to a neighbour.

void ImproveConnectivity(RoomMap map)
{
    // Loop through all rooms.
    for (int j = 0; j < map.rooms.GetLength(1); j++)
        for (int i = 0; i < map.rooms.GetLength(0); i++)
        {
            room = map.rooms[i,j];

            // Skip empty tiles.
            if (room == null)
                continue;

            // Count the amount of connected rooms.
            var count = room.connections.Count(r => r != null);

            // If we have more than two connections, continue.
            // If we have two connections, connect to another room with 15% chance.
            // If we have one connection, always connect to another room.
            if (count > 2 || (count > 1 && Random.value < .85))
                continue;

            // Try to connect to neighbouring rooms ten times.
            int tries = 10;
            while (tries --> 0)
            {
                // Select a random direction.
                var dir = room.RandomEmptyDirection().Value;
                var coordinates = room.transform.position + Dir2Vector(dir);

                // Check if there's a room there.
                if (!IsContained(coordinates) || map.GetRoomAt(coordinates) == null)
                    continue;

                // Connect rooms.
                room.Connect(map.GetRoomAt(coordinates), dir);
                break;
            }
        }
    }
}

Let’s see how this looks.

Connectivity

The dungeon now looks a lot more workable! In the final algorithm I made a final change where I always made the spawn room as connected as possible to make sure the player could move around instantly.

All put together

If we now look at the entire algorithm, the final result is something like this:

Dungeon generation - final result

For the Ludum Dare, this was sufficient. There are still areas I would have improved given the time. It is for example possible that large areas of the dungeon are only connected through a single connection. In this case I would like to force another connection if possible. My suggestion to do this would be to loop through all rooms and for each room see if the dungeon is still connected if that room was removed. If not: add a new connection and/or room to fix this.

Side note: the queue

In the described algorithm I use a queue to keep track of the rooms that should still be expanded from. You can also use different data structures for slightly different results. In the following example I used a stack instead of a queue. While the queue visits the rooms in order of expansion, thus preferring rooms in the centre of the dungeon, the stack visits the rooms last visited. This causes the algorithm to make longer paths. The bias to the centre is removed by this change, but it also increases the likelihood of long dead end paths.

Stack random paths

Another option would be to pop a random room from the collection of rooms to expand from. This would give yet another result. The right choice depends on the application.

Final words

Despite being quite crude, the algorithm I wrote in only a few hours does exactly what I want. There are definitely some improvements, but it is interesting to see how maze generation algorithms could quite easily be adapted to get something I want. I tried several complex solutions before settling on this relatively simple adjustment.

You can find the complete source in the GitHub repository, but since the code was written as part of a game jam, it’s quite messy, so I do not recommend copying it over directly.

With this blog I am hoping to get back on my bi-weekly schedule, so I will be back again with another blog post in two week. Until then, feel free to leave a comment below, and don’t forget to play and rate my Ludum Dare entry!

Place comment

Your email address will not be published. Required fields are marked *