Intermediate

Procedural Dungeon Generation

Generate playable dungeon layouts using algorithms that create interconnected rooms, corridors, and interesting spatial challenges.

Approaches to Dungeon Generation

AlgorithmStyleBest For
BSP (Binary Space Partitioning)Rectangular rooms in a gridTraditional roguelikes, structured layouts
Cellular AutomataOrganic, cave-like spacesNatural caves, caverns, organic environments
Random Room PlacementScattered rooms connected by corridorsFlexible layouts, varied room sizes
Graph-BasedRooms as nodes, corridors as edgesPuzzle-driven games, lock-and-key progression
Prefab AssemblyHand-crafted pieces connected algorithmicallyHigh-quality feel with variety (Spelunky approach)

BSP Dungeon Generation

Python - BSP Dungeon Generator 
import random

class BSPNode:
    def __init__(self, x, y, w, h):
        self.x, self.y, self.w, self.h = x, y, w, h
        self.left = self.right = None
        self.room = None

    def split(self, min_size=8):
        if self.left or self.right:
            return False

        # Choose split direction
        split_h = random.random() > 0.5
        if self.w > self.h * 1.25:
            split_h = False
        elif self.h > self.w * 1.25:
            split_h = True

        max_size = (self.h if split_h else self.w) - min_size
        if max_size <= min_size:
            return False

        split = random.randint(min_size, max_size)

        if split_h:
            self.left = BSPNode(self.x, self.y, self.w, split)
            self.right = BSPNode(self.x, self.y+split, self.w, self.h-split)
        else:
            self.left = BSPNode(self.x, self.y, split, self.h)
            self.right = BSPNode(self.x+split, self.y, self.w-split, self.h)

        return True

    def create_rooms(self):
        if self.left or self.right:
            if self.left: self.left.create_rooms()
            if self.right: self.right.create_rooms()
        else:
            # Create room within leaf node
            rw = random.randint(3, self.w - 2)
            rh = random.randint(3, self.h - 2)
            rx = self.x + random.randint(1, self.w - rw - 1)
            ry = self.y + random.randint(1, self.h - rh - 1)
            self.room = (rx, ry, rw, rh)

Cellular Automata Caves

Cellular automata create organic, cave-like spaces using simple rules applied iteratively:

  1. Initialize

    Fill the grid randomly (e.g., 45% wall, 55% floor).

  2. Iterate

    For each cell, count neighboring walls. If neighbors ≥ 5, become wall; otherwise become floor.

  3. Repeat

    Run 4-5 iterations. The random noise self-organizes into smooth cave systems.

  4. Validate

    Flood-fill to find disconnected caves and connect them with tunnels.

Graph-Based Generation

For games with lock-and-key progression (Zelda, Metroidvania), generate the graph structure first and then lay out rooms spatially:

  • Define a progression graph: Start → Key A → Lock A → Key B → Lock B → Boss → Exit.
  • Add branches and optional paths for exploration.
  • Map the abstract graph to physical room placement.
  • Connect rooms with corridors that respect the graph's connectivity.
✅
Key takeaway: Choose your dungeon generation algorithm based on the game's needs. BSP creates structured layouts, cellular automata create organic caves, and graph-based approaches ensure proper progression and pacing. The Spelunky approach of assembling hand-crafted prefabs combines the best of procedural and manual design.