Maze generation: DFS, randomized Prim and Kruskal

A maze is a spanning tree

Think of cells as vertices and interior walls as possible edges. Opening a wall adds a passage. Each generator connects all cells without creating a cycle, giving a perfect maze: exactly one route between any two cells. A grid with N cells has N−1 open passages. Exterior walls stay closed in this example; generation does not require drawing an entrance or searching for an exit.

The default grid is 9×7: 63 cells and 110 interior walls. Every completed generator opens 62 of them. The order and final passage layout can differ, while all three results satisfy the same connectivity and acyclicity conditions.

DFS: continue the active branch

Start at the top-left cell. Choose a random unvisited geometric neighbour, open the wall and push that neighbour onto the stack. With no unvisited neighbours, pop the stack and return to its previous cell. In this comparison generation stops as soon as all cells are connected; unwinding the final stack would not change the maze.

Blue passages record the carved tree; its brighter branch is the current stack. Popping a cell dims the exhausted branch immediately. This rule often produces long winding branches, but a particular seed is not a promise about every maze. This variant chooses among currently unvisited neighbours; its seed need not reproduce the separate DFS page’s shuffled-direction variant.

Randomized Prim: choose from the whole boundary

Start at the same cell. Put its incident walls into a candidate bag. Pick a random candidate and remove it by swapping with the last entry. If the far cell is new, open the wall, add that cell and enqueue its incident walls once. If both endpoints are already included, discard the stale candidate. Dotted lines show all current crossing edges, not successive positions of a moving traveller.

This is the random-boundary variant: there are no numerical edge weights to minimize. Giving fixed random weights to every edge and running ordinary Prim is a different experiment. The generator keeps one growing connected region and tends to branch from many places on its boundary.

Randomized Kruskal: join separate components

Give every cell its own component. Shuffle all interior walls once with Fisher–Yates. Scan that order: remove a wall only when its endpoints belong to different components, then merge them. A wall inside one component stays closed because opening it would form a cycle. The red × marks that rejection. Stop after N−1 passages.

Green passage fragments can appear far apart: they are separate trees of the same growing forest. Unlike Prim, Kruskal does not have a starting cell or a single growth boundary. Union by size with path compression tracks connectivity efficiently.

Read the synchronized comparison

Each animation round selects one action for every unfinished algorithm, then applies those actions together. A DFS stack return, a new passage and a rejected wall are different actions; matching animation ticks are not equivalent units of computation. A completed generator holds its final maze while the others finish.

Size and seed are shared, but each method owns a fresh copy of the deterministic random generator. Different calls consume random values differently, so the same seed means reproducibility of each version, not identical decisions or uniformly sampled spanning trees. Shared links also store the generator version, current tick and playback speed; they reopen paused on the clean player page.

Compare the finished structures

Passages count opened interior walls. Components include still-isolated cells and therefore equal N minus the number of accepted passages throughout the forest. Final dead ends are cells of degree one; junctions have at least three passages. A single-cell maze has zero passages, zero dead ends and zero junctions.

For the default 9×7 grid with seed 34, DFS has 8 dead ends and 6 junctions, Prim has 23 and 20, and Kruskal has 20 and 17. Change seed and compare several completed mazes before drawing conclusions. These counts describe concrete samples, not a universal ranking or a measure of difficulty. These generator variants do not promise a uniform distribution over all possible perfect mazes.

Time, memory and executable code

Let N be the number of cells and E the number of interior walls; on a rectangular grid E<2N. Without history, this DFS and random-boundary Prim take O(N+E) time and memory. Each wall enters Prim’s bag at most once. Kruskal needs O(N+E·α(N)) amortized time, including an O(E) shuffle, and O(N+E) memory. There is no weight sort in this randomized version.

The player additionally copies O(N+E) data per action snapshot. With O(N+E) actions, its stored history costs O((N+E)²) memory and copying time, unlike the result-only generators below. The UI caps size at 225 cells. Export uses the same snapshots and drawing functions; it saves the full comparison from the start at the selected speed, without audio.

function generateMaze(width, height, seed, method) {
  const n = width * height;
  if (!Number.isInteger(width) || !Number.isInteger(height) ||
      width < 1 || width > 21 || height < 1 || height > 15 || n > 225 ||
      !Number.isInteger(seed) || seed < 0 || seed > 0xffffffff ||
      !["dfs", "prim", "kruskal"].includes(method)) throw Error("Invalid input");
  let state = seed >>> 0;
  const random = () => {
    state = (state + 0x6d2b79f5) >>> 0;
    let v = Math.imul(state ^ (state >>> 15), state | 1);
    v ^= v + Math.imul(v ^ (v >>> 7), v | 61);
    return ((v ^ (v >>> 14)) >>> 0) / 0x100000000;
  };
  const edges = [], incident = Array.from({length: n}, () => []);
  const add = (a, b) => {
    incident[a].push(edges.length); incident[b].push(edges.length);
    edges.push({from: a, to: b});
  };
  for (let v = 0; v < n; v++) {
    if (v % width + 1 < width) add(v, v + 1);
    if (v + width < n) add(v, v + width);
  }
  const other = (id, v) => edges[id].from === v ? edges[id].to : edges[id].from;
  incident.forEach((ids, v) => {
    const dir = id => {
      const u = other(id, v);
      return u === v - width ? 0 : u === v + 1 && v % width + 1 < width ? 1 : u === v + width ? 2 : 3;
    };
    ids.sort((a, b) => dir(a) - dir(b));
  });
  const walls = Array(n).fill(15), passages = [], seen = Array(n).fill(false);
  const stack = [0], frontier = [], queued = new Set();
  const enqueue = v => { for (const id of incident[v]) if (!queued.has(id)) {
    queued.add(id); frontier.push(id);
  }};
  const parent = Array.from({length: n}, (_, i) => i), size = Array(n).fill(1);
  const find = x => { while (parent[x] !== x) {
    parent[x] = parent[parent[x]]; x = parent[x];
  } return x; };
  const order = edges.map((_, i) => i);
  if (method === "kruskal") for (let i = order.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1)); [order[i], order[j]] = [order[j], order[i]];
  }
  if (method !== "kruskal") seen[0] = true;
  if (method === "prim") enqueue(0);
  let cursor = 0;
  while (passages.length < n - 1) {
    let id, from, to;
    if (method === "dfs") {
      from = stack[stack.length - 1];
      const choices = incident[from].filter(id => !seen[other(id, from)]);
      if (!choices.length) { stack.pop(); continue; }
      id = choices[Math.floor(random() * choices.length)]; to = other(id, from);
    } else if (method === "prim") {
      const i = Math.floor(random() * frontier.length);
      id = frontier[i]; frontier[i] = frontier[frontier.length - 1]; frontier.pop();
      from = seen[edges[id].from] ? edges[id].from : edges[id].to;
      to = other(id, from); if (seen[to]) continue;
    } else {
      id = order[cursor++]; from = edges[id].from; to = edges[id].to;
      if (find(from) === find(to)) continue;
    }
    const e = edges[id];
    if (e.to === e.from + 1 && e.from % width + 1 < width) {
      walls[e.from] &= ~2; walls[e.to] &= ~8;
    } else { walls[e.from] &= ~4; walls[e.to] &= ~1; }
    passages.push(id); seen[from] = seen[to] = true;
    if (method === "dfs") stack.push(to);
    if (method === "prim") enqueue(to);
    if (method === "kruskal") {
      let a = find(from), b = find(to);
      if (size[a] < size[b]) [a, b] = [b, a];
      parent[b] = a; size[a] += size[b];
    }
  }
  return {edges, passages, walls};
}
// generateMaze(9, 7, 34, "dfs"); // or "prim", "kruskal"