Procedural Dungeon Generation
This algorithm comes from a Roguelite game that I started to make but didn't finish.
My goal was to generate a set of randomly chosen rooms from an array of room
prefabs
and interconnect them in such a way that every room is reachable.
After doing some research, I liked the approach used for the game "TinyKeep", described in
a 10+ year old reddit post.
I used the steps outlined here as a guide, adapting them to the vision I had in mind for my game.
Step 1 : Generating rooms
First, I instantiate the room prefabs. Each room is created at a random position inside a circle.
Step 2 : Separation Steering Behavior
I separate the rooms using
Craig Reynolds' separation steering behavior for autonomous characters
until there is no overlap.
N.B. I added a "space between rooms" parameter to change the overlap size of the rooms to space them out.
Step 3 : Delaunay Triangulation
I create a graph that connects all the rooms together without intersecting lines.
This is done using
Delaunay Triangulation.
The triangulation is done by adding points (in our case, rooms) one by one to the triangulation,
checking if it is in the circumcircle of any triangle in the triangulation. If it is, we remove those triangles
and create new ones with the added point.
N.B. I created 3 structs :
- An "Edge" struct made of 2 vertices.
- A "Triangle" struct made of 3 vertices and 3 edges.
- A "Circle" struct simply made of a center (Vector3) and a radius value.
This struct is used to store the circumcircle of the triangles which are necessary to perform triangulation.
Step 4 : Minimum Spanning Tree
Now, all the rooms are connected to their neighbors, which results in an uninteresting dungeon with too many paths.
So I create a
minimal spanning tree
from the graph obtained with the triangulation.
A spanning tree is a graph that will always include all of the rooms, making them all reachable.
It's a minimum spanning tree when we only incorporate the minimum possible total edge distance.
Using
Prim's algorithm,
the tree is built one vertex at a time, from a starting vertex (the first generated room).
With each subsequent step, the vertex that is part of the triangulated graph and
at the closest distance from the tree is added to the tree.
N.B. I created a "Graph" struct to store a set of vertices and edges.
Step 5 : Adding Cycles
Now, there is always only 1 possible path from one room to another because the tree contains no cycles, which makes the dungeon not very interesting. So I loop through all the edges from the triangulated graph that are not part of the tree and give each a 15% chance of being incorporated in the final graph.
Result
The final result is a randomly generated set of rooms with multiple paths for the player to take (red graph).
