All articles
26 min read

Maze Generation: How to Create Perfect Labyrinths With Code

maze generationalgorithmscreative codingJavaScriptgenerative artgraph theorypathfinding

A maze is a perfect puzzle: a network of corridors with exactly one solution path between any two points. What makes mazes fascinating from a programming perspective is that behind every labyrinth lies a spanning tree — a mathematical structure that connects every cell exactly once with no loops. Different algorithms for building that tree produce mazes with dramatically different visual characters, from long winding rivers to short branchy dead ends.

Maze generation has a rich history stretching back millennia. The mythological Labyrinth of Crete, Turf mazes in medieval England, hedge mazes in Renaissance gardens — humans have been building and solving mazes for at least 4,000 years. The computational study of mazes began in the 19th century when Charles Pierre Trémaux developed the first systematic maze-solving algorithm. Today, maze generation algorithms are essential in game development (dungeon generation, puzzle design), robotics (path planning), network design, and art.

In this guide, we'll build 8 maze generators from scratch using JavaScript and the HTML Canvas API. No libraries. No frameworks. Just grids, walls, and algorithms.

1. Recursive backtracker — depth-first carving

The recursive backtracker (also called randomized depth-first search) is the most popular maze algorithm. It works by carving a path through a grid, always choosing a random unvisited neighbor. When it hits a dead end, it backtracks until it finds an unvisited cell. The result: long, winding corridors with few short dead ends — the kind of maze that feels like exploring a cave system.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true], visited: false });
// walls: [top, right, bottom, left]

function idx(x, y) {
  if (x < 0 || y < 0 || x >= cols || y >= rows) return -1;
  return y * cols + x;
}

function removeWalls(a, b) {
  const dx = a.x - b.x, dy = a.y - b.y;
  if (dx === 1) { a.walls[3] = false; b.walls[1] = false; }
  if (dx === -1) { a.walls[1] = false; b.walls[3] = false; }
  if (dy === 1) { a.walls[0] = false; b.walls[2] = false; }
  if (dy === -1) { a.walls[2] = false; b.walls[0] = false; }
}

// Animated generation
const stack = [];
let current = grid[0];
current.visited = true;
stack.push(current);

function step() {
  if (stack.length === 0) { draw(); return; }
  const neighbors = [
    [0, -1], [1, 0], [0, 1], [-1, 0]
  ].map(([dx, dy]) => grid[idx(current.x + dx, current.y + dy)])
   .filter(n => n && !n.visited);

  if (neighbors.length > 0) {
    const next = neighbors[Math.floor(Math.random() * neighbors.length)];
    stack.push(current);
    removeWalls(current, next);
    next.visited = true;
    current = next;
  } else {
    current = stack.pop();
  }
  draw();
  requestAnimationFrame(step);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    if (cell.visited) {
      ctx.fillStyle = '#1a1a2e';
      ctx.fillRect(x, y, cellW, cellH);
    }
    ctx.strokeStyle = '#00d4ff';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
  // Highlight current cell
  ctx.fillStyle = '#ff6b6b';
  ctx.fillRect(current.x * cellW + 2, current.y * cellH + 2, cellW - 4, cellH - 4);
}

step();

The recursive backtracker produces mazes with a strong bias toward long corridors. Because it always pushes forward until it can't, the main solution path tends to be long and winding. The algorithm is O(n) in the number of cells and needs O(n) stack space in the worst case. It's the go-to choice when you want a maze that feels like a natural tunnel system.

2. Randomized Kruskal's — edge-based union

Kruskal's algorithm approaches maze generation from the edge perspective rather than the cell perspective. Start with every cell as its own isolated set. Randomly pick walls and remove them if the cells on either side belong to different sets. This produces a very different texture: many short dead ends and a branchy, organic look — more like a coral reef than a cave.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const cells = cols * rows;

// Union-Find data structure
const parent = Array.from({ length: cells }, (_, i) => i);
const rank = new Array(cells).fill(0);

function find(x) {
  while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
  return x;
}
function union(a, b) {
  const ra = find(a), rb = find(b);
  if (ra === rb) return false;
  if (rank[ra] < rank[rb]) parent[ra] = rb;
  else if (rank[ra] > rank[rb]) parent[rb] = ra;
  else { parent[rb] = ra; rank[ra]++; }
  return true;
}

// Grid with all walls
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true] });

// Collect all edges, shuffle them
const edges = [];
for (let y = 0; y < rows; y++) {
  for (let x = 0; x < cols; x++) {
    const i = y * cols + x;
    if (x < cols - 1) edges.push([i, i + 1, 'h']); // horizontal
    if (y < rows - 1) edges.push([i, i + cols, 'v']); // vertical
  }
}
// Fisher-Yates shuffle
for (let i = edges.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [edges[i], edges[j]] = [edges[j], edges[i]];
}

// Animate
let edgeIdx = 0;
function step() {
  // Process a batch per frame for smooth animation
  for (let k = 0; k < 5 && edgeIdx < edges.length; edgeIdx++) {
    const [a, b, dir] = edges[edgeIdx];
    if (union(a, b)) {
      if (dir === 'h') {
        grid[a].walls[1] = false;
        grid[b].walls[3] = false;
      } else {
        grid[a].walls[2] = false;
        grid[b].walls[0] = false;
      }
      k++;
    }
  }
  draw();
  if (edgeIdx < edges.length) requestAnimationFrame(step);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    ctx.fillStyle = '#1a1a2e';
    ctx.fillRect(x, y, cellW, cellH);
    ctx.strokeStyle = '#ff9f43';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
}

step();

Kruskal's produces mazes with low "river" factor — meaning the solution path tends to be shorter relative to the total maze area. The visual texture is uniformly branchy. The algorithm runs in O(E α(V)) time with Union-Find, where α is the inverse Ackermann function (effectively constant). It's beautiful to watch: walls dissolve in random order across the entire grid simultaneously, unlike the backtracker's single carving point.

3. Randomized Prim's — frontier expansion

Prim's algorithm grows the maze outward from a starting cell, like a crystal forming in solution. It maintains a frontier of walls adjacent to the visited region. At each step, it picks a random frontier wall and, if it connects to an unvisited cell, removes it and adds the new cell's walls to the frontier. The result is a maze that radiates outward in an organic, blob-like growth pattern.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true], visited: false });

const dirs = [[0, -1, 0, 2], [1, 0, 1, 3], [0, 1, 2, 0], [-1, 0, 3, 1]];
// [dx, dy, wall of current, wall of neighbor]

const frontier = [];

function addFrontier(cell) {
  cell.visited = true;
  for (const [dx, dy, w1, w2] of dirs) {
    const nx = cell.x + dx, ny = cell.y + dy;
    if (nx >= 0 && ny >= 0 && nx < cols && ny < rows) {
      const ni = ny * cols + nx;
      if (!grid[ni].visited) {
        frontier.push({ from: cell, to: grid[ni], w1, w2 });
      }
    }
  }
}

// Start from center
const startCell = grid[Math.floor(rows / 2) * cols + Math.floor(cols / 2)];
addFrontier(startCell);

function step() {
  if (frontier.length === 0) { draw(); return; }

  // Pick random frontier wall
  const i = Math.floor(Math.random() * frontier.length);
  const { from, to, w1, w2 } = frontier[i];
  frontier.splice(i, 1);

  if (!to.visited) {
    from.walls[w1] = false;
    to.walls[w2] = false;
    addFrontier(to);
  }

  draw();
  requestAnimationFrame(step);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    if (cell.visited) {
      ctx.fillStyle = '#1a2e1a';
      ctx.fillRect(x, y, cellW, cellH);
    }
    ctx.strokeStyle = '#2ecc71';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
  // Highlight frontier cells
  ctx.fillStyle = 'rgba(46, 204, 113, 0.3)';
  for (const f of frontier) {
    if (!f.to.visited) {
      ctx.fillRect(f.to.x * cellW, f.to.y * cellH, cellW, cellH);
    }
  }
}

step();

Prim's produces very branchy mazes similar to Kruskal's, but with a distinctive visual quality: the maze grows outward from the start like a bacterial colony. Shorter dead ends, more uniform branching. The frontier-based expansion makes it especially satisfying to animate — you can see the maze "growing" in real time.

4. Eller's algorithm — row by row, infinite mazes

Eller's algorithm is remarkable: it generates a perfect maze one row at a time, using only the current and previous row in memory. This means it can generate infinitely tall mazes in O(1) memory. Each cell belongs to a set (like Kruskal's), and the algorithm randomly merges sets within a row, then extends sets downward to the next row while ensuring connectivity.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true] });

// Eller's: process row by row
let sets = new Array(cols).fill(0).map((_, i) => i);
let nextSet = cols;

function processRow(row) {
  // Randomly merge adjacent cells in the same row
  for (let x = 0; x < cols - 1; x++) {
    if (sets[x] !== sets[x + 1] && Math.random() < 0.5) {
      const oldSet = sets[x + 1];
      const newSet = sets[x];
      for (let i = 0; i < cols; i++) {
        if (sets[i] === oldSet) sets[i] = newSet;
      }
      // Remove wall between x and x+1
      grid[row * cols + x].walls[1] = false;
      grid[row * cols + x + 1].walls[3] = false;
    }
  }

  if (row === rows - 1) {
    // Last row: merge all remaining separate sets
    for (let x = 0; x < cols - 1; x++) {
      if (sets[x] !== sets[x + 1]) {
        const oldSet = sets[x + 1];
        const newSet = sets[x];
        for (let i = 0; i < cols; i++) {
          if (sets[i] === oldSet) sets[i] = newSet;
        }
        grid[row * cols + x].walls[1] = false;
        grid[row * cols + x + 1].walls[3] = false;
      }
    }
    return;
  }

  // Extend sets downward: each set must have at least one vertical connection
  const setMembers = {};
  for (let x = 0; x < cols; x++) {
    if (!setMembers[sets[x]]) setMembers[sets[x]] = [];
    setMembers[sets[x]].push(x);
  }

  const nextSets = new Array(cols).fill(-1);
  for (const [setId, members] of Object.entries(setMembers)) {
    // At least one member must extend down
    const shuffled = [...members].sort(() => Math.random() - 0.5);
    const extendCount = Math.max(1, Math.floor(Math.random() * members.length) + 1);
    for (let i = 0; i < shuffled.length; i++) {
      const x = shuffled[i];
      if (i < extendCount) {
        // Extend down
        grid[row * cols + x].walls[2] = false;
        grid[(row + 1) * cols + x].walls[0] = false;
        nextSets[x] = Number(setId);
      }
    }
  }

  // Assign new sets to cells not extended
  for (let x = 0; x < cols; x++) {
    if (nextSets[x] === -1) nextSets[x] = nextSet++;
  }
  sets = nextSets;
}

// Animate row by row
let currentRow = 0;
function step() {
  processRow(currentRow);
  currentRow++;
  draw();
  if (currentRow < rows) requestAnimationFrame(step);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    if (cell.y < currentRow) {
      ctx.fillStyle = '#2e1a2e';
      ctx.fillRect(x, y, cellW, cellH);
    }
    ctx.strokeStyle = '#e056a0';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
}

step();

Eller's is the most memory-efficient maze algorithm: O(width) space regardless of height. It was invented by Marlin Eller in the 1980s and remains the best choice for generating infinite scrolling mazes in games. The visual character is balanced — neither as winding as the backtracker nor as branchy as Kruskal's. Watch the animation: each row appears fully formed, like a loom weaving a textile.

5. Recursive division — top-down fractal walls

While most maze algorithms work bottom-up (starting with all walls and removing them), recursive division works top-down: start with an empty room and recursively add walls with single-cell passages. Bisect the space horizontally or vertically, leave one gap, then recurse on the two halves. The result has a distinctive rectilinear look — long straight walls that reveal the fractal subdivision structure.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const hWalls = []; // horizontal walls: hWalls[y][x] = wall below cell (x, y)
const vWalls = []; // vertical walls: vWalls[y][x] = wall right of cell (x, y)
for (let y = 0; y < rows; y++) {
  hWalls[y] = new Array(cols).fill(false);
  vWalls[y] = new Array(cols).fill(false);
}

// Add border walls
const steps = [];

function divide(x1, y1, x2, y2) {
  const w = x2 - x1, h = y2 - y1;
  if (w < 2 && h < 2) return;

  // Choose orientation: prefer splitting the longer dimension
  const horizontal = h > w ? true : w > h ? false : Math.random() < 0.5;

  if (horizontal && h >= 2) {
    // Draw horizontal wall
    const wy = y1 + 1 + Math.floor(Math.random() * (h - 1));
    const gap = x1 + Math.floor(Math.random() * w);
    for (let x = x1; x < x2; x++) {
      if (x !== gap) {
        steps.push({ type: 'h', x, y: wy - 1 });
      }
    }
    divide(x1, y1, x2, wy);
    divide(x1, wy, x2, y2);
  } else if (w >= 2) {
    // Draw vertical wall
    const wx = x1 + 1 + Math.floor(Math.random() * (w - 1));
    const gap = y1 + Math.floor(Math.random() * h);
    for (let y = y1; y < y2; y++) {
      if (y !== gap) {
        steps.push({ type: 'v', x: wx - 1, y });
      }
    }
    divide(x1, y1, wx, y2);
    divide(wx, y1, x2, y2);
  }
}

divide(0, 0, cols, rows);

// Animate
let stepIdx = 0;
function animate() {
  const batch = Math.min(8, steps.length - stepIdx);
  for (let i = 0; i < batch; i++) {
    const s = steps[stepIdx++];
    if (s.type === 'h') hWalls[s.y][s.x] = true;
    else vWalls[s.y][s.x] = true;
  }
  draw();
  if (stepIdx < steps.length) requestAnimationFrame(animate);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  ctx.fillStyle = '#1a1a2e';
  ctx.fillRect(0, 0, cols * cellW, rows * cellH);

  ctx.strokeStyle = '#f1c40f';
  ctx.lineWidth = 2;

  // Border
  ctx.strokeRect(0, 0, cols * cellW, rows * cellH);

  // Internal walls
  for (let y = 0; y < rows; y++) {
    for (let x = 0; x < cols; x++) {
      if (hWalls[y][x]) {
        ctx.beginPath();
        ctx.moveTo(x * cellW, (y + 1) * cellH);
        ctx.lineTo((x + 1) * cellW, (y + 1) * cellH);
        ctx.stroke();
      }
      if (vWalls[y][x]) {
        ctx.beginPath();
        ctx.moveTo((x + 1) * cellW, y * cellH);
        ctx.lineTo((x + 1) * cellW, (y + 1) * cellH);
        ctx.stroke();
      }
    }
  }
}

animate();

Recursive division produces mazes with a distinctive "room and corridor" feel. The long straight walls are immediately recognizable — you can see the binary space partition in the structure. This makes it less natural-looking than the backtracker but perfect for architectural floor plans, dungeon generators, or any context where rectilinear structure is desirable. It runs in O(n) time and is the only common maze algorithm that works by adding walls rather than removing them.

6. Growing tree — tunable character

The growing tree algorithm is a generalization that can behave like the recursive backtracker, like Prim's, or anything in between. It maintains a list of active cells. At each step, it selects a cell from the list (the selection strategy determines the maze's character), picks a random unvisited neighbor, and connects them. Select the most recent cell: you get the backtracker. Select randomly: you get Prim's. Mix both: you get something in between.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true], visited: false });

const dirMap = [[0, -1, 0, 2], [1, 0, 1, 3], [0, 1, 2, 0], [-1, 0, 3, 1]];
const active = [];

function getNeighbors(cell) {
  return dirMap.map(([dx, dy, w1, w2]) => {
    const nx = cell.x + dx, ny = cell.y + dy;
    if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) return null;
    const n = grid[ny * cols + nx];
    return n.visited ? null : { cell: n, w1, w2 };
  }).filter(Boolean);
}

// Start
const start = grid[0];
start.visited = true;
active.push(start);

// Selection strategy: 75% newest (backtracker-like), 25% random (Prim's-like)
function selectIndex() {
  return Math.random() < 0.75 ? active.length - 1 : Math.floor(Math.random() * active.length);
}

function step() {
  if (active.length === 0) { draw(); return; }

  const i = selectIndex();
  const cell = active[i];
  const neighbors = getNeighbors(cell);

  if (neighbors.length > 0) {
    const { cell: next, w1, w2 } = neighbors[Math.floor(Math.random() * neighbors.length)];
    cell.walls[w1] = false;
    next.walls[w2] = false;
    next.visited = true;
    active.push(next);
  } else {
    active.splice(i, 1);
  }

  draw();
  requestAnimationFrame(step);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    if (cell.visited) {
      ctx.fillStyle = '#1a2e2e';
      ctx.fillRect(x, y, cellW, cellH);
    }
    ctx.strokeStyle = '#00cec9';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
  // Active cells glow
  ctx.fillStyle = 'rgba(0, 206, 201, 0.3)';
  for (const c of active) {
    ctx.fillRect(c.x * cellW + 1, c.y * cellH + 1, cellW - 2, cellH - 2);
  }
}

step();

The growing tree is the Swiss army knife of maze generation. By adjusting the selection probability — newest vs. random vs. oldest — you can smoothly interpolate between very different maze textures. A 50/50 split produces mazes that are neither too winding nor too branchy. Game developers love this algorithm because one parameter gives them full control over the maze's feel.

7. Wilson's algorithm — uniform spanning tree

Wilson's algorithm produces an unbiased sample from the uniform distribution over all possible spanning trees of the grid. In other words, every possible maze is equally likely. It works by performing loop-erased random walks: start from a random unvisited cell, walk randomly until you reach the visited region, then add the walk (with loops removed) to the maze. The animation is mesmerizing: random walks wander aimlessly, sometimes for ages, before finally connecting.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true], inMaze: false });

const dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]];
const wallIdx = [[0, 2], [1, 3], [2, 0], [3, 1]]; // [from, to] wall indices

// Mark a random cell as in the maze
grid[Math.floor(Math.random() * grid.length)].inMaze = true;

// Find unvisited cells
function getUnvisited() {
  const unv = grid.filter(c => !c.inMaze);
  return unv.length > 0 ? unv[Math.floor(Math.random() * unv.length)] : null;
}

let walkPath = [];
let walkFrom = null;
let walking = false;
let walkDir = []; // direction taken from each cell in path

function startWalk() {
  walkFrom = getUnvisited();
  if (!walkFrom) return false;
  walkPath = [walkFrom];
  walkDir = [];
  walking = true;
  return true;
}

function stepWalk() {
  const current = walkPath[walkPath.length - 1];
  // Random neighbor
  const validDirs = [];
  for (let d = 0; d < 4; d++) {
    const nx = current.x + dirs[d][0], ny = current.y + dirs[d][1];
    if (nx >= 0 && ny >= 0 && nx < cols && ny < rows) validDirs.push(d);
  }
  const d = validDirs[Math.floor(Math.random() * validDirs.length)];
  const nx = current.x + dirs[d][0], ny = current.y + dirs[d][1];
  const next = grid[ny * cols + nx];

  // Check for loop
  const loopIdx = walkPath.indexOf(next);
  if (loopIdx >= 0) {
    // Erase loop
    walkPath = walkPath.slice(0, loopIdx + 1);
    walkDir = walkDir.slice(0, loopIdx);
  } else {
    walkDir.push(d);
    walkPath.push(next);
  }

  if (next.inMaze) {
    // Walk reached the maze — carve the path
    for (let i = 0; i < walkPath.length - 1; i++) {
      const c = walkPath[i];
      const di = walkDir[i];
      c.inMaze = true;
      c.walls[wallIdx[di][0]] = false;
      const n = walkPath[i + 1];
      n.walls[wallIdx[di][1]] = false;
    }
    walkPath[walkPath.length - 1].inMaze = true;
    walking = false;
  }
}

startWalk();

function animate() {
  if (walking) {
    for (let i = 0; i < 10; i++) { stepWalk(); if (!walking) break; }
    if (!walking && !startWalk()) { draw(); return; }
  }
  draw();
  requestAnimationFrame(animate);
}

function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    if (cell.inMaze) {
      ctx.fillStyle = '#2e2e1a';
      ctx.fillRect(x, y, cellW, cellH);
    }
    ctx.strokeStyle = '#fdcb6e';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }
  // Show random walk in progress
  if (walking && walkPath.length > 1) {
    ctx.strokeStyle = '#e17055';
    ctx.lineWidth = 3;
    ctx.beginPath();
    ctx.moveTo(walkPath[0].x * cellW + cellW / 2, walkPath[0].y * cellH + cellH / 2);
    for (let i = 1; i < walkPath.length; i++) {
      ctx.lineTo(walkPath[i].x * cellW + cellW / 2, walkPath[i].y * cellH + cellH / 2);
    }
    ctx.stroke();
  }
}

animate();

Wilson's algorithm is mathematically special: it's the only standard algorithm that produces a perfectly uniform random spanning tree. The catch is that it can be slow to start — the first few random walks may wander for a long time before hitting the tiny maze region. But as more cells join the maze, walks terminate faster. The visual character is beautifully balanced: neither too winding nor too branchy, just the statistically average maze for the given grid. David Bruce Wilson published this algorithm in 1996.

8. Maze solver — A* pathfinding with animation

No maze article is complete without solving them. A* (A-star) is the gold standard for pathfinding: it combines the actual cost from the start with a heuristic estimate to the goal, always expanding the most promising cell first. With Manhattan distance as the heuristic (admissible for grid mazes), A* finds the shortest path guaranteed. We'll generate a maze with the recursive backtracker, then solve it with an animated A* search.

const canvas = document.createElement('canvas');
canvas.width = 800; canvas.height = 600;
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');

const cols = 40, rows = 30, cellW = 20, cellH = 20;
const grid = [];
for (let y = 0; y < rows; y++)
  for (let x = 0; x < cols; x++)
    grid.push({ x, y, walls: [true, true, true, true], visited: false });

function idx(x, y) {
  if (x < 0 || y < 0 || x >= cols || y >= rows) return -1;
  return y * cols + x;
}

// Generate maze with recursive backtracker (instant)
const stack = [];
let cur = grid[0];
cur.visited = true;
stack.push(cur);
while (stack.length > 0) {
  const neighbors = [[0,-1],[1,0],[0,1],[-1,0]]
    .map(([dx,dy]) => grid[idx(cur.x+dx, cur.y+dy)])
    .filter(n => n && !n.visited);
  if (neighbors.length > 0) {
    const next = neighbors[Math.floor(Math.random() * neighbors.length)];
    stack.push(cur);
    const dx = cur.x - next.x, dy = cur.y - next.y;
    if (dx===1) { cur.walls[3]=false; next.walls[1]=false; }
    if (dx===-1) { cur.walls[1]=false; next.walls[3]=false; }
    if (dy===1) { cur.walls[0]=false; next.walls[2]=false; }
    if (dy===-1) { cur.walls[2]=false; next.walls[0]=false; }
    next.visited = true;
    cur = next;
  } else {
    cur = stack.pop();
  }
}

// A* pathfinding
const startCell = grid[0];
const endCell = grid[grid.length - 1];

const gScore = new Map();
const fScore = new Map();
const cameFrom = new Map();
const openSet = new Set([startCell]);
const closedSet = new Set();

gScore.set(startCell, 0);
fScore.set(startCell, Math.abs(endCell.x - startCell.x) + Math.abs(endCell.y - startCell.y));

let solved = false;
let solutionPath = [];

function solveStep() {
  if (openSet.size === 0 || solved) return;

  // Find cell in openSet with lowest fScore
  let current = null, minF = Infinity;
  for (const cell of openSet) {
    const f = fScore.get(cell) || Infinity;
    if (f < minF) { minF = f; current = cell; }
  }

  if (current === endCell) {
    // Reconstruct path
    solved = true;
    let c = endCell;
    while (c) { solutionPath.unshift(c); c = cameFrom.get(c); }
    return;
  }

  openSet.delete(current);
  closedSet.add(current);

  // Check accessible neighbors (no wall between)
  const checkDirs = [
    [0, -1, 0], [1, 0, 1], [0, 1, 2], [-1, 0, 3]
  ];
  for (const [dx, dy, wallIdx] of checkDirs) {
    if (current.walls[wallIdx]) continue; // wall blocks
    const ni = idx(current.x + dx, current.y + dy);
    if (ni < 0) continue;
    const neighbor = grid[ni];
    if (closedSet.has(neighbor)) continue;

    const tentG = (gScore.get(current) || 0) + 1;
    if (tentG < (gScore.get(neighbor) || Infinity)) {
      cameFrom.set(neighbor, current);
      gScore.set(neighbor, tentG);
      fScore.set(neighbor, tentG + Math.abs(endCell.x - neighbor.x) + Math.abs(endCell.y - neighbor.y));
      openSet.add(neighbor);
    }
  }
}

function animate() {
  for (let i = 0; i < 5; i++) solveStep();
  draw();
  if (!solved || solutionPath.length > 0) requestAnimationFrame(animate);
}

let pathAnimIdx = 0;
function draw() {
  ctx.fillStyle = '#0a0a0a';
  ctx.fillRect(0, 0, 800, 600);

  // Closed set (explored)
  ctx.fillStyle = 'rgba(116, 185, 255, 0.15)';
  for (const cell of closedSet) {
    ctx.fillRect(cell.x * cellW, cell.y * cellH, cellW, cellH);
  }

  // Open set (frontier)
  ctx.fillStyle = 'rgba(255, 234, 167, 0.3)';
  for (const cell of openSet) {
    ctx.fillRect(cell.x * cellW, cell.y * cellH, cellW, cellH);
  }

  // Solution path
  if (solved && solutionPath.length > 1) {
    ctx.strokeStyle = '#ff6b6b';
    ctx.lineWidth = 4;
    ctx.lineCap = 'round';
    ctx.beginPath();
    ctx.moveTo(solutionPath[0].x * cellW + cellW/2, solutionPath[0].y * cellH + cellH/2);
    for (let i = 1; i < solutionPath.length; i++) {
      ctx.lineTo(solutionPath[i].x * cellW + cellW/2, solutionPath[i].y * cellH + cellH/2);
    }
    ctx.stroke();
  }

  // Walls
  for (const cell of grid) {
    const x = cell.x * cellW, y = cell.y * cellH;
    ctx.strokeStyle = '#636e72';
    ctx.lineWidth = 2;
    if (cell.walls[0]) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + cellW, y); ctx.stroke(); }
    if (cell.walls[1]) { ctx.beginPath(); ctx.moveTo(x + cellW, y); ctx.lineTo(x + cellW, y + cellH); ctx.stroke(); }
    if (cell.walls[2]) { ctx.beginPath(); ctx.moveTo(x + cellW, y + cellH); ctx.lineTo(x, y + cellH); ctx.stroke(); }
    if (cell.walls[3]) { ctx.beginPath(); ctx.moveTo(x, y + cellH); ctx.lineTo(x, y); ctx.stroke(); }
  }

  // Start and end markers
  ctx.fillStyle = '#2ecc71';
  ctx.fillRect(startCell.x * cellW + 4, startCell.y * cellH + 4, cellW - 8, cellH - 8);
  ctx.fillStyle = '#e74c3c';
  ctx.fillRect(endCell.x * cellW + 4, endCell.y * cellH + 4, cellW - 8, cellH - 8);
}

animate();

The A* solver visualization reveals the maze's structure: the blue explored region shows where A* searched, the yellow frontier shows its current candidates, and the red path shows the optimal solution. In a well-generated maze, A* explores a surprisingly small fraction of the total cells before finding the solution — the heuristic guides it efficiently toward the goal. For game development, A* with Manhattan distance is the standard choice for grid-based pathfinding.

Maze generation algorithms compared

Each algorithm produces a distinct visual texture:

  • Recursive backtracker: long winding passages, high "river" factor, few short dead ends. Best for cave-like exploration mazes.
  • Kruskal's: uniform branching, many short dead ends, low river factor. Best for organic, coral-like patterns.
  • Prim's: similar to Kruskal's but grows outward from a point. Best for radial, colony-like growth animations.
  • Eller's: balanced texture, O(1) memory per row. Best for infinite or very large mazes.
  • Recursive division: long straight walls, room-like structure. Best for architectural layouts.
  • Growing tree: tunable from backtracker to Prim's. Best when you need control over the maze's feel.
  • Wilson's: perfectly unbiased, statistically average texture. Best for mathematical fairness.

A property shared by all seven: they produce perfect mazes — spanning trees of the grid graph where every cell is reachable and there are no loops. This means exactly one path between any two cells. To create mazes with multiple solutions, you can remove a few random walls after generation, creating loops that add ambiguity.

The mathematics behind mazes

A maze on an n×m grid is a spanning tree of the grid graph G = (V, E) where V = n×m cells and E connects each cell to its 4-connected neighbors. The number of possible spanning trees for a rectangular grid grows astronomically — for a 5×5 grid, there are 4,960,832 possible mazes. For a 10×10 grid, the number exceeds 10^48. Kirchhoff's matrix tree theorem gives the exact count as a determinant of the graph Laplacian, but the numbers are too large to enumerate for any practical grid size.

This is why Wilson's algorithm is so remarkable: it samples uniformly from this incomprehensibly large space of possible mazes, using only random walks and loop erasure.

Maze generation in practice — game design tips

  • Dead end density: more dead ends (Kruskal's/Prim's) = easier mazes. Fewer dead ends (backtracker) = harder, more winding mazes.
  • Solution length: the backtracker tends to produce the longest solution paths. Recursive division produces shorter ones with many rooms.
  • Difficulty control: the growing tree algorithm gives you a single slider (newest vs. random selection) that controls difficulty smoothly.
  • Visual variety: generate with one algorithm, then "braid" the maze by removing random dead-end walls. This creates loops and makes the maze less frustrating.
  • Non-rectangular grids: all these algorithms work on any graph. Hexagonal grids, circular grids, 3D grids, torus topology — just change the neighbor function.
  • Weighting: add weights to edges before running Kruskal's or Prim's. Use Perlin noise for weights to create mazes with organic density variation — dense tangles in some areas, open spaces in others.

Where to go from here

  • Combine maze generation with procedural generation for dungeon layouts — use BSP for rooms and recursive backtracker for connecting corridors
  • Explore cellular automata for cave-like level generation that complements maze algorithms
  • Apply maze algorithms to mathematical art — generate mazes on Penrose tilings, hyperbolic planes, or 4D cubes projected into 2D
  • Use Perlin noise to weight maze edges, creating organic density variation where some regions are dense tangles and others are open spaces
  • Add color theory to maze visualizations — gradient-fill solution paths by distance, or use complementary colors for walls and passages
  • Animate mazes with Bézier curves — replace straight corridor walls with smooth spline curves for an organic, hand-drawn look
  • On Lumitree, several micro-worlds use maze generation — labyrinth explorers where visitors navigate generated mazes, procedural dungeon crawlers, and abstract art pieces built from recursive division patterns

Related articles

Procedural Generation: How to Create Infinite Worlds With Code
A complete guide to procedural generation — the algorithms behind infinite game worlds, generative art, and adaptive content. Covers noise-based terrain, wave function collapse, cellular automata, BSP dungeons, L-systems, Poisson disc sampling, random walks, and marching squares. 8 working code examples.
Cellular Automata: How to Create Emergent Art From Simple Rules With Code
Learn how cellular automata like Conway's Game of Life, Rule 30, and Langton's Ant create stunning emergent patterns from minimal rules. 8 interactive code examples using HTML Canvas.
Pathfinding Algorithm: How to Visualize A*, Dijkstra, and BFS With Code
Learn how to build interactive pathfinding visualizations with JavaScript and Canvas. 8 code examples: BFS, Dijkstra, A* search, diagonal movement, maze solving, weighted terrain, bidirectional search, and an interactive playground.
Wave Function Collapse: How to Generate Infinite Tile-Based Worlds With Code
Learn how to implement Wave Function Collapse (WFC) with JavaScript and Canvas. 8 code examples: basic tile constraints, simple WFC solver, terrain generation, city blocks, platformer levels, pipe networks, pixel art patterns, and interactive tilemap editor.