BFS for dungeon generation

 from Red Blob Games
22 Oct 2020

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:

Rough outline:

  1. Use poisson disc to place lots of room seeds.
  2. Parallel bfs to expand these slightly so that they all have a minimum room size.
  3. Serial bfs to expand them one by one up to their maximum room size.
  4. Door detection to place one door candidate for each pair of rooms that share a wall.
  5. Graph analysis to choose a subgraph that meets the goals.
  6. Door placement to choose the doors that are needed for the subgraph.
  7. 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.

Email me , or tweet @redblobgames, or comment: