Lesson 9: Dungeons & Caves (BSP, Cellular Automata)

🎲 Seeds, Grids and a First Attempt

Roguelikes such as Spelunky, The Binding of Isaac and Dead Cells build a new layout for every run from rules plus a random seed. You already have the two tools this needs from Game Dev II: a seeded random.Random instance from Randomness for Games, and breadth-first search from A* Pathfinding.

Every generator in this lesson works on the same simple world: a grid, stored as a list of rows, where each cell is WALL or FLOOR. A grid is easy to print, easy to test and easy to turn into tiles later.

Two rules from Randomness for Games matter even more here:

• Each generator owns its RNG. rng = random.Random(seed) gives this map its own stream of numbers. Calling random.seed() inside a generator would reset the global stream that your loot, AI and particles also use.
• Seed 0 is a real seed. Test for "no seed given" with if seed is not None:, never if seed:. random.Random(None) seeds from the operating system, so passing the seed straight through does the right thing.

The obvious first attempt scatters rooms at random and throws away any that overlap. Run it:

import random

WALL, FLOOR = "#", "."


def scatter_rooms(cols, rows, seed=None, tries=30):
    rng = random.Random(seed)              # this generator's own RNG
    grid = [[WALL] * cols for _ in range(rows)]
    rooms = []
    for _ in range(tries):
        w, h = rng.randint(4, 10), rng.randint(3, 7)
        x, y = rng.randint(1, cols - w - 1), rng.randint(1, rows - h - 1)
        if any(x < rx + rw + 1 and rx < x + w + 1 and y < ry + rh + 1 and ry < y + h + 1
               for rx, ry, rw, rh in rooms):
            continue                       # overlaps (or touches) a room: try again
        rooms.append((x, y, w, h))
        for yy in range(y, y + h):
            for xx in range(x, x + w):
                grid[yy][xx] = FLOOR
    return grid, rooms


grid, rooms = scatter_rooms(60, 20, seed=0)
print("\n".join("".join(row) for row in grid))
print(f"{len(rooms)} rooms from 30 tries, and nothing connects them yet")

It works, and plenty of games ship with a version of it. But look at the result: rooms bunch up in some areas and leave big empty ones elsewhere, many tries are wasted on overlaps, and nothing connects the rooms. Joining "each room to the previous one" adds corridors that cross other rooms at random. We want an algorithm that spreads rooms evenly and hands us a connection plan for free.

🌳 Binary Space Partitioning

Think of cutting a sheet cake for a party. You cut it in half, then cut each half in half, and keep going until the pieces are the size you want. Every piece is a sensible size, no two pieces overlap, and you can always say which two pieces came from the same cut. That is binary space partitioning: a binary tree in which each node is a rectangle and each split makes two children.

Each node remembers its rectangle and, once it is split, its two children. A dataclass (from Intermediate Python) keeps that tidy:

@dataclass
class BSPNode:
    x: int
    y: int
    w: int
    h: int
    left: Optional["BSPNode"] = None
    right: Optional["BSPNode"] = None
    room: Optional[Room] = None

The split function is recursive. It stops when a node is too small to cut into two pieces of at least min_leaf tiles, and it prefers to cut across the long side, so partitions do not become long thin strips:

def split_node(node, rng, min_leaf=MIN_LEAF):
    """Cut node in two, then cut each half, until the pieces get too small."""
    can_cut_h = node.h >= 2 * min_leaf          # a horizontal cut makes top/bottom halves
    can_cut_v = node.w >= 2 * min_leaf          # a vertical cut makes left/right halves
    if not (can_cut_h or can_cut_v):
        return                                  # a leaf: it will hold one room
    if can_cut_h and can_cut_v:
        if node.w > node.h * 1.25:              # wide: cut vertically
            horizontal = False
        elif node.h > node.w * 1.25:            # tall: cut horizontally
            horizontal = True
        else:
            horizontal = rng.random() < 0.5
    else:
        horizontal = can_cut_h
    if horizontal:
        cut = rng.randint(min_leaf, node.h - min_leaf)
        node.left = BSPNode(node.x, node.y, node.w, cut)
        node.right = BSPNode(node.x, node.y + cut, node.w, node.h - cut)
    else:
        cut = rng.randint(min_leaf, node.w - min_leaf)
        node.left = BSPNode(node.x, node.y, cut, node.h)
        node.right = BSPNode(node.x + cut, node.y, node.w - cut, node.h)
    split_node(node.left, rng, min_leaf)
    split_node(node.right, rng, min_leaf)

Two details make it safe. The cut position is drawn from randint(min_leaf, size - min_leaf), so both halves are at least min_leaf wide. And the stop test uses >= 2 * min_leaf, so a node that can't produce two legal halves is never cut. Each call makes the pieces strictly smaller, which is why the recursion always ends. The leaves (nodes with no children) exactly cover the map, with no gaps and no overlaps.

Press Step in BSP mode and watch each level of the tree appear. Predict first: how many steps until every partition is a leaf? It depends on the seed, because some branches reach the minimum size sooner than others.

🚪 Rooms and Corridors

With the tree built, the rest is two short passes.

Rooms. Each leaf gets one room of random size placed at a random spot inside it, with a one-tile margin, so two rooms in neighboring leaves never touch. The margin also keeps the outer border of the map solid wall.

Corridors. Walk the tree from the bottom up. At every split, pick a room from the left subtree and a room from the right subtree and carve an L-shaped corridor between their centers. Here is why that is enough. Each leaf's room is connected to itself. If both halves of a split are internally connected, one corridor between them connects the whole node. By induction, the root, which is the whole map, is connected. A tree with n leaves has n − 1 splits, so you get exactly n − 1 corridors, the fewest that can join n rooms.

Here is the complete generator. It prints the dungeon as text, so you can run it without a window:

import random
from dataclasses import dataclass
from typing import Optional

WALL, FLOOR = 1, 0
MIN_LEAF = 10          # smallest partition, in tiles
MIN_ROOM = 4           # smallest room side, in tiles


@dataclass
class Room:
    x: int
    y: int
    w: int
    h: int

    @property
    def center(self):
        return (self.x + self.w // 2, self.y + self.h // 2)


@dataclass
class BSPNode:
    x: int
    y: int
    w: int
    h: int
    left: Optional["BSPNode"] = None
    right: Optional["BSPNode"] = None
    room: Optional[Room] = None


def split_node(node, rng, min_leaf=MIN_LEAF):
    """Cut node in two, then cut each half, until the pieces get too small."""
    can_cut_h = node.h >= 2 * min_leaf          # a horizontal cut makes top/bottom halves
    can_cut_v = node.w >= 2 * min_leaf          # a vertical cut makes left/right halves
    if not (can_cut_h or can_cut_v):
        return                                  # a leaf: it will hold one room
    if can_cut_h and can_cut_v:
        if node.w > node.h * 1.25:              # wide: cut vertically
            horizontal = False
        elif node.h > node.w * 1.25:            # tall: cut horizontally
            horizontal = True
        else:
            horizontal = rng.random() < 0.5
    else:
        horizontal = can_cut_h
    if horizontal:
        cut = rng.randint(min_leaf, node.h - min_leaf)
        node.left = BSPNode(node.x, node.y, node.w, cut)
        node.right = BSPNode(node.x, node.y + cut, node.w, node.h - cut)
    else:
        cut = rng.randint(min_leaf, node.w - min_leaf)
        node.left = BSPNode(node.x, node.y, cut, node.h)
        node.right = BSPNode(node.x + cut, node.y, node.w - cut, node.h)
    split_node(node.left, rng, min_leaf)
    split_node(node.right, rng, min_leaf)


def leaves(node):
    if node.left is None:
        return [node]
    return leaves(node.left) + leaves(node.right)


def carve_room(grid, room):
    for y in range(room.y, room.y + room.h):
        for x in range(room.x, room.x + room.w):
            grid[y][x] = FLOOR


def carve_corridor(grid, a, b, rng):
    """L-shaped corridor from point a to point b (either bend, chosen at random)."""
    (x1, y1), (x2, y2) = a, b
    corner = (x2, y1) if rng.random() < 0.5 else (x1, y2)
    for (sx, sy), (ex, ey) in ((a, corner), (corner, b)):
        for x in range(min(sx, ex), max(sx, ex) + 1):
            for y in range(min(sy, ey), max(sy, ey) + 1):
                grid[y][x] = FLOOR


def connect(node, grid, rng):
    """Join the two halves of every split with one corridor. Returns the subtree's rooms."""
    if node.left is None:
        return [node.room]
    left_rooms = connect(node.left, grid, rng)
    right_rooms = connect(node.right, grid, rng)
    carve_corridor(grid, rng.choice(left_rooms).center, rng.choice(right_rooms).center, rng)
    return left_rooms + right_rooms


def make_bsp_dungeon(cols, rows, seed):
    rng = random.Random(seed)                   # a local RNG: same seed, same dungeon
    grid = [[WALL] * cols for _ in range(rows)]
    root = BSPNode(0, 0, cols, rows)
    split_node(root, rng)
    rooms = []
    for leaf in leaves(root):
        w = rng.randint(MIN_ROOM, leaf.w - 2)   # keep a 1-tile wall inside the leaf
        h = rng.randint(MIN_ROOM, leaf.h - 2)
        x = rng.randint(leaf.x + 1, leaf.x + leaf.w - w - 1)
        y = rng.randint(leaf.y + 1, leaf.y + leaf.h - h - 1)
        leaf.room = Room(x, y, w, h)
        carve_room(grid, leaf.room)
        rooms.append(leaf.room)
    connect(root, grid, rng)
    return grid, rooms


grid, rooms = make_bsp_dungeon(60, 30, seed=4)
print("\n".join("".join("#" if t == WALL else "." for t in row) for row in grid))
print(f"{len(rooms)} rooms, all connected")

Change seed=4 to other numbers and run it again. The layout changes completely, but a given seed always gives the same dungeon. Corridors sometimes run through a third room; that is harmless, and it often makes the layout feel less like a tree.

🕳️ Caves with Cellular Automata

Rooms and corridors look built. Caves should look grown. A cellular automaton is a grid where every cell updates by the same local rule, looking only at its neighbors. Conway's Game of Life is the famous one. For caves, the rule is about walls:

1. Fill the map with noise: each cell is a wall with probability 0.45.
2. For every cell, count the walls among its 8 neighbors. Cells outside the map count as walls, which thickens the edges.
3. More than 4 wall neighbors: the cell becomes wall. Fewer than 4: it becomes floor. Exactly 4: it stays as it is.
4. Repeat step 2–3 four or five times.

Lonely walls get eaten, crowded floor gets filled, and the noise clumps into smooth caverns. Switch the canvas demo above to Cave and step through the smoothing passes to watch it happen.

The one rule that trips everyone up: each step must read the old grid and write a new one. If you update cells in place, a cell near the top-left has already changed by the time its neighbors count it, so the result depends on the order you visit cells and the caves smear diagonally. The fix is a copy: new = [row[:] for row in grid].

import random
from collections import deque

WALL, FLOOR = 1, 0


def wall_neighbors(grid, x, y):
    """Walls among the 8 neighbors. Cells outside the map count as walls."""
    rows, cols = len(grid), len(grid[0])
    count = 0
    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            if dx == 0 and dy == 0:
                continue
            nx, ny = x + dx, y + dy
            if not (0 <= nx < cols and 0 <= ny < rows) or grid[ny][nx] == WALL:
                count += 1
    return count


def smooth(grid):
    """One cellular-automata step, written into a NEW grid (never in place)."""
    new = [row[:] for row in grid]
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            n = wall_neighbors(grid, x, y)
            if n > 4:
                new[y][x] = WALL
            elif n < 4:
                new[y][x] = FLOOR
    return new


def regions(grid, kind=FLOOR):
    """Flood-fill every connected area of `kind` tiles (4-way). Returns a list of tile lists."""
    rows, cols = len(grid), len(grid[0])
    seen = set()
    found = []
    for y in range(rows):
        for x in range(cols):
            if grid[y][x] != kind or (x, y) in seen:
                continue
            region = []
            queue = deque([(x, y)])
            seen.add((x, y))
            while queue:
                cx, cy = queue.popleft()
                region.append((cx, cy))
                for nx, ny in ((cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)):
                    if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == kind and (nx, ny) not in seen:
                        seen.add((nx, ny))
                        queue.append((nx, ny))
            found.append(region)
    return found


def keep_largest_region(grid):
    """Wall off every floor pocket except the biggest one."""
    found = regions(grid)
    if not found:
        return
    biggest = max(found, key=len)
    for region in found:
        if region is not biggest:
            for x, y in region:
                grid[y][x] = WALL


def make_cave(cols, rows, seed, fill=0.45, steps=5):
    rng = random.Random(seed)
    grid = [[WALL if rng.random() < fill else FLOOR for _ in range(cols)] for _ in range(rows)]
    for _ in range(steps):
        grid = smooth(grid)
    for x in range(cols):                       # a solid border keeps the player inside
        grid[0][x] = grid[rows - 1][x] = WALL
    for y in range(rows):
        grid[y][0] = grid[y][cols - 1] = WALL
    keep_largest_region(grid)
    return grid


cave = make_cave(60, 30, seed=2)
print("\n".join("".join("#" if t == WALL else "." for t in row) for row in cave))
print("floor regions:", len(regions(cave)))

Try changing fill: at 0.40 the caves open into big halls, at 0.50 they close into narrow tunnels. Try steps=1 and steps=10: after about five steps the map barely changes, because almost every cell already agrees with the majority of its neighbors, so the rule leaves it alone. (On an 80 × 50 test map, the first step changed about 1,500 cells and the fifth only about 60.)

🧹 Flood Fill: Is Every Map Playable?

The cave program above calls two helpers you haven't met yet. They exist because cellular automata make no promises: the cave you get is usually one big cavern plus a few sealed pockets. A pocket is harmless until you put the exit in one.

Flood fill is breadth-first search from A* Pathfinding with no goal: start at a floor tile, visit every floor tile reachable from it, and record them as one region. Repeat from any floor tile not yet visited, and you have every region in the map:

def regions(grid, kind=FLOOR):
    """Flood-fill every connected area of `kind` tiles (4-way). Returns a list of tile lists."""
    rows, cols = len(grid), len(grid[0])
    seen = set()
    found = []
    for y in range(rows):
        for x in range(cols):
            if grid[y][x] != kind or (x, y) in seen:
                continue
            region = []
            queue = deque([(x, y)])
            seen.add((x, y))
            while queue:
                cx, cy = queue.popleft()
                region.append((cx, cy))
                for nx, ny in ((cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)):
                    if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == kind and (nx, ny) not in seen:
                        seen.add((nx, ny))
                        queue.append((nx, ny))
            found.append(region)
    return found

With regions in hand, the cleanup is one line of intent: keep the largest region and fill every other one with wall (keep_largest_region in the program). Other options are to tunnel between regions, or to reject the seed and try the next one. All three are legitimate; keeping the largest is the simplest and never fails.

The same function doubles as a test. "Connected" means exactly one floor region, so you can check hundreds of seeds in a few seconds instead of trusting your eyes on three:

for seed in range(200):
    grid, rooms = make_bsp_dungeon(80, 50, seed)
    assert len(regions(grid)) == 1, f"BSP seed {seed} is not connected"
    assert len(regions(make_cave(80, 50, seed))) == 1, f"cave seed {seed} is not connected"
print("200 seeds, every map connected")

Notice that we use 4-way neighbors for regions but 8-way neighbors for the cave rule. The player in these maps moves in four directions, so two floor tiles that only touch at a corner must not count as connected.

🏁 Start, Exit and Drawing the Map

A good exit is far from the start, measured in steps along the corridors, not in a straight line. BFS gives you the step count to every tile, so the farthest tile is one max() away. Doing it twice gives a pair of tiles that are very far apart: BFS from any floor tile, take the farthest tile as the start, then BFS from the start and take the farthest tile as the exit.

def place_start_and_exit(grid):
    """Two BFS sweeps: the tile farthest from any floor tile, then the tile farthest from that."""
    first = next((x, y) for y, row in enumerate(grid) for x, t in enumerate(row) if t == FLOOR)
    d1 = distances_from(grid, first)
    start = max(d1, key=d1.get)
    d2 = distances_from(grid, start)
    exit_tile = max(d2, key=d2.get)
    return start, exit_tile, d2[exit_tile]

On a tree-shaped map this two-sweep trick finds the longest path exactly. Our maps have loops where corridors cross, so it finds a very long path rather than a guaranteed longest one, which is all a level needs.

Drawing. An 80 × 50 map is 4,000 tiles. Filling 4,000 rectangles every frame is wasted work, because the map only changes when you generate a new one. Draw the tiles once onto a Surface when the map is built, and blit that one Surface each frame:

def render_map(grid):
    """Draw the tiles ONCE onto a Surface; the game loop only blits it."""
    surf = pygame.Surface((len(grid[0]) * TILE, len(grid) * TILE))
    surf.fill(WALL_COLOR)
    for y, row in enumerate(grid):
        for x, tile in enumerate(row):
            if tile == FLOOR:
                surf.fill(FLOOR_COLOR, (x * TILE, y * TILE, TILE, TILE))
    return surf

That is the same "build once, draw many times" idea as caching fonts and converted images. In a real game you would blit tile images instead of flat colors, with the tile map drawing and camera code from Game Dev II.

🏋️ Practice Exercise: Dungeon & Cave Viewer

"""Dungeon & Cave Viewer: Advanced Lesson 9 practice exercise (solution).

B builds a BSP dungeon, C grows a cellular-automata cave, N moves to the
next seed. Every map is checked for connectivity, and the start (green)
and exit (gold) are placed as far apart as the corridors allow.
"""
import random
from collections import deque
from dataclasses import dataclass
from typing import Optional

import pygame


WALL, FLOOR = 1, 0
COLS, ROWS = 80, 50
TILE = 12
HUD_H = 28
MIN_LEAF = 10          # smallest BSP partition, in tiles
MIN_ROOM = 4           # smallest room side, in tiles
WALL_COLOR = (30, 32, 44)
FLOOR_COLOR = (150, 140, 120)
START_COLOR = (80, 220, 120)
EXIT_COLOR = (250, 200, 60)
TEXT_COLOR = (230, 230, 230)


@dataclass
class Room:
    x: int
    y: int
    w: int
    h: int

    @property
    def center(self):
        return (self.x + self.w // 2, self.y + self.h // 2)


@dataclass
class BSPNode:
    x: int
    y: int
    w: int
    h: int
    left: Optional["BSPNode"] = None
    right: Optional["BSPNode"] = None
    room: Optional[Room] = None


def split_node(node, rng, min_leaf=MIN_LEAF):
    """Cut node in two, then cut each half, until the pieces get too small."""
    can_cut_h = node.h >= 2 * min_leaf          # a horizontal cut makes top/bottom halves
    can_cut_v = node.w >= 2 * min_leaf          # a vertical cut makes left/right halves
    if not (can_cut_h or can_cut_v):
        return                                  # a leaf: it will hold one room
    if can_cut_h and can_cut_v:
        if node.w > node.h * 1.25:              # wide: cut vertically
            horizontal = False
        elif node.h > node.w * 1.25:            # tall: cut horizontally
            horizontal = True
        else:
            horizontal = rng.random() < 0.5
    else:
        horizontal = can_cut_h
    if horizontal:
        cut = rng.randint(min_leaf, node.h - min_leaf)
        node.left = BSPNode(node.x, node.y, node.w, cut)
        node.right = BSPNode(node.x, node.y + cut, node.w, node.h - cut)
    else:
        cut = rng.randint(min_leaf, node.w - min_leaf)
        node.left = BSPNode(node.x, node.y, cut, node.h)
        node.right = BSPNode(node.x + cut, node.y, node.w - cut, node.h)
    split_node(node.left, rng, min_leaf)
    split_node(node.right, rng, min_leaf)


def leaves(node):
    if node.left is None:
        return [node]
    return leaves(node.left) + leaves(node.right)


def carve_room(grid, room):
    for y in range(room.y, room.y + room.h):
        for x in range(room.x, room.x + room.w):
            grid[y][x] = FLOOR


def carve_corridor(grid, a, b, rng):
    """L-shaped corridor from point a to point b (either bend, chosen at random)."""
    (x1, y1), (x2, y2) = a, b
    corner = (x2, y1) if rng.random() < 0.5 else (x1, y2)
    for (sx, sy), (ex, ey) in ((a, corner), (corner, b)):
        for x in range(min(sx, ex), max(sx, ex) + 1):
            for y in range(min(sy, ey), max(sy, ey) + 1):
                grid[y][x] = FLOOR


def connect(node, grid, rng):
    """Join the two halves of every split with one corridor. Returns the subtree's rooms."""
    if node.left is None:
        return [node.room]
    left_rooms = connect(node.left, grid, rng)
    right_rooms = connect(node.right, grid, rng)
    carve_corridor(grid, rng.choice(left_rooms).center, rng.choice(right_rooms).center, rng)
    return left_rooms + right_rooms


def make_bsp_dungeon(cols, rows, seed):
    rng = random.Random(seed)                   # a local RNG: same seed, same dungeon
    grid = [[WALL] * cols for _ in range(rows)]
    root = BSPNode(0, 0, cols, rows)
    split_node(root, rng)
    rooms = []
    for leaf in leaves(root):
        w = rng.randint(MIN_ROOM, leaf.w - 2)   # keep a 1-tile wall inside the leaf
        h = rng.randint(MIN_ROOM, leaf.h - 2)
        x = rng.randint(leaf.x + 1, leaf.x + leaf.w - w - 1)
        y = rng.randint(leaf.y + 1, leaf.y + leaf.h - h - 1)
        leaf.room = Room(x, y, w, h)
        carve_room(grid, leaf.room)
        rooms.append(leaf.room)
    connect(root, grid, rng)
    return grid, rooms


def wall_neighbors(grid, x, y):
    """Walls among the 8 neighbors. Cells outside the map count as walls."""
    rows, cols = len(grid), len(grid[0])
    count = 0
    for dy in (-1, 0, 1):
        for dx in (-1, 0, 1):
            if dx == 0 and dy == 0:
                continue
            nx, ny = x + dx, y + dy
            if not (0 <= nx < cols and 0 <= ny < rows) or grid[ny][nx] == WALL:
                count += 1
    return count


def smooth(grid):
    """One cellular-automata step, written into a NEW grid (never in place)."""
    new = [row[:] for row in grid]
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            n = wall_neighbors(grid, x, y)
            if n > 4:
                new[y][x] = WALL
            elif n < 4:
                new[y][x] = FLOOR
    return new


def regions(grid, kind=FLOOR):
    """Flood-fill every connected area of `kind` tiles (4-way). Returns a list of tile lists."""
    rows, cols = len(grid), len(grid[0])
    seen = set()
    found = []
    for y in range(rows):
        for x in range(cols):
            if grid[y][x] != kind or (x, y) in seen:
                continue
            region = []
            queue = deque([(x, y)])
            seen.add((x, y))
            while queue:
                cx, cy = queue.popleft()
                region.append((cx, cy))
                for nx, ny in ((cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)):
                    if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == kind and (nx, ny) not in seen:
                        seen.add((nx, ny))
                        queue.append((nx, ny))
            found.append(region)
    return found


def keep_largest_region(grid):
    """Wall off every floor pocket except the biggest one."""
    found = regions(grid)
    if not found:
        return
    biggest = max(found, key=len)
    for region in found:
        if region is not biggest:
            for x, y in region:
                grid[y][x] = WALL


def make_cave(cols, rows, seed, fill=0.45, steps=5):
    rng = random.Random(seed)
    grid = [[WALL if rng.random() < fill else FLOOR for _ in range(cols)] for _ in range(rows)]
    for _ in range(steps):
        grid = smooth(grid)
    for x in range(cols):                       # a solid border keeps the player inside
        grid[0][x] = grid[rows - 1][x] = WALL
    for y in range(rows):
        grid[y][0] = grid[y][cols - 1] = WALL
    keep_largest_region(grid)
    return grid


def distances_from(grid, start):
    """BFS step counts from start to every reachable floor tile."""
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}
    queue = deque([start])
    while queue:
        x, y = queue.popleft()
        for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == FLOOR and (nx, ny) not in dist:
                dist[(nx, ny)] = dist[(x, y)] + 1
                queue.append((nx, ny))
    return dist


def place_start_and_exit(grid):
    """Two BFS sweeps: the tile farthest from any floor tile, then the tile farthest from that."""
    first = next((x, y) for y, row in enumerate(grid) for x, t in enumerate(row) if t == FLOOR)
    d1 = distances_from(grid, first)
    start = max(d1, key=d1.get)
    d2 = distances_from(grid, start)
    exit_tile = max(d2, key=d2.get)
    return start, exit_tile, d2[exit_tile]


def render_map(grid):
    """Draw the tiles ONCE onto a Surface; the game loop only blits it."""
    surf = pygame.Surface((len(grid[0]) * TILE, len(grid) * TILE))
    surf.fill(WALL_COLOR)
    for y, row in enumerate(grid):
        for x, tile in enumerate(row):
            if tile == FLOOR:
                surf.fill(FLOOR_COLOR, (x * TILE, y * TILE, TILE, TILE))
    return surf


def build(mode, seed):
    if mode == "BSP":
        grid, rooms = make_bsp_dungeon(COLS, ROWS, seed)
        extra = f"rooms {len(rooms)}"
    else:
        grid = make_cave(COLS, ROWS, seed)
        extra = "cave"
    floor = sum(row.count(FLOOR) for row in grid)
    connected = len(regions(grid)) == 1
    start, exit_tile, steps = place_start_and_exit(grid)
    info = (f"{mode} seed {seed} | {extra} | floor {100 * floor // (COLS * ROWS)}% | "
            f"connected {connected} | path {steps}")
    return grid, start, exit_tile, info, connected


def main():
    pygame.init()
    screen = pygame.display.set_mode((COLS * TILE, ROWS * TILE + HUD_H))
    pygame.display.set_caption("Dungeon & Cave Viewer")
    clock = pygame.time.Clock()
    font = pygame.font.Font(None, 24)

    mode, seed = "BSP", 1
    grid, start, exit_tile, info, connected = build(mode, seed)
    map_surf = render_map(grid)
    hud = font.render(f"{info}   [B] BSP  [C] cave  [N] next seed", True, TEXT_COLOR)
    built, all_connected = 1, connected

    running = True
    while running:
        clock.tick(60)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.KEYDOWN and event.key in (pygame.K_b, pygame.K_c, pygame.K_n):
                if event.key == pygame.K_b:
                    mode = "BSP"
                elif event.key == pygame.K_c:
                    mode = "Cave"
                else:
                    seed += 1
                grid, start, exit_tile, info, connected = build(mode, seed)
                map_surf = render_map(grid)
                hud = font.render(f"{info}   [B] BSP  [C] cave  [N] next seed", True, TEXT_COLOR)
                built += 1
                all_connected = all_connected and connected

        screen.fill((0, 0, 0))
        screen.blit(map_surf, (0, HUD_H))
        for (tx, ty), color in ((start, START_COLOR), (exit_tile, EXIT_COLOR)):
            center = (tx * TILE + TILE / 2, ty * TILE + TILE / 2 + HUD_H)
            pygame.draw.circle(screen, color, center, TILE * 0.45)
        screen.blit(hud, (8, 6))
        pygame.display.flip()

    pygame.quit()
    print(f"Generated {built} maps; last: {info}")
    print(f"All maps connected: {all_connected}")


if __name__ == "__main__":
    main()

📓 Learning Journal

📝 Summary

You built two generators that turn one number into a whole level. Binary space partitioning cuts the map recursively into a tree of rectangles, puts a room in every leaf and joins the two halves of every split, which guarantees a connected dungeon with the fewest possible corridors. Cellular automata turn random noise into natural caves by repeating one neighbor-counting rule on a fresh copy of the grid, and flood fill cleans up the pockets they leave behind. Two BFS sweeps place a start and an exit far apart, and drawing the map once to a Surface keeps the game loop cheap.

🔭 Looking Ahead

BSP and cellular automata decide where walls go, but they know nothing about how tiles look next to each other. In the next lesson, Wave Function Collapse, you fill a grid with tiles whose edges always match, by propagating constraints the way a sudoku solver does.

❓ Common Questions

🎯 Quick Quiz

🌟 Going Further

• Mixed maps: generate a BSP dungeon, then run two cellular-automata steps only inside a few chosen leaves to turn those rooms into collapsed caverns. Re-run the connectivity check afterwards.
• Tunnel instead of fill: rewrite the cave cleanup to connect every region to the largest with a straight corridor between their closest tiles, instead of walling the pockets off.
• Room roles: keep the BSP tree and tag rooms: the start and exit from the two BFS sweeps, a treasure room in the leaf farthest from both, and a shop next to the start.
• Seed sharing: show the seed on screen and let players type one in, so they can share a map they liked.
• Read more: the RogueBasin wiki's articles on BSP dungeon generation and cellular automata caves describe the classic versions of both algorithms.