mirror of
https://github.com/openfrontio/OpenFrontIO.git
synced 2026-06-22 02:27:43 +00:00
scamiv
72 lines
3.0 KiB
Markdown
72 lines
3.0 KiB
Markdown
# Coarse-to-fine pathfinding (boats) — notes
|
|
|
|
## Why
|
|
|
|
Full-res water BFS is optimal and simple, but the “ocean case” can still expand a lot of tiles.
|
|
Coarse-to-fine is the next lever: do a cheap solve on a low-res map to guide / bound the expensive solve.
|
|
|
|
## We already have low-res maps
|
|
|
|
The terrain loader already ships multiple resolutions per map:
|
|
|
|
- `manifest.map` + `map.bin` (full res)
|
|
- `manifest.map4x` + `map4x.bin` (coarser)
|
|
- `manifest.map16x` + `map16x.bin` (even coarser)
|
|
|
|
At runtime we load:
|
|
|
|
- `gameMap`: full res for normal games (or `map4x` for compact games)
|
|
- `miniGameMap`: lower res (`map4x` for normal games, or `map16x` for compact games)
|
|
- `microGameMap`: always `map16x` (in compact games this is the same instance as `miniGameMap`)
|
|
|
|
So we can prototype coarse-to-fine without extending mapgen first.
|
|
|
|
## Core idea
|
|
|
|
Stage 1 (coarse):
|
|
- Run the same multi-source/any-target search on `miniGameMap` (BFS, water-only, king-moves if desired).
|
|
- Result is a coarse path (or just a coarse distance field).
|
|
|
|
Stage 2 (refine):
|
|
- Run full-res BFS on `gameMap`, but **restricted** by what stage 1 learned (a “corridor”) *or* guided by a coarse heuristic.
|
|
|
|
Important: the coarse map is an approximation. It must never be allowed to make the final path invalid.
|
|
If the refine stage fails inside the corridor, fall back to full-res BFS.
|
|
|
|
## Option A: Coarse corridor (this)
|
|
|
|
1) Map fine tiles → coarse cells by integer scaling:
|
|
- `scaleX = gameMap.width / miniGameMap.width`
|
|
- `scaleY = gameMap.height / miniGameMap.height`
|
|
2) Solve on coarse, get a coarse cell path.
|
|
3) Inflate that path into a corridor:
|
|
- include all coarse cells within radius `r` of the coarse path (e.g. `r = 1..3` )(Manhattan or Chebyshev radius depending on move rules)
|
|
4) Refine on full-res with a fast mask:
|
|
- `passableFine(tile) = gm.isWater(tile) && corridorMask[coarseOf(tile)]`
|
|
5) If no path found, retry without the corridor (or inflate `r` and retry once).
|
|
|
|
Notes:
|
|
- If the low-res generation is “optimistic” (water if any child tile is water), the coarse path can cut across land.
|
|
Inflation + fallback is what keeps this safe.
|
|
|
|
## Option B: Coarse heuristic for A* (future?)
|
|
|
|
If we ever move from BFS → A* on full-res, a cheap heuristic is:
|
|
|
|
- Precompute `coarseDist[coarseCell]` by BFS on `miniGameMap` seeded from coarse targets.
|
|
- Use `h(tile) = coarseDist[coarseOf(tile)] * min(scaleX, scaleY)`
|
|
|
|
If the coarse map is “more passable” than the fine map (typical for minimaps), `coarseDist` tends to **underestimate**,
|
|
which is admissible (safe) but not always very tight.
|
|
|
|
## Where component IDs fit
|
|
|
|
Water-component IDs are still a free early reject:
|
|
|
|
- `WaterComponents.ts` already precomputes IDs per `GameMap` instance.
|
|
- Do the same check on `miniGameMap` if useful, but full-res component filtering already prevents the worst “wrong ocean” searches.
|
|
|
|
## Practical next steps
|
|
Measure: expansions + ms, before/after, on worst-case oceans.
|
|
decide if mapgen needs a better “navmap” (e.g. conservative water, coastline preservation, etc.).
|