Grid, graph and search state: snapshot and restore

A host that rolls back (lockstep with prediction, rollback netcode, replays) needs to put the mutable pathfinding state back exactly and get the results it would have got had it never left. This document is the normative description of what is saved, the byte format, what is not saved and why, and what each family counts as one iteration of a budget. A port must reproduce the same bytes.

What is covered

Not covered, and why: HPA* and bidirectional sliced searches (an HPA* search works on temporary abstract nodes of the hierarchy it was built on, a bidirectional search has two buffer sets and a meeting node; both are cheap to restart and neither is what a host holds across frames, but their grids roll back like any other), PointGraph and CsrGraph and Landmarks (immutable), the navmesh (its own snapshot: docs/navmesh-snapshot.md). Tier-1 one-shot queries keep no state between calls.

Restoring: the contract

• SaveState() returns a byte[]; RestoreState(ReadOnlySpan<byte>) puts it back in place; FromState(...) on Grid, HexGrid, VoxelGrid and Graph creates a new object. Saving twice without a change gives the same bytes; save → restore → save gives the same bytes; the same history gives the same bytes on every platform.
• Objects that are built over something (a replanner, a flow field, a sliced search) are restored in place into an object that was created the same way: same grid (restored first), same options (agent size, connectivity, diagonal rule, algorithm, delegate hooks, heuristic weight). Delegates cannot be saved, so the caller supplies them again. What can be checked is checked: sizes, algorithm, mode, goals and the heuristic weight must match, otherwise GridStateException names the mismatch. (Graph state, saved by Graph.SaveState and GraphAStar, throws GraphStateException instead; both are OnePathFormatException.)
• Order: restore the grid, then everything built on it. Restoring a grid tells its listeners: flow fields, replanners and HPA* hierarchies drop what they derived and rebuild on next use; other listeners see each cell that differs as an ordinary edit (voxel listeners likewise per voxel, in ascending node order). Restoring a dependent afterwards replaces that rebuild with its exact saved state.
• Versions can repeat after a rollback (restore to version 7, edit once, and an object cached at "version 8" from the other timeline matches by number only). Nothing derived is therefore trusted across a restore; this is why the caches above are dropped.
• A restore validates before it changes anything where it can: Grid, HexGrid, VoxelGrid, Graph, GridReplanner and HexReplanner are unchanged when GridStateException or GraphStateException is thrown. Flow fields and sliced searches are read in place and are unusable after a failed restore until restored again, recomputed (Recompute) or begun again.
• Hostile bytes: every count is bounded by the object's size and by the bytes left, every node index and parent is range-checked, heaps may not list a node twice, NaN is rejected, and the parent links of a search must lead only to visited nodes that cost no more and contain no cycle. The state is structurally validated, not semantically: a restored cost field (replanner g/rhs, flow integration costs) is trusted to be consistent, as a snapshot of your own memory is. An inconsistent one cannot index out of range or hang a bounded call, but it can make a path query report InvalidOperationException ("direction field contains a cycle", "has a cost but no path").
• A graph state names its node count outright (isolated nodes cost no bytes), up to the 2^26 new Graph(n) allows: restoring allocates nothing for them, but the first compile or query does.
• Must not overlap a running query or an edit on the same object (as for edits in general).

Byte format (version 1)

Little-endian throughout (BinaryPrimitives); i32 is a signed 32-bit integer, f64 a binary64 written by its bit pattern, u8 flag is 0 or 1 (any other value is an error). Counts are i32 and must be in range.

Header (8 bytes): u32 magic = 0x5347504F (the bytes 4F 50 47 53, "OPGS"), u16 format version = 1, u16 kind.

After the payload nothing may follow.

Pieces

• Space (GridSpace): f64 originX, f64 originY, f64 cellSize. All three zero is the unassigned default (behaves as unit cells); otherwise the same range rules as the constructor apply (|origin| ≤ 2^21, 0 < cellSize ≤ 2^21). VoxelSpace has four values, originX, originY, originZ, cellSize.
• Areas: i32 version (≥ 0), then 255 × f64 multiplier for areas 0..254 (each > 0 and finite). Area 255 is the wall and is not stored.
• Heap OpenSet (F, G, node): i32 count, then per slot in heap order i32 node, f64 F, f64 G. Slots are written as they lie in the array so a restored heap behaves exactly as the original; nodes must be distinct and F, G not NaN.
• Heap ReplanOpenSet (key1, key2, node): i32 count, then per slot in heap order i32 node, f64 key1, f64 key2.
• Search buffers (over nodeCount nodes): i32 visited, then per visited node in increasing index i32 node, u8 closed, f64 g, i32 parent (parent −1 or a node); then the open heap (OpenSet); then i32 expandedCount and that many i32 nodes. "Visited" means seen by the current search; the buffers' epoch counter is not saved because it never affects a result.

Objects

• Grid (1): i32 width, i32 height, i32 version, Space, Areas, u8[width*height] cells (row-major). Restore requires the same width and height.

• HexGrid (2): i32 width, i32 height, i32 layout, i32 version, Space, Areas, cells. Same width, height and layout required.

• VoxelGrid (3): i32 sizeX, sizeY, sizeZ, u8 defaultArea, i32 version, VoxelSpace, Areas, then for each of chunksX*chunksY*chunksZ chunks (x fastest, then y, then z) u8 flag and, when 1, 4096 bytes (index x | y<<4 | z<<8 within the chunk, padding past the grid edge included). Same size and default area required.

• Graph (4): i32 nodeCount (0..2^26), i32 edgeCount, then per edge in id order i32 from, i32 to, f64 weight, u8 alive (endpoints < nodeCount, weight ≥ 0 and finite).

• Replan search: i32 nodeCount, u8 mode (0 LPA*, 1 D* Lite), i32 start, i32 goal, u8 initialized, u8 found, i64 iterations, i64 expanded, i32 lastExpanded. When initialized: f64 km, u8 overflow, i32 pendingCount and the pending entries (i32: node, or the bitwise complement of the node when its neighbours are to be re-examined too; none when the overflow flag is set), i32 plannedCount and per node with a finite g or rhs, in increasing index, i32 node, f64 g, f64 rhs, then the ReplanOpenSet. An uninitialised search (never planned, or restarted by InvalidateAll, SetGoal, or a start move under LPA*) stores nothing more, and reads back with g and rhs at +∞: its old values are never used because planning overwrites them.

• GridReplanner / HexReplanner (5, 6): i32 width, i32 height, u8 algorithm (GridAlgorithm value), i32 areaVersion, i32 start, i32 goal, then the replan search.

• Flow field search: i32 nodeCount, u8 status (0 not started, 1 running, 2 complete), i32 settled, u8 repairing, i32 goalCount and goal nodes (strictly increasing), i32 reachedCount and per node with a finite cost in increasing index i32 node, f64 cost, i32 stepCount and per node with a step, in increasing index, i32 node, i32 next (the next node must be reached and cost no more than the node), the OpenSet, and when repairing i32 touchedCount and that many distinct nodes.

• GridFlowField (7): i32 width, i32 height, i32 areaVersion, i32 goalCount and the goal nodes in the order given at creation (must equal the field's own), i32 pendingCount and the pending edited cells, then the flow field search.

• A*, jump point, Theta*, graph A* (8–11): i32 nodeCount, u8 status (SearchStatus), f64 heuristicWeight, i32 start (−1 if unused), i32 goal, i32 expanded, i32 iterations, f64 pathCost; unless the status is NotStarted, the search buffers. The weight must equal the restoring search's (A* and Theta*; 1.0 for the others). Every visited node's parent must be -1 or a visited node that costs no more, with no cycles.

• GridSearch (12): u8 mode (0 not begun, 1 specialised A*, 2 generic, 3 specialised jump point), i32 width, i32 height. Mode 1: u8 status, u8 zeroEstimate, i32 start, i32 goal (cell indexes), i32 expanded, i32 iterations, i32 pathA, i32 pathB, i32 visited, then per visited cell in increasing index i32 cell, i32 a, i32 b, u8 flags (a, b: straight and diagonal steps so far; flags bit 0 closed, bits 1–3 the direction to the parent: 0 south, 1 west, 2 north, 3 east, 4 south-west, 5 north-west, 6 north-east, 7 south-east). Restore checks that every cell but the start has a closed visited parent whose pair differs by exactly one step, that the start has cost 0, and that a found search has its goal closed with the reported pair; the open list is the visited cells that are not closed. Mode 2: i32 startX, startY, goalX, goalY, i32 length and an embedded AStar (8) state. The restoring search must pick the same engine from its options and the (restored) grid. Mode 2 holds an embedded AStar (8) state when the options select A* (including a jump point algorithm whose options fall back to A*) and an embedded JumpSearch (9) state when they select the generic jump point search; the embedded kind is checked. Mode 3 (added without changing the format version; older readers refuse it as an undefined mode): u8 finder (0 JPS block scans, 1 JPS+ tables), then the same fixed fields as mode 1 (u8 status, u8 zeroEstimate, i32 start, goal, expanded, iterations, pathA, pathB, visited), then per visited cell in increasing index i32 cell, i32 a, i32 b, i32 parent, u8 flags (a, b: straight and diagonal steps of the cost; parent −1 for the start; flags bit 0 closed, bits 1–3 the direction of the last move, 0 north, 1 east, 2 south, 3 west, 4 north-east, 5 south-east, 6 south-west, 7 north-west), then the open list as it lies: f64 level (bit pattern; NaN when no entry has popped), i32 heapCount and per slot in array order f64 F, u64 T (T: the bitwise complement of the cost so far as float32 in the high 32 bits, the cell in the low 32), i32 stackCount and that many i32 cells (the entries of the current level, popped last-in first-out). The list is saved as it lies, stale entries included, because the pop order among equal estimates depends on the order of pushing. Restore checks that: every cell is inside the grid, walkable and listed once in increasing order; the start has cost 0, no parent, and is closed unless nothing has popped; every other cell has a closed visited parent that is a valid hop back (the cost pair grows by max(|dx|,|dy|) − min(|dx|,|dy|) straight and min(|dx|,|dy|) diagonal steps) and a direction that points along the hop; the goal is closed exactly when the status is Found, with the reported pair; the counters equal the closed cells (iterations = closed, expanded = iterations − 1 when found); every entry names a visited cell, the heap array is a heap, every open cell has an entry, and a search that ran out of cells has none. The restoring search must select the specialised jump point engine and the same finder from its options and the (restored) grid. Restoring a grid and then a search needs no extra step: the search compares the grid's version and restore count, not its own cache.

What one iteration is

Every sliced form counts iterations, never time; a budget of n does the same work on every machine, and sliced = unsliced for every budget (tested).

Tier-1 GridOptions.IterationBudget, VoxelOptions.IterationBudget and GraphOptions.IterationBudget (0 = unlimited) are a single cap: the query stops with PathStatus.BudgetExhausted and is not resumable. To resume, use the tier-2 Begin/Step form, whose state can also be saved.

Debug geometry

RecursiveAI.OnePath.Debug.GridDebug.Describe(...) copies a result into immutable plain data:

Expansion lists are opt-in (RecordExpansions on GridOptions, VoxelOptions, GraphOptions), so the happy path pays nothing; when recorded, the list's length equals ExpandedCount. What an "expanded cell" is: the cell popped and expanded (A*, voxel, Theta*); the jump point popped (JPS); the abstract node's cell (HPA*); for a replanner result, each node that replan settled (overconsistent) or reset (underconsistent), in order.