Procedural Dungeon Generation
For my bachelors degree I developed a procedural dungeon generator in a three dimensional space, that works during runtime. An additional goal was to maximize the players fun traversing the dungeon.
To simulate a real usecase of the generator, I created a dungeon room with loads of vertices. A single brick within the wall is made with around 600 vertices.
Later on I also added decorations like fire goblets.
I managed all the functionality of how to structure the dungeon with a graph based approach. I created nodes that have a position and hold a list of edges.
The edges have a weight property as well as a Node declared as startnode and one declared as endnode. This makes the graph dynamic, weighted and directional.
The structure itself is supposed to be fitting to the playstyle of each individual. Therefore the paths through the dungeon are balanced between the number of rooms that need to be cleared and the difficulty of them.
With algorithms like dijkstra or A* a short path is easily found. Hard to clear rooms are more likely to be placed on the nodes on this path.
The longest path was quite interesting to create because the longest path within a graph is mostly connected with a known mathematical problem, working with the 'hamiltonian cycle'.
I solved the problem by traversing the graph in an 'A* reverse'-manner. What I mean is that I always choose the node furthest away from the goal. If it is a dead end, I take a step back and repeat the process, excluding the dead end node.
After all the calculations are done, the graph is being generated. Though to go easy on the hardware and to avoid disruptions of the player experience, the dungeon is generated over time(left picture).
Another aspect of sparing the cpu and gpu is the culling around the player. The dungeon is only processed within a predefined radius.