Procedural Dungeon Generation
Alright~ After much work we have finally completed our dungeon generation algorithm.
First, we generate the rooms, separate them using a separation steering algorithm.
Second, we generate a graph that represents connections between the various rooms
Third, we perform what is known as Delaunay Triangulation, in which we evaluate pairs of triangles and swap their shared edge if it fails a test boiled down to a simple matrix determinant evaluation
Fourth, we construct a Graph of connectivity from the Delaunay triangulation
Fifth, we perform an A* pathfinding algorithm to connect points on the delauney triangulation through the neighborhood graph
Finally, if we didn't traverse through a room, we can remove it to simplify the dungeon into something a little less dense
There are some extra things we can do here and there, and bugs and edge cases to iron out here and there, but for now, we have a pretty neat little dungeon generator. The next step is to actually procedurally generate the rooms and then use the connectivity graphs to implement game logic and whatnot, but that we will save for another time.
gracieabrams
origamiaround
kianamaiart
