Game Dev Mechanics: Procedural Dungeon Generation — How It Works

Every time you start a new run in a roguelike, the dungeon layout is different. Rooms appear in unexpected places, corridors twist through the dark, and the map never repeats. This is procedural dungeon generation. Rather than hand-crafting thousands of unique levels, developers write algorithms that build them on the fly, producing near-infinite variety from a finite set of rules.

This article breaks down the most widely used approach, Binary Space Partitioning (BSP), walking through every step from initial space subdivision to the final connected dungeon. We'll also cover alternative methods and look at how real games apply these techniques.

Why Procedural Dungeons Matter

Hand-designed levels are expensive to produce and finite in number. Once a player has memorized a dungeon layout, the tension evaporates. Procedural generation solves this by producing novel content each time the game runs. The benefits go beyond variety:

• Replayability: no two runs are the same, which underpins the roguelike genre.
• Scalability: a small team can ship a game with effectively unlimited levels.
• Emergent gameplay: when rooms and corridors are random, player strategies must adapt. Players encounter situations that no designer explicitly scripted.
• Rapid prototyping: dungeon generators let designers test mechanics against a wide range of layouts without building each one by hand.

The challenge is that purely random dungeons tend to be boring or unplayable. Good algorithms impose structure, guaranteeing every room is reachable and the layout feels like a real place rather than noise.

Binary Space Partitioning: The Classic Approach

The BSP method has been the workhorse of dungeon generation since the original Rogue (1980). The idea is straightforward: take a rectangular space, recursively divide it into smaller rectangles, place a room inside each leaf rectangle, then connect sibling rooms with corridors.

BSP produces dungeons that feel natural because the partitioning guarantees non-overlapping rooms with good spatial distribution. The tree structure also gives us a natural hierarchy for connecting rooms: every pair of sibling nodes gets a corridor, ensuring full connectivity without extra pathfinding passes.

The algorithm has three phases:

Step 1: Recursive Partitioning

Start with the full dungeon area as the root node of a binary tree. At each step, pick a leaf node and split it into two children, either horizontally or vertically. The split position is chosen randomly within a constrained range to prevent extremely thin partitions.

For a partition of width $w$ and height $h$, we choose the split direction based on the aspect ratio. If $\frac{w}{h} > 1.25$, we split vertically; if $\frac{h}{w} > 1.25$, we split horizontally; otherwise, we choose randomly. This heuristic prevents long, narrow partitions that would produce awkward rooms.

The split position $s$ is constrained so that both children are at least $S_{min}$ cells wide (or tall):

$$S_{min} \leq s \leq D - S_{min}$$

where $D$ is the dimension being split and $S_{min}$ is typically 5–7 cells. After $n$ iterations, the tree has approximately $2^n$ leaf nodes, each representing a potential room location.

function splitNode(node) {
    // Choose split direction based on aspect ratio
    let splitH = Math.random() > 0.5;
    if (node.w > node.h * 1.25) splitH = false;  // force vertical
    else if (node.h > node.w * 1.25) splitH = true;   // force horizontal

    const dimension = splitH ? node.h : node.w;
    const maxSplit = dimension - MIN_SIZE;

    if (maxSplit <= MIN_SIZE) return false;  // too small to split

    const pos = randomInt(MIN_SIZE, maxSplit);

    if (splitH) {
        node.left  = new BSPNode(node.x, node.y, node.w, pos);
        node.right = new BSPNode(node.x, node.y + pos, node.w, node.h - pos);
    } else {
        node.left  = new BSPNode(node.x, node.y, pos, node.h);
        node.right = new BSPNode(node.x + pos, node.y, node.w - pos, node.h);
    }
    return true;
}

Step 2: Room Placement

Once the tree is fully subdivided, we visit each leaf node and carve a room inside its bounds. The room is randomly sized but always smaller than the partition, leaving a buffer of at least one cell on each side. This buffer is what creates the walls and negative space between rooms.

For a leaf partition with bounds $(x, y, w, h)$, the room dimensions are:

$$w_r = \text{randInt}(3,\; w - 2), \quad h_r = \text{randInt}(3,\; h - 2)$$

The room position is offset randomly within the remaining space:

$$x_r = x + \text{randInt}(1,\; w - w_r - 1), \quad y_r = y + \text{randInt}(1,\; h - h_r - 1)$$

Even with the same BSP tree structure, rooms can vary significantly in size and position.

function createRoom(leaf) {
    const rw = randomInt(3, leaf.w - 2);
    const rh = randomInt(3, leaf.h - 2);
    const rx = leaf.x + randomInt(1, leaf.w - rw - 1);
    const ry = leaf.y + randomInt(1, leaf.h - rh - 1);
    return { x: rx, y: ry, w: rw, h: rh };
}

Step 3: Corridor Connection

The tree structure makes connectivity straightforward. For each internal node, we find a room in its left subtree and a room in its right subtree, then connect their centers with an L-shaped corridor. Since we do this recursively from the leaves up to the root, every room ends up connected to the rest of the dungeon.

Given room centers $(x_1, y_1)$ and $(x_2, y_2)$, the L-shaped corridor consists of two segments. We randomly choose one of two configurations:

$$\text{Config A: } (x_1, y_1) \rightarrow (x_2, y_1) \rightarrow (x_2, y_2)$$

$$\text{Config B: } (x_1, y_1) \rightarrow (x_1, y_2) \rightarrow (x_2, y_2)$$

The total corridor length equals the Manhattan distance between the centers: $d = |x_1 - x_2| + |y_1 - y_2|$. L-shaped corridors feel more natural than straight diagonal paths and are trivial to carve on a grid.

function connectRooms(nodeA, nodeB) {
    const roomA = getRoom(nodeA);
    const roomB = getRoom(nodeB);

    const cx1 = Math.floor(roomA.x + roomA.w / 2);
    const cy1 = Math.floor(roomA.y + roomA.h / 2);
    const cx2 = Math.floor(roomB.x + roomB.w / 2);
    const cy2 = Math.floor(roomB.y + roomB.h / 2);

    if (Math.random() > 0.5) {
        carveHorizontal(cy1, cx1, cx2);
        carveVertical(cx2, cy1, cy2);
    } else {
        carveVertical(cx1, cy1, cy2);
        carveHorizontal(cy2, cx1, cx2);
    }
}

The Full Algorithm

Putting it all together, the complete dungeon generation pipeline looks like this:

function generateDungeon(width, height, iterations) {
    // 1. Create root node spanning the full map
    const root = new BSPNode(0, 0, width, height);

    // 2. Recursively split leaf nodes
    for (let i = 0; i < iterations; i++) {
        const leaves = getLeafNodes(root);
        for (const leaf of leaves) {
            splitNode(leaf);
        }
    }

    // 3. Place rooms in each leaf
    const finalLeaves = getLeafNodes(root);
    for (const leaf of finalLeaves) {
        leaf.room = createRoom(leaf);
    }

    // 4. Connect sibling rooms with corridors
    connectTree(root);

    // 5. Convert to a 2D grid
    return buildGrid(root, width, height);
}

The number of iterations controls dungeon complexity. With 3 iterations you get roughly 8 rooms; with 5 iterations, roughly 32. Most roguelikes use 4–6 iterations for a single floor, yielding 10–30 rooms per level depending on the map size and minimum partition constraints.

Alternative Approaches

BSP is the most popular technique, but it's far from the only one. Each method produces a different feel.

Random Room Placement

The simplest approach: randomly place non-overlapping rectangles on the grid, then connect them with corridors using a minimum spanning tree or nearest-neighbor heuristic. This produces more organic-looking layouts than BSP but requires an explicit connectivity check to ensure all rooms are reachable. Games like TinyKeep use physics-based room separation after random placement, pushing overlapping rooms apart like rigid bodies.

Cellular Automata Caves

Start with a grid of random wall/floor tiles (typically 45–55% walls). Then apply a smoothing rule for several iterations: a cell becomes a wall if it has 5 or more wall neighbors (out of 8), and becomes floor otherwise. After 4–6 iterations, the noise resolves into organic cave systems with smooth, natural-looking walls. This is how Dwarf Fortress generates its cavern layers, and variations appear in Spelunky and Nuclear Throne.

function smoothStep(grid) {
    const next = grid.map(row => [...row]);
    for (let y = 1; y < H - 1; y++) {
        for (let x = 1; x < W - 1; x++) {
            let walls = 0;
            for (let dy = -1; dy <= 1; dy++)
                for (let dx = -1; dx <= 1; dx++)
                    if (grid[y + dy][x + dx] === 1) walls++;
            next[y][x] = walls >= 5 ? 1 : 0;
        }
    }
    return next;
}

Drunkard's Walk

Also called a random walk: start from a point and repeatedly move in a random direction, carving floor tiles as you go. Stop when a target percentage of the map is floor (typically 30–50%). This produces winding, cave-like layouts. The technique combines well with other methods. For example, drunkard's walks can carve connecting tunnels between BSP rooms for a more organic feel.

Graph-Based Generation

Some games define the dungeon as an abstract graph first: how many rooms exist, which connect to which, and what constraints must hold (e.g., the boss room must be at least 5 edges from the entrance). The generator then maps this graph to a physical layout. The Binding of Isaac uses a variant of this approach, constructing a room graph and placing it onto a grid.

Games That Use Procedural Dungeons

• Rogue (1980): the original. Used a 3×3 grid with rooms connected by corridors, a direct ancestor of BSP-based generation.
• Diablo (1996): procedurally generated dungeon floors with hand-authored set pieces mixed in for narrative moments.
• Spelunky (2008/2012): combines a guaranteed solvable path through a 4×4 room grid with random tile-level details inside each room.
• The Binding of Isaac (2011): graph-based room layout with hand-designed individual rooms chosen from a pool.
• Dead Cells (2018): uses a constraint-based system where hand-crafted room segments are stitched together procedurally.
• Hades (2020): procedurally sequences hand-designed encounter rooms, blending authored content with procedural structure.
• Enter the Gungeon (2016): room-based generation with themed floor layouts and carefully tuned room pools.

Design Tips for Better Dungeons

• Guarantee connectivity. Always verify that every room is reachable. A flood-fill from the starting room should touch every floor tile. If it doesn't, add corridors until it does.
• Control pacing with distance. Place the exit, boss room, or key items based on graph distance from the entrance rather than Euclidean distance. This forces players to traverse more of the dungeon before reaching the goal.
• Mix procedural and authored content. Use the generator for layout and connectivity, but fill rooms from a hand-designed pool. This gives you the variety of procedural generation with the quality of authored encounters.
• Use seeds for reproducibility. Seeded random number generators let players share dungeons and make debugging vastly easier.
• Validate and reject. Not every generated dungeon is good. Build validation checks (minimum room count, path length constraints, dead-end limits) and regenerate if a layout fails them. Fast generation makes rejection sampling practical.
• Layer multiple techniques. The best results often come from combining approaches: BSP for room structure, cellular automata for natural cave sections, hand-placed set pieces for narrative beats.

Getting BSP working takes an afternoon. Getting it to consistently produce good dungeons takes more iteration, but that's where the interesting design work is. Start there, then add complexity as your game needs it.