Lesson 9

Rooms, corridors and caves

Four ways to generate a dungeon and what each guarantees: BSP splits the map into rooms, TinyKeep-style rooms are joined by a Delaunay graph and a spanning tree, cellular automata grow caves, and Spelunky lays hand-made rooms along a random path.

A level generator has two jobs: make a layout that is interesting to move through, and make sure the player can actually get from the start to the end. Each technique here handles the second in its own way, or leaves it to you, and that guarantee, more than the look, is what decides which one to use. All of them work on a grid of cells (rock, room floor, corridor) on the lab’s medium map, 64 × 40 cells, seed 1.

BSP: split, place, connect

Binary space partitioning splits the map in two, splits each half again, and stops when a leaf would be smaller than a minimum size. Each leaf gets one room, at a random size and position inside it. Then, walking back up the tree, each split joins its two sides with a corridor: the two closest rooms across it, by an L-shaped path.

void split(Node& n, int min_leaf, Rng& rng) {
    bool can_v = n.w >= 2 * min_leaf, can_h = n.h >= 2 * min_leaf;
    if (!can_v && !can_h) return;                                   // a leaf: it gets a room
    bool vertical = can_v && (!can_h || n.w >= 1.25f * n.h || (n.h < 1.25f * n.w && rng.next() < 0.5f));
    int  size = vertical ? n.w : n.h;
    int  cut  = min_leaf + int(rng.next() * (size - 2 * min_leaf + 1));
    n.kids = vertical ? split_x(n, cut) : split_y(n, cut);           // long leaves are cut across their length
    split(n.kids[0], min_leaf, rng);
    split(n.kids[1], min_leaf, rng);
}

Leaves never overlap, so rooms can’t; every split is joined, so everything connects. A binary tree with n leaves has n − 1 splits, so there is one fewer corridor than rooms.

Loading…

With the smallest leaf at 8 cells, seed 1 ends with 22 rooms and 21 corridors, 43% of the map as floor, all in one region. At 13 cells there are 8 rooms; at 6, 44. Press ▶ to watch the splits, then the rooms, then the corridors from the deepest splits up.

BSP’s tidiness is also its weakness: rooms fill the map in a grid-like way, and corridors only join neighbours in the tree, so the layout is a tree with few loops unless you add some.

Rooms first, then a graph

The generator Phi Dinh described for TinyKeep in 2013 turns this around: make rooms anywhere, then decide how to join them with a graph.

Spawn many rectangles of random size in a small area (Dinh used 150), sizes skewed small.
Separate them until none overlap. TinyKeep used separation steering, the flocking behaviour; the lab uses a simpler deterministic shove.
Pick rooms: Dinh keeps every cell “above a certain threshold”; a327ex’s 2015 write-up of the method uses 1.25 times the mean width and height, and so does the lab. The rest are spares.
Triangulate the room centres (Delaunay, here Bowyer-Watson): each room is linked to its natural neighbours, and no two edges cross.
Take the minimum spanning tree of that graph: every room reachable, least total length, no loops.
Add back some loops: Dinh used 15% of the left-over edges; a327ex found 8–10% better.
Turn every kept edge into an L-shaped hallway. Any spare cell a hallway passes through is dug out with it, which gives the corridors their uneven, roomy walls.

The spanning tree is a few lines of Kruskal’s algorithm with a union-find:

std::sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.len2 < b.len2; });
for (const Edge& e : edges) {
    int ra = find(e.a), rb = find(e.b);          // which group of rooms is each end in?
    if (ra != rb) { parent[ra] = rb; tree.push_back(e); }
    else          spare.push_back(e);            // already connected: this edge would make a loop
}

Loading…

On seed 1, of the 60 cells spawned, 8 are pushed off the map, 8 become rooms, the triangulation has 15 edges, and the tree keeps 7 of them, always one fewer than the rooms. At 15%, 1 more comes back as a loop; at 50%, 4. Loops matter more than they look: a tree has exactly one route between any two rooms, so every dead end means walking all the way back.

Caves from a cellular automaton

For natural caves, fill the map with random walls and smooth it with a rule applied to every cell at once. The classic 4-5 rule from RogueBasin’s cave article: a wall stays a wall if 4 or more of its 8 neighbours are walls, and a floor becomes a wall if 5 or more are.

for (int y = 1; y < H - 1; ++y)
    for (int x = 1; x < W - 1; ++x) {
        int walls = count_walls_around(cur, x, y);                    // of the 8 neighbours
        next[y][x] = cur[y][x] == WALL ? (walls >= 4 ? WALL : FLOOR)
                                       : (walls >= 5 ? WALL : FLOOR);
    }
std::swap(cur, next);                                                  // every cell updates at once

Loading…

A few passes turn static into caves. The starting fill decides almost everything: on seed 1 with 5 passes, 40% wall gives one big open cave; 45% gives 3 separate caves, the largest holding 87% of the floor; 50% gives 8. The rule knows nothing about connectivity, so the generator has to repair it afterwards: flood-fill to find the caves, then fill all but the largest (at 45% that leaves 51% of the map as floor), or dig tunnels between them.

The simplest generator that does guarantee connectivity is the drunkard’s walk: one walker starts in the middle and digs every cell it steps on until enough of the map is floor. Everything is connected because it walked there, but it keeps re-crossing old ground: on seed 1 it takes 3,765 moves to dig 942 cells.

Watch the drunkard's walk in the procgen lab →

Caves are cheap at any size and look natural, but there is no notion of rooms, entrances or a critical path. Games generate, then check and repair, or regenerate.

Hand-made pieces on a generated path

Pure algorithms tend to make levels that all look alike. Many shipped games mix generation with authored content, and the original Spelunky (Derek Yu, 2008) is the classic example, laid out in Darius Kazemi’s “Spelunky Generator Lessons”:

The level is a 4 × 4 grid of rooms. A start room goes in the top row.
The path rolls a number from 1 to 5: 1 or 2 moves left, 3 or 4 moves right, 5 goes down. If it hits the edge of the level it drops a row and switches direction. Trying to drop out of the bottom row places the exit.
Every room on the path is typed by the exits it needs: 1 left and right, 2 also a bottom exit (the path drops out of it), 3 also a top exit (it lands there). A room dropped into and out of is a 2 with a top exit too. Rooms off the path are 0, with no guaranteed exits.
Each room is then filled with a hand-made template of its type, 10 × 8 tiles, picked at random from the typically 8 to 16 made for that type. Some template tiles are probabilistic (a “2” is solid or empty with even odds), and some mark where a 5 × 3 “obstacle block”, with a template of its own, goes.

The path guarantees the level can be finished; the templates make each room feel designed.

Loading…

This widget’s generator follows those rules, with three small templates per type written for the lesson. Kazemi doesn’t say whether the path can turn back along a row; the game’s released source never steps into a room already on the path, so along a row it keeps the direction it started with, and so does this generator. Over seeds 1 to 10,000 the path takes 9.6 of the 16 rooms on average (from 4 to 16), and in every one the start connects to the exit through open tiles.

Takeaways

Choose a dungeon generator by its guarantee first: BSP and spanning trees connect by construction, a drunkard’s walk by digging, cellular automata not at all.
BSP: split, a room per leaf, a corridor per split. Even and tidy, no loops unless you add them.
Rooms + Delaunay + MST: rooms anywhere, joined by a minimum spanning tree of their triangulation, plus a few edges back for loops.
Cellular automata make natural caves from a random fill and the 4-5 rule; flood-fill and repair afterwards.
Templates on a path (Spelunky): generate the route, fill the rooms with authored pieces.

In the lab

The lab’s dungeon mode has all four algorithms on three map sizes, with every setting live and each run recorded so you can step it either way.

Build a TinyKeep-style dungeon in the procgen lab →

Rooms, corridors and caves

BSP: split, place, connect

Rooms first, then a graph

Caves from a cellular automaton

Hand-made pieces on a generated path

Takeaways

In the lab

Further reading