Skip to content

Path Foundation

The current path layer is a synchronous pathfinding foundation with sparse-resident support as detailed below. It lives under include/tess/path/ and is exported by tess/tess.h. tess/path/path.h remains the public umbrella for core path APIs; larger implementation sections may live in include/tess/path/detail/ and are included from that umbrella. The route cache (UnitRouteCache, cached_astar_path) lives in tess/path/route_cache.h, which the umbrella includes, so including tess/path/path.h or tess/tess.h keeps compiling the full core path surface.

A shared lifetime policy applies to every path cache: caches never hand out views into storage that can reallocate. Results are either copied into caller-supplied scratch/storage, or point at per-entry heap allocations that other entries cannot move.

Choosing a Path Strategy

Choose for the workload first; the optional region-graph precheck can guard any search and only skips it when connectivity is definitively unreachable.

flowchart LR
  accTitle: Optional topology precheck
  accDescr: Only an Unreachable precheck result skips grid search; every other status continues conservatively.

  Graph["Optional fresh RegionGraph"] --> Precheck["precheck_path"]
  Precheck -->|Unreachable| Stop["Return without grid search"]
  Precheck -->|Every other status| Choose["Choose a search strategy"]

Unit-Cost Workloads

flowchart TB
  accTitle: Unit-cost pathfinding strategy
  accDescr: Shared goals favor fields, retained route reuse favors the cache, and isolated requests use A star.

  Unit["Unit-cost requests"] --> Shared{"Many starts share goals?"}
  Shared -->|Yes| Field["Distance field or field product"]
  Shared -->|No| Stable{"Stable map and route reuse?"}
  Stable -->|Yes| Cached["cached_astar_path or runtime route cache"]
  Stable -->|No| AStar["astar_path"]

Weighted Workloads

flowchart TB
  accTitle: Weighted pathfinding strategy
  accDescr: Isolated weighted requests use A star, while shared goals favor weighted fields or bounded batches.

  Weighted["Weighted requests"] --> Shared{"Many starts share goals?"}
  Shared -->|No| AStar["weighted_astar_path"]
  Shared -->|Yes| Bounded{"Small known maximum cost?"}
  Bounded -->|Yes| Batch["bounded field or weighted_path_batch"]
  Bounded -->|No| Field["weighted distance field"]

Public Surface

  • PathRequest contains a start and goal Coord3.
  • PathTieBreak optionally seeds deterministic tertiary ordering among A* nodes with equal search cost and progress. A zero seed preserves canonical tile-index ordering; nonzero seeds can change route shape but not optimal cost or passability.
  • PathStatus reports NotComputed, Found, InvalidStart, InvalidGoal, NoPath, Indeterminate, CostOverflow, or NoCandidate. NotComputed means a default, cleared, stale, or model-mismatched product has no current result. NoCandidate means a bounded or heuristic strategy found no candidate and an exact search is required for a reachability conclusion. Indeterminate occurs only on sparse worlds: the search reached the edge of the resident set and could not rule out a route through a non-resident chunk, so it is deliberately distinct from NoPath. NoPath means no route exists in the graph considered under the selected missing-chunk policy; it is a whole-world conclusion only when no unknown boundary was assumed impassable. A caller that receives Indeterminate can materialize the missing chunks and retry. CostOverflow means every remaining realized route required a cost at or above the reserved uint32_t infinity sentinel; it carries no usable path.
  • MissingChunkPolicy selects how a search treats a step into a non-resident chunk of a sparse world: AssumeImpassable treats it as impassable (the search stays within the resident set and may report NoPath), while ReportIndeterminate returns PathStatus::Indeterminate rather than a possibly-wrong NoPath when the search exhausts the resident set having skipped a non-resident neighbor. It is inert for dense (AlwaysResident) worlds, where every chunk is resident.
  • precheck_path<ClassOrTag> (in tess/path/precheck.h) is a cheap pre-A topology gate: it consults a RegionGraph built over the world for whether start can reach goal through region connectivity, without expanding the grid, and returns a PrecheckStatus. The explicit first template argument is the movement class the SEARCH uses (a raw passable tag normalizes to its UnitCostFieldMovement identity, exactly as in astar_path). Only Unreachable -- the graph definitively rules out any route within known topology -- licenses skipping A, reported by precheck_rules_out_path. Every other status means "run A": Reachable (a region path exists; A realizes it), MissingChunk (the search reached a boundary exit into a non-resident chunk, so a route through non-resident space cannot be ruled out -- sparse worlds only), InvalidStart / InvalidGoal (A* is authoritative on tile validity), GraphStale (the graph no longer matches the world OR was labeled for a different movement class or provider instance/revision), and NoGraph (no built graph supplied). The overloads accept the same MissingChunkPolicy as authoritative search and default to ReportIndeterminate. Under AssumeImpassable, a resident search region cut off only by non-resident space is Unreachable, while a non-resident endpoint is InvalidStart or InvalidGoal. The path runtime forwards its selected policy to this precheck, so the optimization cannot silently change the requested semantics. Staleness is resolved conservatively and first: an empty graph is NoGraph and a graph that fails is_region_graph_fresh_for<ClassOrTag> -- topology versions, residency snapshot, or the movement-class stamp -- is GraphStale. The provider-aware overload also requires matches_provider(provider). These checks happen before reachable(), so neither a stale snapshot, wrong-class graph, nor equal-revision graph from another provider object can yield a definitive but wrong Unreachable. The query reuses a caller-owned RegionGraphScratch (allocation-free once warm); the gate can only ever prune provably unreachable goals, never turn a solvable query into a wrong failure.
  • Sparse residency covers the single-shot searches -- astar_path, weighted_astar_path, the unweighted build_distance_field, and the weighted build_weighted_distance_field, build_weighted_distance_field_in_box, and build_bounded_weighted_distance_field, plus their readers distance_field_path and weighted_distance_field_path -- and the path runtime built on them: weighted_path_batch, the unit route cache (UnitRouteCache, cached_astar_path), and PathRequestRuntime::process_unit_cached / process_weighted_batch. The route cache's world fingerprint is residency-aware -- it folds each resident chunk's key, residency generation, and meta().content_version through an order-independent sum -- so any eviction, rematerialization, or in-place edit changes the fingerprint and invalidates the whole cache before a stale route can be served. The two-call builder/reader distance-field API stamps world.residency_fingerprint() in DistanceFieldScratch at build time -- the route cache's terms plus each chunk's resident slot, since a distance field is indexed by slot where the route cache is keyed by coordinate; a reader whose world changed residency between the paired calls -- or a scratch read against a different/copied/swapped world -- returns NotComputed (forcing a rebuild) rather than descending a slot-rebound stale field. Each single-shot builder takes an optional trailing MissingChunkPolicy whose default is ReportIndeterminate. Runtime, cache, batch, precheck, and path-agent layers pass the selected policy through without substituting another value. Agent movement commit is residency-safe to match: validate_movement_intent and movement_versions_match reject a move into or out of a non-resident chunk with the transient StaleContent (a non-resident chunk is a recoverable, not terminal, condition), so an agent whose route crosses a chunk evicted since planning re-plans against the changed residency instead of stranding or walking into non-resident data. The readers are pure readers (a non-resident start is InvalidStart). Still dense-only -- a compile error to instantiate on a sparse world -- are the distance-field product family (build_distance_field_product, distance_field_product_path, nearest_target), the unit field-product cache (process_unit_cached's repeated-goal pass, guarded out for sparse worlds), and the route/portal route products. Those are retained artifacts indexed by raw tile ID and require an AlwaysResidentWorld.
  • PathResult returns status, movement cost ticks, expanded-node count, reached-node count, a PathView, and cost_scale. Default orthogonal and axial-hex models use scale one. Diagonal models use scale 128: cardinal steps cost 128 ticks and diagonal steps cost 181 ticks per destination entry-cost unit; 181 is the nearest scale-128 integer approximation to sqrt(2). NearestTargetResult carries the same scale.
  • CostRangeAssessment and path_cost_range_assessment<World, MovementClass, Provider> expose a conservative compile-time classification of the compact std::uint32_t cost domain. ProvenSafe means every simple path fits below the reserved infinity sentinel, PotentialOverflow means the known conservative bound does not, and Unknown means a cost expression or provider lacks a usable maximum. require_proven_path_cost_range is the opt-in compile-time gate; queries themselves remain available for every assessment and report a realized overflow as PathStatus::CostOverflow.
  • PathView (in tess/path/path_view.h) is the non-owning view of a path that PathResult and the runtime's ticket accessors hand out. It carries the same lifetime contract as the underlying span -- valid only until the storage it views is reused (A* scratch on the next query, the runtime's node buffer on the next process/clear) -- and copying it never copies path data. It offers read-only span parity (size, empty, operator[], front, back, begin/end, data), span() to recover the raw std::span where an API needs it, and suffix(offset): the remaining path from a walked index, bounds-clamped (an offset at or past the end yields an empty view) and sharing the same storage without copying. It is constructible from a std::span or a std::vector<Coord3>, so existing result-construction sites are unchanged.
  • The optional tess/io.h header provides human-readable stream insertion for PathStatus and PathView. Streaming a path traverses its borrowed coordinates without extending their lifetime. The text is diagnostic output, not a supported serialization format.
  • DistanceFieldResult returns the status and node counts for a reverse shared-goal field build.
  • WeightedPathBatchStats returns request count, unique-goal count, field build count, A* fallback count, and copied path-node count for weighted batch planning.
  • PathScratch owns reusable vectors for open nodes, visited records, and the returned path. reserve_nodes(count) prepares storage for allocation-free repeated queries when capacity is sufficient.
  • DistanceFieldScratch owns reusable vectors for reverse shared-goal fields and reconstructed paths. reserve_nodes(count) also prepares weighted bucket storage for allocation-free bounded weighted field rebuilds after warmup.
  • GoalSet, DistanceFieldProduct, and FieldProductCache provide reusable unit-cost and weighted distance-field products in tess/path/field_product_cache.h. Products copy retained dense field data out of scratch, track reached transition and clearance content-version dependencies, stamp the resolved lattice/class/step model, and can be stored in a byte-budgeted LRU cache. Diagonal products use reverse Dijkstra for their non-unit geometric ticks; axial products use the six-neighbor reverse flood.
  • build_weighted_distance_field_product<World, Class> runs reverse Dijkstra from an ordered goal set through the resolved movement model, including provider-composed edges. weighted_distance_field_product_path reconstructs an exact path and weighted_nearest_target reports the selected lowest-cost goal. These persistent products are explicitly dense-only, stamp every model identity, stateful-provider object identity, and provider revision, and use the same byte-budgeted cache through lookup_weighted / store_weighted. Provider instances and revisions are exact cache-key components: historical revisions remain reusable entries until ordinary LRU eviction, so callers with continually changing provider state should configure a finite byte budget. A stateful provider must stay at an address-stable address while a product or cache can retain that identity, and callers must clear those artifacts before destroying it. Moving a cache is safe because the provider remains externally owned; moving the provider causes a conservative miss/rebind at its new address.
  • Unit products retain the BFS fast path only for regular unit-cost models. Provider-composed products use reverse Dijkstra even when the regular step scale is one, because a provider may attach a larger exact cost to a special edge.
  • UnitRouteCache (in tess/path/route_cache.h) owns reusable route-cache entries and cached path nodes for exact route and same-goal suffix reuse. Exact (start, goal) lookups and suffix lookups are served by open-addressed flat hash indexes (power-of-two capacity, linear probing) instead of linear scans; the suffix index is populated per stored Found-path node with first-write-wins, so the earliest stored entry containing a queried node keeps winning deterministically. Cache hits copy the cached route into the caller's PathScratch and return a span into that scratch, so hit and miss results share one lifetime: valid until the next path call that uses the same scratch. Later misses may grow cache-internal storage without invalidating results returned through other scratches. Storage is capped (set_caps(UnitRouteCacheLimits); defaults 512 entries and 2^20 path nodes): an insert that would exceed either cap invalidates the whole cache first and counts a cap_invalidations stat. Lowering either cap below the live footprint applies the same invalidation immediately, including a zero cap; existing entries can never remain readable above a new limit. stats() reports the counters as UnitRouteCacheStats. invalidate() drops cached route data and both indexes while preserving hit/miss counters; clear() drops routes and resets counters. capture_world_versions(world) and invalidate_if_world_changed(world) provide coarse whole-cache invalidation from chunk content-version fingerprints. The cache also binds the resolved lattice, step, cost scale, provider type, live stateful-provider object, and provider revision. A provider rebind invalidates entries and increments provider_rebinds. Non-unit models retain exact hits but conservatively skip suffix reuse whose historical step-count arithmetic cannot recover cost.
  • ContentVersionDependencies records explicit chunk/content-version pairs and can validate whether those chunks are unchanged. It is supporting infrastructure for retained route products; current unit-route-cache hits use conservative whole-cache invalidation by default.
  • WeightedRouteProduct stores one verified weighted route plus the chunk content versions touched by that route. Replaying it succeeds only while those chunk content versions are unchanged.
  • WeightedPortalRouteProduct stores a supplied-waypoint weighted route product. It stitches exact weighted A* segments through caller-provided portal waypoints, stores the resulting path, and validates content versions on replay. It also supports an automatic chunk-boundary portal builder and reports candidate and boundary-scan counters for that automatic builder.
  • WeightedPortalSegmentCache owns caller-managed weighted portal segment entries for repeated builds with the same portal waypoints. Entries belong to one movement class. for_class<ClassOrTag>() returns the required lightweight view; binding a different class clears all entries, and each view operation rechecks its class so an older retained view cannot alias another class's paths. On a hit, the view's lookup_append(world, request, out_path) appends the cached segment path into caller-owned storage (deduplicating a shared junction node when stitching consecutive segments) and returns a SegmentHit with the found flag, status, and cost. The cache never returns pointers or spans into its own storage, so store() growth cannot invalidate a previous lookup. Found segments record content-version dependencies for the chunks touched by the segment path; cache hits are reused only while those versions still match. Failed segments are not cached, and stale hits leave the output storage untouched. Storage is bounded by a segment budget (set_segment_budget, default 256 entries). Lowering the budget immediately evicts the oldest entries and reclaims their path storage. At insertion time, a store at budget first sweeps stale entries in one compaction pass that also rebuilds the path-node arena, then evicts the oldest live entries in insertion order if needed; a zero budget stores nothing. stats() reports entries, path nodes, sweeps, evictions, and stale rejections as PortalSegmentCacheStats. Segment construction and stale compaction commit transactionally. If allocation fails, no partial dependency set becomes visible, live entries and their path-node offsets remain unchanged, observable statistics do not advance, and the operation can be retried. reserve_segments_checked and reserve_path_nodes_checked report deterministic pre-allocation capacity failure through ReserveStatus. The class view's store_checked reports capacity failure through PortalSegmentStoreStatus, but not before allocating: a store already at its segment budget is bounded by how many entries survive compaction, which is only known after a full dependency-validity sweep, so it rejects in constant time where it can and otherwise captures the candidate entry's dependencies first. That capture appends to an unreserved vector, so a path crossing several chunks may reallocate more than once before the status comes back. Cache storage is untouched either way. See the exception-free note, which is authoritative here. Oversized reserve and store calls preserve std::length_error with exceptions enabled and fail fast for the same detected error without exceptions.
  • WeightedPathBatchScratch owns reusable search scratch and retained copied result paths for weighted batch planning.
  • PathRequestRuntime owns a small deterministic request/result lifecycle for simulation callers. submit(request) returns a PathTicket, processing methods copy completed paths into runtime-owned storage, and publish the complete result batch only after every borrowed path span has been installed. try_result(ticket) returns no value for a detectable stale, out-of-range, or unpublished lookup; result(ticket) fails fast for those same conditions rather than manufacturing NoPath. A throwing provider leaves the new batch unpublished, including its result-status and path-node counters. Cache counters continue to describe the retained cache state. Tickets remain valid until clear_requests() starts a new request set. Tickets do not carry runtime identity, so passing a ticket from another runtime remains an unenforceable precondition when its index and generation happen to match. clear_requests() starts a new request set without dropping long-lived caches; clear_caches() drops the owned unit route cache, shared unit/weighted field-product cache, and weighted portal segment cache. PathRuntimeCachePolicy::clear_every_world_change lets long-lived callers reclaim caller-managed cache storage after repeated world edits, and the policy also carries the route-cache caps (max_route_entries, max_route_path_nodes) and the portal segment budget (portal_segment_budget), applied to the owned caches at the start of each processing pass. Reducing a policy budget therefore takes effect before any lookup in that pass.
  • PathAgentState and the path-agent helper functions provide the first simulation-facing path wrapper. Agents store position, goal, path ticket, path index, an optional last_result, active-goal state, and an explicit PathAgentPhase lifecycle (Idle, NeedsPath, Following, Blocked, Unreachable) with a blocked_retries budget. The helpers submit active agents into a PathRequestRuntime, apply ticketed results, and advance agents along returned paths. Occupied or reserved destinations keep the Found route and enter Blocked so the retained step can be retried; other transient failures invalidate the route and enter Blocked for replanning. Structural failures (invalid endpoints, non-adjacent steps) are terminal Unreachable until a new goal is assigned.
  • process_unit_path_agents<World, ClassOrTag>(world, agents, runtime, policy) and process_weighted_path_agents<World, Class, MaxCost>(world, agents, runtime, policy) run the current conservative synchronous agent pathing loop. They resubmit active agents each processing pass, so stale PathTicket values do not survive runtime request clears. Provider-aware trailing overloads bind runtime planning and retained-route movement commits to the same provider instance and revision.
  • SimClock, PathAgentTickState, PathAgentTickOptions, and PathAgentTickStats provide the first minimal path-agent tick wrapper. tick_unit_path_agents<World, ClassOrTag>(state, world, agents, runtime, options) and tick_weighted_path_agents<World, Class, MaxCost>(state, world, agents, runtime, options) and the _with_movement variants advance the clock, process paths when state.pathing_dirty is set or when any agent is in NeedsPath or has a route-invalidated Blocked state (with retry budget remaining), then move agents up to options.max_steps path nodes. Processing is SCOPED (per-agent pathing dirt): state.pathing_dirty is world-scoped and replans every agent, while agent-scoped needs (a newly armed goal, a Blocked retry) replan only those agents -- Following agents keep walking routes retained in state.routes (PathAgentRoutes; index-paired with the agents span, so reordering or removing agents requires a mark_pathing_dirty -- see the struct comment). In the class forms ONE movement class drives pathing, the precheck, and (for the _with_movement variants) commit validation, so plan and commit provably agree per class. Goals assigned through either set_path_agent_goal overload are picked up on the next tick. Blocked agents consume one retry per following movement-enabled tick until options.max_blocked_retries runs out. The default RemainBlocked exhaustion policy then sleeps without inventing NoPath; MarkUnreachable explicitly selects the historical terminal transition. Occupied/reserved destinations retry the retained step without processing because occupancy is intentionally absent from planning passability; other transient failures request a re-search. Ticks with max_steps == 0 pause the retry budget without attempting movement. Successful movement resets the consecutive-block count. mark_pathing_dirty(state) remains the hook -- and the only correct one -- for replans after world edits.
  • BlockedAgentRecoverySchedule is caller-owned scheduling scratch for persistently blocked checks. It applies deterministic exponential backoff, equal jitter, round-robin fairness, and a per-call selection cap, but never claims reachability. A position change starts a fresh recovery episode even when an agent moves and becomes blocked again within one tick. PathAgentReplanQueue separately deduplicates replan requests in FIFO order. process_path_agent_replans composes that lifecycle with a synchronous caller callback, immediately copying its borrowed PathResult into retained routes. It does not validate the callback's route. The exact unit and weighted helpers build on this generic drain and perform no more than the configured request count. A successful blocked-agent replan keeps the retry streak until movement proves progress. Both mechanisms are externally synchronized and index-paired with the agent span. The replan budget does not bound work within one synchronous callback or A*.
  • astar_path<World, PassableTag>(world, request, scratch, policy) runs optimized unit-cost deterministic pathfinding. The passability field is treated as boolean-like. It runs natively on sparse worlds, honoring MissingChunkPolicy (the pre-A* fast-path scan is compiled out there). The tag parameter also accepts a tess::movement class: a raw tag normalizes to the byte-identical UnitCostFieldMovement identity class, and a composed class contributes its passability predicate (unit search ignores entry cost). A trailing provider overload composes allocation-free special edges and disables regular direct-route shortcuts that could miss a cheaper special route.
  • weighted_astar_path<World, Class>(world, request, scratch, policy) runs deterministic weighted A* over ONE movement class fusing the passability predicate and the u32-saturated entry-cost expression (0 = impassable). It includes exact unit-cost direct and blocked-axis detour fast paths when their local optimality proofs apply. Like astar_path, it is sparse-capable and honors MissingChunkPolicy (the fast paths are compiled out for sparse worlds). Weighted APIs require one explicit movement class, normally movement::PositiveCostFieldMovement<PassableTag, CostTag>. They reject raw tags at compile time — a raw tag would normalize to the unit-cost identity class and silently discard the cost field. The class-typed path, field, product, batch, cache, and runtime families accept matching trailing provider overloads. Reverse operations require the provider's reverse-enumeration contract. Reverse enumeration independently rejects a missing or impassable forward destination rather than relying on a field builder to prevalidate its frontier. Persistent products capture model identity plus provider instance and revision; until a generic provider dependency index exists, provider-composed dense products conservatively depend on every world chunk.
  • build_weighted_route_product<World, Class>(world, request, scratch, product) builds and stores a weighted route product.
  • weighted_route_product_path(world, product) replays a stored weighted route product if its chunk dependencies are still valid.
  • build_weighted_portal_route_product<World, Class>(world, request, waypoints, scratch, product) builds a supplied-waypoint portal route product.
  • build_weighted_portal_route_product<World, Class>(world, request, waypoints, scratch, segment_cache, product) builds the same supplied-waypoint route product while reusing cached segment results.
  • build_weighted_chunk_portal_route_product<World, Class>( world, request, scratch, product) derives adjacent chunk-boundary portal route candidates, chooses the lowest-score candidate, then builds the same weighted portal route product.
  • weighted_portal_route_product_path(world, product) replays a stored portal route product if its chunk dependencies are still valid.
  • weighted_path_batch<World, Class, MaxCost>(world, requests, scratch) groups weighted requests by goal, builds bounded weighted fields for repeated goals, uses weighted A for singleton goals, and returns borrowed result spans backed by WeightedPathBatchScratch until its next mutation. A shared reverse field's CostOverflow is global rather than start-specific, so every member in that group retries through weighted A to preserve exact per-request statuses.
  • PathRequestRuntime::process_unit_cached<World, ClassOrTag>(world, policy) processes the current request set through cached_astar_path, optionally reuses unit distance-field products for repeated goals when policy.use_unit_field_product_cache is set, invalidates the unit route cache when chunk content versions change, and returns borrowed result spans backed by the runtime until the next processing pass or request reset. The opt-in field-product pass only considers repeated single-goal groups, requires at least unit_field_product_min_start_chunks distinct start chunks by default, and reports candidate, used, and skipped group counts in PathRuntimeStats. Before building, the runtime verifies that the configured byte budget can hold the product's mandatory world-sized distance labels. An undersized budget skips directly to exact per-request search, avoiding a doomed build and an over-budget store. Invalid out-of-shape starts are resolved to InvalidStart during the existing grouping pass before any unchecked tile-key conversion. This adds no second validation pass and no duplicate passability read. The unit route cache keys entries on (start, goal) plus a content-version fingerprint and nothing on the movement class, so each unit process call binds the runtime to its (normalized) class: a rebind clears the unit caches -- correct even on misuse -- and counts in PathRuntimeStats::class_cache_invalidations. One runtime per (world, class) is therefore the PERF contract, not a correctness precondition. Weighted portal-route builders bind the owned portal segment cache through the same normalized movement-class identity. Reusing one runtime across classes is therefore safe but clears both unit and portal entries; one runtime per (world, class) avoids those conservative drops.
  • PathRequestRuntime::process_weighted_batch<World, Class, MaxCost>(world, policy) processes the current request set through weighted_path_batch. When use_weighted_field_product_cache is enabled on a dense world, repeated goals spanning the configured number of start chunks first use a persistent weighted product; remaining requests retain the bounded-field or A* batch fallback. The product cache survives processing calls and uses the same world-change cadence for invalidation. Unit and weighted products share that one runtime-owned cache. Whichever processing pass runs most recently applies its corresponding policy byte budget to the combined footprint and may therefore evict products retained by the other pass. One movement class drives both the search and the precheck.
  • Both process_unit_cached and process_weighted_batch take an optional trailing const RegionGraphT<World::residency_type>* (default nullptr). When a graph is supplied, a pre-A* pass runs precheck_path for each request and resolves the ones it proves Unreachable to NoPath (zero expanded nodes) without searching, counting them in PathRuntimeStats::precheck_ruled_out -- a subset of no_path, so aggregate failure counts are unchanged. The unit path skips ruled-out requests in its search loop; the weighted path runs the batch over only the survivors and scatters results back to their original slots. Passing nullptr (the default) is byte-identical to the un-gated path. Class and provider agreement are enforced through the graph's stamps (is_region_graph_fresh_for and matches_provider): a graph labeled for a different class or provider than the call searches with degrades to GraphStale (nothing ruled out) rather than pruning a route the exact search can walk. The gate can only prune provably unreachable goals, never turn a solvable query into a failure.
  • cached_astar_path<World, PassableTag>(world, request, scratch, cache) checks the route cache before falling back to astar_path. Hits copy the cached route into scratch and return a span with the same lifetime contract as a miss.
  • build_distance_field<World, PassableTag>(world, goal, scratch, policy) builds a unit-cost reverse distance field from one passable goal. On a sparse world it floods only the resident set; under MissingChunkPolicy::ReportIndeterminate a field truncated by a non-resident chunk reports PathStatus::Indeterminate instead of Found.
  • distance_field_path<World, PassableTag>(world, request, scratch) reconstructs a start-to-goal path from the most recent matching field. It is a pure reader. A reached start can still return Found from a field whose build reported Indeterminate; an unreached or non-resident start preserves that Indeterminate outcome. Under AssumeImpassable, the corresponding outcomes are NoPath and InvalidStart. Mismatched scratch or an inconsistent descent gradient is NotComputed, never a reachability claim.
  • build_distance_field_product<World, PassableTag>(world, goals, product, scratch) builds a multi-source unit-cost product for an ordered GoalSet.
  • distance_field_product_path<World, PassableTag>(world, start, product, scratch) replays a path from a valid product; nearest_target follows decreasing distances and returns a NearestTargetResult with the status, cost, reached goal coordinate, node counts, and path span.
  • build_weighted_distance_field<World, Class>(world, goal, scratch, policy = ReportIndeterminate) builds a weighted reverse Dijkstra field for positive integral entry costs. On a sparse world it honors MissingChunkPolicy: a field truncated by a non-resident chunk is Found under AssumeImpassable and Indeterminate under ReportIndeterminate.
  • build_weighted_distance_field_in_box<World, Class>(world, goal, domain, scratch, policy = ReportIndeterminate) builds the same exact weighted reverse field, but only inside the supplied Box3 domain. The domain filter runs ahead of the residency check, so a tile outside the box is never reached even when its chunk is resident.
  • build_bounded_weighted_distance_field<World, Class, MaxCost>(world, goal, scratch, policy = ReportIndeterminate) builds the same exact weighted reverse field through a bounded bucket queue when all reached entry costs are between 1 and MaxCost. If it encounters a higher positive entry cost, it falls back to the general weighted field builder, forwarding the missing-chunk policy.
  • weighted_distance_field_path<World, Class>(world, request, scratch) reconstructs a weighted start-to-goal path from the most recent matching weighted field and follows the same retained Indeterminate, InvalidStart, NoPath, and NotComputed rules as the unit-cost reader.

Behavior

The unit-cost raw-tag/default-step APIs on an orthogonal shape use six axis-adjacent candidates in fixed order:

+x, -x, +y, -y, +z, -z

Resolved movement-class APIs instead use their shared transition model. Diagonal policies add four clearance-checked planar diagonals after the face steps; axial-hex shapes use their six fixed axial directions; providers append their special transitions after regular steps. Candidates outside the compile-time shape are rejected through the existing shape containment helpers. Degenerate axes naturally reject out-of-bounds neighbors.

The default orthogonal astar_path costs are unit-weighted and use Manhattan distance. Resolved models use Manhattan distance for orthogonal default steps, fixed-point octile distance for diagonal steps, and axial distance for hex steps. A model with special provider transitions uses a zero heuristic because an extra edge may make geometric progress more cheaply than the regular lattice. Tie-breaking is deterministic by lower total score, then higher path cost for equal-score nodes, then tile-key order. Preferring higher path cost on equal-score nodes avoids open-grid wavefront expansion while preserving shortest paths.

weighted_astar_path charges the destination tile's positive integral entry cost for each move. The start tile's cost is not charged, but start and goal costs must be positive. Zero-cost and negative signed-cost tiles are treated as blocked, and oversized integral costs saturate to the public 32-bit path-cost range. Weighted A* uses a binary heap and the resolved model's admissible heuristic in model ticks, so it preserves optimal weighted paths while skipping the unit-cost-only bucket queue and route cache. The default orthogonal model also includes an exact direct Manhattan fast path when every entered tile on a probed route has cost 1; no positive-cost path can beat that Manhattan lower bound. For axis-aligned routes where the straight line is blocked, it can also return a one-tile parallel detour when every entered detour tile has cost 1; any positive-cost path around the blocked line needs at least Manhattan+2 moves.

Before entering open-set A, the implementation probes direct Manhattan paths in the shape-relevant axis orders. If any route is fully passable, it returns that direct shortest path immediately. If a direct probe hits a blocked tile whose axis plane is fully blocked, it returns NoPath immediately because the plane separates start from goal under the current axis-adjacent movement model. For axis-aligned requests, a clear one-tile parallel detour is also returned before A because its Manhattan+2 cost is optimal when the straight line is blocked. For top-down 2D requests blocked by a non-separating axis plane, the implementation can scan that plane for the cheapest passable gap and return a verified Manhattan route through it; the same logic applies to vertical 2D layouts. It also handles 2D forced-gap sequences by walking toward the goal, scanning a barrier line only when the next progress step is blocked, and accepting only fully open lines or lines with exactly one passable gap. In 3D, a blocked direct route can scan the blocked axis plane for the cheapest passable crossing and return a verified Manhattan route through it. Other non-separating blockers fall back to normal A*.

Pre-A* scan cost model

The fast paths above are accepted with an O(world-slice) worst case (decision logged in docs/planning/optimization-log.md, 2026-07-06). The direct probes walk up to the Manhattan distance per axis order. A blocked probe triggers is_full_axis_barrier, which scans the impassable tile's full axis plane: one extent line in 2D, size.y * size.z (or the matching pair) tiles in 3D. The 2D plane-gap and forced-gap scans each walk one extent line per blocked step, and the 3D plane-gap scan walks the whole blocked plane. Every scan runs before any A node is expanded, so a miss — the scans all fail and the query still floods A — pays the full scan cost as pure overhead on top of the search. Two worst-case benchmarks pin this cost: path/astar_plane_gap_miss_512x512 (direct blocked, sealed wall gap, falls through every 2D scan into a full-flood NoPath A) and path/astar_plane_gap_miss_3d_64x64x16 (the best-scoring 3D plane gap is sealed, so segment stitching fails and A routes through a second gap). Their thresholds in bench/thresholds/path.json are deliberately generous (10x measured) documentation ceilings, not tuned gates: the scans stay accepted because hit rates on real layouts dwarf the miss cost, and a miss is bounded by one world slice per failed scan.

The returned path span points into the supplied PathScratch and remains valid until the next path query or scratch clear/reserve operation. Scratch keeps dense per-tile state arrays and clears only nodes touched by the previous query, so repeated queries avoid full-world scratch resets when the search visits a small fraction of the world.

For many agents repeating unit-cost point-to-point routes, UnitRouteCache can amortize complete path searches. Exact (start, goal) hits return the cached path without expanding nodes. Same-goal suffix hits are also supported when the new start already appears inside a cached optimal path; with unit positive edge costs, that suffix is also optimal. Both hit forms copy the cached route into the supplied PathScratch before returning, so a returned span never points into cache-owned storage that a later miss could reallocate; warm hits stay allocation-free when the scratch is pre-reserved. The cache assumes the caller runs its staleness entry point (refresh_if_world_changed, or the exact-mode invalidate_if_world_changed) when passability or movement rules change.

Staleness has two modes (UnitRouteStaleness). The default, WholeWorldExact, is deliberately conservative: when any chunk content version changes the whole cache drops, and every served route is identical to fresh recomputation. The opt-in ScopedFeasible mode records each stored route's chunk footprint with captured content versions and validates it lazily at serve time: entries whose crossed chunks are unchanged survive edits elsewhere. Surviving routes are guaranteed legal with a truthful cost and were optimal when stored, but an edit that opens a shortcut elsewhere can leave a served route suboptimal until it is retired; under blocking-only edit sequences survivors remain optimal. The mode applies to unit-cost models without special transitions on dense worlds (the same condition as suffix reuse — those are the models whose accepted steps read only tiles on the path); other models' entries, and all sparse-world entries, keep whole-world sensitivity.

Weighted route products are narrower than the route cache: they store one weighted path and the chunk content versions for chunks touched by that path. They are safe for replaying that exact product while those chunks are unchanged. They do not prove that unrelated obstacle removals could not create a shorter route, so they support portal-route products rather than acting as a general optimality-preserving weighted route cache.

Weighted portal route products are also exact for the supplied waypoint route, not for arbitrary routing. The caller provides portal waypoints from a topology or room graph; the product verifies each segment with weighted A, concatenates the segment paths, and records content-version dependencies. This makes topology evidence measurable before the repository owns a full portal graph builder. The automatic chunk-boundary builder uses a deliberately bounded candidate set. It tries the six axis-order permutations plus one greedy monotone candidate, walks from the start chunk to the goal chunk through adjacent chunks for each candidate, scans each adjacent chunk boundary for passable crossings, chooses the crossing with the lowest Manhattan score to the current point and final goal, then keeps the lowest-scoring waypoint candidate and verifies every resulting segment with weighted A. The greedy candidate can interleave progress axes instead of exhausting one axis before the next. The builder still does not search non-Manhattan chunk routes or prove global portal optimality.

The seven candidates overlap: they re-walk the same chunk seams from the same tile, measured at roughly two thirds of all seam queries in the profiled portal workloads. Selection therefore memoizes each query for the duration of one selection, keyed on the tile the walk arrives from and the signed direction of the step. The goal is not part of the key because it is invariant across a selection, so a generation stamp retires every entry when the next selection begins, and a nested selection — reachable when a caller supplies its own passability predicate — bypasses the memo rather than sharing that generation. The memo retains nothing between selections and needs no invalidation: the world cannot change while one runs. It changes no route, but portal_scan_tiles falls accordingly, because the skipped scans do not happen.

WeightedPortalSegmentCache can reuse previously verified segment paths for repeated supplied-waypoint portal builds. Cached hits avoid A* expansion for the segment, but still rebuild the route-product path and dependencies. Every lookup and store goes through a movement-class-bound view. A class rebind clears the cache, is counted in class_rebinds, and makes stale retained views rebind safely on their next use. Segments carry content-version dependencies and stale entries are rejected on lookup (counted as stale rejections). Recomputing a stale segment appends the new entry next to the rejected stale one until the segment budget is reached; the budget-triggered sweep then compacts stale entries and their path storage away in one pass, and insertion-order eviction of live entries keeps the cache at budget in fully live worlds. Lowering the budget evicts immediately, using the same oldest-first order. The cache stays caller-managed for retention (budget choice and clear()), and it does not imply region-selective optimality before the topology layer exists.

For many agents sharing a goal, DistanceFieldScratch can amortize search work. A unit-cost field build visits reachable passable tiles once from the goal, and each path query follows decreasing distances back to that goal. A weighted field uses reverse Dijkstra: when expanding backward from tile c, the reverse edge to predecessor n costs entry_cost(c), matching the forward move from n into c. Weighted reconstruction follows neighbors where distance(current) == entry_cost(neighbor) + distance(neighbor). The scratch remembers the field goal and rejects path reconstruction for a different goal instead of returning a path to stale field data. build_weighted_distance_field_in_box applies the same weighted model inside one explicit domain box. It is useful for local products, such as finding many starts inside one room to the same portal, while starts outside the box remain unreached.

DistanceFieldProduct is the reusable unit-cost or weighted product form. It builds from one or more goals, stores an ordered goal list, copies the dense distance array out of scratch, and captures chunk content versions for chunks reached by the field. Replay and nearest-target queries reject stale products before returning a path. distance_at<World>(coord) reads one tile's distance-to-nearest-goal in O(1), returning DistanceFieldProduct::unreachable_distance for unreached tiles, coordinates outside the shape, products whose shape identity does not match World, and unbuilt products; it guards only those O(1) identity checks — content freshness against a mutated world stays the caller's job, exactly as for the route cache. Its primary consumer is a PIBT ranking oracle built over the same movement class the agents move with. FieldProductCache is caller-owned and exact-match only: lookup keys include the passability tag identity, shape-compatible tile/chunk metadata, and ordered goals. Products are world-sized, so the cache stores each one behind address-stable per-entry heap storage and takes ownership on store(DistanceFieldProduct&&) by move; the moved-from argument is left empty but reusable, and no world-sized copy happens. A lookup() pointer stays valid only while its entry remains cached. Any store that replaces or evicts that entry invalidates the pointer, including a store for another key that causes least-recently-used eviction. clear() also invalidates every borrowed pointer. A product whose entry exceeds the byte budget on its own cannot be cached: that store returns false without disturbing existing entries or borrowed pointers; a zero byte budget therefore caches nothing. The cache evicts least-recently-used entries (by lookup/store recency, not insertion order) to a byte budget and reports entries, bytes, hits, misses, evictions, and stale rejections as FieldProductCacheStats. PathRequestRuntime owns one such cache and uses it only when the matching PathRuntimeCachePolicy unit or weighted product flag is set. Runtime use is conservative: only repeated single-goal groups at or above the configured reuse threshold are candidates, starts must span the configured number of chunks, and stale products are rejected through their content-version dependencies before replay. Unit leftovers use route/suffix caching; weighted leftovers use the established bounded-field/A* batch.

When weighted entry costs are known to be small bounded positive integers, build_bounded_weighted_distance_field avoids binary heap traffic with a Dial-style bucket queue. The result is still exact, because nodes are expanded in nondecreasing distance order. The bounded builder is an optimization of weighted field construction, not a different path model. An entry cost above the declared bound or a realized accumulated-cost saturation rebuilds through the unbounded heap implementation so neither condition is silently discarded.

weighted_path_batch makes the current weighted reuse policy explicit for callers. Repeated goals use one bounded weighted field per unique goal; singleton goals use normal weighted A*. Returned paths are copied into batch scratch so all result spans remain valid until the next batch call or scratch clear.

The runtime adds an opt-in strategy on top of that fallback (WeightedReplanStrategy). The default, ExactAStar, leaves singleton goals on normal weighted A* and is optimal. PortalFirst first tries a chunk-portal route stitched through the runtime's segment cache for eligible singletons (dense orthogonal-lattice worlds, default adjacent transitions, and explicit movement classes): accepted routes are verified and legal but may exceed the optimal cost, bounded by a premium cap relative to the Manhattan lower bound, and every other outcome — no candidate, a failed segment, a cap rejection, or an ineligible request — leaves the request to the untouched exact fallback with byte-identical results. The cap is a route-quality contract, not a latency bound: a rejection pays the portal work and then the exact search. Per-outcome counters are reported in the runtime stats as WeightedPortalReplanStats, and a new cache-aware builder, build_weighted_chunk_portal_route_product_cached, exposes the same waypoint-selection-plus-segment-cache composition to direct callers.

The path-agent tick wrapper is intentionally small and synchronous. The simulation scheduler in include/tess/sim/scheduler.h layers queued operation execution and render deltas around it, but the path tick itself only centralizes the common path-agent order: advance the simulation tick, optionally rebuild active paths after a dirty event, then move agents along runtime-owned result paths whose validity covers the tick. It does not observe world mutations on its own. Any edit to passability, movement costs, or topology-relevant movement rules must call mark_pathing_dirty(state) before the next tick that should replan (goal assignments need no mark: an armed goal is agent-scoped and replans just that agent). If a stateful transition provider stops emitting a retained special edge before that mark, commit validation reports StaleTopology rather than terminal NotAdjacent, so the bounded retry lifecycle can recover by re-planning.

Deliberate Limits

This path core implements a topology precheck (precheck_path, wired into the runtime and agent ticks) and runs natively over sparse-resident worlds, but does not implement async tickets or rich path diagnostics. Movement commit validation, reservation checks, queued-operation-driven path dirtying, and render deltas live in the simulation integration layer, but pathfinding does not automatically infer every dirty cause. Callers must mark the path-agent tick state dirty directly or run through the scheduler with accurate dirty masks when world movement data or agent goals change. The implementation uses reusable dense per-tile scratch arrays, a two-bucket monotone open set for the current unit-cost Manhattan A fallback, exact route/suffix caches, dense reverse distance fields for shared-goal batches, weighted shared-goal fields with optional bounded-cost bucket construction, weighted batch grouping, exact unit-cost and weighted distance-field products with explicit LRU caching, coarse region paths and chunk corridors, weighted route products, supplied-waypoint and chunk-boundary portal route products, and weighted A for positive integral entry costs.

The unit-cost A API is suitable for individual point-to-point queries and regression coverage. Weighted A is suitable for correctness-first weighted terrain queries, and weighted distance fields are suitable for weighted batches with substantial goal reuse. Shared-goal distance fields are suitable for batches with substantial goal reuse. Unit-cost and weighted distance-field products are suitable when an unchanged map can reuse a multi-goal field across frames or query batches. Runtime field-product reuse is opt-in because route suffix caching can be faster when many starts lie on already-cached paths; the runtime therefore skips opt-in product use for repeated-goal groups whose starts do not span enough distinct chunks. Route caches are suitable for unchanged maps with repeated exact routes or starts that lie on cached same-goal paths. Local crowd coordination, tactical target assignment, hierarchical corridor selection, and persistent shared-goal fields now cover the broad many-agent routing substrate. The path core keeps growing under those layers; the stability of what it already exposes is the support policy's subject, not this page's.

Current Profiling Notes

Large open-grid benchmarks currently expand one node per path coordinate, but reach roughly 2.5x more nodes because neighbor candidates are discovered around the corridor. On a 1024x1024 open 2D world from corner to corner, the Release benchmark reports a 2,046 unit path, 2,047 expanded nodes, and 5,112 reached nodes.

Sampling the 1024x1024 query shows time concentrated in neighbor processing: open-set maintenance, passability/world lookup for each accepted neighbor candidate, and fixed six-axis neighbor generation even for degenerate 2D shapes. Those are the first optimization targets before treating this A* path as suitable for hundreds of independent agents per tick.