Maze generation and pathfinding

Start with a small maze

Use 7 × 5 cells and seed 2. Play generation: the stack follows a branch, retreats from a dead end and resumes an unfinished branch. It finishes only after visiting the whole grid. Reaching T while carving does not stop the generator.

After generation, run BFS to see distance layers, then DFS on the same maze to see a branch and its backtracking. The results table keeps both runs while the maze and endpoints stay the same. The root of generation is always the top-left cell; choosing another search start changes only the search.

1. Pause, step in either direction, then seek to inspect the queue or stack at that position.
2. Choose Select start or Select exit and click a cell, or edit its one-based column and row. Use Play or Find path after editing the fields. Picking a cell prepares a fresh search on pause.
3. Zoom and drag to inspect large grids. Follow keeps the current cell visible for generation and DFS; it is unavailable for BFS because the wave has several branches. Manual movement turns following off.

Cells are vertices, passages are edges

A width × height grid contains N = width · height logical cells. Each cell can have four geometric neighbors; movement is allowed only across an open passage. There are no diagonal steps or edge weights: every move costs one. Walls do not occupy additional vertices.

Cell id is row · width + column, with zero-based coordinates in code. The player and JSON endpoints use one-based coordinates. S and T are cell markers, not holes in the outer boundary. For example, in a 7-column maze, (column 1, row 2) has id 7.

Four bits store CLOSED walls: north = 1, east = 2, south = 4, west = 8. Mask 15 closes all four sides. Opening an east passage clears bit 2 in one cell and bit 8 in its neighbor. Both sides must agree, and the outside boundary stays closed. The site validates these rules when loading JSON.

JavaScript

// Directions: north, east, south, west. A set bit means a closed wall.
const WALL = [1, 2, 4, 8];
const DX = [0, 1, 0, -1], DY = [-1, 0, 1, 0];
function neighbor(maze, cell, direction) {
    const x = cell % maze.width + DX[direction];
    const y = Math.floor(cell / maze.width) + DY[direction];
    return x < 0 || x >= maze.width || y < 0 || y >= maze.height
        ? -1 : y * maze.width + x;
}
function seededRandom(seed) {
    let state = seed >>> 0;
    return () => {
        state = (state + 0x6d2b79f5) >>> 0;
        let value = Math.imul(state ^ (state >>> 15), state | 1);
        value ^= value + Math.imul(value ^ (value >>> 7), value | 61);
        return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
    };
}

Randomized DFS carves passages and backtracks

Initially all walls are closed. Mark the top-left cell visited and push its call frame. On entering each cell, shuffle the four directions once with Fisher–Yates. A frame remembers that order and the next direction to inspect. An explicit stack reproduces recursive backtracking without consuming the JavaScript call stack.

The next code block uses the helpers above. It is synchronous algorithm code for valid inputs, without the player's validation, immutable result wrappers, animation events or history. Pass positive integer dimensions and a uint32 seed; the site additionally limits each side to 201 cells.

1. Inspect the next direction of the top frame. Skip an out-of-bounds or already visited neighbor.
2. For an unvisited neighbor, remove the shared wall on both sides, mark the neighbor and push its newly shuffled frame.
3. When a frame has inspected all four directions, pop it and resume its parent. Continue until the stack is empty.

JavaScript

function generateMaze(width, height, seed) {
    const maze = { width, height, walls: new Uint8Array(width * height).fill(15) };
    const visited = new Uint8Array(width * height), random = seededRandom(seed);
    function frame(cell) {
        const directions = [0, 1, 2, 3];
        for (let i = 3; i > 0; i--) {
            const j = Math.floor(random() * (i + 1));
            [directions[i], directions[j]] = [directions[j], directions[i]];
        }
        return { cell, directions, next: 0 };
    }
    const stack = [frame(0)];
    const counters = { visitedCount: 1, passageCount: 0,
        directionChecks: 0, maxStackSize: 1 };
    visited[0] = 1;
    while (stack.length) {
        const call = stack[stack.length - 1];
        if (call.next === 4) { stack.pop(); continue; }
        const d = call.directions[call.next++];
        const next = neighbor(maze, call.cell, d);
        counters.directionChecks++;
        if (next === -1 || visited[next]) continue;
        maze.walls[call.cell] &= ~WALL[d];
        maze.walls[next] &= ~WALL[(d + 2) % 4];
        visited[next] = 1;
        counters.visitedCount++;
        counters.passageCount++;
        stack.push(frame(next));
        counters.maxStackSize = Math.max(counters.maxStackSize, stack.length);
    }
    return { topology: maze, counters };
}

Why a route is guaranteed

Every new passage connects the visited region to exactly one previously unvisited cell. The visited region remains connected, and no passage joins two vertices already in that region, so a cycle cannot appear. The stack represents the current branch of this growing tree.

If any grid cell remained unvisited at termination, the connected rectangular grid would contain a neighboring visited/unvisited pair. The visited cell's frame must have inspected that direction before returning, and would have entered the unvisited cell. This contradiction proves that all N cells are reached.

There are exactly N − 1 passages, and the result is a spanning tree of the grid: exactly one simple route connects any pair of cells. Any valid S and T therefore have a route, including S = T with length zero. This guarantee applies to generated mazes; an imported maze can be disconnected.

A seed reproduces the maze, not a uniform distribution

The implementation uses Mulberry32 with a fixed direction order before each Fisher–Yates shuffle. The same dimensions, seed and generator version reproduce the same maze. Changing playback speed, viewport or search endpoints does not consume random numbers or change its walls. A seed is an integer from 0 to 4294967295; zero is valid.

Randomized DFS does not sample all possible spanning trees uniformly. Shuffling directions removes a fixed directional preference from a call, but does not turn this generator into a uniform spanning-tree sampler. Save JSON when you want to preserve the exact walls independently of future generator versions.

BFS is a wave of shortest distances

Put S into a FIFO queue and assign distance zero. Remove the oldest waiting cell, inspect its north, east, south and west directions, and enqueue each undiscovered neighbor reached through an open passage. Mark it when enqueuing, set its parent once and assign distance[current] + 1. A cycle cannot enqueue the cell a second time.

The queue processes layers in nondecreasing distance order. If a cell at distance d first discovers a neighbor, every shorter layer has already been processed; that neighbor's d + 1 is a shortest distance. On this equal-cost grid, BFS is the wave search commonly associated with Lee's algorithm. The wave propagates through passages rather than geometric proximity across walls.

This player stops when T is removed from the queue and becomes current, before inspecting its directions. Other implementations may stop on discovery; that is also enough to find the distance, but produces different counters. Colors and distance labels show the layers; a live queue may contain waiting cells from adjacent layers.

DFS follows one branch before trying another

The search uses a fixed north–east–south–west order, without randomness. Each frame remembers which direction to inspect next. Discover an unvisited neighbor, record its parent and depth, and enter it immediately. If all four directions are inspected, pop the frame and return to its parent. Returning does not count as another discovery or activation.

The stack contains the unfinished branch from S to the current cell, including both endpoints. This is different from pushing all neighbors at once: explicit suspended calls preserve recursive DFS order. Visited marks remain after a return, so cycles cannot make it loop forever.

Stop on first entry into T. The recorded level is depth in the DFS tree, not generally a shortest distance. In a generated tree the only simple route happens to be shortest; with cycles DFS can take a longer route. It may also reach a nearby-in-its-order target before BFS finishes exploring its wave.

Restore the route through parents

The first discovery of a cell stores the cell it came from. Once T is current, follow parent[T], then the parent's parent, until S. These links point toward an earlier discovery, so they cannot form a cycle. Reverse the collected cells to display a route from S to T.

The animation adds path cells from T back toward S; the completed route is presented in the opposite order. Path length counts transitions: path.length − 1, not the number of cells. For S = T the route is [S] and its length is zero. If the frontier empties without reaching T, the result is No path, an empty route and null length. No route is declared impossible merely because the animation has not reached it yet.

7 × 5, seed 2: the same route, different work

With S = (1, 1) and T = (7, 5), generation visits 35 cells, opens 34 passages and inspects 140 directions; the largest generation stack has 29 frames. These values describe a completed generation, not a search stopped at T.

Both searches restore ids 0 → 1 → 2 → 9 → 10 → 3 → 4 → 11 → 12 → 13 → 20 → 27 → 34: 13 cells and 12 transitions. DFS backtracks from other branches too; its walked animation is not the final route. In this example both methods discover 15 cells, but inspect different numbers of directions.

What the counters actually measure

Discovery is the first mark, including S. Activation is the first time a discovered cell becomes current. A cell can wait in the BFS queue when the target is reached; therefore discovered and activated counts need not match. Path restoration changes neither count.

A direction check includes an outside boundary, a closed wall and an already discovered neighbor. Each fully processed cell inspects four directions. Completed generation checks exactly 4N directions; a search can stop before that. BFS excludes the current cell from the waiting queue; DFS includes it in its call stack.

The comparison table is meaningful only for the same walls, endpoints and neighbor order. Queue and stack peaks are different structures, not a measurement of total memory. Animation duration is controlled by event granularity and speed: it is not a benchmark of BFS against DFS.

Import a cycle to reveal a longer DFS route

Save the JSON below as a file and use Load JSON. It contains a 3 × 2 cycle with S = (1, 1) and T = (1, 2). BFS takes the direct southern passage: ids [0, 3], one transition. DFS tries east first and finds [0, 1, 2, 5, 4, 3], five transitions. Both results are valid; only BFS guarantees the shortest one.

The file can also describe disconnected regions. A valid file keeps symmetric shared walls and a closed outside boundary, but need not be connected or acyclic. Loading it prepares search on pause; no imaginary generation is shown. Save JSON exports the finished topology and chosen endpoints/method, not the intermediate carving frame.

JSON

{
  "format": "grundyjs-maze", "version": 1,
  "width": 3, "height": 2,
  "walls": [9, 1, 3, 12, 4, 6],
  "start": { "column": 1, "row": 1 },
  "target": { "column": 1, "row": 2 },
  "method": "bfs"
}

JavaScript: the same search rules without animation

Run this block after the model helpers. It accepts a validated maze, valid zero-based start/target ids and method "bfs" or "dfs". Both methods share the same discovery rules and stop on activation of T, as the player does. cursor remembers the next direction, parent restores the route, and levels doubles as a discovered mark.

BFS uses an array with a head index instead of repeatedly shifting its contents. Processed entries remain allocated, although the displayed queue size excludes them. DFS uses the same array as a call stack. The website additionally emits small immutable events and validates/copies inputs; those layers are intentionally absent from this executable teaching version.

JavaScript

function searchMaze(maze, start, target, method = "bfs") {
    const count = maze.walls.length;
    const parent = new Int32Array(count).fill(-1);
    const levels = new Int32Array(count).fill(-1);
    const cursor = new Uint8Array(count), frontier = [start];
    const counters = { discoveredCount: 1, activatedCount: 0,
        finishedCount: 0, directionChecks: 0, maxFrontierSize: 1 };
    let head = 0, current = -1, found = false;
    const size = () => method === "bfs" ? frontier.length - head : frontier.length;
    levels[start] = 0;
    while (current !== -1 || size() > 0) {
        if (current === -1) {
            current = method === "bfs" ? frontier[head++] : frontier[frontier.length - 1];
            counters.activatedCount++;
            if (current === target) { found = true; break; }
        }
        if (cursor[current] === 4) {
            counters.finishedCount++;
            if (method === "bfs") current = -1;
            else { frontier.pop(); current = frontier.at(-1) ?? -1; }
            continue;
        }
        const d = cursor[current]++, next = neighbor(maze, current, d);
        counters.directionChecks++;
        if (next === -1 || (maze.walls[current] & WALL[d]) || levels[next] !== -1) continue;
        parent[next] = current;
        levels[next] = levels[current] + 1;
        counters.discoveredCount++;
        frontier.push(next);
        counters.maxFrontierSize = Math.max(counters.maxFrontierSize, size());
        if (method === "dfs") current = -1;
    }
    const path = [];
    if (found) {
        for (let cell = target; cell !== -1; cell = parent[cell]) path.push(cell);
        path.reverse();
    }
    return { found, path, pathLength: found ? path.length - 1 : null,
        parent, levels, counters };
}

Run and compare the examples

Paste the model, generation and search blocks in that order into the same JavaScript scope, then run this example. The site's checks compare these exact article snippets with the real algorithm core, including walls, routes, levels, parents and counters.

JavaScript

// Run after the three code blocks above, in the same scope.
const generated = generateMaze(7, 5, 2);
const bfs = searchMaze(generated.topology, 0, 34, "bfs");
const dfs = searchMaze(generated.topology, 0, 34, "dfs");
console.log(bfs.pathLength, dfs.pathLength); // 12, 12

// A cyclic 3 x 2 maze: a direct edge 0-3 and a longer route around it.
const cyclic = { width: 3, height: 2, walls: [9, 1, 3, 12, 4, 6] };
console.log(searchMaze(cyclic, 0, 3, "bfs").path); // [0, 3]
console.log(searchMaze(cyclic, 0, 3, "dfs").path); // [0, 1, 2, 5, 4, 3]

Linear algorithms, separate playback costs

Let N = width · height and E be the number of open undirected passages. A grid vertex has at most four neighbors, so E ≤ 2N − width − height. Generation visits each cell once and checks four directions: O(N) time. BFS and DFS take O(N + E), hence O(N) here, in the worst case. Initializing full-grid arrays already costs O(N), even when the target is near the start.

All three implementations use O(N) working memory. Generation may have N frames; BFS retains visited marks, parents, distances and its queue storage; DFS retains marks, parents, depths, cursors and up to N frames. Restoring a route of L transitions takes O(L + 1) additional time and output space. None of these bounds include retained animation history or the canvas bitmap.

How the player handles large histories

The visualizer records compact events instead of a full grid after every action. Sparse checkpoints and a current working state support seeking: restore a preceding checkpoint and replay the missing events in slices. A newer request cancels the old seek, so an older task cannot overwrite the latest position.

The history pool shares a 32 MiB limit between generation and the current search. Under pressure it drops extra checkpoints, trading seek speed for retained-buffer space; this is not a limit on the whole tab's memory. The canvas draws visible cells and reuses viewport pixels during small pans, but a full overview or long seek can still be expensive.

Use the 7 × 5 example to understand individual actions, and larger grids to inspect the overall structure. At a small fit scale, zoom in to read passages and distances. Playback may skip intermediate display frames at high speed while still applying events in order. This does not change the generated maze or the search result.

Sources

Algorithm background: backtracking generation and BFS shortest paths. The wall masks, seed rules, counters and playback described here belong to this site's implementation.

• Jamis Buck — Maze Generation: Recursive Backtracking
• Sedgewick & Wayne — BreadthFirstPaths