Video
Details
Programming Language: C#
Engine: Unity
Project Type: Personal Project.
Technical Features
Separating Axis Theorem Based Room Placement
The dungeon rooms are initially placed by randomly spawning them inside a radius. This results in a lot of overlapping squares, Separating Axis Theorem is then used to detect which squares are overlapping. The squares are then moved outward from the overlapped squares until they are no longer overlapping, similarity to how a lot of physics based collision systems work. So Separating Axis Theorem is in this case quite literally used to separate the dungeon rooms.
Delaunay Triangulation
Now that the rooms have been placed they need to be connected. A great to connect a large volume of points is triangulation. Delaunay triangulation is a form of triangulation that results in the points being triangulated in such a way that no point is inside a triangle. This is ideal for dungeons as that means we wont have any crazy overlapping or strange long connections.
Urquhart Graph
Once the rooms have all been connected we don’t need every single connection so you want to construct a planer graph for a more balanced amount of connections. There are lots of different planar graphs that can be used but i chose the Urquhart graph due its simplicity and elegance. How it works is you go through all the triangles and simply remove the longest side. This results in a very pleasing and effective set of coordinates.
About
In this project I created a procedural dungeon generator by combining several different algorithms. You start by randomly placing a set amount of rectangles in a defined radius. You then separate out the rectangles so none are overlapping using Separating Axis Theorem. Once you have all the rooms placed you connect them up using Delaunnay Triangulation. This results in a nice set of triangles but we don’t need that many connections, we need to make a more dungeon like layout which i do here by using a Urquhart graph to get a very dungeon-y lay out of paths. We now have all the data we need, we just have to construct it. So we take the rooms and replace the inner areaswith floor tiles and the outer areas with wall tiles, we then can replace connection lines with corridor tiles and then finally we have a dungeon.
This system will hopefully be fleshed out further in the future with the addition of a random interior to the dungeon rooms with multiple kinds of tiles.