OpenFrontIO/docs/LocalCorridorWidening.md

Local corridor widening (adaptive coarse-to-fine water pathfinding, adaptive constraint relaxation)

Goal: keep the coarse corridor win, but avoid the current “corridor fails → global full-res BFS” cliff.

Local widening behaves like a cheap BSP refinement:

• start with a narrow corridor (fast)
• if it fails, expand only where it matters (still fast)
• only as a last resort, drop the mask entirely

This is intended to be a generic wrapper around MultiSourceAnyTargetBFS (used by transport/trade/warship).

Inputs / outputs

Inputs:

• fineMap: GameMap
• coarseMap: GameMap (typically map16x)
• seedNodes[], seedOrigins[] (multi-source)
• targets[] (any-target)
• bfsOpts (king moves, no-corner-cutting, etc.)
• initial corridor radius r0, max attempts k

Output:

• { source, target, path } like MultiSourceAnyTargetBFSResult, or null

Baseline (what we have today)

1. Coarse BFS to get coarsePath
2. Corridor = inflate coarsePath by radius r
3. Fine BFS restricted by corridor mask
4. If fail: widen radius globally or fall back to unrestricted fine BFS

Problem: a tiny lie in the coarse map (optimistic water) can cause step (4) to explode to “search the whole ocean”.

Local widening: two practical variants

Variant A (chosen): widen around visited coarse regions

If fine BFS fails inside the corridor, we already know where it was trying.

Implementation sketch:

1. Build initial corridor mask: allowedCoarse[coarseCell] = true.
2. Run fine BFS with allowedMask = coarse corridor.
3. If it succeeds: done.
4. If it fails:
   • compute visitedCoarse: all coarse cells that were actually visited by fine BFS
   • expand corridor by 1 ring around visitedCoarse (Chebyshev ring, since king moves)
   • retry fine BFS
5. Repeat up to k times.
6. If still no path: unrestricted fine BFS fallback (correctness guardrail).

Clarification: widening is cumulative. Each failed attempt expands around that attempt’s visitedCoarse, and newly allowed coarse cells stay allowed across subsequent attempts (via the same allowedCoarseStamp).

Why it works:

• you only “pay more” near the constriction you hit
• open-ocean cells that were never approached don’t get unlocked

What “visitedCoarse” means (cheaply):

• while expanding fine BFS, map fineTile -> coarseCell (precomputed fineToCoarse[])
• stamp visitedCoarseStamp[coarseCell] = stamp when the BFS pops/visits a tile

How to expand by one ring:

• for each coarse cell in visitedCoarse, mark its 8 neighbors as allowed
• use stamps, not Set, to avoid allocations

Variant B (not chosen): widen only along the coarse path segment you reached

Similar, but tighter:

• intersect visitedCoarse with the original coarsePath (or the prefix that’s reachable)
• widen only around that subset

This can be even cheaper on huge corridors, but is easier to get wrong (requires careful “prefix” reasoning).

Hot-path constraints (don’t regress perf)

• No per-call allocations in the inner BFS loop.
• Use stamp arrays:
  • allowedCoarseStamp[coarseCell]
  • visitedCoarseStamp[coarseCell]
• Reuse MultiSourceAnyTargetBFS instances via WeakMap<GameMap, MultiSourceAnyTargetBFS>.
• Keep attempt count small (k = 2..4).

Correctness guardrails

• Coarse map is approximate: coarse success never guarantees fine success.
• Local widening can still miss a path if the corridor is too wrong; that’s fine:
  • always end with an unrestricted fine BFS fallback
• Preserve current move rules:
  • king moves (8-neighbor)
  • no-corner-cutting

Suggested defaults

• r0 = 1..2 coarse cells (start tight)
• k = 3 (initial + 2 widen steps)
• widen step = +1 ring around visitedCoarse
• final fallback = unrestricted fine BFS

Where this plugs in

Replace the current “attempt loop that only increases radius globally” inside coarse-to-fine helper with:

• attempt loop driven by visitedCoarse
• optional “global radius bump” as a last attempt before full fallback

This keeps the interface identical for all callsites (transport/trade/warship), but makes “tight corridor” failures cheap.