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) ################################################################################ ################################################################################ #####.........#####.............###################################....#......## #####.........#####.............##..........##############........#....#......## #####...........................##..........##############....................## #####.........#####.............##..........##############.............#......## #####.........#####.............##..........##############........#....#......## ##########.#######################..........##############........#....#......## ##########.#######################..........################..################## ######..........##################..........################..################## ######..........##################..........################..######..........## ######..........##################..........################..######..........## ######..........##################..........################..######..........## ######.............###############..........################..######..........## ######..........##.###############..........################..######..........## ######..........##.###############..........################..######..........## ######..........##.###############..........################..######..........## ######..........##.###############..........################..######..........## ######..........##.###################.##.##################..######..........## ##################.###################.##.##################..#...............## ##################.###################.##.##################..#.####..........## ##################.###################.##.##################..#.####..........## ##################.###################.##.##################..#.####..........## ##################.###################.##.################......####..........## ##################.###################.##.################......####..........## ##################.###################.##.################......####..........## ##################.###############................########....................## ##################.###############................########......####..........## ##################.###############................########......####..........## ##################.###############................########......####..........## ##################.###############................###########.#.################ ######.........................#######..#####################.#.########......## ######.........................#######..####..........######........####......## ######.........................#####.......#..........######........####......## ######.....................................#..................................## ######.........................#####..................######........####......## ######.........................#####.......#..........######........####......## ######.........................#####.......#..........######........####......## ################################################################################ ################################################################################ Clean rectangular rooms connected by corridors. The BSP partition ensures coverage across the whole map. Longest paths (105 steps on average) because rooms chain along the partition tree. Cellular Automata (organic caves, never connected) ################################################################################ ########.#..#.##.######.##############.######################################### ######.#.........#.####...##########...###############################.#.#.##### ###............#............########....##############.####.#.#####........##### ###..........#.....####.....#.#####......##########...........###.#..........### ##...........#####..........#.#...#.....######.####.............#...........#### ##..........####..####.###.....###.......##.#..............................##### ##...........######..#.....####........####....................#.#.......####### #............###...#...###.#....#.#....###.....................#.#.#...#.####### ##...........#.#.#.####....#....#.#.#######....................#.#.###..######## ##..#.#......#.#.#.....####.....#.#.#...#..........................#......###### ##..###...........####.#..#.#.#.#.#..####...................###...........###### ########.............#.#.#..#.#.#...#.....................###...............#### #######............#.#.#.#.#..........#....................####............##### ########............##.#.#.#..............................###.........#.....#### #########..............###.#................#...............#........########### ########............###...................#.#.#.....................###....##### ##########..........#.#.##.#..............#.#.#.......................####.##### ###.#.#.............#.##.#.#.............##.####.........................####### ###.....##.............#.#.#...............####............................##### ##..............#......#.#..............#######...........................###### ##......##......#.........#.....#.#........#####...........###......#.......#### ###.............#......###......#.#.#.#.#######.....................#.......#### ##......##......#...............#.#.#.#.#.###.#....................###........## ##...................####.......#...#####.#...................................## ###......###.......####..............###.#.#........#..............###.........# ##...................###.......#.#.#####.#.......####...........#............### ##.........###......#####......##.................#####.......#.#....#........## #....................####........#######.........#####........#.##...#........## ##...........###....#####......#.#................###.......#.####...........### ##.................#######.....#.#................#.#.......###.#.............## ####..........##....#####........###................#.....#####.#...........#### ####.............####.###....................#.#....#......####..............### ##...........###.#....#.#.........##.........###.#.#......#####..............### ##...........#...##..............#...........#####.#.......#####............#### #..........######........##......####.......######........######.#...........### ###.........######.#......#....######.#.#.#.######.#....#.########...#......#### ###.......##########.##.#####.######################.#.#############.####.###### ######.#.####################################################################### ################################################################################ Looks great. Natural cave formations, organic shapes. But see those isolated pockets? The player can never reach them. Every game using cellular automata needs post-processing: flood-fill the largest cave and either tunnel to the others or delete them. Random Walk (amorphous blobs, always connected) ################################################################################ ######.................###########################..##.#....#################### ######.........#.......###########################...........################### #####....................########################...###......################### ####.....................###.##.#################.##.##.##...################### ####..#..............#........#.###############....#..........################## #.####...............###........###############................################# #...#................######......###############................################ #....#.#............#######......#############................#.################ #.................###########.#..##############.................################ ##................##############.############.#..............#...############### ###...#..........###############..##########..#...........#.##...############### ###...#...........###############.#########.....###......##..#...############### ###...............###############.###########..###...........################### ##...............###############......#######..###...###.#...################### ###..............###############....#.#######..###...####....################### ##............##.###############.........####.####........##.################### #...#..........#..##################.#........####..####..##.################### #.................#####################........##########..#..################## ##................#########..#########........########........################## #.#...............########...###.##.##..........######....###################### #.................########........#..............#####..######################## #...##...###......##................................##.######################### ######...#####..................................###....######################### ######.#######..................................####..########################## ##############.#...#..#........#...............################################# #####################.....#.#..##...............################################ #########################.#.#..###................############################## ###########################.....................#.############################## ###########################....#........#..........############################# ############################............#.........############################## #############################........#...........############################### ##########################.............#........################################ ##########################.#...........#...#...################################# ##########################......#..............################################# ###########################.....##................#..########################### ###########################.###.##.....................######################### #################################.....................########################## #############################...........#.............########################## ################################################################################ Connected by construction since the walker carves a single continuous path. But no distinct rooms, no structure. The result looks like someone spilled water on the map. Takes 275ms because the walker needs thousands of steps to carve 35% of the grid. Room Placement (compact, fast, always connected) ################################################################################ ################################################################################ ################################################################################ ################################################################################ ################################################################################ ################################################################......########## ################################################################......########## ################################################################......########## ################################################################......########## ###############################.......................................########## #######.......#################.##########.#####################......########## #######.......#####.....#######.##.....###.#####################......########## #######.......#####.....#######.##.....###.#####################......########## #######...................................................###################### #######.......#####.....#######.##.....###.##############.###################### #######.......#####................................######.###################### #######.......#####.....#######.####.#####.#######.######.###################### ###################.....#######.####.#####.#######.######.###################### ###################.....#######.####.#####.#######.######.###################### ###############################.####.#####.#######.####.....#################### ###############################.####.#####.####......##.....#################### ###############################.####.#####..................#################### ###############################.####.#####.####......##.....#################### ###########......##############.####.#####.####.............#################### ###########......##############.####.##......##......####.###################### ###########..........................##......##......####.###################### ###########......##############.#######......##......####.###################### ###############################.#######......############.###################### ###############################.#######......############.###################### ###############################.#######......############.###################### ###############################.#######......############.###################### ###############################.#######......########........################### ############################.......##################........################### ############################.......##################........################### ############################.......##################........################### ############################.......##################........################### ############################.......##################........################### ############################.......##################........################### ################################################################################ ################################################################################ Most controlled output: distinct rooms with corridor connections. Fastest algorithm at 0.29ms. But the most compact (only 18.9% open space) with the most rigid feel. What I Learned Connectivity is not free. Three of four algorithms guarantee it, but cellular automata (arguably the best-looking one) doesn't. If you use it, you need a second pass. Speed varies 1000x. Room placement generates a map in 0.29ms. Random walk takes 274ms. That's the difference between generating 3,400 maps per second and 3.6. Path length measures exploration depth. BSP trees create the deepest maps (105 steps to traverse). This means more exploration, more backtracking, longer gameplay per floor. Random walk creates the shallowest (73 steps) because the walker tends to revisit areas. There's no best algorithm. It depends on what you want: Structured dungeon with rooms? BSP or room placement. Natural caves? Cellular automata (+ connectivity fix). Amorphous exploration? Random walk. Need speed? Room placement. Need depth? BSP trees. Code Everything runs in pure Python with no dependencies beyond numpy: gen = BSPDungeon(width=80, height=40, seed=42) gen.generate(min_room=5, max_depth=4) print(gen.to_string()) print(f"Connected: {gen.is_connected()}") print(f"Path length: {gen.longest_path()}") Full code, paper (LaTeX/PDF), and raw data: github.com/turingrtss/vulndetect Next: using these generators as environments for RL agents. Can an agent learn to navigate procedurally generated dungeons?