Three maze algorithms compared: why I picked recursive backtracking

Building Pixel Path, I compared three mainstream maze generators: recursive backtracker, Prim, Kruskal. All "generate mazes," but the mazes they produce look different and play differently. Here's my comparison and final choice.

What every maze really is

An observation that hit me early: a "perfect maze" is mathematically just a tree.

"Perfect maze" definition: between any two cells there's exactly one path (no loops, no disconnections). Identical to the definition of a tree — a connected, acyclic graph. So maze generation is fundamentally "generate a spanning tree on a grid."

That observation immediately simplifies the choice: any "graph spanning tree algorithm" can generate a maze. So Prim and Kruskal — both originally for minimum spanning tree — are borrowed for maze generation. Plus a non-classical but excellent one: recursive backtracking.

Recursive backtracker

Idea: depth-first search. From a starting cell, randomly pick an unvisited neighbor, carve through the wall, recurse into that neighbor. If no unvisited neighbors, backtrack to the previous cell with unvisited neighbors and continue.

The code is short:

function carve(x, y) {
  maze[y][x] = 0;
  shuffle(dirs);
  for (const [dx,dy] of dirs) {
    const nx = x+dx, ny = y+dy;
    if (inBounds(nx, ny) && maze[ny][nx] === 1) {
      maze[y+dy/2][x+dx/2] = 0;  // carve wall
      carve(nx, ny);  // recurse
    }
  }
}

Characteristics: long corridors, few branches. Because DFS dives all the way before backtracking, it produces lots of long straight stretches. Players feel "walk a long straight, then a junction."

Performance: O(N), where N is cell count. A 25x25 grid takes a few milliseconds. Watch JavaScript's recursion stack — for grids over ~40x40 you may need an explicit stack to avoid stack overflow.

Prim

Idea: from a start cell, maintain a "frontier" of walls (between explored and unexplored). Each iteration: randomly pick a frontier wall, carve through, add the cell behind it to explored, update the frontier. Repeat until no walls remain.

This "expanding from explored borders" logic produces mazes with: many short branches, fluffy. Corridors near each junction are short. Overall feel: plant root system.

Implementation slightly more complex (needs a wall list data structure), but still O(N).

Kruskal

Idea: list every wall and shuffle. Iterate: if a wall's two adjacent cells aren't in the same connected component, carve through and merge the components. Else skip. Repeat until done (or only one component remains).

Needs Union-Find for efficient component checks. Mazes generated are: uniformly random, neutral. No bias toward long corridors or short branches; balanced. Feel: most "engineering-y," weakest visual character.

I picked recursive backtracker

Main reason: gameplay experience. Pixel Path is an action exploration — player races from start to end. Long corridors are a positive:

• Long corridors → fewer direction changes → smoother feel
• Fewer branches → clearer main path → low decision cost
• Occasional dead ends → "tricked" moments → not tiring

Prim's fluffy mazes are pretty but feel scattered — players hit a junction every 2–3 steps, high cognitive load. Kruskal's neutral mazes lack character — players don't remember the layout.

Also: recursive backtracker has the shortest, most maintainable code, important for a project iterating long-term.

Recursive backtracker is a mountain road. Prim is a wetland. Kruskal is a chessboard. Which maze fits your game depends on what feeling you want.

A meta-reflection on "algorithm choice"

I spent about a day on this comparison. Honestly, by "is it usable" any of the three works. They all generate connected, acyclic, random mazes. But their effect on player experience is specific and very different.

This makes me reflect on a common engineer trap: we love optimizing for "best performance" or "shortest code." For user-facing products, what often matters more is "the algorithm's output character." Prim and Kruskal are near-equivalent on minimum spanning tree, but completely different in a maze game.

This "output character" was historically the hardest thing for engineers and designers to communicate about before the LLM era. Designers can feel "this maze is too scattered" but can't explain why; engineers respond "I'm using the standard algorithm" without hearing the complaint. Both right. Algorithm choice itself is a product decision.

Performance benchmark

On my MacBook Air M1, generating 51x51:

• Recursive backtracker: ~3.2 ms
• Prim: ~4.8 ms
• Kruskal (Union-Find): ~5.5 ms

Differences negligible. Performance not a selection criterion.

Closing

Maze generation is one of computer graphics' earliest topics (traceable to the 1970s). English-language resources are abundant; Jamis Buck's maze series on Buckblog is the bible. Chinese-language coverage is thinner. Hopefully this fills a small gap.

Next time you face an "algorithm choice" decision, ask: does this algorithm's output character match my product's tone?

Leo is BverGame's co-engineer. Performance numbers are based on personal testing with high variance; treat as illustrative. For deeper material: Jamis Buck's Mazes for Programmers (Pragmatic Bookshelf, 2015).