SWIsland Recursion Saga

The SWIsland Recursion Saga builds a recursive island generator from the ground up using core SketchWaveJS classes — one stage at a time. Each stage adds one new idea, keeping the code small and the concept visible, until the final stages produce an island that grows itself through recursive backtracking.

The Java Connection

This saga runs in parallel with a Java project (Island.java, RecursiveIslandDriver.java, Coordinates.java) studied in APCS A. The JavaScript sketches mirror the Java logic step by step — the same orthogonal-adjacency rule, the same row/column grid, and eventually the same recursive grow() strategy — so you can see the algorithm in motion before (or after) reading the Java source.

The Building Blocks

• SWGrid — Serves as the ocean. Its user-coordinate system (y increases upward) maps cleanly to row/column addressing. screenToUser() converts a mouse click to a grid coordinate; userToScreen() converts back for drawing labels.
• SWSquare — Each island cell is one SWSquare instance, sized to fit exactly one grid cell. drawOnGrid(grid) handles the screen-space conversion at draw time. The seed cell is orange; expanded cells are soft green.
• SWColor — HSB colors (hue 0–360, saturation, brightness, alpha, all 0–100) used for island cell fills, strokes, hint overlays, and rejection flashes.
• SWPoint — Stores the center of each island cell in user coordinates so SWSquare can position itself correctly on the grid.

The Adjacency Rule

Island cells connect orthogonally only — up, down, left, right; never diagonally. This is enforced using direction arrays that mirror the Java source exactly:

const DR4 = [-1, 1,  0, 0];   // row offsets
const DC4 = [ 0, 0, -1, 1];   // col offsets

A candidate cell (r, c) is a valid next island cell if and only if it is not already part of the island and shares an edge with at least one cell that is.

The Saga in Stages

1. Island 1 — One Cell, One Click: Click anywhere on the ocean grid to drop a single orange seed cell. Establishes SWGrid as the ocean, SWSquare as the tile, and the row/column coordinate system that all later stages rely on.
2. Island 2 — Growing the Island: After placing a seed, click adjacent cells to grow the island manually. Valid neighbor cells are highlighted in faint green before you click; invalid clicks flash red and fade. You are doing by hand exactly what the recursive algorithm will do automatically in Stage 3.
3. Island 3 — Animated Recursive Growth: Place a seed, set a target size, choose a speed, and press Start. The algorithm grows the island itself, one step at a time, using a JavaScript port of Island.grow() from the Java project. Every ADD and BACKTRACK decision is shown in real time and logged in a scrollable breadcrumb panel. With Randomize ON, candidates are Fisher–Yates shuffled before each recursion, producing a different organic shape every run; with Randomize OFF, they are tried in a fixed sorted order, giving predictable results you can replay exactly. The full pool of valid candidate cells is highlighted in light green each step so you can see which option the algorithm chose.
4. Island 4 — Ocean Pits: Adds pit cells — water squares marked permanently impassable (stored as oceanGrid = 2) — that the recursive algorithm must route around. Users can place and remove pits individually or sprinkle a random percentage across the ocean before starting the algorithm. The core _grow() function is unchanged; pits are blocked automatically because _isValidExpansion() already rejects any non-zero cell. The main pedagogical payoff: denser pit fields force dramatically more backtracking, making the log and the red flashes much more active.
5. Island 5 — Recursion Cost: Adds a live Recursion Cost readout that counts every ADD step, every BACKTRACK step, and the backtrack ratio (backtracks ÷ total steps) as the island grows in real time. Use it alongside the Ocean Pits feature from Stage 4 to measure concretely how pit density raises the cost of finding a solution. A ratio near 0 % means the algorithm found its path efficiently; a high ratio means much of the work was wasted on dead ends. A Reset button preserves the pit layout while clearing the island and log, so you can compare costs for different seed positions on the same pitted ocean without re-sprinkling. Two safety guards prevent the browser from hanging on adversarial layouts: a BFS reachability pre-check fast-fails impossible configurations before any recursion begins, and a 150 000-step ceiling aborts builds that would otherwise require millions of recursive calls.
6. Island 6a — Multiple Islands: The ocean now hosts N islands at once (user-controlled, 1–8). Seeds are auto-placed from findRandomSeedPosition(); each island targets a random size in [min, max] and picks a unique color from an 8-hue palette. A single outer loop calls _grow() once per island and merges all ADD / BACKTRACK / ISLAND_START / ISLAND_SUCCESS / ISLAND_FAIL events into one step queue for a unified animation. Note: in Stage 6a, two islands may still touch corner-to-corner — that gap is closed in Stage 6b.
7. Island 6b — Diagonal Separation Rule: Adds the full separation rule from Island.java: no two islands may share an edge or a corner. _isValidExpansion() now checks all 8 surrounding neighbors of every candidate cell for foreign island land, and findRandomSeedPosition() similarly checks all 8 directions before accepting a seed. The stricter rule cuts off more expansion paths, so backtrack counts are noticeably higher than in Stage 6a.
8. Island 7 — OOP Refactoring (SWIsland & Coordinates): Same visual output as Stage 6b, but the algorithm is encapsulated in two JavaScript classes that mirror the Java source one-to-one. Coordinates (shapeClasses/coordinates.js) mirrors Coordinates.java; SWIsland (shapeClasses/swIsland.js) mirrors Island.java, with one JS-specific addition: grow() records every ADD / BACKTRACK step into an internal queue so the sketch can animate them. The sketch’s buildAllStepQueues() shrinks dramatically — a single SWIsland.buildIsland() call replaces six standalone helper functions. When an island completes, the recursion log prints island.toString(), matching the console output from RecursiveIslandDriver.java.
9. Island 8 — Fractal Coastlines (SWFractalIsland): Same island growth as Stage 7, with one additive layer: after all islands are placed the user presses 🌊 Apply Fractal Coastline to redraw them as organic polygon outlines using the midpoint displacement algorithm. A new class, SWFractalIsland, handles two phases: (1) extractOutline() traces the border of each island’s grid cells into a closed CCW-wound polygon in screen coordinates; (2) midpointDisplace() repeatedly bisects each edge and offsets the new midpoint along the perpendicular, shrinking the displacement each iteration using the Hurst exponent H = 0.7 to mimic the self-similar texture of natural coastlines. A seeded LCG (Linear Congruential Generator) replaces Math.random() so that every island gets a unique but reproducible coastline; pressing the button again picks a new seed for a fresh shape on the same islands. Two sliders let students tune roughness (amplitude of the displacement bumps) and subdivision passes (each pass doubles the vertex count and adds a finer level of detail). An ↩ Grid button restores the rectangular view at any time without losing the island data, enabling direct comparison between the grid version and the fractal version. The feature is disabled while the animation runs and re-enables automatically when all islands finish.

What to Watch For

• How the row/column grid maps to the ocean — row 0 is the top row, column 0 is the leftmost column.
• How the y-axis inversion between screen pixels and math coordinates is handled once, cleanly, so the rest of the code never has to think about it.
• How the Stage 2 hint system (getValidNeighbors()) becomes the candidate-collection loop inside the Stage 3 recursive method.
• How removing the human from the loop in Stage 3 requires only one change: replace “wait for a click” with “recurse into each valid neighbor.”
• How Stage 6a extends the data model to support multiple independent islands without changing _grow() at all — only the outer orchestration loop and the step-queue format change.
• How Stage 6b tightens one validity check — swapping a 4-direction loop for an 8-direction loop — to jump from “no orthogonal touching” to “no touching of any kind,” and how that single change measurably raises the backtrack cost.
• How Stage 7 moves the algorithm out of the sketch entirely and into two reusable classes — and how SWIsland.buildIsland() consolidates seed selection, BFS reachability pre-check, and recursive growth into one clean static factory call, exactly mirroring Island.buildIsland() in Java.
• How Stage 8 adds a pure visual post-processing layer on top of a finished algorithm without changing any of the island logic — the grid cells are still there; the fractal is just a new way to draw their shared border.
• How the Hurst exponent (H = 0.7) controls the rate at which displacement shrinks each iteration — a smaller H gives rougher, more jagged shapes; a larger H gives smoother, rounder ones — mirroring the parameter used to describe real fractal terrain.
• How using a seeded PRNG instead of Math.random() makes a generative result both random (different seeds give different shapes) and reproducible (same seed always gives the same shape) — a pattern that appears everywhere in procedural content generation.

🧩 Maze 1 — A Variant: Same Algorithm, Different Domain

The island saga is deliberately linear — each stage adds exactly one idea. The Maze 1 app sits outside that sequence as a variant: it does not evolve the island class, but it applies the same algorithmic skeleton to a completely different problem domain. The goal is to show that recursive DFS backtracking is not a one-trick pattern tied to organic shapes — it is a general strategy that reappears wherever a problem can be framed as “explore, commit, and undo if stuck.”

Why a maze?

• Generation: The maze is carved by the same recursive DFS that grows an island — visit an unvisited neighbor, commit (carve the shared wall), recurse, backtrack when all neighbors are exhausted. Because a perfect maze has no loops, the generator visits every cell before backtracking all the way to the start, making the full backtrack chain visible in a way that the island rarely is.
• Solving: A second, independent DFS explores the finished maze from S to T. Unlike generation, the solver will walk down many dead-end corridors before finding the exit, painting each dead end red as it retreats. This produces the clearest possible animation of what “backtrack” feels like at runtime.
• BFS contrast: Pressing View Solution instantly highlights the shortest path using BFS — a breadth-first search that the DFS solver does not follow. Comparing the two shows concretely why BFS guarantees the shortest path while DFS merely guarantees a path.
• Same infrastructure: SWMaze is modeled directly after SWIsland — it uses the same pre-recorded step-queue pattern, the same SWGrid for rendering, and the same SWColor / SWPoint building blocks. A student who studied Stage 7 will recognize the structure immediately.

In short: once you have seen the island recursion, the maze should feel familiar but surprising — the same rhythm of try / recurse / backtrack, but now with walls, corridors, dead ends, and a guaranteed exit waiting somewhere at the other corner.

🧩 Maze 2 — One Extra Color, New Insight

Maze 2 is byte-for-byte identical to Maze 1 except for a single addition: an orange resume junction color. When the DFS solver backtracks from a dead end, the cell it retreats to — the junction where it will now try the next available direction — briefly glows orange.

• What it shows: In Maze 1 you can see where the solver retreats to, but the moment of “picking back up” is invisible. The orange cell makes that exact moment a first-class visual event: the solver is standing here, deciding.
• Duration: The orange lasts exactly one decision. If the solver finds a new direction it proceeds deeper and the cell returns to green. If every neighbor is already exhausted, the cell turns red and the retreat continues.
• Code cost: One new cell state ('resume'), one new SWColor declaration, and four lines added to the SOLVE_BACKTRACK and SOLVE_TRY handlers — no other logic changes.
• Compare & contrast goal: Open both Maze 1 and Maze 2 and run the same maze. Then discuss: does the orange junction improve comprehension, or add unnecessary noise? There is no right answer — the exercise is the analysis.