Stage 4 keeps everything from Stage 3a — the animated recursive
backtracking, the speed control, the recursion log — and adds one new
twist: Ocean Pits.
A pit is a water cell marked as permanently too deep for island growth.
The algorithm must now navigate around them, which tends to produce
more backtracking, tighter squeezes, and more dramatic log entries,
especially when pits wall off part of the ocean.
What’s New: Ocean Pits
- Allow Pit Placement toggle — while ON, clicking any open water cell plants a dark navy pit (
oceanGrid = 2). Clicking a pit again removes it. The seed and island cells are ignored.
- 🎲 Sprinkle! — set the percentage slider and press Sprinkle to randomly scatter that percentage of the 600-cell ocean as pits (using the same Fisher–Yates shuffle the island uses). Cherry-picked pits and sprinkled pits are interchangeable; Clear pits removes them all at once.
- Effect on the algorithm:
_isValidExpansion() already returned false for any non-zero cell, so pits (value 2) are blocked from island growth with no code change to the core algorithm. The only addition was a guard in getValidNeighbors() so candidate hints also skip pit cells.
💡 Try this: sprinkle 20–30% pits, place your seed in a tight corner,
then run with Randomize OFF and a slow speed. Watch the algorithm methodically
explore every corridor until it finds one that works — or backs all the way
out and tries a completely different direction. Then compare to Randomize ON,
which may find a path immediately or may wander just as badly.
The Algorithm (unchanged from Stage 3a)
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.
- Dark navy — an Ocean Pit; permanently blocked from island growth.
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, including all pits; C also works.
- Allow Pit Placement — toggle ON to click-place or click-remove individual pits. Toggle OFF to place the seed and run the algorithm.
- Random sprinkle slider + 🎲 Sprinkle! — set a percentage (0–50%) and press Sprinkle to randomly fill that fraction of ocean cells with pits. Can be combined with manual pit placement.
- Clear pits — removes all pits without disturbing the island or animation state.
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.