Maze Generation: Carving a Perfect Maze With Backtracking

What "perfect" means: a maze is a spanning tree

Model the grid as a graph. Each cell is a vertex; a possible passage between two adjacent cells is an edge. A maze is perfect when its graph of open passages is a spanning tree of the grid: it touches every cell, contains no cycle, and is connected. Those three properties have direct consequences a solver cares about.

• Connected + acyclic ⇒ exactly one path between any two cells. No shortcuts, no islands.
• No loops means no closed corridors you can circle forever.
• A spanning tree on n vertices has precisely n − 1 edges, so a perfect maze on an n-cell grid has exactly n − 1 carved passages — a fixed number regardless of shape.

Every perfect-maze algorithm is, underneath, a randomized spanning-tree generator. They differ only in which spanning tree they tend to pick, which is what gives each its visual "texture."

The mechanism: randomized DFS with backtracking

Recursive backtracking is a depth-first search that visits cells in random order and carves a passage the moment it steps into an unvisited neighbor. The procedure:

• Start at any cell; mark it visited and push it on a stack (or recurse into it).
• Advance: look at the current cell's unvisited neighbors. If any exist, pick one at random, knock down the wall between them (carve the passage), mark the neighbor visited, and move to it.
• Backtrack: if the current cell has no unvisited neighbors — a dead end — pop the stack and return to the previous cell, then try again from there.
• Stop when the stack empties, i.e. you have backtracked all the way past the start.

The invariant that makes it correct: the set of carved passages is always a tree over the set of visited cells. Each carve step adds exactly one new vertex (a previously unvisited neighbor) via exactly one new edge, so no carve can ever close a cycle. When every cell has been visited, the tree spans the whole grid — a perfect maze, guaranteed.

Canonical pseudocode

The iterative form (explicit stack) avoids the recursion-depth pitfall on large grids while staying faithful to the recursive idea:

function carve(grid):
  start = grid.cell(0, 0)
  start.visited = true
  stack = [start]
  while stack not empty:
    cur = stack.top()
    nbrs = unvisited neighbors of cur
    if nbrs is empty:
      stack.pop()  // dead end → backtrack
    else:
      next = random_choice(nbrs)
      remove_wall_between(cur, next)
      next.visited = true
      stack.push(next)

The recursive version is a one-liner shorter — replace the stack with a call carve(next) — but on a 1000×1000 grid a fully unlucky run can nest a million frames deep and overflow the call stack. That is the single most common bug in a first implementation, and the reason production code uses the explicit stack above.

Complexity, and why it is linear

Let n be the number of cells. Each cell is pushed onto the stack exactly once (when first visited) and popped exactly once (when it becomes a dead end), so there are 2n stack operations. At each cell we inspect a constant number of neighbors — 4 on a square grid, bounded by the max degree — so total work is Θ(n), with no gap between best, worst, and average cases. Randomization changes the shape of the maze, not the amount of work.

• Time: Θ(n). Every edge of the grid is examined O(1) times.
• Space: O(n). The stack holds the current DFS path; a degenerate run (a single snaking corridor visiting every cell before backtracking) puts all n cells on the stack at once. Best case the path is short, but you cannot rely on that.

Contrast with Aldous-Broder, which is also Θ(n) space-cheap but takes Θ(n log² n) expected time on a 2-D grid because it wanders by random walk and re-treads visited cells — its cost is the walk's cover time, the expected number of steps to eventually stumble into the last unvisited cell.

Bias, texture, and choosing a variant

Recursive backtracking is not uniform over spanning trees — it strongly favors trees with long paths, because DFS commits to a direction until forced to turn back. Empirically its mazes have the longest average corridors and the fewest dead ends of the common generators, giving a distinctive "river" look that feels harder to a human solver.

• Want bushy mazes with many short dead ends? Use randomized Prim's, which grows from a frontier and branches eagerly.
• Want a uniform, unbiased maze (every spanning tree equally likely — useful for research or fair benchmarking)? Use Wilson's algorithm, which is Θ(n) expected and provably uniform via loop-erased random walks.
• Want simple code and even texture? Randomized Kruskal's with union-find shuffles all edges and adds any that join two components.

For games and procedural levels, recursive backtracking is usually the default: it is trivially fast, memory-light in practice, and its long corridors read as "interesting" to players. When you need statistical fairness, reach for Wilson's instead.

Turning a perfect maze into a playable one

A perfect maze has a unique solution, which can make large mazes tedious. Level designers often add loops by carving a small fraction of extra walls after generation — this is called braiding. Removing every dead end yields a fully braided maze with no cul-de-sacs; removing a random 10–20% yields a partial braid with a few alternate routes.

A few practical notes and misconceptions:

• Entrance and exit are not part of generation. You carve them into the outer wall afterward; they do not affect the spanning-tree property.
• "Recursive division" is a different algorithm. It builds a maze by recursively adding walls with gaps, not by carving — same perfect-maze output, opposite mental model, and it produces long straight walls rather than corridors.
• A perfect maze is always solvable by wall-following (the right-hand rule), precisely because it has no loops. Braiding a maze can break that guarantee if it creates a detached loop the follower can circle.

Recursive backtracking vs. other perfect-maze generators on an n-cell grid.

Algorithm	Time	Extra space	Texture / bias
Recursive backtracking (randomized DFS)	Θ(n)	O(n) stack	Long winding corridors, low branching
Randomized Prim's	Θ(n) with O(1) edge ops	O(n) frontier	Short dead ends, bushy, many junctions
Randomized Kruskal's	Θ(n α(n))	O(n) union-find	Uniform texture, no directional bias
Wilson's algorithm	Θ(n) expected	O(n)	Unbiased — uniform over all spanning trees
Aldous-Broder	Θ(n log² n) expected	O(1) extra	Unbiased but slow (random walk)