Home Pathfinding Route Modes

Pathfinding Route Modes (Fastest vs Direct)

1. Summary

Shared grid A* (flatland-pathfinding) serves player auto-nav, workers, schedule NPCs, and wildlife. Two route modes:

Mode Behavior
Fastest (default) Minimize travel time (true ETA) using the same terrain speed multipliers that move actors
Direct Minimize geometric path length on any walkable cell — no terrain preference

Blocked / impassable cells stay blocked in both modes (buildings, props, Rock, DeepWater, etc.).

2. Decisions (locked)

Topic Decision
Default Fastest
Cost fidelity True ETA from terrain-kinds.yaml move_speed_mult (admin-editable)
Designer “feel” Edit World → Terrain kinds → Movement (move_speed_mult); pathfinding follows after publish
Direct walkability Anything not blocked is walkable — bog / shallow water / slow tiles use the same uniform walkable cost as grass
Direct meaning Shortest walkable geometric route only — no soft avoid
Player setting Persist auto_nav_mode: fastest | direct on ClientConfig (client.json); default fastest
Server agents Workers, NPCs, wildlife, chase — always Fastest (player toggle does not apply)

3. Terrain costs

3.1 Source of truth

Sim already applies per-kind modifiers in TerrainKind::modifiers() → (stamina_drain_mult, move_speed_mult). Pathfinding must not keep a separate hand-tuned cost table that drifts from those speeds.

Canonical Fastest cost (integer grid units):

cost(kind) = round(BASE / move_speed_mult(kind))

with BASE = grass baseline (today’s DEFAULT_COST 10), and impassable kinds (Rock, DeepWater) remaining non-walkable (u16::MAX / blocked).

Direct mode: every walkable cell uses BASE (uniform).

3.2 Feel without lying

Raising Road move_speed_mult makes the player actually faster on roads and makes Fastest prefer roads in proportion.

Corridor stickiness: when both path endpoints resolve to Road or Trail, Fastest multiplies off-path cell costs (×3) so A* stays on the pavement instead of cutting grassy corners. Direct is unchanged. Escape onto non-path still works if the corridor is blocked.

Building pads: nav blocking for buildings matches runtime collision (PLAYER_RADIUS only). Extra clearance must not seal road cells the player can still walk (that forced grass detours beside storage halls).

3.3 Admissible heuristic

A* octile h must scale by the minimum walkable Fastest cost (fastest terrain, e.g. Road) so paths stay optimal under variable costs.

4. API surface

pub enum PathMode {
    Fastest,
    Direct,
}

// find_path* / PathSession::plan / replan take PathMode
// AutoNavigator reads ClientConfig → PathMode

Call sites:

Caller Mode
AutoNavigator (TUI + gfx click / map target) From ClientConfig
Workers / schedule NPC / wildlife / combat path PathMode::Fastest

5. Client UX

  • Field: ClientConfig.auto_nav_mode ("fastest" | "direct", default fastest)
  • Settings: gfx Connection / play options (F2 or adjacent) — radio or toggle
  • Optional later: keybind to flip mid-route and replan
  • Changing mode while auto-nav is active → replan with the new mode
  • Client version bump when shipping (client-path change)

No content-admin / YAML surface — this is a client preference, not authored content.

6. Implementation checklist

  1. PathMode in crates/pathfinding — wire through find_path*, grid paint, PathSession ✅
  2. Derive costs from shared speed multipliers (or one shared table used by sim + pathfinding) ✅
  3. Fix heuristic for min walkable cost under Fastest ✅
  4. ClientConfig + AutoNavigator + gfx settings UI ✅
  5. Server call sites — pass PathMode::Fastest explicitly ✅
  6. Tests — Fastest detours onto road when ETA wins; Direct crosses slow terrain when shorter; impassable still blocked ✅
  7. Docs — this plan + short cross-link from 11-entities-attributes-and-movement.html ✅

7. Out of scope

  • Per-NPC authored path mode overrides
  • Stamina-minimizing routes (time-only for Fastest v1)
  • Hierarchical / long-range road graphs beyond cell A*
  • Native editor / content-admin map tools for the toggle