Procedural Dungeon Generation
In roguelike games, the game designer must generate a random dungeon for the player to traverse. The generated dungeon consists of rectangular rooms and single-tile-wide hallways, and ideally has neither too many nor too few of either. How can the designer make such a dungeon, given an assortment of rooms?
To generate a floor, the algorithm first generates many more rooms than necessary. Rooms are then selected by a size threshold and connected via the Delaunay Triangulation using the rooms as nodes. The Delaunay Triangulation creates a graph with the property “for each point, this point does not lie inside the circumcircle of any triangle generated by the triangulation”. Connecting each of these rooms would make a rather cluttered dungeon; however, removing hallways at random may leave disconnected components. The solution here is to make a minimum spanning tree of the graph, which ensures that all rooms are connected, but aren’t clustered too much. All that remains is to re-add some edges from the triangulation and to draw the rooms and hallways on the grid.
Once generated, the dungeon floor has network features that are of strategic importance. Bridges and local bridges can provide chokepoints for the player, but also trap the player between two rooms. Rooms that are connected to a common room that are nearby spatially can be connected via terrain-transforming tools and demonstrate triadic closure.
Network theory can provide game designers with tools to generate appealing levels and the gamer to identify strategically important elements of such games.