03 · Maze Generation
Same starting grid · same end goal (a spanning tree of the rooms) · four algorithms · four visibly different mazes.
All four algorithms start from the same fully-walled grid (13 × 8 logical rooms). They differ only in which wall to carve next — and that single choice produces dramatically different maze styles.
What you're watching
Every algorithm here is solving the same problem: pick a spanning tree of the room graph (where rooms are vertices and the wall between two adjacent rooms is an edge). The algorithm carves each chosen edge, leaving exactly enough passages to reach every room with no loops. The maze that pops out is just which spanning tree got picked — and that's where the bias of the algorithm becomes visible.
(R, C) sits at grid coordinates
(2R, 2C). The wall between adjacent rooms
(R₁, C₁) and (R₂, C₂) sits at
(R₁+R₂, C₁+C₂). Every cell with both odd row and odd
column is a "wall corner" that stays a wall forever.
The four algorithms
Recursive-backtracker DFS stack-based · biased toward long corridors
Pick a starting room. Walk to a random unvisited neighbour, carving the wall between. When stuck, backtrack and try another direction. The bias produces long winding corridors with relatively few branches — visually the most "labyrinthine" style of the four. Maze game designers often pick this one for that feel.
Prim's random frontier expansion · spiky branches
Maintain a "frontier" of walls between the in-maze region and the outside. Repeatedly pick a frontier wall at random; if it leads to an unvisited room, carve. The result is a maze with many short branches sticking out from a roughly compact core — visibly different from DFS's long snakes.
Kruskal's union-find on shuffled edges · uniform-looking
Generate every wall between adjacent rooms, shuffle the list, process them in order. For each wall, if the two rooms it separates belong to different components (checked via union-find), carve the wall and merge. The result has no obvious local pattern: no preferred direction, no preferred branch length. Looks the most "natural" of the four.
Wilson's loop-erased random walks · uniform spanning tree
The sophisticated one. Start with one cell already "in maze." Pick any other cell, do a random walk, and whenever the walk crosses itself, erase the loop. When the walk eventually reaches the in-maze region, carve the loop-erased path and add all its cells to the in-maze set. Repeat until every cell is in.
Mathematically, this is the only one of the four that produces a truly uniform random spanning tree — every possible maze topology is equally likely. The other three are biased toward certain shapes. The cost: it's by far the slowest, especially in the early iterations when the in-maze region is still small.
Why this is interesting
These algorithms touch a surprising number of CS topics:
- Graph theory: maze gen is spanning-tree construction in disguise.
- Disjoint-set / union-find: Kruskal's is the canonical example.
- Random walks & loop erasure: Wilson's is closely related to electrical-network theory.
- Algorithmic bias visualisation: same problem, four answers, each with a recognisable visual signature.
What I learned writing this
-
The room/wall mapping is half the work. Once
(R, C) → (2R, 2C)and "wall between rooms is at their midpoint coordinates" are clear in code, all four algorithms drop in trivially. - Wilson's runs slowly at first, then accelerates. When the maze contains few cells, random walks have to travel a long way to find any in-maze cell. As more cells get added, the walks shorten dramatically — the last 30 % of cells finish almost instantly.
- Kruskal's looks the most "natural" because it has the fewest priors. No preferred direction, no preferred shape. It's the maze-generation equivalent of a uniform prior.
- You can already feel #04's primitives forming. Union-find from Kruskal's, BFS from #02, frontier expansion from Prim's — these are the building blocks for graph algorithms in general. The next page will lift them into a more general graph view.