JPS+ And Flow-Field Acceleration

Pathfinder now has two acceleration layers for common RTS movement patterns:

• JPS+-style jump successors for long straight or diagonal rays.
• Goal-centered flow fields reused across many units heading to the same destination.

Both systems are implemented as deterministic integer logic, then integrated as additive fast paths that fall back to classic A* whenever preconditions are not met.

Locomotor Classes And Precompute Ownership

The precompute module is declared in GeneralsMD/Code/GameEngine/Include/GameLogic/AIPathfindPrecomputed.h and implemented in GeneralsMD/Code/GameEngine/Source/GameLogic/AI/AIPathfindPrecomputed.cpp.

It reduces locomotor sets into five deterministic classes via PathfindPrecomputed::classifyLocomotorSet:

• GROUND
• AMPHIBIOUS
• CLIFF_CLIMBER
• RUBBLE_WALKER
• CRUSHER

Per class, it stores an Int16 jump table indexed as cellIndex * 8 + direction. Direction encoding is shared with the classic neighbor expansion ordering so both systems talk in the same axis and diagonal indices.

Jump Entry Semantics

Each jump-table value encodes one directional ray result from a source cell:

// For cellIndex c in direction d, m_jumpTable[c * 8 + d] is:
//   > 0  : distance in cells to a forced-neighbor jump point
//   == 0 : immediately blocked from this cell in direction d
//   < 0  : open run length (negated) — no forced jump, just clearance

The sign convention lets a single Int16 fit both "found a jump point at distance N" and "clear for N cells before the edge" without an extra flag. Callers check entry > 0 for a usable jump; entry < 0 is still valuable because it means the ray can be extended another |entry| cells without re-probing the grid.

PathfindPrecomputed::buildClass runs straight sweeps first, then diagonal stubs, and publishes readiness with release-order atomic stores. Callers check readiness with acquire-order loads before consuming the data.

The builder runs in parallel at map setup in PathfindPrecomputed::buildAll: one worker per locomotor class plus one worker for the zone-distance table.

Zone-Distance Lower-Bound Heuristic

PathfindPrecomputed::buildZoneDistanceTable constructs a graph of raw zone adjacencies, then runs BFS from each zone and stores hop counts in a flat matrix.

PathfindPrecomputed::zoneDistanceCost converts hop count into cost by multiplying with 10, matching orthogonal step cost. The value is used as an admissible lower bound. If the table is not ready or zones are disconnected, the method returns 0 and caller logic falls back to octile-only behavior.

JPS+ Integration In Neighbor Expansion

Pathfinder::appendJumpPointSuccessors in GeneralsMD/Code/GameEngine/Source/GameLogic/AI/AIPathfind.cpp is the bridge between precompute and the live open list.

The helper exits early for cases that should remain classic-only:

• Attack-distance pathing.
• Tunneling mode.
• Downhill-only locomotion.
• Non-ground layer parents.
• Missing goal cell.
• Non-ready precompute table for the unit class.

When active, it reads the precomputed jump entry for each of 8 directions, selects either:

• A direct goal intercept on the ray, or
• The forced-neighbor jump point distance.

It then walks the ray conservatively and stops if any intermediate cell is already in open or closed lists, or contains blocking allied occupancy fields. Only safe long jumps are pushed as additional successors.

The classic eight-neighbor expansion still runs immediately after this helper in Pathfinder::examineNeighboringCells, so the optimization is additive. If jump expansion cannot help, behavior remains that of baseline A*.

Flow-Field Cache For Shared Goals

The flow-field module is in GeneralsMD/Code/GameEngine/Include/GameLogic/AIPathfindFlowField.h and GeneralsMD/Code/GameEngine/Source/GameLogic/AI/AIPathfindFlowField.cpp.

PathfindFlowField::build runs Dijkstra outward from a goal cell and stores one byte per cell:

enum : uint8_t {
    FLOW_DIR_MASK    = 0x07,   // bits 0..2 = direction (N/NE/E/SE/S/SW/W/NW)
    FLOW_CELL_GOAL   = 0xFE,   // this IS the goal
    FLOW_UNREACHABLE = 0xFF,   // no path to goal from here
};

Important implementation details:

• Integer costs only: 10 orthogonal, 14 diagonal. Pre-multiplied by 10 so the diagonal factor sqrt(2) * 10 ≈ 14.14 rounds to 14 with stable determinism.
• Deterministic min-heap tie-breaking using an insertion sequence counter — if two cells expand at the same cost, the one enqueued earlier wins. Crucial for lockstep: without this, two peers with the same map but different heap insertion orders would produce different flow fields.
• Diagonal validity requires adjacent orthogonals to be passable, matching classic adjacency constraints — no squeezing through a one-cell diagonal gap between walls.

PathfindFlowFieldCache::getOrBuild keeps an LRU of fields keyed by locomotor class and goal cell. Cache hits splice to the front; misses build synchronously and evict from the tail when full. Failed builds are not retained as permanent negative entries.

Flow Fast Path In Runtime Path Requests

Pathfinder::tryFlowFieldPath in AIPathfind.cpp attempts to produce a full Path without A* when preconditions are safe.

It rejects cases that mismatch the flow assumptions, including:

• Map not ready.
• Downhill-only locomotion.
• Non-ground layers.
• Unavailable flow field for target goal.
• Unreachable start cell in the field.

On success, it forward-walks the field from start to goal, emits path nodes at start, direction bends, and final exact destination, then runs path optimization. A hard step cap protects against corrupted-field infinite loops and forces fallback.

Invalidation And Rebuild Behavior

When map topology changes, both accelerators are invalidated:

• PathfindFlowFieldCache::invalidateAll clears cached fields.
• PathfindPrecomputed::rebuildAsync marks all classes BUILDING, clears zone-distance readiness, and rebuilds in worker threads.

During rebuild windows, readiness checks fail and caller code naturally falls back to classic A* until READY is published again.

Why This Works Well In RTS Loads

Classic A* cost scales with number of path requests. RTS games often issue many requests with shared destination structure. This design attacks both sides:

• JPS+ reduces node expansions for single long-range searches.
• Flow fields amortize work across many units with common goals.

Both retain deterministic lockstep behavior because all decisions are integer-based, class mapping is pure, and cache evolution follows lockstep request order.

Quirks

• Jump table diagonal sweeps are stubbed as phase-two work. Only straight sweeps provide the active shortcut gains today. Diagonal forced-neighbor math is more delicate — it has to check both axis-aligned jump rays from the cell being checked — and was deferred to keep the initial integration safe. The fall-through to classic A* still covers everything the diagonals would accelerate.
• Zone-distance cost duplicates the orthogonal step constant locally. zoneDistanceCost multiplies hops by 10 inline rather than importing the flow-field constant. Constant drift between the two files would require synchronized updates — a subtle coupling that's easy to miss in refactors.
• Flow fields are built synchronously on cache miss. First-touch to a brand-new goal can be noticeably heavier than warmed reuse — on a 256×256 map a fresh build is ~10 ms, a hit is essentially free. The cache is sized to fit typical command destinations (rally points, repeated attack targets); rare goals pay the build cost every time.
• LRU eviction is from the tail only. No negative-cache entry for failed builds — an unreachable goal is rebuilt on every path request, which can show up as CPU cost on maps with many isolated subregions. A negative-cache entry would need careful invalidation on map dirty, so the simpler "no cache" was chosen.
• Zone-distance is a lower bound, not an estimate. It's admissible — using it as an A* heuristic never overestimates, so optimality is preserved. It's also very coarse: two cells in the same zone report distance 0, which means the heuristic only helps for inter-zone searches. Intra-zone searches still rely on octile distance.
• Async rebuild uses release/acquire atomics. Readers check readiness with acquire-order loads before consuming the data, so a partially-built jump table can never be read as ready. This is more load-bearing than it looks — even one frame of "table is halfway" would mean inconsistent pathing across peers.