Maze Generation Algorithms Explained: Backtracking, Prim’s, and Kruskal’s

Maze generation is both an art and a science. In this guide, we’ll cover three widely-used algorithms, explain their intuition, show pseudo-code/JS snippets, and compare their characteristics.

1) Recursive Backtracking (Depth-First Search)

• Intuition: Always carve forward until you can’t, then backtrack

• Output: Long corridors with occasional branches; can create dead-ends naturally

• Complexity: Time O(N), Space O(N) for recursion stack

Pseudo-code

e.g., grid with walls between cells

1. Pick a random start cell and mark visited
2. While there are unvisited neighbors:

• Choose a random unvisited neighbor

• Knock down the wall between current and neighbor

• Move to neighbor and repeat

3. If stuck, backtrack to the last cell with unvisited neighbors

JS snippet (conceptual)

```js
function generateBacktracking(grid) {
const stack = []
let current = randomCell(grid)
current.visited = true
while (true) {
const next = randomUnvisitedNeighbor(current)
if (next) {
removeWall(current, next)
stack.push(current)
current = next
current.visited = true
} else if (stack.length) {
current = stack.pop()
} else {
break
}
}
return grid
}
```

2) Prim’s Algorithm

• Intuition: Start from a frontier and expand by adding the lowest-cost/random frontier edges

• Output: More uniform branching than backtracking; fewer long corridors

• Complexity: O(E log V) with priority queue; simpler random frontier is acceptable for games

Steps

1. Choose a random starting cell 2. Add its walls to a frontier set 3. Repeatedly pick a random wall that leads to an unvisited cell, remove it, and add new frontier walls

JS snippet (conceptual)

```js
function generatePrim(grid) {
const frontier = []
const start = randomCell(grid)
markVisited(start)
addFrontierWalls(start, frontier)
while (frontier.length) {
const wall = pickRandom(frontier)
if (leadsToUnvisitedCell(wall)) {
removeWall(wall)
const cell = wall.otherSide
markVisited(cell)
addFrontierWalls(cell, frontier)
}
}
return grid
}
```

3) Kruskal’s Algorithm

• Intuition: Treat cells as nodes and walls as edges; randomly remove walls if it connects two different sets (Union-Find)

• Output: Very uniform; good for ensuring no cycles and connectedness

• Complexity: Near-linear with Union-Find (Disjoint Set)

JS snippet (conceptual)

```js
function generateKruskal(grid) {
const sets = new DisjointSet(grid.cells)
const walls = shuffled(grid.walls)
for (const wall of walls) {
const [a, b] = wall.cells
if (sets.find(a) !== sets.find(b)) {
removeWall(wall)
sets.union(a, b)
}
}
return grid
}
```

Comparison & Tips

• Backtracking: Fast, long corridors, high variability

• Prim: More uniform branching, fewer dead-ends

• Kruskal: Uniform, tree-like structure, easy to reason about

For interactive demos and performance comparisons, see: Maze Algorithms and Hex Maze Generator.

FAQ

Which algorithm gives the shortest solution? None of these guarantees shortest path by design; they generate the maze structure. For solving shortest path, use BFS or Dijkstra.

Which is best for mobile devices?
Backtracking is fast and memory-friendly; Prim/Kruskal are fine for small to medium grids.

How to avoid too many dead-ends?
Use Prim or post-process dead-ends by carving additional connectors.