Random dungeon generation blog - Baldurius

Hey buddies!

My last blog-post is more than one week ago and that's way too long! This period is caused by me being busy fixing bugs and tweaking some details of the following topic.

The problem

When I first thought about random dungeon generation I had no idea how complicated it will be figuring out an appropriate algorithm to meet my requirements.

The first question is: What does a typically dungeon consist of?

All my approaches use the idea that a dungeon is simply a set of rooms of different sizes and shapes which are connected by corridors. Therefore the big problem of dungeon-generation splits into the two essential parts of room-placement and connecting these rooms in a natural and plausible manner.

First attempt

To solve the problem of room-placement I decided to use a very simple approach at first. So I took an empty map with fixed width and height and threw a room with random size at it (of course this is meant metaphoric... I can't throw rooms, especially not of random size). After placing a second room randomly I simply check, whether it intersects the first one and if it does, I simply redo the placement.
This process got repeatet until there were enough rooms.


To connect the existing rooms I then generated a perfect maze.
A perfect maze is called perfect because of the fact that every point in the maze has exactly one path to every other point. Because I needed to connect all rooms in a way I can reach every room starting at a certain position I thought this kind of maze could be useful.
The generation of such a maze is very simple and can be implemented using a small depth-first-search-method with a few tweaks.

The main idea then was to simply merge the map containing the rooms with the one containing the generated maze. To do this I needed to add the following two limitations to the room-placement:

• a room can only pe put at even coordinates
• the length of the edges of a room must be odd

The reason for this is that I don't want rooms to directly lie next to a parallel passing corridor.
With this technique I was able to create nice looking dungeons like the one shown on the following picture:

But as you might already see, because of the underlying maze these are very difficult dungeons. So I started thinking about an algorithm to reduce the amount of deadends and redundant corridors and I came up with a method which does exactly this.
Based on the already generated dungeon the algorithm first builds a graph and computes the minmal spanning tree. Then all unused edges are removed and the result is a dungeon with perfectly connected rooms. After making the algorithm a little dumber I was also able to control the difficulty.

The advantages of this method are evidently. It is simple, creates nice looking dungeons and can be scaled to huge maps.
But there are some disadvantages too which caused me to find another, better and much more complicated method. These disadvantages are among others:

• I'm not able to place manually generated rooms of different shapes on the map
• the corridors are highly branched and quite long
• the space between the rooms is too big
• the needed calculation-time is mostly short, but highly depends on randomness and is therefore unbounded

In order to make this post not too long I decided to split the topic of dungeon generation up into multiple parts. So my next post will be about how to overcome the issues in the first approach.