Stage 5 keeps everything from Stage 4 — the animated recursive
backtracking, the speed control, the recursion log, and Ocean Pits —
and adds one new idea: a live Recursion Cost readout.
Every ADD step and every BACKTRACK step is counted in real time, and a
backtrack ratio is computed as the island grows.
The ratio makes the cost of a difficult path measurable rather than
just visible.
What’s New: Recursion Cost
- ✅ Cells added — the total number of ADD steps executed so far. Each ADD means the algorithm committed to a new cell and recursed deeper.
- ↩️ Backtracks — the total number of BACKTRACK steps. Each backtrack means a previously added cell was removed because the path it opened led nowhere.
- 📉 Backtrack ratio — backtracks ÷ (adds + backtracks), expressed as a percentage.
- 0 % → the algorithm never needed to backtrack — it picked a winning candidate every time.
- 50 % → exactly half of all steps were wasted on dead ends.
- Near 100 % → almost all of the algorithm’s work was undone before it found a valid path (or it failed entirely).
💡 Try this:
Run the island twice on the same seed: once with no pits, then again
with 20–30 % pits sprinkled around the same area.
Compare the backtrack ratios. Does a more obstacle-filled ocean always cost
more? Try placing pits in a tight ring around the seed to force the algorithm
to search for a gap — then watch the ratio climb.
Ocean Pits (from Stage 4)
Toggle Allow Pit Placement ON to click ocean cells and mark them
as permanently forbidden (dark navy). Press 🎲 Sprinkle! to
scatter a random percentage of the ocean with pits at once.
The higher the pit density, the narrower the corridors the algorithm must thread,
and the higher the backtrack ratio tends to be.
The Algorithm (unchanged from Stage 3)
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 open water.
- Shuffle or sort the candidate list (Randomize ON/OFF).
- Try each candidate:
- ADD the cell and recurse.
- If recursion returns
true → success.
- If recursion returns
false → BACKTRACK: remove the cell and try the next candidate.
- If all candidates fail → return
false.
🔍 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
}
What the Colors Tell You
- Light blue — open ocean.
- Orange — the seed cell.
- Soft green — confirmed island cell.
- Yellow-green — the cell currently being tried (contributes +1 to the ADD counter).
- Light green tint — valid candidate cells at this moment.
- Fading red flash — a backtracked cell (+1 to the BACKTRACK counter).
- Dark navy — Ocean Pit; permanently blocked.
Controls
- Target size — 1–200 cells. Larger targets give the ratio time to stabilize into a meaningful average.
- Speed — 1 (slowest) to 10 (fastest). Slow down to follow each ADD and BACKTRACK individually.
- Randomize ON/OFF — organic shapes vs. deterministic; ratio often differs between the two for the same seed and pit layout.
- Allow Pit Placement / 🎲 Sprinkle! — increase pit density to drive up the backtrack ratio.
- Reset — clears the island, counters, and log while keeping the current pit layout. Use this to run the algorithm again on the same pitted ocean with a new seed, so you can compare costs across placements without re-sprinkling.
- Clear — resets everything, including pits. C also works.
⚠️ Too Complex — Browser Safeguard
Very high pit density combined with Randomize OFF can force the algorithm to
explore an exponentially large number of dead-end paths before finding a solution or
confirming there is none. To prevent the browser from stalling, the sketch uses two guards:
- Reachability pre-check — before any recursion begins, a fast BFS counts how many open-water cells are reachable from the seed. If fewer cells exist than the target size, the algorithm records an instant FAIL without recursing at all.
- Step-count limit — if the recorded step queue reaches 150 000 entries, the build is aborted and the animation shows “Too Complex.” To recover: try fewer pits, a different seed position, or turn Randomize ON to escape the deterministic worst case.
Reading the Recursion Log
- ▶ ADD (r, c) — algorithm placed this cell and recursed deeper.
- ✗ BACKTRACK (r, c) — that path failed; the cell was removed.
- ✓ SUCCESS — the island reached its target size.
- ✘ FAIL — the seed was completely surrounded before the target was reached.
- ⚠️ TOO COMPLEX — the 150 000-step safety limit was hit; reduce pit density or enable Randomize.
- —— Reset (pits kept) —— — separator marking the start of a new run on the same pit layout.