TNT | SWMaze Class Reference

Overview

SWMaze is the single JavaScript class that drives both maze stages of the SWIsland Recursion Saga. It encapsulates two independent recursive DFS algorithms: one that generates a perfect maze by carving walls, and one that solves it by finding a path from S to T.

The class follows the same design pattern as SWIsland: all computation runs synchronously and records every decision into a step queue so the sketch can replay it as a frame-by-frame animation. The sketch only handles orchestration and drawing; the algorithm logic lives entirely inside SWMaze.

Source file

shapeClasses/swMaze.js
Load it before any sketch that uses it.

Two algorithms

Generator — generate() carves a perfect maze via recursive DFS.
Solver — solve() finds the path via recursive DFS backtracking.

Perfect maze

Every cell is reachable from every other cell via exactly one path. No loops, no isolated regions. S→T is always solvable.

Cell Representation

Every cell in the grid is a plain object with two fields. The maze is stored as a 2D array: this._cells[row][col].

// One cell — same structure for every cell, row 0..rows-1, col 0..cols-1 cell = { walls: { N: true, // north wall (toward row - 1) — true = wall present, false = open S: true, // south wall (toward row + 1) E: true, // east wall (toward col + 1) W: true, // west wall (toward col - 1) }, visited: false // scratch flag — reused by generator AND solver }

Walls start closed

Every cell is initialized with all four walls true. Generation carves selected walls to false. Once a wall is opened it is never closed again.

Shared walls

The wall between two adjacent cells is stored on both cells. Opening a passage always sets two booleans: cell.walls[dir] = false and neighbor.walls[opposite] = false.

The visited flag is a two-pass scratch pad. The generator sets it to true when it enters a cell, preventing re-entry. After generation, _clearVisited() resets all flags to false so the solver can do its own independent pass. The generator and solver never share flag state.

Direction Table

SWMaze.DIR is a static lookup table that encodes everything needed to move from one cell to an adjacent cell in any of the four cardinal directions. Both the generator and solver use it — loop over SWMaze.DIRECTIONS and look each direction up in SWMaze.DIR.

// Static field — read as: "to go direction D from (r, c), use these values" static DIR = { N: { dr: -1, dc: 0, wall: 'N', opposite: 'S' }, // row - 1 = up on screen S: { dr: 1, dc: 0, wall: 'S', opposite: 'N' }, // row + 1 = down on screen E: { dr: 0, dc: 1, wall: 'E', opposite: 'W' }, // col + 1 = right W: { dr: 0, dc: -1, wall: 'W', opposite: 'E' }, // col - 1 = left }; static DIRECTIONS = ['N', 'S', 'E', 'W'];

N (r-1, c)

W (r, c-1)

(r, c)

E (r, c+1)

S (r+1, c)

4 cardinal neighbors

How to use the table:

// Move from (r, c) in direction dir: const { dr, dc, wall, opposite } = SWMaze.DIR[dir]; const nr = r + dr; // neighbor row const nc = c + dc; // neighbor col // Carve the shared wall (both sides): cell(r, c ).walls[wall] = false; cell(nr, nc).walls[opposite] = false;

Field	Type	Description
`dr`	number	Row offset to reach the neighbor (`-1`=N, `+1`=S, `0`=E/W).
`dc`	number	Column offset to reach the neighbor (`+1`=E, `-1`=W, `0`=N/S).
`wall`	string	The wall key on this cell that faces the neighbor (e.g. `'E'` for eastward travel).
`opposite`	string	The corresponding wall key on the neighbor that faces back (e.g. `'W'` for eastward travel).

Constructor

const maze = new SWMaze(rows, cols);

Kind	Signature	Description
instance	`new SWMaze(rows, cols)`	Creates an ungenerated `rows × cols` maze with all walls present and no passages. Call `generate()` before using the maze. Initializes empty step queues and a blank cell grid.

The constructor allocates the 2D cell array (_makeBlankCells()) but does not carve any passages. Both step queues start empty. The _generated flag starts false and is set to true by the first successful generate() call.

Getters

All the read-only accessors provided by SWMaze:

Kind	Signature	Description
instance	`getRows() → number`	Returns the number of rows in the grid.
instance	`getCols() → number`	Returns the number of columns in the grid.
instance	`getCell(r, c) → {walls, visited}`	Returns the raw cell object at `(r, c)`. Primarily used by the sketch's draw loop to query wall state for rendering. Do not mutate the returned object directly.
instance	`isOpen(r, c, dir) → boolean`	Returns `true` if the wall in direction `dir` at cell `(r, c)` has been carved away (passage is open). Equivalent to `!getCell(r, c).walls[dir]`. Used by the solver to check which neighbors are reachable.
instance	`isGenerated() → boolean`	Returns `true` if `generate()` has been called and completed. The sketch uses this to gate solve actions.
instance	`getSolutionPath() → {row, col}[] \| null`	Returns the BFS shortest-path array set by `findSolutionPath()`, or `null` if that method hasn't been called. Each element is `{ row: number, col: number }`.
instance	`getBuildStepQueue() → object[]`	Returns the array of `BUILD_CARVE` and `BUILD_BACKTRACK` steps recorded by `generate()`. See Step Queues.
instance	`getSolveStepQueue() → object[]`	Returns the array of `SOLVE_TRY`, `SOLVE_BACKTRACK`, and `SOLVE_SUCCESS` steps recorded by `solve()`. See Step Queues.
instance	`toString() → string`	Returns a brief diagnostic string. Example: `"SWMaze [10×10, 100 cells, solveSteps=143]"`

generate()

The public entry point for maze generation. Resets all cells and step queues, then calls the private recursive carver _generateDFS() starting from the given cell.

Kind	Signature	Returns
instance	`generate([startRow = 0], [startCol = 0])`	`void`

What generate() does, in order:

Resets _cells to a fully-walled blank grid.
Clears both step queues and _solutionPath.
Sets _generated = false.
Calls _generateDFS(startRow, startCol) — runs synchronously, fully populates _buildStepQueue.
Sets _generated = true.
Calls _clearVisited() to reset all visited flags for the solver's future use.

The private carver: `_generateDFS(r, c)`

_generateDFS(r, c) { // 1. Mark visited so no other branch re-enters this cell. this._cells[r][c].visited = true; // 2. Shuffle directions so each maze looks different. const dirs = this._shuffle([...SWMaze.DIRECTIONS]); for (const dir of dirs) { const { dr, dc, wall, opposite } = SWMaze.DIR[dir]; const nr = r + dr; const nc = c + dc; // 3. Skip if out of bounds or already visited. if (!this._inBounds(nr, nc) || this._cells[nr][nc].visited) continue; // 4. Carve: open the shared wall on both cells. this._cells[r ][c ].walls[wall] = false; this._cells[nr][nc].walls[opposite] = false; // 5. Record the carve step for animation. this._buildStepQueue.push({ type: 'BUILD_CARVE', fromRow:r, fromCol:c, toRow:nr, toCol:nc, dir }); // 6. Recurse deeper — the call stack remembers where we are. this._generateDFS(nr, nc); // 7. Recursion returned — record the backtrack, then try next direction. this._buildStepQueue.push({ type: 'BUILD_BACKTRACK', row:r, col:c }); } // All 4 directions tried. Return — caller pushes BUILD_BACKTRACK for itself. }

Why this produces a perfect maze: The visited flag ensures each cell is entered from exactly one direction. No loops can form (you can never carve back into an already-visited cell). Starting from any cell, the DFS will visit all rows × cols cells before finishing. The result: exactly one path between any two cells.

findSolutionPath()

Finds the shortest path from start to end using BFS (Breadth-First Search). This is used by the "View Solution" feature to highlight the correct path instantly — before the solver animation runs.

Kind	Signature	Returns
instance	`findSolutionPath(startRow, startCol, endRow, endCol)`	`{row, col}[]`

Uses a standard BFS queue with a parent pointer array to reconstruct the path.
Only crosses through open passages — respects walls[dir] === false.
In a perfect maze, the BFS path = the DFS solution path (there is only one).
Stores the result in _solutionPath and returns it as an ordered array from start to end.
Does not use or disturb the visited flags on cells — it uses its own local visited array.

solve()

The public entry point for maze solving. Calls the private recursive solver _solveDFS() and records every decision into _solveStepQueue for animation replay.

Kind	Signature	Returns
instance	`solve(startRow, startCol, endRow, endCol, [useRandom = true])`	`boolean` — always `true` for a perfect maze

What solve() does, in order:

Calls _clearVisited() to reset all flags.
Clears _solveStepQueue.
Pushes a SOLVE_TRY step for the start cell.
Calls _solveDFS(startRow, startCol, endRow, endCol, useRandom).
If succeeded, pushes a SOLVE_SUCCESS step.
Calls _clearVisited() again to leave the maze clean.

The `useRandom` parameter

When true (default), the solver shuffles its direction order before trying neighbors — producing a different-looking exploration path each time. When false, directions are tried in the fixed order N, S, E, W, making the solver deterministic. This is what the "Randomize" checkbox in the app controls. It has no effect on maze generation, only on solving.

The private solver: `_solveDFS(r, c, endRow, endCol, useRandom)`

_solveDFS(r, c, endRow, endCol, useRandom) { // BASE CASE — reached the treasure cell. if (r === endRow && c === endCol) return true; this._cells[r][c].visited = true; const dirs = useRandom ? this._shuffle([...SWMaze.DIRECTIONS]) : [...SWMaze.DIRECTIONS]; // N, S, E, W — deterministic for (const dir of dirs) { if (this._cells[r][c].walls[dir]) continue; // wall: impassable const { dr, dc } = SWMaze.DIR[dir]; const nr = r + dr; const nc = c + dc; if (!this._inBounds(nr, nc) || this._cells[nr][nc].visited) continue; // TRY: step into this neighbor. this._solveStepQueue.push({ type: 'SOLVE_TRY', row: nr, col: nc }); if (this._solveDFS(nr, nc, endRow, endCol, useRandom)) { return true; // success — propagate up } // BACKTRACK: this direction led to a dead end. this._solveStepQueue.push({ type: 'SOLVE_BACKTRACK', row: nr, col: nc }); } return false; // all directions failed — signal backtrack to our caller }

Comparison with SWIsland.grow(): The solver and the island grower use the same backtracking structure. The key difference: in grow(), backtracking physically undoes a cell (pops from the list, restores the ocean). In _solveDFS(), backtracking just records a SOLVE_BACKTRACK step for the animation — the maze structure itself is never modified.

Step Queues

SWMaze maintains two separate step queues — one for the build phase and one for the solve phase. Both work the same way: the algorithm records every decision as a plain object, and the sketch replays them one per frame as the animation.

Build step queue — `getBuildStepQueue()`

// BUILD_CARVE — a wall between two cells was opened. { type: 'BUILD_CARVE', fromRow: number, fromCol: number, // cell where the DFS is currently running toRow: number, toCol: number, // cell that was carved into (becomes new frontier) dir: string // 'N' | 'S' | 'E' | 'W' } // BUILD_BACKTRACK — _generateDFS returned from a neighbor back to (row, col). { type: 'BUILD_BACKTRACK', row: number, col: number // the cell the DFS backed up to }

Solve step queue — `getSolveStepQueue()`

// SOLVE_TRY — the solver stepped into this cell (it's on the active path). { type: 'SOLVE_TRY', row: number, col: number } // SOLVE_BACKTRACK — this cell was a dead end; solver retreated from it. { type: 'SOLVE_BACKTRACK', row: number, col: number } // SOLVE_SUCCESS — the treasure cell was reached; the current DFS path is the solution. { type: 'SOLVE_SUCCESS' } // no row/col — applies to the whole path

How the sketch uses these

Step type	Cell state set by sketch	Visible color
`BUILD_CARVE`	`from` cell → `'carved'`; `to` cell → `'frontier'`	Gray / Teal
`BUILD_BACKTRACK`	cell → `'buildback'` (if still frontier)	Dim blue
`SOLVE_TRY`	cell → `'trying'`	Green
`SOLVE_BACKTRACK`	cell → `'dead'`	Red flash
`SOLVE_SUCCESS`	all cells on `getSolutionPath()` → `'solution'`	Gold

Usage Example

The typical call pattern used by swMaze1Sketch.js:

// 1. Create the maze object (no walls carved yet). const ROWS = 10, COLS = 10; const maze = new SWMaze(ROWS, COLS); // 2. Generate (starts from top-left by default). maze.generate(); // or maze.generate(0, 0) // 3. Get the build animation steps. const buildSteps = maze.getBuildStepQueue(); console.log(`Build steps: ${buildSteps.length}`); // ~ 2 × rows × cols // 4. Find the BFS shortest path (for View Solution). const path = maze.findSolutionPath(0, 0, ROWS-1, COLS-1); console.log(`Solution length: ${path.length} cells`); // 5. Solve with DFS (for Solve Maze animation). maze.solve(0, 0, ROWS-1, COLS-1, true); // useRandom = true // 6. Get the solve animation steps. const solveSteps = maze.getSolveStepQueue(); console.log(maze.toString()); // → "SWMaze [10×10, 100 cells, solveSteps=143]" // 7. Query individual cells (used by the draw loop to render walls). const cell = maze.getCell(3, 5); console.log(cell.walls.N); // false = north wall is open (passage exists) console.log(maze.isOpen(3, 5, 'E')); // true = east passage is open

Calling `generate()` again

Calling generate() a second time is safe — it performs a full reset internally before carving. All walls are restored to closed, both step queues are cleared, and _solutionPath is set to null. The app does this every time the user presses Build Maze.

Private Methods

These methods are internal implementation details — you won't call them directly, but understanding them helps when reading the source code.

Kind	Name	What it does
private	`_makeBlankCells()`	Allocates and returns a fresh 2D array of cell objects with all walls `true` and `visited: false`. Called by the constructor and by `generate()` on each reset.
private	`_shuffle(arr)`	Fisher-Yates in-place shuffle. Used by both the generator and solver when `useRandom` is true. Uses `Math.random()` — no seed, always different.
private	`_inBounds(r, c)`	Returns `true` if `(r, c)` is within the grid. Guards all neighbor lookups in both DFS methods.
private	`_generateDFS(r, c)`	The recursive maze carver. Marks visited, shuffles directions, carves walls into unvisited neighbors, records BUILD_CARVE and BUILD_BACKTRACK steps. See generate() for the full annotated code.
private	`_solveDFS(r, c, endRow, endCol, useRandom)`	The recursive maze solver. Marks visited, tries each open passage, records SOLVE_TRY and SOLVE_BACKTRACK steps, returns `true` on success. See solve() for the full annotated code.
private	`_clearVisited()`	Sets every cell's `visited` flag back to `false`. Called after generation (to prepare for the solver) and around the solve pass (before and after).

SWMaze vs. SWIsland

Both classes use recursive DFS with backtracking. The table below maps the equivalent concepts side by side — useful when studying both structures together.

Concept	`SWIsland`	`SWMaze`
Grid element	Ocean cell — `ocean[r][c]`, integer (0/1/2)	Maze cell — `_cells[r][c]`, object with `walls` + `visited`
What grows / is built	A set of land cells added to a list	A network of passages between cells
Backtracking undoes…	Removes a cell from the list, restores `ocean[r][c] = 0`	Nothing — carves are permanent. Records a BACKTRACK step only for animation.
Visited / in-use check	`ocean[r][c] === 0` + three expansion rules	`cell.visited === false` + wall open check for solver
Direction representation	Parallel arrays `DR4[]`, `DC4[]`	Object table `SWMaze.DIR` with `wall` and `opposite`
Success condition	Island reaches target size	Generator: all cells visited. Solver: reaches (endRow, endCol).
Step queue types	`'ADD'`, `'BACKTRACK'`	`'BUILD_CARVE'`, `'BUILD_BACKTRACK'`, `'SOLVE_TRY'`, `'SOLVE_BACKTRACK'`, `'SOLVE_SUCCESS'`
Java equivalent	`Island.java` / `Coordinates.java`	None — `SWMaze` is original JavaScript
Browser-safety abort	`maxSteps` guard in `grow()`	Not needed — the DFS always terminates in `O(rows × cols)` steps

← Back to the Saga Index Open Maze 1 → SWIsland Reference →

SWMaze Class Reference