I Compared 4 Dungeon Generation Algorithms. One of Them Never Works.

In a recent experiment, the author compared four different dungeon generation algorithms on a 80x40 grid. The algorithms tested were BSP trees, cellular automata, random walk, and room placement. Each algorithm was run 20 times, and the results were measured across several criteria: open space, connectivity between rooms, average path length, and speed of generation.

The BSP tree algorithm was found to provide the most structured layout with 100% connectivity between rooms. On average, paths in this method were 105 steps long, and the generation process took 0.88 milliseconds per run. This method ensures that every room is reachable from any other, making for a more predictable and navigable dungeon.

Cellular automata, on the other hand, produced cave systems with zero percent connectivity. Across 20 runs, every single map generated by this algorithm had areas that were completely unreachable. This algorithm creates organic-looking cave systems that lack the structured paths found in the other methods.

Random walk and room placement both maintained 100% connectivity between rooms, similar to the BSP tree. However, their path lengths were comparable, with random walk averaging 73 steps per run and room placement at 81 steps. Despite this, random walk took the longest time to generate maps at 274.7 milliseconds per run, likely due to its more complex nature involving random movement.

In conclusion, while cellular automata offers a unique and organic approach to dungeon generation, it falls short in terms of connectivity. The BSP tree provides the most reliable and navigable layout, making it the best choice for structured dungeon maps. Random walk and room placement offer a middle ground, balancing connectivity and generation speed.