This demo hosts two separate recursive algorithms on the same grid.
Both use Depth-First Search (DFS) with backtracking — the same pattern
you saw in the Island Saga — but for completely different goals.
Algorithm: Recursive DFS wall carver
- Starts at cell S (top-left)
- Visits one random unvisited neighbor per step
- Carves the shared wall to open a passage
- Recurses into the neighbor
- When all neighbors are visited → backtrack
- Guarantees every cell is visited exactly once → perfect maze
Algorithm: Recursive DFS path finder
- Starts at S; goal is T (bottom-right)
- Tries each open passage in turn
- If next cell leads to T → return true
- If all passages fail → return false (backtrack)
- In a perfect maze the solver always explores dead-end branches before finding the unique solution
Why a Perfect Maze?
A perfect maze has exactly one path between any two cells — no loops,
no isolated regions. This guarantees:
- There is always a solution from S to T.
- That solution is unique, so the solver will hit dead ends and must backtrack
before finding it.
- The backtracking is not a bug — it is the recursion demonstrating its power.
The Code Structure (SWMaze class)
// Generation: recursive DFS carver
_generateDFS(r, c) { BUILD
this._cells[r][c].visited = true;
const dirs = this._shuffle([...SWMaze.DIRECTIONS]);
for (const dir of dirs) {
// if neighbor is unvisited: carve wall → recurse → backtrack
this._buildStepQueue.push({ type: 'BUILD_CARVE', ... });
this._generateDFS(nr, nc);
this._buildStepQueue.push({ type: 'BUILD_BACKTRACK', ... });
}
}
// Solving: recursive DFS path finder
_solveDFS(r, c, endRow, endCol, useRandom) { SOLVE
if (r === endRow && c === endCol) return true; // ← BASE CASE
for (const dir of dirs) {
this._solveStepQueue.push({ type: 'SOLVE_TRY', ... });
if (this._solveDFS(nr, nc, endRow, endCol)) return true;
this._solveStepQueue.push({ type: 'SOLVE_BACKTRACK', ... }); BACK
}
return false;
}
What the Colors Tell You
- Cyan frontier — current DFS head during generation.
- Gray carved — a passage has been opened here.
- Green trying — cell is on the solver’s current path stack (call stack depth shown when ≤ 25 cells).
- Red flash — solver just backtracked from this cell; it was a dead end.
- Gold — final solution path (both View Solution and Solve Maze).
- S (green) — start, top-left.
- T (amber) — treasure, bottom-right.
Three Buttons, Three Phases
- Build Maze — run the DFS generator and animate wall carving.
Each BUILD_CARVE step opens one passage; each BUILD_BACKTRACK step dims the cell.
The cyan frontier moves through the grid like a snake.
- View Solution — instantly highlight the BFS shortest path (gold).
This uses a different algorithm (Breadth-First Search) to guarantee
the shortest path, not just any path.
- Solve Maze — watch the recursive DFS solver explore the maze.
Every wrong turn shows backtracking in real time.
When it reaches T the winning path lights up gold.
- Reset — keeps the same maze and clears all solve colors
so you can re-run the solver immediately. Toggle
Randomize before pressing Reset to watch the DFS take a completely
different path through the exact same passages.
To generate a brand-new maze, press Build Maze instead.
Randomize Option
When Randomize is ON, the solver shuffles direction order (N/S/E/W)
before each cell. Turning it OFF forces the fixed order N→S→E→W, which
produces the same solve path every time — useful for comparing a
predictable run vs. a random one.
Reading the Recursion Log
── Build started ── — generator DFS beginning.── Maze complete ── — all cells visited; maze is ready.── Solve started ── — solver DFS beginning.TRY (r, c) — depth N — solver added this cell at recursion depth N.BACK (r, c) — depth N — solver backtracked from this dead end.── SOLVED ── — path found; summary of adds/backtracks logged.