Maze Generation Algorithms: How Different Algorithms Create Different Mazes

Not All Mazes Feel the Same

If you have ever solved a dozen random mazes and noticed that some feel like long winding tunnels while others feel like dense bushes of short branches, you were not imagining it. The generation algorithm determines the maze's "texture" — its dead-end density, average corridor length, branching factor, and directional bias. Understanding these properties lets you predict a maze's difficulty before you solve a single cell.

DFS Recursive Backtracking

The most popular algorithm, and what most people picture when they think "computer-generated maze."

How It Works

1. Start with a solid grid. Pick a random cell, mark it visited.
2. Choose a random unvisited neighbor, carve a passage to it, move there.
3. If all neighbors are visited, backtrack along the carved path until you find a cell with unvisited neighbors.
4. Repeat until every cell is visited.

What It Produces

DFS generates mazes with a high river factor — long, winding corridors that snake across the grid before branching. This happens because the algorithm plunges deep into unvisited territory before being forced to backtrack. A 21×21 DFS maze typically has corridors averaging 8–12 cells long, with dead-end density around 25–30% (percentage of cells that are dead ends).

The bias is toward long solution paths. The first cell visited and the last cell visited are usually far apart both in grid distance and path distance, making DFS mazes feel challenging even at moderate sizes. The downside is predictability: experienced solvers learn to "ride the river" — following the longest visible corridor, which is statistically likely to be part of the solution.

Complexity

O(n) time and O(n) space (the recursion stack or an explicit stack). For a 41×41 maze (1,681 cells), generation takes under 5 milliseconds on modern hardware.

Randomized Prim's Algorithm

Adapted from Prim's minimum spanning tree algorithm (1957), this approach grows the maze outward from a frontier rather than diving deep.

How It Works

1. Pick a random starting cell. Add all its walls to a frontier list.
2. Pick a random wall from the frontier.
3. If the cell on the other side is unvisited, carve through the wall and mark the cell visited. Add the new cell's walls to the frontier.
4. Remove the wall from the frontier either way. Repeat until the frontier is empty.

What It Produces

Prim's produces mazes with high branching and short corridors. Dead-end density jumps to 35–45%. The river factor is low — corridors rarely exceed 3–4 cells before forking. This is because the frontier grows radially outward from the start, and each new passage is chosen from the entire boundary of explored territory rather than from a single advancing tip.

The result feels "bushy." There are many decision points close together, which makes the maze feel harder for beginners (more wrong turns available) but easier for advanced solvers (shorter backtrack distances). Solution paths tend to be shorter relative to maze size compared to DFS.

Randomized Kruskal's Algorithm

Based on Kruskal's MST algorithm (1956), this approach treats every cell as an isolated component and merges them by removing walls.

How It Works

1. Initialize a Union-Find (disjoint set) data structure with each cell as its own set.
2. Create a list of all interior walls. Shuffle it randomly.
3. For each wall: if the two cells it separates belong to different sets, remove the wall and union the sets. If they are already in the same set, skip (removing the wall would create a cycle).
4. Stop when all cells belong to one set.

The Role of Union-Find

Union-Find is what makes Kruskal's efficient. With path compression and union by rank, each find/union operation is nearly O(1) (technically O(α(n)), where α is the inverse Ackermann function — effectively constant for any practical input). Without Union-Find, checking whether two cells are connected would require a BFS/DFS each time, inflating the cost to O(n²) or worse.

What It Produces

Kruskal's generates the most uniform and unbiased mazes of the four algorithms. Every wall has equal probability of being removed (subject only to the cycle constraint). There is no directional bias, no river tendency, and dead-end density sits around 30–35%. The visual result looks "random" in a way DFS and Prim's do not — no obvious structure or texture. Difficulty is moderate and consistent.

Binary Tree Algorithm

The simplest possible maze generator. For each cell, flip a coin: remove the north wall or the west wall. That is the entire algorithm.

How It Works

1. Iterate through every cell, row by row.
2. For each cell, randomly remove either the north wall or the west wall.
3. Edge cases: cells on the top row can only carve west; cells in the leftmost column can only carve north; the top-left corner cell does nothing.

What It Produces

Binary Tree is fast — O(n) with no stack, no set, no frontier — but it has a severe directional bias. The top row and left column are always open corridors (they have no choice). The solution path has a strong northwest-to-southeast diagonal tendency. Dead-end density is around 25%, but the distribution is uneven: the southeast corner region has far more dead ends than the northwest.

Binary Tree mazes are useful for teaching and prototyping but rarely used in production because the bias is visually obvious and the mazes feel unfair.

Algorithm Comparison at a Glance

• DFS: Long rivers, 25–30% dead ends, high difficulty, strong solution-path bias.
• Prim's: Short branches, 35–45% dead ends, bushy feel, many decision points.
• Kruskal's: Uniform, 30–35% dead ends, unbiased, moderate difficulty.
• Binary Tree: Diagonal bias, 25% dead ends, trivially simple, always has open top row and left column.

What We Use

Our maze generator uses DFS Recursive Backtracking with extra passages — a hybrid approach. After generating a standard DFS maze, we randomly remove a small number of additional walls (typically 2–5% of total walls) to introduce loops and alternative paths. This preserves the satisfying long-corridor feel of DFS while reducing the "single solution path" problem that makes pure DFS mazes feel linear. The extra passages also defeat the wall-following shortcut, forcing solvers to actually think at junctions.

Want to feel the difference? Play through a few levels and pay attention to how often you face genuine choices versus being funneled down a single corridor. That is the hybrid algorithm at work.