How Maze Carving Works

A step-by-step walkthrough of recursive DFS wall carving — from a fully-walled grid to a perfect maze

← back to Saga Index   •   Open Maze 1 while you read →

What this covers: how the grid starts, what a "wall" actually is in memory, what "carving" means, how the DFS frontier (the teal cell) moves, and — the key question — how the algorithm knows exactly where to pick back up after reaching a dead end. No prior code knowledge required; the code snippets are here to show the real thing, not to be memorized.

1. The Starting State — A Fully-Walled Grid

Before a single line of carving code runs, every cell in the maze exists and every wall between every pair of adjacent cells is closed. Think of it as a sheet of graph paper where every single grid line is solid. You can see all the cells, but there are no passages between any of them.

What one cell looks like in memory
// Every cell starts like this: cell = { walls: { N: true, // north wall is UP S: true, // south wall is DOWN E: true, // east wall is RIGHT W: true, // west wall is LEFT }, visited: false // not yet explored }

Key design choice: walls are stored as booleans on each cell, not as separate wall objects. Every wall is shared between two cells — the north wall of cell (1, 0) is the same physical wall as the south wall of (0, 0). When we carve it, we set both booleans to false.

Wall = true means the wall is present (solid, impassable).
Wall = false means the wall has been carved away (open passage).
Carving is a one-way operation — once a wall is removed it stays removed.

The outer boundary walls are never carved — the maze always has a solid perimeter. Only interior walls between two valid cells can be removed.

2. What "Carving" Actually Means

"Carving a wall" is the heart of maze generation. All it means is: set two booleans to false.

// DFS is at cell (r, c) and wants to // carve a passage EAST to cell (r, c+1). // Step 1: open THIS cell's east wall cell(r, c ).walls.E = false; // Step 2: open the NEIGHBOR'S west wall cell(r, c+1).walls.W = false; // That's it. The passage is open. // The cell data model now says: // "you can walk from (r,c) east to (r,c+1)" // "you can walk from (r,c+1) west to (r,c)"

The direction table in SWMaze stores both sides of each wall so the code never has to figure this out manually:

static DIR = { N: { dr:-1, dc: 0, wall:'N', opposite:'S' }, S: { dr: 1, dc: 0, wall:'S', opposite:'N' }, E: { dr: 0, dc: 1, wall:'E', opposite:'W' }, W: { dr: 0, dc:-1, wall:'W', opposite:'E' }, };

So the actual carving code is just: cell.walls[wall] = false and neighbor.walls[opposite] = false.

Mental model: imagine the grid as a city of rooms. Every room starts with four solid concrete walls. Carving means knocking a doorway through one wall (and simultaneously through the matching wall on the other side of the boundary). Once the doorway is open you can walk through it in either direction.

3. The DFS Algorithm — How It Decides Where to Carve

Maze generation uses recursive Depth-First Search (DFS). Here is the complete real code from swMaze.js with annotations:

_generateDFS(r, c) { // STEP 1: Mark this cell visited so we never return to it. this._cells[r][c].visited = true; // STEP 2: Get all four directions in a RANDOM order. const dirs = this._shuffle([...SWMaze.DIRECTIONS]); // STEP 3: Try each direction, one at a time. for (const dir of dirs) { const { dr, dc, wall, opposite } = SWMaze.DIR[dir]; const nr = r + dr; // neighbor row const nc = c + dc; // neighbor col // Skip if out of bounds OR already visited. if (!this._inBounds(nr, nc) || this._cells[nr][nc].visited) continue; // STEP 4: Carve the shared wall (both sides). this._cells[r][c].walls[wall] = false; this._cells[nr][nc].walls[opposite] = false; // Record this carve for the animation playback. this._buildStepQueue.push({ type: 'BUILD_CARVE', fromRow:r, fromCol:c, toRow:nr, toCol:nc, dir }); // STEP 5: Recurse — go explore from the neighbor. this._generateDFS(nr, nc); // STEP 6: The recursion returned — record the backtrack. this._buildStepQueue.push({ type: 'BUILD_BACKTRACK', row:r, col:c }); } // All directions tried. Return — caller handles the backtrack. }
The "visited" flag is the DFS's memory. Once a cell is marked visited, no other branch of the recursion will ever try to carve into it. This is what guarantees the maze is perfect — every cell is reachable, and there are no loops, because each cell is visited from exactly one direction exactly once.
Two separate passes, two separate uses of "visited." After generation finishes, generate() calls _clearVisited() to reset all the flags to false. The solver then reuses the same flag for its own pass. The flag is scratch space — it gets reused, not accumulated.

4. What the Colors Mean During the Build

The demo shows the carving as an animation. Each cell changes color as the algorithm visits it. Here is what each color means:

Color State name What it means When it changes
Light blue-gray 'floor' Cell has not been touched by the DFS yet. All four walls still up. Immediately when carved for the first time.
Cyan / teal 'frontier' Where the DFS pencil tip is right now. This is the most recently carved destination — the cell that _generateDFS is currently running inside. Set to frontier when a BUILD_CARVE step points to it. Cleared to 'carved' when the next BUILD_CARVE step fires from it.
Medium gray 'carved' Cell has been carved and explored. One or more passages open. The DFS has been here and moved on to a neighbor (or will shortly). Set when a BUILD_CARVE fires from this cell (it was frontier, now it moves the frontier forward).
Dark dim blue 'buildback' The DFS backtracked through this cell after fully exhausting all its unvisited neighbors. It is a "dead end from above" — all forward paths from here led back. Set when a BUILD_BACKTRACK step fires and the cell is still the frontier (no further carves came from it).
Green 'start' Cell S — always fixed top-left. Never changes color during build. Never changes during build.
Amber 'treasure' Cell T — always fixed bottom-right. Never changes color during build. Never changes during build.
The teal cell = "where the call stack's top frame is executing." As the DFS dives deeper, the teal cell jumps forward one step at a time. When it reaches a dead end (no unvisited neighbors), it stops jumping — and the gray "carved" trail it left behind is the path back up the call stack.

5. The Big Question — How Does It Know Where to Pick Back Up?

This is the core of recursion. The answer is: the JavaScript call stack remembers exactly where every function call came from and what it was doing. You never have to track it manually — the language does it for you.

Every time _generateDFS(r, c) calls _generateDFS(nr, nc), JavaScript:

  1. Pauses the current function at exactly that line.
  2. Saves everything about the current state: the values of r, c, dirs, and which iteration of the for-loop we're on.
  3. Starts a brand-new call of _generateDFS with the neighbor's coordinates.
  4. When that new call returns, JavaScript automatically restores everything it saved and continues the paused for-loop from exactly where it left off — trying the next direction.
The "where to pick back up" answer in one sentence: The paused for-loop is sitting frozen in memory on the call stack, and JavaScript resumes it the instant the deeper recursive call returns. No bookkeeping needed. The language is the bookkeeper.

Visualizing the call stack growing and shrinking:

After carving deep into one corridor:
_generateDFS(0,0) — trying dir W
_generateDFS(0,1) — trying dir S
_generateDFS(1,1) — trying dir S
_generateDFS(2,1) — RUNNING ← teal cell
After (2,1) exhausts all directions and returns:
_generateDFS(0,0) — trying dir W
_generateDFS(0,1) — trying dir S
_generateDFS(1,1) — resumes here, tries next dir ← teal moves back

6. A Traced Example — a 3×3 Grid

Let's walk through a tiny 3×3 grid manually. Directions are chosen as E, S, W, N at every cell (fixed for this trace — normally they'd be shuffled). S = start at (0,0), T = treasure at (2,2).

Reading cell coordinates: (row, col) where row 0 is the top row and col 0 is the left column. So (0,0) = top-left, (2,2) = bottom-right.
# Event Call stack (bottom→top) What happens visually Walls opened
— generate(0,0) called empty All 9 cells are light gray (floor). S=(0,0) is green, T=(2,2) is amber. —
1 _generateDFS(0,0) starts.
dirs=[E,S,W,N].
Try E → (0,1) is unvisited.		 [DFS(0,0)] (0,1) turns teal. (0,0).E = false
(0,1).W = false
2 Recurse → _generateDFS(0,1).
dirs=[E,S,W,N].
Try E → (0,2) unvisited.		 [DFS(0,0), DFS(0,1)] (0,1) turns gray (carved). (0,2) turns teal. (0,1).E = false
(0,2).W = false
3 Recurse → _generateDFS(0,2).
dirs=[E,S,W,N].
E → OOB. Try S → (1,2) unvisited.		 [DFS(0,0), DFS(0,1), DFS(0,2)] (0,2) turns gray. (1,2) turns teal. (0,2).S = false
(1,2).N = false
4 Recurse → _generateDFS(1,2).
dirs=[E,S,W,N].
E→OOB. Try S → (2,2) unvisited.		 […, DFS(0,2), DFS(1,2)] (1,2) turns gray. (2,2) turns teal. (1,2).S = false
(2,2).N = false
5 Recurse → _generateDFS(2,2).
E→OOB. S→OOB. W→(2,1) unvisited. Try W.		 […, DFS(1,2), DFS(2,2)] (2,2)→T stays amber. (2,1) turns teal. (2,2).W = false
(2,1).E = false
6 Recurse → _generateDFS(2,1).
E→visited. S→OOB. W→(2,0) unvisited. Try W.		 […, DFS(2,2), DFS(2,1)] (2,1)→gray. (2,0) turns teal. (2,1).W = false
(2,0).E = false
7 Recurse → _generateDFS(2,0).
E→visited. S→OOB. W→OOB. N→(1,0) unvisited. Try N.		 […, DFS(2,1), DFS(2,0)] (2,0)→gray. (1,0) turns teal. (2,0).N = false
(1,0).S = false
8 Recurse → _generateDFS(1,0).
E→(1,1) unvisited. Try E.		 […, DFS(2,0), DFS(1,0)] (1,0)→gray. (1,1) turns teal. (1,0).E = false
(1,1).W = false
9 Recurse → _generateDFS(1,1).
E→(1,2) visited. S→(2,1) visited. W→(1,0) visited. N→(0,1) unvisited. Try N.		 […, DFS(1,0), DFS(1,1)] (1,1)→gray. (0,1) is already carved — passage added. (1,1).N = false
(0,1).S = false
10 _generateDFS(0,1): already visited! Wait — (0,1) IS visited.
So DFS(1,1) tries all 4 dirs — all neighbors visited/OOB. Returns.		 […, DFS(1,0)] ← stack shrinks! (1,1) dims to dark blue (buildback). DFS is now back inside DFS(1,0)'s for-loop. —
11 DFS(1,0) tries next dirs: S→visited, W→OOB, N→(0,0) visited. All done. Returns. […, DFS(2,0)] DFS resumes at DFS(2,0)'s for-loop. Stack shrinks further. —
12–… Each remaining call finds all neighbors visited and returns. Stack unwinds all the way back to DFS(0,0). [ ] (empty) The stack fully unwinds. All 9 cells visited. Maze complete! —
Notice row 10: DFS(2,2) carved to (2,1), then (2,1) carved to (2,0), and so on. The entire bottom row and then the left column was explored in one deep dive. When DFS(1,1) ran out of options and returned, execution jumped back to DFS(1,0)'s for-loop — which was sitting frozen exactly where we left it. It tried its next direction, found nothing, and returned too, propagating the unwind all the way back. This is backtracking: the call stack automatically returns to every parent in order, each resuming mid-loop.

7. The "Perfect Maze" Guarantee

After the DFS finishes, the maze is guaranteed to be perfect:

✅ Every cell visited exactly once
The visited flag prevents any cell from being entered from two different directions. There is no second path in.
✅ No loops
A loop would require carving into a visited cell. The if (visited) continue; check prevents this absolutely.
✅ No unreachable cells
DFS starting from (0,0) will always explore all cells in a connected rectangular grid before it finishes.

These three properties together mean: there is exactly one path between any two cells in the finished maze. Because of this, the solver that comes later will always reach T from S — and it will hit dead ends on the way, because wrong corridors have no alternative exit.

8. Why the Walls Don't All Disappear at Once

Here is a subtlety worth understanding. When you press Build Maze, the generation code runs synchronously — meaning the entire maze is computed in a single JavaScript call, all at once, before the browser draws even one frame. The actual wall-opening happens invisibly fast.

So how does the animation work? There are two separate systems:

The step queue — what the algorithm records

Every time the DFS carves a wall or backtracks, it pushes a plain object onto a list (_buildStepQueue):

// A carve event: { type: 'BUILD_CARVE', fromRow: 0, fromCol: 0, toRow: 0, toCol: 1, dir: 'E' } // A backtrack event: { type: 'BUILD_BACKTRACK', row: 0, col: 0 }

The algorithm doesn't draw anything. It only records what happened.

The animWalls shadow array — what the animator uses

There is a second wall array called animWalls. It starts fully closed (all walls true) and is updated one step at a time as the animation plays back.

The draw loop processes one step from the queue per frame, opens the corresponding wall in animWalls, and redraws — so you see exactly one wall disappear per frame.

Without this, the very first frame would show the fully-finished maze with all walls already open, because maze.getCell() already has the final state. animWalls is the "slow motion replay" layer.

Summary of the two-phase design:
Phase 1 — maze.generate() runs instantly: computes the entire maze, records every decision as a step object. No drawing.
Phase 2 — The p5.js draw() loop plays back one step per frame: updates cell colors, opens one wall in animWalls, redraws. This is the animation you watch.

9. Putting It All Together — One Frame of Animation

Here is what happens inside the sketch during a single animation frame when a BUILD_CARVE step fires:

if (step.type === 'BUILD_CARVE') { // 1. The cell we carved FROM is no longer the frontier — mark it carved (gray). cellState[step.fromRow][step.fromCol] = 'carved'; // 2. The cell we carved TO becomes the new frontier (teal). cellState[step.toRow][step.toCol] = 'frontier'; // 3. Open the wall in the shadow array so it visually disappears. animWalls[step.fromRow][step.fromCol][step.dir] = false; animWalls[step.toRow ][step.toCol ][SWMaze.DIR[step.dir].opposite] = false; }

And for a BUILD_BACKTRACK step — the DFS returned from a neighbor, and now the current cell goes dim to show the algorithm retreated through here:

if (step.type === 'BUILD_BACKTRACK') { // Dim the cell if it's still showing as frontier. if (cellState[step.row][step.col] === 'frontier') { cellState[step.row][step.col] = 'buildback'; // dark dim blue } // No wall change — backtracking doesn't close any walls. }
Backtracking never closes walls. Once carved, a passage stays open forever. The state change on backtrack is purely visual — it dims the cell to show the trail the DFS retreated through. The maze structure in memory (maze.getCell().walls) is not touched at all by backtrack events.

10. Things to Watch For in the App

Continue Exploring

🧩 Open the app while you re-read this

Watch the Build phase closely now. Set speed to 3 or 4 so each step is slow enough to see the teal cell jump and the walls disappear one at a time.

Open Maze 1 →
🏝️ Compare with island growth

The island saga uses the same DFS skeleton, but the "carve" equivalent is adding a cell to a list, and backtracking removes it. The maze never removes anything — every carve is permanent.

Islands vs. Mazes →
📋 Saga Index

Return to the index to explore all stages of the island saga, both maze variants, and all companion documents.

Saga Index →