Hard mazes · graphs · randomness

Maze carver

Walk forward until you are stuck, back up, try again: a perfect maze every time.

Write maze(w, h, seed). Return a maze as a grid of (2 * h + 1) rows and (2 * w + 1) columns, with 1 for wall and 0 for open floor. Room (cx, cy), for cx from 0 to w - 1 and cy from 0 to h - 1, lives at row 2 * cy + 1, column 2 * cx + 1. Everything starts as wall.

Carve with a depth-first backtracker. Open room (0, 0), mark it visited and push it on a stack. While the stack is not empty, look at the room on top. List its unvisited neighbour rooms in this order: up (cy - 1), right (cx + 1), down (cy + 1), left (cx - 1), skipping any outside the maze. If there are none, pop. Otherwise roll the dice, pick neighbours[s % count], open the wall cell between the two rooms and the new room, mark it visited and push it.

The dice: keep s, starting at seed, and before each pick update it with s = (s * 48271) % 2147483647. Roll only when there is a choice to make (count of 1 or more).

Call show(grid) after each new room is opened so the stage watches the corridors grow.

Example: maze(2, 1, 1) opens room (0, 0), finds only its right neighbour, rolls s = 48271, takes it, and returns [[1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]].

Tests you can see

maze(2, 1, 1)[[1,1,1,1,1],[1,0,0,0,1],[1,1,1,1,1]]
maze(4, 3, 7)[[1,1,1,1,1,1,1,1,1],[1,0,1,0,0,0,0,0,1],[1,0,1,1,1,0,1,0,1],[1,0,0,0,1,0,1,0,1],[1,1,1,0,1,0,1,0,1],[1,0,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,1,1]]
maze(12, 12, 2026)[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1],[1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1],[1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1],[1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1],[1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1],[1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1],[1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1],[1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1],[1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1],[1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1],[1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1],[1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1],[1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1],[1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1],[1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1],[1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1],[1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1],[1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1],[1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1],[1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1],[1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1],[1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptmaze()

function maze(w, h, seed) {
  const grid = Array.from({ length: 2 * h + 1 }, () => new Array(2 * w + 1).fill(1));
  let s = seed;
  // open (0, 0), then walk with a stack
  return grid;
}

function maze(w, h, seed) {
  const grid = Array.from({ length: 2 * h + 1 }, () => new Array(2 * w + 1).fill(1));
  let s = seed;
  // open (0, 0), then walk with a stack
  return grid;
}

Tab indents · Cmd/Ctrl+Enter runs