ENG2-P8-01: Grid A* + flow fields reusing ecs/spatial_grid; nav FFI surface (#546)

[aram-devdocs]

Parent

• Program: ENG2 — GoudEngine v2 Rebuild (see the pinned master tracking issue)
• Phase / Milestone: Phase 8 — Capability Gaps (eng2-p8-capabilities)
• Batch / Group: Batch 8.1 — Highest-demand capabilities, Group A
• Runbook spec: docs/src/runbook/phases/phase-8.md (committed with the roadmap)

Summary

Add a grid-based A* pathfinder and flow-field solver built on the existing ecs/spatial_grid data structure, plus an FFI surface (handle registry, request/query functions) so all 10 SDKs can request paths. Closes #546.

Architecture Context

Layer: Layer 3 (Services) for the pathfinding module (new goud_engine/src/ecs/nav/ or sibling of ecs/spatial_grid/, consuming ecs/ types only); Layer 5 (FFI) for the new ffi/nav/ export surface.
Modules/types touched:

• goud_engine/src/ecs/nav/ (new) — grid A* implementation, flow-field solver, obstacle/cost-grid representation.
• goud_engine/src/ecs/spatial_grid/core.rs, grid.rs, queries.rs — reused as the underlying cell/neighbor representation; do not fork a second grid type.
• goud_engine/src/ffi/nav/ (new, mirrors goud_engine/src/ffi/spatial_grid/mod.rs structure: lifecycle.rs + operations.rs + queries.rs, handle-registry pattern).

Boundary constraints (only those that apply):

• No raw GPU calls here; this is CPU-only pathfinding logic.
• FFI exports: #[no_mangle] extern "C", #[repr(C)], null checks, // SAFETY: comments.
• Downward-only deps: ecs/nav/ MAY depend on ecs/spatial_grid/ and core/; it MUST NOT depend on ffi/, sdk/, or rendering/.

Pattern to follow: goud_engine/src/ffi/spatial_grid/mod.rs:1-24 — global registry keyed by a u32 handle (GoudSpatialGridHandle), lifecycle/operations/queries module split, GOUD_INVALID_*_HANDLE sentinel constant. Mirror this exactly for the nav grid handle rather than inventing a new FFI shape.

Scope

• Grid A* over a cost grid: 4/8-directional neighbor expansion reusing SpatialGrid's cell/coordinate types (ecs/spatial_grid/core.rs, grid.rs::CellCoord).
• Flow-field solver: single-source Dijkstra/BFS producing a per-cell direction field for many-agent-to-one-goal queries (avoids per-agent A* when N agents share a destination).
• Obstacle/cost representation: per-cell walkable/blocked flag plus optional movement-cost weighting.
• FFI surface: create/destroy a nav grid (handle registry per the spatial_grid pattern), set obstacles, request a path (A*), request/query a flow field, free returned path buffers.
• Tests: spec test + unit tests for A* correctness (known shortest paths on fixture grids) and flow-field correctness (direction-field matches BFS distances).
• Docs/rules updates: extend .agents/rules/ecs-patterns.md with the nav module's place in the layer model if it introduces a new top-level ecs/nav/ directory.

Acceptance Criteria

• A* returns optimal-cost paths on fixture grids (straight line, single obstacle, maze) with correctness asserted against precomputed expected paths.
• Flow-field output matches BFS distance ordering for all reachable cells from the goal.
• PERF: 10k agents repathing (or querying a shared flow field) within ≤ 5 ms/frame budget on a scripted scene, per the Phase 8 gate in docs/src/runbook/phases/phase-8.md and perf-dod.md.
• FFI nav surface has wrappers in all 10 SDKs (sdks/) and passes python codegen/validate_coverage.py.
• cargo check && cargo fmt --all -- --check && cargo clippy -- -D warnings clean; cargo test green; ./codegen.sh && git diff --exit-code (drift gate)

Breaking Change & Throne Follow-up

None — additive/internal (new module, new FFI surface; no existing exports change).

Blocked By

ENG2-P5-03 (work-stealing job system — batch repathing across many agents should run on the job system rather than blocking the main thread; land the job system first so nav can use it from day one instead of retrofitting parallelism later).

Files Likely Touched

• New: goud_engine/src/ecs/nav/mod.rs, goud_engine/src/ecs/nav/astar.rs, goud_engine/src/ecs/nav/flow_field.rs, goud_engine/src/ffi/nav/mod.rs, goud_engine/src/ffi/nav/lifecycle.rs, goud_engine/src/ffi/nav/operations.rs, goud_engine/src/ffi/nav/queries.rs
• Generated: SDK bindings under sdks/*/ for the new nav FFI exports (via ./codegen.sh)
• Modified: goud_engine/src/ffi/mod.rs (register new nav module), codegen/goud_sdk.schema.json (nav export schema)

Agent Notes

• No navigation module exists anywhere in the engine today — grep-verified (pathfind|navmesh|flow.?field|nav_grid, case-insensitive, across goud_engine/src) returns zero matches. This closes Add grid-based A* pathfinding module #546 ("Add grid-based A* pathfinding module"), which is currently open with no prior implementation.
• ecs/spatial_grid/core.rs:1-22 is a point-based grid (SpatialGrid) with O(1) insert/remove/update and O(k) radius queries, explicitly documented as "Independent of the physics system" and designed for "AI neighbor lookups, combat range checks, resource gathering" — reuse its CellCoord (ecs/spatial_grid/grid.rs) and cell-indexing scheme as the nav grid's coordinate system rather than building a parallel grid type. Note this is distinct from ecs::broad_phase::SpatialHash, which is AABB-based and physics-oriented — do not conflate the two.
• FFI precedent for handle-based subsystems already exists at goud_engine/src/ffi/spatial_grid/mod.rs:1-24: a global registry keyed by u32 handle, GOUD_INVALID_SPATIAL_GRID_HANDLE sentinel, and a lifecycle.rs/operations.rs/queries.rs split. The nav FFI surface should be structurally identical (GoudNavGridHandle, GOUD_INVALID_NAV_GRID_HANDLE, same three-file split) so SDK codegen and consumers see a familiar shape.
• Flow fields are explicitly named in the roadmap because they align with Throne's own hierarchical-pathfinding plan (throne_ge repo, phase-1.md:138-143) — Throne's THR-C-01 sync issue will evaluate adopting this engine capability over its own C# stub once it lands.

Verification

cargo check && cargo fmt --all -- --check && cargo clippy -- -D warnings
cargo test
./codegen.sh && git diff --exit-code
python3 scripts/bench-gate.py  # nav repath budget, per perf-dod.md