Procedural Dungeons: BSP Trees, Cellular Caves & Seeded Chaos

Why "random" levels need a seed

Every procedural dungeon starts from a number. That number, the seed, feeds a pseudo-random number generator — a fast, deterministic algorithm like mulberry32 or xorshift32 that produces a long sequence of numbers which look random but are entirely reproducible from the same starting state. Generators do not reach for the operating system's true entropy source, because true randomness would defeat the point: type the same seed in twice and you should get the exact same dungeon back, corridor for corridor, room for room.

That reproducibility is what makes seed-sharing between players possible, what lets a daily challenge give everyone the same layout, and what lets a developer reproduce a bug report by simply asking for the seed that triggered it. Every decision downstream — how a region gets split, where a room lands, which neighbour count flips a cell to floor — is really just the next few numbers pulled from that one deterministic stream.

Binary space partitioning: rooms from a tree

Binary space partitioning, or BSP, starts with one large rectangle representing the whole map and recursively slices it in two with a random axis-aligned line — sometimes vertical, sometimes horizontal, at a randomised position. Each half is split again, and again, until a region is too small to subdivide further or a fixed recursion depth is reached. The result is a binary tree of nested rectangles, and every leaf of that tree becomes a room: typically an irregular rectangle carved somewhat smaller than its leaf region, so rooms do not touch their partition boundaries exactly.

Connectivity falls out of the same tree structure for free. Walking back up from any two sibling leaves to their shared parent node gives a pair of rooms that must be joined, so a corridor is carved from the centre of one room toward the centre of the other — usually a simple L-shape, one straight run horizontally and one vertically. Because every leaf is reachable from the root by construction, a BSP dungeon is guaranteed fully connected and never has overlapping rooms, without ever needing to check for either.

Random rooms and a spanning tree

A looser approach scatters a fixed number of rectangular rooms directly onto the map at random sizes and positions, rejecting and retrying any room that overlaps one already placed. Once enough rooms exist, they still need corridors, so the generator treats each room's centre as a graph node and builds a connective structure over them — a Delaunay triangulation of the centres, or simply a minimum spanning tree over every pairwise distance — then carves an L-shaped corridor along each surviving edge.

A pure spanning tree connects everything with the fewest possible corridors, which also means the dungeon is a single tree with no loops — every path is a dead end or a through-route with no alternative. Generators commonly add a handful of extra edges back in from the triangulation that the spanning tree discarded, creating occasional loops so players are not funnelled down one linear corridor for the entire level.

Cellular automata: caves that grow like life

Cellular automata caves begin from pure noise: every cell in a grid is independently marked floor with some initial probability, commonly around 45%, and wall otherwise. A smoothing rule is then applied to the whole grid simultaneously, once per generation, for several generations in a row — structurally the same idea as Conway's Game of Life, but tuned with a threshold that makes the grid converge toward smooth blobs instead of oscillating forever.

for generation in 1..N:
  for each cell (x, y) in grid:
    count = number of FLOOR cells among the 8 neighbours of (x, y)
    if count > 4:
      newGrid[x][y] = FLOOR
    else if count < 4:
      newGrid[x][y] = WALL
    else:
      newGrid[x][y] = grid[x][y]   // unchanged on a tie
  grid = newGrid

After four or five generations the noise has settled into rounded, organic-looking caverns. The rule alone does not guarantee the result is one connected space, though — it commonly leaves a few small disconnected pockets — so a flood fill is run afterward to find every connected region, keep only the largest, and fill the rest back in as wall.

Choosing a method: control vs. chaos

None of the three methods is strictly better — they trade control for naturalness in different amounts. BSP guarantees connectivity and produces rectangular, architecturally sensible rooms, which suits dungeons, buildings and space stations where straight walls make sense. Cellular automata gives up that architectural control entirely in exchange for organic, cave-like shapes that no human would design by hand, at the cost of needing a connectivity pass afterward. Random rooms with a spanning tree sit in between: irregular room shapes and positions, like a cave, but with the explicit connectivity guarantee of a graph, like a BSP tree — a reasonable default when neither pure geometry nor pure noise is exactly what a level needs.

Frequently asked questions

Try it live

Everything above runs in your browser — open Procedural Dungeon Generator and regenerate the layout with a new seed to see how each algorithm reshapes the map. Nothing is installed, nothing is uploaded, the whole model lives in one tab.