Maze Generation Algorithms — DFS, Prim's, Wilson's and More

1. Mazes as Spanning Trees

Model a W×H grid as a graph where each cell is a vertex and adjacent cells share an edge. A perfect maze requires:

• All W×H cells are connected (exactly one path between any two cells).
• No cycles (no loops, no multiple paths).

This is precisely a spanning tree — a connected, acyclic subgraph that visits every vertex. A W×H grid has W×H vertices and W(H−1) + H(W−1) = 2WH−W−H edges; a spanning tree uses exactly W×H − 1 edges. Each algorithm selects different edges to include, producing different spanning trees with different statistical properties.

2. Recursive Backtracking (DFS)

The simplest and most popular maze algorithm. Start at a random cell, mark it visited, then repeatedly:

1. Choose a random unvisited neighbour.
2. Knock down the wall between the current cell and the chosen neighbour.
3. Move to the chosen cell and repeat.
4. If no unvisited neighbours, backtrack to the previous cell.

function generateDFS(grid, start) {
  const visited = new Set([start]);
  const stack = [start];
  while (stack.length) {
    const cell = stack[stack.length - 1];
    const unvisited = neighbours(cell).filter(n => !visited.has(n));
    if (unvisited.length === 0) { stack.pop(); continue; }
    const next = unvisited[randInt(0, unvisited.length)];
    removeWall(cell, next);
    visited.add(next);
    stack.push(next);
  }
}

Complexity: O(W×H). Character: Long, winding corridors with few junctions. Easy to solve by intuition following the main path. Memory usage: O(W×H) stack depth worst case.

3. Prim's Algorithm

Builds the spanning tree by always expanding the "cheapest" frontier edge. For random mazes, all edges have equal weight — so we pick uniformly at random from the current frontier:

1. Start with one random cell in the maze set; add all its walls to the frontier list.
2. Pick a random wall from the frontier. If the neighbour on the other side is not yet in the maze: remove the wall, add the neighbour to the maze, add its new walls to the frontier.
3. Repeat until the frontier is empty.

Prim's produces mazes with uniform, tree-like branching. The maze spreads outward from the start like a growing crystal, with many short dead-end tentacles in all directions simultaneously — visually very different from DFS's long corridors.

4. Wilson's Loop-Erased Random Walk

Wilson's algorithm (1996) is the only simple algorithm that generates a uniformly random spanning tree — every possible perfect maze for the given grid is equally probable.

1. Add one arbitrary cell to the maze set.
2. Choose any unvisited cell as a starting walker.
3. Perform a random walk until the walk hits any cell already in the maze.
4. Erase all loops from the walk path (making it a simple path).
5. Add the entire loop-erased path to the maze.
6. Repeat from step 2 until all cells are in the maze.

The loop erasure step is critical: whenever the walk visits a cell it has visited before, erase everything since the previous visit to form a simple (non-self-crossing) path. This is the loop-erased random walk (LERW).

5. Aldous-Broder

The simplest unbiased uniform spanning tree algorithm — but also the slowest:

1. Start at a random cell. Mark it visited.
2. Move to a random neighbour. If the neighbour has not been visited, remove the wall and mark it visited.
3. Repeat until all cells are visited.

No loop erasure needed — any random walk eventually visits all cells by definition. The last edge leading to each newly-visited cell forms the spanning tree. Like Wilson's, this produces uniform random spanning trees, but it requires O(N log N) expected steps (the "coupon collector" problem) — typically 5–10× slower than DFS for large grids.

6. Kruskal's and Eller's

Kruskal's Algorithm

Assign random weights to all grid edges, then add edges in order of increasing weight while an edge connects two different components (using Union-Find). The result is a uniformly random spanning tree. Runtime O(E log E) = O(N log N) with efficient Union-Find implementation.

Eller's Algorithm

The unique row-by-row maze algorithm: generates mazes in O(W) memory regardless of height, making it the only algorithm suitable for generating arbitrarily tall mazes with very low memory:

• Assign each cell in the first row a unique set ID.
• Randomly merge adjacent cells in the same row (removing vertical walls) while ensuring all sets remain connected downward.
• For each set, create at least one downward connection to the next row.
• Cells in the next row that didn't receive a connection start new sets.
• Repeat; final row must merge all distinct sets.

7. Comparison and Bias

The choice of algorithm is both aesthetic and mathematical. Game designers typically prefer DFS for satisfying playable mazes; researchers studying diffusion-limited aggregation or spatial models may need Wilson's unbiased trees. The maze simulation on this site lets you generate and compare all five families side-by-side.