Procedural Dungeons
For our Action-RPG game Quinn’s Quest we wanted to have procedurally generated dungeons. These dungeons contain rooms for the player to explore, fight and loot! I’ve been working on the dungeon generator this summer, and in this post I will explain how I ventured through this task. But let us start with a top-down view of a generated dungeon. (Figure 1)
Figure 1 – Top-down view of a generated dungeon.
The dungeon has an entrance room (the green room), and an exit room (the red one), which is placed as far apart as possible from the entrance room. The exit room can be reached from multiple corridors. The grey room is a hidden room, this one should be hidden from the player until they find the secret entrance to it. The dungeon is generated using a seed, so there is an almost infinite amount of different dungeons possible.
Triangulation
Figure 2- Example of Delaunay triangulation on the rooms.
To create this dungeon I start by generating rooms with random positiond and sizes I also make sure they don’t overlap with each other. After that it gets a little bit more complicated. To decide how the rooms should connect with each other I take the room position and triangulate them. The circumcircle of the three rooms shouldn’t contain any other room. This is called Delauney triangulation (See Figure 2).
It is easier to add a triangle inside another triangle, so I start with one big overlapping triangle at the start of the triangulation. When a room is added, it checks in which triangle it is positioned. It then creates three new triangles by creating new edges between the new room and the three old points from the old triangle it is in. After that I check the neighboring triangles. If the angle at the new point added by the angle of the opposing point is greater than 180, an edge flip is performed (see fig. 3).
Figure 3- Edge flip example – source
Minimal Spanning Tree
After triangulating, the minimal spanning tree is calculated. The minimal spanning tree gives us the least amount of connections required for the entire dungeon to connect, so this determines what rooms get connected through a corridor. It’s not the perfect minimal spanning tree because I (intentionally) added a small chance to connect more rooms. With this the dungeon is able to create loops, and doesn’t always result in a dead end. This makes a dungeon more enjoyable to play, since you don’t always have to backtrack through a previously explored section.
Figure 4- The minimal spanning tree to connect rooms
Corridors
Generating corridors is the next big step. My first attempt at generating these was by doing it the Manhattan way. These corridors didn’t look all too good, since they were too close to the rooms and all looked like an ‘L’. Instead, by just extending the exit of the room, and then connecting them the Manhattan way resulted in way better looking corridors that didn’t always lie next to rooms. By grouping the corridors (Figure 5) we can be sure what rooms are actually connected to each other. This is also later used for creating 3D models, and storing the entire corridor group in one vertex buffer (great for culling the different corridor groups).
Figure 5 – Corridors colored by group
And that is about it! We are now able to generate millions of unique dungeons! A lot of ideas this dungeon generator uses are inspired from this blog post on procedural dungeon generation: Procedural Dungeon Generation Algorithm (contains cool GIFs!). I’ll save the 3D dungeon topic for some other time, since that deserves its own post.
If you have any questions, feel free to ask them!