mirror of
https://github.com/openfrontio/OpenFrontIO.git
synced 2026-06-22 08:38:10 +00:00
scamiv
aa09240d40
- Introduced a new approach to local corridor widening in the `CoarseToFineWaterPath` module, allowing for more efficient pathfinding by expanding the search corridor based on visited coarse regions. - Implemented a mechanism to avoid global radius increases, enhancing performance and reducing unnecessary searches. - Updated `MultiSourceAnyTargetBFS` to support marking visited coarse regions during BFS, facilitating the local widening process. - Adjusted parameters for maximum attempts and corridor radius to optimize pathfinding behavior.
108 lines
4.1 KiB
Markdown
108 lines
4.1 KiB
Markdown
# 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.
|