May 2024
In this project I made two methods of procedurally generating dungeons. This is for a project which I am working on currently however the generation seemed to be worth writing about.
I first method I created was a more mathematical generation algorithm. The first generation method was based off two posts: Phidinh6’s method and a327ex’s post.
This algorithm starts by creating X rooms of random sizes in a grid. Then it culls (removes) any overlapping rooms. After culling the system creates a delaunay triangulation mesh(web of vectors) between each room, this mesh is going to be where hallways will be spawned. From this mesh we use Prim’s algorithm to create a path from the first room we generated to the last. Finally we create some extra hallways so that we rooms have some loops and it creates a more dynamic feeling dungeon. Hallways are then dug out by turning the diagonal vectors into L shaped tunnels. This method was great because it created truly random dungeons, however I ran into several problems: Firstly, Unreal Engine for some dumb reason does not support 2D arrays C++ or blueprints, so I had to create my own system for 2D arrays which was not efficient. This also limited me to 2D dungeons with a single floor and I wanted stairways and multiple levels to each dungeon. Secondly and what ultimately lead me to create a new system was the fact that this method results in really inorganic layouts when it comes to props, while this is a fixable issue I decided that a new approach would solve both my first and second problem. The second model uses prefabbed rooms and it spawns them out like a tree. This model is limited in variety by the number of different rooms but in exchange it offers very natural feeling levels. This is the algorithm I’m using because its much simpler, easy to replicate for multiplayer and allows for fast generation of multiple dungeons.
