In the video "Procedurally Generated 3D Dungeons" by Vazgriz, the creator demonstrates an algorithm for generating unique and interesting dungeons using Unity 3D. The algorithm is based on a Reddit post describing the process used in the game TinyKeep, which the creator extended to work in 3D. The video explains the steps involved in the algorithm, provides examples of generated dungeons, and discusses the challenges and limitations of the process.
The algorithm for generating dungeons consists of five main steps. The first step involves placing rooms in the dungeon, with random sizes and locations. The second step is creating a Delaunay triangulation graph from each room, which is a triangle mesh that avoids long, narrow triangles. This step results in a diagram where each dot represents a room and each edge represents a potential hallway. The creator used the Bowyer-Watson algorithm to produce this triangulation.
In the third step, a minimum spanning tree (MST) is created from the triangulation graph, ensuring that every room is reachable with only a single path between them. The MST contains no cycles. The fourth step involves randomly choosing from the potential hallways (gray edges) to add loops to the dungeon, with the creator using a 12.5% chance for each edge to be chosen.
The fifth and final step is using the A* algorithm to find a path between hallways. This algorithm finds the lowest cost path given a graph and a cost function, with the cost function used in this case making it cheaper to go through existing hallways than to carve out new ones. The pathfinder produces short and believable hallways between rooms.
To extend the dungeon generator to 3D, the creator used 3D versions of each algorithm. The first step involved generating rooms in 3D instead of 2D, with some rooms placed on different floors. The second step required finding the 3D Delaunay triangulation of the rooms, which is actually a tetrahedralization. The third and fourth steps, creating an MST and choosing hallways randomly, were trivial to implement in 3D.
The most complicated part of extending the algorithm to 3D was the pathfinding step. The creator had to modify the A* algorithm to allow for movement up and down, connecting rooms on different floors. This involved adding constraints for staircases and handling special cases to ensure that hallways and staircases did not intersect inappropriately. The final algorithm successfully generates complex 3D dungeons with hallways and staircases, though there are some limitations, such as hallways that did not successfully pathfind.
In summary, the video demonstrates a five-step algorithm for procedurally generating 3D dungeons in Unity, based on the process used in the game TinyKeep. The algorithm involves placing rooms, creating a Delaunay triangulation graph, finding an MST, choosing random hallways, and using the A* algorithm for pathfinding. The creator highlights the challenges and limitations of the process, but ultimately presents a solid foundation for generating unique and interesting dungeons in video games.
