← Blog
AlgorithmMazeVisualization

Comparing Maze Generation Algorithms — Structural Differences Between Recursive Backtracking, Kruskal, and Prim

19 min read

Go deeper on this topic

Browser Game Development

Game loop design, collision detection, pathfinding, and tooling for browser games

Article 3 of 7 in this series.

View topic page

Next reads

Visualizing Pathfinding Algorithms — Watching A*, BFS, and DFS Solve a Maze

Techniques for visualizing the search process of A*, BFS, and DFS implemented in the MazeRunner component, with a comparison of each algorithm.

Collision Detection Fundamentals — Circles, Rectangles, and Impulse-Based Response

A deep dive into circle-circle and circle-rectangle collision detection algorithms, restitution-based bounce control, and the math behind impulse-based collision response, explained through the physics.ts implementation.

Designing a Type-Safe Game Loop in TypeScript — State Management for Snake and Tetris

Game state management and frame rate control using TypeScript's type system, explored through Snake, Tetris, and Breakout implementations.

Use the topic hub as a map, then continue to the next article in the series. New here? Start at the home hub →

Maze Generation Algorithms Have "Personality"

While implementing MazeRunner and TiltMaze, I noticed that each maze generation algorithm produces mazes with completely different "personalities." Mazes with long corridors, mazes full of branches, mazes with symmetry — the choice of algorithm significantly affects the user experience.

This article compares three representative algorithms by implementing each and examining their characteristics.

Common Data Structure

First, the grid representation shared by all algorithms is defined in TypeScript:

type Cell = {
  x: number
  y: number
  walls: { top: boolean; right: boolean; bottom: boolean; left: boolean }
}

type Maze = Cell[][]

function createGrid(cols: number, rows: number): Maze {
  return Array.from({ length: rows }, (_, y) =>
    Array.from({ length: cols }, (_, x) => ({
      x,
      y,
      walls: { top: true, right: true, bottom: true, left: true },
    })),
  )
}

function removeWall(a: Cell, b: Cell) {
  const dx = b.x - a.x
  const dy = b.y - a.y

  if (dx === 1) {
    a.walls.right = false
    b.walls.left = false
  } else if (dx === -1) {
    a.walls.left = false
    b.walls.right = false
  } else if (dy === 1) {
    a.walls.bottom = false
    b.walls.top = false
  } else if (dy === -1) {
    a.walls.top = false
    b.walls.bottom = false
  }
}

The "cell + walls" representation is chosen over the wall-carving approach because Kruskal's and Prim's algorithms need to manipulate walls individually. A unified representation makes comparing algorithms easier.

Recursive Backtracking

The most popular DFS-based method. Uses a stack to traverse unvisited neighboring cells, backtracking when hitting a dead end:

function recursiveBacktracker(cols: number, rows: number): Maze {
  const maze = createGrid(cols, rows)
  const visited = new Set<string>()
  const stack: Cell[] = []
  const key = (c: Cell) => \\`\\\${c.x},\\\${c.y}\\`

  const start = maze[0][0]
  visited.add(key(start))
  stack.push(start)

  while (stack.length > 0) {
    const current = stack[stack.length - 1]
    const neighbors = getUnvisitedNeighbors(maze, current, cols, rows).filter(
      (n) => !visited.has(key(n)),
    )

    if (neighbors.length === 0) {
      // Dead end → backtrack
      stack.pop()
      continue
    }

    // Randomly select a neighbor and remove the wall
    const next = neighbors[Math.floor(Math.random() * neighbors.length)]
    removeWall(current, next)
    visited.add(key(next))
    stack.push(next)
  }

  return maze
}

function getUnvisitedNeighbors(
  maze: Maze,
  cell: Cell,
  cols: number,
  rows: number,
): Cell[] {
  const { x, y } = cell
  const neighbors: Cell[] = []

  if (y > 0) neighbors.push(maze[y - 1][x])
  if (x < cols - 1) neighbors.push(maze[y][x + 1])
  if (y < rows - 1) neighbors.push(maze[y + 1][x])
  if (x > 0) neighbors.push(maze[y][x - 1])

  return neighbors
}

Characteristics

  • Long corridors: DFS keeps carving in one direction, creating long, winding passages
  • Few branches: Branches only form during backtracking
  • Long solution path: The route from start to finish tends to be circuitous
  • Simple implementation: Requires just a single stack

TiltMaze uses this algorithm. Long corridors pair well with the experience of rolling a ball by tilting a phone.

Kruskal's Algorithm (Randomized Kruskal)

Based on the minimum spanning tree algorithm from graph theory. All walls are processed in random order, with Union-Find managing connectivity:

class UnionFind {
  parent: number[]
  rank: number[]

  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i)
    this.rank = new Array(size).fill(0)
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]) // Path compression
    }
    return this.parent[x]
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a)
    const rb = this.find(b)
    if (ra === rb) return false // Already in the same set

    // Union by rank (keeps tree height low)
    if (this.rank[ra] < this.rank[rb]) {
      this.parent[ra] = rb
    } else if (this.rank[ra] > this.rank[rb]) {
      this.parent[rb] = ra
    } else {
      this.parent[rb] = ra
      this.rank[ra]++
    }
    return true
  }
}

type Wall = { a: Cell; b: Cell }

function kruskalMaze(cols: number, rows: number): Maze {
  const maze = createGrid(cols, rows)
  const uf = new UnionFind(cols * rows)
  const cellId = (c: Cell) => c.y * cols + c.x

  // Enumerate all walls
  const walls: Wall[] = []
  for (let y = 0; y < rows; y++) {
    for (let x = 0; x < cols; x++) {
      if (x < cols - 1) walls.push({ a: maze[y][x], b: maze[y][x + 1] })
      if (y < rows - 1) walls.push({ a: maze[y][x], b: maze[y + 1][x] })
    }
  }

  // Fisher-Yates shuffle
  for (let i = walls.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1))
    ;[walls[i], walls[j]] = [walls[j], walls[i]]
  }

  // Remove walls in random order (only between cells in different sets)
  for (const { a, b } of walls) {
    if (uf.union(cellId(a), cellId(b))) {
      removeWall(a, b)
    }
  }

  return maze
}

Why Union-Find

When removing a wall, you need to quickly determine "are these two cells already connected?" Union-Find's find operation runs in effectively O(1) with path compression, allowing maze generation in linear time proportional to the number of walls.

Characteristics

  • Short corridors with many branches: Random wall removal produces less bias
  • Uniform appearance: Overall well-balanced mazes
  • Short solution path: More branches mean the shortest path is easier to find
  • Easy to parallelize: Wall processing is independent, making parallel execution theoretically possible

Prim's Algorithm (Randomized Prim)

Also based on minimum spanning trees, but grows differently. A "wall list" is grown from a single cell:

function primMaze(cols: number, rows: number): Maze {
  const maze = createGrid(cols, rows)
  const inMaze = new Set<string>()
  const wallList: Wall[] = []
  const key = (c: Cell) => \\`\\\${c.x},\\\${c.y}\\`

  // Add starting cell to the maze
  const start = maze[0][0]
  inMaze.add(key(start))
  addWalls(maze, start, wallList, cols, rows)

  while (wallList.length > 0) {
    // Randomly select a wall
    const idx = Math.floor(Math.random() * wallList.length)
    const wall = wallList[idx]
    wallList.splice(idx, 1)

    const aIn = inMaze.has(key(wall.a))
    const bIn = inMaze.has(key(wall.b))

    // Only remove the wall if exactly one side is in the maze
    if (aIn !== bIn) {
      removeWall(wall.a, wall.b)
      const newCell = aIn ? wall.b : wall.a
      inMaze.add(key(newCell))
      addWalls(maze, newCell, wallList, cols, rows)
    }
  }

  return maze
}

function addWalls(
  maze: Maze,
  cell: Cell,
  wallList: Wall[],
  cols: number,
  rows: number,
) {
  const { x, y } = cell
  if (x > 0) wallList.push({ a: cell, b: maze[y][x - 1] })
  if (x < cols - 1) wallList.push({ a: cell, b: maze[y][x + 1] })
  if (y > 0) wallList.push({ a: cell, b: maze[y - 1][x] })
  if (y < rows - 1) wallList.push({ a: cell, b: maze[y + 1][x] })
}

Characteristics

  • Grows radially: Expands outward from the starting point, making the generation process visually beautiful
  • Short corridors: Like Kruskal's, produces well-balanced mazes with many branches
  • Dense near the start: Since the wall list is small initially, short corridors tend to concentrate around the starting point

Algorithm Comparison Table

Property Recursive Backtracker Kruskal Prim
Base DFS Minimum spanning tree Minimum spanning tree
Corridor length Long Short Short
Branch frequency Few Many Many
Dead-end count Few Many Many
Visual generation Winding line Random patches Radial growth
Difficulty tendency Hard (many detours) Easy (short optimal path) Medium
Time complexity O(cells) O(walls × α(cells)) O(walls × log(walls))
Data structure Stack Union-Find Array (wall list)

Implementation Insights

Why Wall Selection Must Be Random

Both Kruskal's and Prim's original algorithms determine order by edge weight. For maze generation, a "completely random spanning tree" is desired, so random selection replaces weight. By introducing weight bias, you can intentionally create mazes where corridors tend to extend in specific directions.

Why Perfect Mazes

A perfect maze is one where "there exists exactly one path between any two cells." In graph theory terms, this is a spanning tree. Since there are no loops, search visualizations like MazeRunner offer the clarity of "exactly one correct answer." Intentionally adding loops creates multiple paths and changes the gameplay.

Why splice the Wall List in Prim's

wallList.splice(idx, 1) is O(n), but the wall list is at most around 2 × cols × rows (thousands to tens of thousands), so it's not a practical issue. For O(1), swap with the last element and pop:

// O(1) random removal
const idx = Math.floor(Math.random() * wallList.length)
wallList[idx] = wallList[wallList.length - 1]
wallList.pop()

Canvas API Rendering Performance

Drawing each wall individually with strokeRect results in enormous draw call counts. Instead, painting pixels based on wall presence is faster:

function renderMaze(ctx: CanvasRenderingContext2D, maze: Maze, cellSize: number) {
  const cols = maze[0].length
  const rows = maze.length

  ctx.fillStyle = '#1a1a2e'
  ctx.fillRect(0, 0, cols * cellSize, rows * cellSize)

  ctx.fillStyle = '#16213e'

  for (let y = 0; y < rows; y++) {
    for (let x = 0; x < cols; x++) {
      const cell = maze[y][x]
      const px = x * cellSize
      const py = y * cellSize

      // Paint cell interior with corridor color
      ctx.fillRect(px + 1, py + 1, cellSize - 2, cellSize - 2)

      // Extend corridor where walls are removed
      if (!cell.walls.right && x < cols - 1) {
        ctx.fillRect(px + cellSize - 1, py + 1, 2, cellSize - 2)
      }
      if (!cell.walls.bottom && y < rows - 1) {
        ctx.fillRect(px + 1, py + cellSize - 1, cellSize - 2, 2)
      }
    }
  }
}

Using fillRect only at wall removal points and leveraging the background color as walls avoids beginPath / stroke entirely.

Summary: Tools for Maze Generation Algorithms

Maze generation is a spanning tree problem where graph theory fundamentals apply directly. Implementing algorithms while looking at illustrated explanations gives you a visceral understanding of "why this data structure is needed" for Union-Find and heaps.

Follow @sakimyto