Last year I made a dungeon map on a sphere. The goal was to make a sphere map, but I needed a dungeon to go with it, so I made a quick & dirty dungeon generator. I had never made a dungeon generator before. I later realized I like that dungeon generator but it had some problems (corridors to nowhere, disconnected rooms, etc.). Here’s my attempt at explaining how the dungeon generator works, and along the way I’ll also try to fix the problems.
There is an occasional infinite loop that I haven’t yet debugged
Goals:
- one primary path through the dungeon
- many side paths with limited length
- occasional loops
- locks where you have to find the key to pass
Rough outline:
- Use poisson disc to place lots of room seeds.
- Parallel bfs to expand these slightly so that they all have a minimum room size.
- Serial bfs to expand them one by one up to their maximum room size.
- Door detection to place one door candidate for each pair of rooms that share a wall.
- Graph analysis to choose a subgraph that meets the goals.
- Door placement to choose the doors that are needed for the subgraph.
- Pruning to clean up rooms and corridors that don’t meet our needs.
Room sizes should increase over time. That way later rooms will flow around earlier rooms and ensure connectivity. Since room order is randomized this means the large rooms will be scattered around the map.
Related: brogue room accretion http://anderoonies.github.io/2020/04/07/brogue-generation-2.html[1] generates a room and then tries to attach it to an existing room by pathfinding. I’m assuming my graph is dense enough that I will have connectivity without pathfinding.