Procedural Generation Techniques – Procedural Dungeon Generation

There are many ways of creating procedurally generated dungeon rooms. Some involve the use of noise, where others use pathfinding algorithms such as A* or Dijkstra’s shortest path.

In most cases, you’ll want a number of rooms of different sizes and in different positions, as shown below:

Multiple rooms of different widths and heights, evenly spaced

A good place to start with this is to figure out the size of the rooms that you want. Many implementations use a normal distribution to produce sizes of even spread, however if you’re short on time or don’t need much complexity, simply using a random range between 2 values will suffice.

Vector2 GenerateBox(int min, int max) { 
            Vector2 box;
            int rand = Random.Range(min, max);

            box = new Vector2(rand, rand);
            return box;
}

You can customise this function fit your needs, but the above code snippet should give you a good starting point. A good modification would be to allow for much taller or longer rooms, depending on whether the direction in which the game moves is horizontal or vertical.

Now that you have the size of the rooms, you need to actually generate them. Similarly to the previous step, there are a number of ways to do this. One solution is to spawn each object inside a sphere, give them each a physics object, and then let the physics engine resolve the collisions so that no room is inside another. While this works, it does require the use of an external physics library and can be quite resource intensive if the dungeons are big enough.

Another approach then, is to essentially imitate this process. Given that we know the exact positions and sizes of each room, we can use this information to manually resolve the rectangular collisions using AABB (Axis-Aligned Bounding Box) detection.

AABB collision detection

If one rectangle is found to be inside another, simply shift one rectangle outside of the other by the collision depth. Most game engines have this capability built in, but it’s easy enough to write your own if not.

Having resolved your rooms, you should be left with non-overlapping individual boxes. From here, it’s time to link them together with pathways and doors. 

In order to make sure that every room within the dungeon is reachable, you’ll probably want to perform Delaunay Triangulation. It’s probably best to import a pre-made solution for this, as it’s quite a tricky algorithm to implement from scratch. The basic idea is to provide it with the positions of each of your rooms, and it will link them all together in a nice triangular web, seen below:

Delaunay Triangulation of the rooms

You could, in theory, use these connections as-is to link your rooms together with corridors, if you’re fine with the number of connections and doors that each room will have. Alternatively, you could perform the following additional step.

The final step is to create a Spanning Tree. I also recommend finding a pre-made solution for this, but having already generated the triangulation web it shouldn’t be too difficult to integrate the 2. The ST is a way of connecting all the rooms together so that there is exactly one path from one point to another.

If you have time, you might consider adding weights to the tree edges, depending on corridor length to create a Minimum Spanning Tree. This would allow you to create the smallest possible dungeon, with the shortest room paths.

Spanning Tree

And that’s it! I’ve included some additional reading below for more information about the various components that make up this system.

https://en.wikipedia.org/wiki/Delaunay_triangulation

https://simple.wikipedia.org/wiki/Minimum_spanning_tree

https://tutorialedge.net/gamedev/aabb-collision-detection-tutorial/

http://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php