7/2020 - 8/2020
"Augustine" Dungeon Generation Prototype
Engine/Software
Languages
Roles
Notable Features Worked On
: Unity3D
: C#
: Programmer
: Procedural Dungeon Generation
About
This prototype was created for a dungeon crawler idea, "Augustine", where I was responsible for the procedural dungeon generation. This idea was based around a concept of combining elements to create different spells. Spells could also interact with the floor, for example, if the floor was wet, similar to Divinity Original Sins 2. The story would have consisted of a corrupt King requesting the player character to venture into his castle killing English mythical creatures that have mysteriously occupied the castle. The theme of the different levels would have consisted of different areas of the castle (kitchen, prison, sewers), and the ending would have revealed that these mythical creatures were actually once the castle's servants that had been transformed by the King. Thereafter, the player would fight their way back through the castle to the start fighting the King's men instead.
Binary Space Partition (BSP)
For this, I did some research into techniques of procedural dungeon generation and came across a paper by Nathan Williams: An Investigation in Techniques used to Procedurally Generate Dungeon Structures. From there, I narrowed it down to two different possible techniques, Binary Space Partition (BSP) and Delauney Triangulation. I first tried to implement BSP as it was much easier to do, but the format of the dungeon came out a little rigid and uninteresting. From there, I moved on to the Delauney Triangulation method.
Delauney Triangulation
The first step in the process was to calculate the number of rooms to generate and how large the rooms should be. This is done through normal distribution and the values can be set in the editor. These rooms are then instantiated as cubes, but their scale is normalised for the next step.
The second step was to separate out all the cubes so that they are not overlapping each other. Rather than figure out an algorithm to perform this, I simply utilised Unity's physics to push everything away from each other. For this, a rigidbody component is added to each cube. However, at its normal scale, the physics did not work, which is why I had to normalise the scale. Once the physics simulation has finished (about 3 seconds), I restored the original scale of every cube and rounded their positions, and again waited a little while for the physics to resolve again before rounding their positions again.
Following that, I performed Delauney Triangulation on the rooms using the Triangle.NET library and created a minimum spanning tree of the results, storing them as a graph. They are also converted into multiple dictionaries holding the room id (order they were generated in) as its key and various other information such as the vertice, position, and connections as its value. Hallway connections are created directly through the edges of the graph by creating a vertical or horizontal (or L shaped) line towards each vertice. These rooms are then visualised by instantiating different coloured cubes, and the walls by instantiating cylinders. Red represents a hub room, blue a normal room, and yellow a hallway connection.
The entire process can be viewed in the below 2 gifs.
