Stage 3 makes the recursion visible.
Instead of asking you to click each cell manually (Stage 2), the algorithm
now grows the island itself — but at a pace you control, so you can watch
every decision it makes.
The Algorithm
This is a direct JavaScript port of Island.grow() from the Java source.
It uses recursive backtracking:
- Base case: the island already has targetSize cells → done, return
true.
- Collect candidates: find every cell orthogonally adjacent to the island that is still water.
-
Shuffle (if Randomize is ON): randomly reorder the candidate
list using the Fisher–Yates algorithm → produces
organic shapes. With Randomize OFF the candidates are sorted
top→left→right→down, giving predictable boxy shapes every time.
This is the only difference between an “organic” and a
“non-organic” island.
🃏 Fisher–Yates in plain English:
Imagine you wrote each candidate cell on a separate slip of paper
and tossed all the slips into a hat.
Reach in and pull one out at random — that becomes candidate #1.
Pull another from what’s left — that’s candidate #2.
Keep going until the hat is empty.
Because every slip had an equal chance of being drawn at any point,
the final order is completely fair and unpredictable — a true shuffle.
Fisher–Yates does exactly that in code, in one fast pass through the list.
- Try each candidate:
- ADD the cell (mark as land, add to island list).
- Recurse — call
grow() again from the new state.
- If recursion returns
true → success, propagate it up.
- If recursion returns
false → BACKTRACK: remove the cell and try the next candidate.
- If all candidates fail → return
false (signal the caller to backtrack).
🔍 The Recursive Function — Actual Code
Here is the real _grow() function from the sketch, annotated.
BASE CASE stops the recursion when the island is big enough.
CALLS ITSELF is where the recursion happens.
BACKTRACK undoes a failed step and tries the next option.
function _grow(cells, targetSize, useRandom) {
if (cells.length >= targetSize) return true; // island is big enough — stop! BASE CASE
// collect all water cells that touch the island's edge
const candidates = [];
for (const cell of cells) {
for (let d = 0; d < 4; d++) {
const nr = cell.row + DR4[d];
const nc = cell.col + DC4[d];
if (_isValidExpansion(nr, nc) && !_alreadyCandidate(nr, nc, candidates))
candidates.push({ row: nr, col: nc });
}
}
if (candidates.length === 0) return false; // completely surrounded — dead end
// shuffle (organic shapes) or sort (predictable shapes)
if (useRandom) _shuffleCandidates(candidates);
else candidates.sort((a, b) => a.row - b.row || a.col - b.col);
// try each candidate neighbor in turn
for (const { row, col } of candidates) {
cells.push({ row, col }); // ADD: claim this cell
oceanGrid[row][col] = 1;
if (_grow(cells, targetSize, useRandom)) CALLS ITSELF
return true; // deeper call succeeded — bubble success up
cells.pop(); // UNDO: remove from island BACKTRACK
oceanGrid[row][col] = 0; // mark as water again
}
return false; // all candidates failed — tell the caller to backtrack
}
📖 How to read it:
Each time _grow() is called it does exactly one thing: check whether the island is
big enough (base case), then try one candidate neighbor at a time.
For each candidate it adds the cell and calls itself — handing the whole
problem back to a fresh copy of the same function with one more cell already placed.
If that deeper call eventually returns false, the add is undone (backtrack)
and the next candidate gets a turn.
No call ever needs to know how deep the stack is —
each one just does its small part and trusts recursion to handle the rest.
Why Pre-record Then Replay?
JavaScript recursion runs to completion in one go — you can’t pause it
mid-call to draw a frame. So Stage 3 runs the full grow()
synchronously first, recording every ADD and BACKTRACK decision in a
step queue. The p5.js draw() loop then replays that queue
one step per frame at whatever speed you choose.
The algorithm is real recursion; the animation is a replay.
What the Colors Tell You
- Light blue — open ocean; any unoccupied grid cell. This is the background color of the entire canvas.
- Orange — the seed cell you placed; it never moves.
- Soft green — a confirmed island cell the recursion accepted and kept.
- Yellow-green — the cell currently being tried; it becomes soft green on the next ADD, or flashes red if a backtrack is needed.
- Light green tint — the full pool of valid candidate cells right now. Every tinted cell was a legal next choice; watch which one the algorithm picks.
- Fading red flash — a backtracked cell, just removed; the algorithm will try a different candidate next.
Controls
- Target size — how many cells the island should have (1–200, including the seed). Sizes 1–20 are good for following the recursion step by step. Sizes 25–100 let you explore how the island fills the ocean, where it hugs borders, and how often backtracking occurs. Size 200 (out of 600 total cells) pushes the algorithm hard — especially with Randomize OFF, where the sorted growth will visibly march across the grid and may back itself into a tight corner near the edges.
- Speed — 1 is slowest (~2 seconds per step), 10 is fastest (one step every frame). Use slow speeds to follow the recursion log entry by entry.
- Randomize ON/OFF — compare organic vs. deterministic growth by running the same seed with the toggle in each position.
- Start / Pause / Resume — available after placing the seed; Spacebar also toggles.
- Clear — resets everything; C also works.
Reading the Recursion Log
- ▶ ADD (r, c) — algorithm just placed this cell and is recursing deeper.
- ✗ BACKTRACK (r, c) — that path failed; the cell was removed.
- ✓ SUCCESS — the island reached its target size.
- ✘ FAIL — the seed location was completely surrounded before the target was reached.