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

Four algorithms. Same grid. Very different dungeons. I implemented BSP trees, cellular automata, random walk, and room placement, ran each one 20 times on an 80x40 grid, and measured everything: connectivity, open space, path length, speed. The Results Algorithm Open Space Connected Rooms Path Length Speed BSP Tree 42.1% 100% 1.0 105 steps 0.88 ms Cellular Automata 55.8% 0% 15.2 78 steps 52.8 ms Random Walk 35.0% 100% 1.0 73 steps 274.7 ms Room Placement 18.9% 100% 1.0 81 steps 0.29 ms The big surprise: cellular automata never produces a connected map. Zero percent connectivity across 20 runs. Every single cave system has unreachable areas. The Maps BSP Tree (structured rooms, always connected) ################################################################################ ################################################################################ #####.........#####.............###################################....#......## #####.........#####.............##..........##############........#....#......## #####...........................##..........##############....................## #####.........#####.............##..........##############.............#......## #####.........#####.............##..........##############........#....#......## ##########.#######################..........##############........#....#......## ##########.#######################..........################..################## ######..........##################..........################..################## ######..........##################..........################..######..........## ######..........##################..........################..######..........## ######..........##################..........################..######..........## ######.............###############..........################..######..........## ######..........##.###############..........################..######..........## ######..........##.###############..........################..######..........##