Grids: square and hex, open set, A*, area costs, clearance · onepath docs

Normative. A port must reproduce the same expansion order, costs and paths from this text. Code lives in src/OnePath/Grids/. The tier-1 types (Grid, HexGrid, VoxelGrid, their options and results, Cell, WorldPoint, VoxelCell, VoxelPoint, GridSpace, VoxelSpace, AreaCosts, HexCoord, GridAlgorithm, PathStatus, GridFlowField and the replanners) live in the root namespace RecursiveAI.OnePath; the search cores, topologies, heuristics, buffers and indexes (tiers 2 and 3) live in RecursiveAI.OnePath.Grids and .Grids.Voxel.

Layout

Square grid (Grid): Width x Height cells, one byte each, indexed row-major: index = y * Width + x. x is the column (0 at the left), y the row (0 at the top). At most 2^28 cells.
Area ids. A cell byte is an area id: 0..254 are walkable areas, 255 is a wall. AreaCosts holds one multiplier per walkable area (default 1; must be positive and finite). Edits go through Grid.SetArea, which bumps Version and tells registered IGridChangeListeners the changed cell.
Hex grid (HexGrid): a rectangular offset array (Width columns, Height rows), same indexing, same area ids. HexLayout says which rows/columns are shifted: PointyOddRow, PointyEvenRow, FlatOddColumn, FlatEvenColumn. Axial coordinates (q, r) from offset (col, row):
- pointy odd: q = col - (row - (row & 1)) / 2, r = row;
- pointy even: q = col - (row + (row & 1)) / 2, r = row;
- flat odd: q = col, r = row - (col - (col & 1)) / 2;
- flat even: q = col, r = row - (col + (col & 1)) / 2. Hex distance: with dq, dr, ds = -dq - dr, (|dq| + |dr| + |ds|) / 2.

World mapping and the coordinate rule

GridSpace(originX, originY, cellSize). Square cell (x, y) has its centre at origin + ((x + 0.5) * size, (y + 0.5) * size); a world point maps to floor((p - origin) / size) per axis and is outside the grid unless both results lie in range. Hex: the origin is the centre of cell (0, 0) and size is the distance between adjacent centres; pointy layouts place axial (q, r) at size * (q + r/2, (√3/2) r), flat layouts at size * ((√3/2) q, r + q/2); the inverse divides, then rounds fractional cube coordinates: round each of q, r, s = -q-r with floor(v + 0.5), then repair the coordinate with the largest rounding error so the three sum to 0 (q if its error is strictly larger than both others, else r if strictly larger than the error of s, else s, which is implied). (√3/2) is the double 0.8660254037844386.

World coordinates (origin, query points) cross the boundary as double and must satisfy |v| <= 2^21 (exact for Q31.32 fixed point). NaN, infinities and larger values throw ArgumentOutOfRangeException naming the value and the bound. Internally grids are integer cell indices and costs are double; there is no float32 on the grid paths. A point outside the grid (but within the bound) is not an exception: the query returns StartInvalid/GoalInvalid.

Movement

Square, neighbour order (normative; it decides which of two equal-cost parents wins): north (0,-1), east (1,0), south (0,1), west (-1,0), then, if eight-connected, north-east (1,-1), south-east (1,1), south-west (-1,1), north-west (-1,-1). Hex: axial directions (+1,0), (+1,-1), (0,-1), (-1,0), (-1,+1), (0,+1).

Diagonal rule (square, eight-connected). For a diagonal move the two beside cells are the two cells that share an edge with both the start and the target (for north-east: north and east of the start).

NoCornerCutting (default; the Moving AI benchmark convention, Sturtevant 2012): both beside cells walkable.
NoSqueezing: at least one beside cell walkable.
AllowAll: no condition beyond the target being walkable.

Step cost of a move from cell a to cell b: length * ((m[a] + m[b]) * 0.5) evaluated in exactly that order in double, where m is the area multiplier of the cell's area id and length is 1 for a straight step, GridMath.Sqrt2 for a diagonal (hex: always 1). A caller's cost hook may replace the result (see Tier 2). The cost of a path is the sum of its step costs added in path order starting from 0.

√2. Sqrt2 = 1.4142135623730951 (bits 0x3FF6A09E667F3BCD), the correctly rounded double of √2; it equals Math.Sqrt(2.0) because IEEE-754 square root is correctly rounded. Octile costs a + b√2 are therefore exact up to ordinary double rounding and identical on every platform. (The published Moving AI lengths differ from exact sums by up to 1.7e-9 relative; see Verification.)

Clearance and agent sizes

An agent of size s (1..255 cells) occupies the s x s block of cells whose top-left cell is the agent's position (extending towards +x and +y). True clearance of a cell is the side of the largest square of walkable cells with that cell as its top-left corner (0 for walls; cells outside the grid count as walls; capped at 255). It is computed by c(x,y) = 0 for a wall, else 1 + min(c(x+1,y), c(x,y+1), c(x+1,y+1)) from the bottom-right corner, in O(cells). A cell is walkable for size s iff clearance >= s. All movement rules above are then applied to the "walkable for s" predicate: for a diagonal move the beside cells are tested for size s, which is exactly "the swept blocks are free". The step cost uses the area ids of the two position cells only. Clearance is recomputed lazily after edits; create a new SquareTopology after editing cells. Hex grids support only size 1.

Open set

OpenSet is an indexed 4-ary min-heap over node indices with decrease-key. Order: smaller f first; on equal f larger g first; on equal g smaller node index first, comparing doubles with ==/</>; NaN keys are rejected. A node is in the set at most once (pushing an existing node replaces its keys and re-sifts), so the pop order depends only on the keys. The arity is an implementation detail.

A*

Hart, Nilsson & Raphael 1968. f = g + w * h with weight w (default 1); h from IHeuristic after SetGoal(goal).

g[start] = 0, push start with f = w * h(start).
Iteration: pop the best node n (an iteration is one pop); mark it closed; if n == goal finish (cost g[goal]); otherwise expand: visit the topology's neighbours in order; for each, step = hook(n, m, baseCost); skip it if step is NaN, negative or +infinity; g' = g[n] + step; if the neighbour was never reached, or g' < g[m] strictly, set g[m] = g', parent[m] = n, mark it open (reopening it if closed) and push (g' + w*h(m), g'). Equal-cost alternatives therefore keep the first parent found.
If the open set empties first, there is no path.

The goal test happens at pop. With ZeroHeuristic this is Dijkstra. Heuristics: Manhattan scale*(|dx|+|dy|); octile scale*((max-min) + min*√2) (with dx, dy integer cell distances); hex distance scale*steps; scale is the smallest area multiplier (AreaCosts.MinCost), which keeps them admissible when multipliers are below 1. Heuristics are admissible and consistent for the default cost model; hooks that lower costs, or weights above 1, give up optimality. Auto picks Manhattan for four-connected, octile for eight-connected, hex distance for hex.

Sliced search. AStar.Step(n) performs at most n iterations and returns Running while work remains; Run() is Step(int.MaxValue) with cooperative cancellation; time is never consulted. Any sequence of budgets gives the same expansion order, path and cost as one unsliced run. The tier-1 GridOptions.IterationBudget ends the query with PathStatus.BudgetExhausted after that many iterations.

Cancellation and async (tier 1). Every one-line FindPath (square, hex, voxel) takes an optional CancellationToken. A token that can be cancelled makes the engine run in slices of 256 iterations and check the token before each one; cancelling throws OperationCanceledException, leaves the grid untouched and the next query exact. Slicing never changes a result (see above), so a token that is never cancelled returns the same path, cost and counts as no token, and IterationBudget counts the same iterations. Grid.FindPathAsync (cells or world points) is the cooperative sliced form: it drives the resumable GridSearch on the caller's synchronization context in slices of GridOptions.IterationsPerSlice (default 256) iterations with a Task.Yield() between slices, checks the token between slices and returns what FindPath returns, however the iterations are sliced (a budget that runs out gives BudgetExhausted after the same IterationBudget iterations). It supports AStar, Jps and JpsPlus without RecordExpansions and refuses other options with an ArgumentException through the task. Callbacks (Blocked, StepCost) run on the calling thread. For a search on another thread run FindPath inside Task.Run; the grid must not be edited until the task completes, and cancellation, like any error, comes through the task. Hex and voxel grids have no async form.

API tiers

Happy path. Grid.From(bool[,]) (or spans, Grid.FromText(picture) with . open, # wall and 1-9 areas, or MovingAiMap.ToGrid(); HexGrid.FromText likewise), grid.FindPath(a, b[, GridOptions]) with cells or world points; GridOptions (connectivity, diagonal rule, agent size, heuristic, weight, StepCost and Blocked delegates, expansion recording, iteration budget) with presets Default, FourConnected, NoSqueezing, ForAgentSize(n). GridOptions, VoxelOptions and PathOptions are immutable once built: set properties in an object initializer, and a shared preset such as GridOptions.Default cannot be changed under another caller. Start or goal outside the grid, blocked or too narrow for the agent give StartInvalid/GoalInvalid, not exceptions. The delegates are adapted onto the struct-generic core; nothing here needs a struct callback.
Middle. grid.CreateTopology(agentSize, connectivity, diagonals) gives a SquareTopology (hex: HexGrid.CreateTopology()); new AStar<TTopology, TCost, THeuristic>(topology, cost, heuristic, buffers) with IStepCost / IHeuristic structs; GridSearchBuffers are reusable working memory (the search allocates nothing in steady state; marks carry a generation number so nothing is cleared between searches).
Raw. OpenSet, IGridTopology + INeighborVisitor (implement your own graph), GridSearchBuffers, AreaCosts, IGridChangeListener; for jump point search JumpRules (pruning), IJumper with OnlineJumper, BlockJumper and TableJumper, BlockMap, JpsPlusIndex (the tables), and JumpSearch<TJumper, THeuristic> (tier 2: struct-generic over the jumper and heuristic). Tier 1 picks them with GridOptions.Algorithm.

Debug data: GridOptions.RecordExpansions / GridSearchBuffers.RecordExpansions record the expanded nodes in order (GridPath.ExpandedCells, GridSearchBuffers.ExpandedNodes); the path is GridPath.Cells / Points.

Jump point search (JPS, JPS+)

Papers: Harabor & Grastien 2011 (Online Graph Pruning for Pathfinding on Grid Maps) for JPS; Harabor & Grastien 2014 (Improving Jump Point Search) for block-based scanning and the offline (JPS+) variant, with Rabin's formulation of the preprocessed distances (Game AI Pro 2). Code: src/OnePath/Grids/Jps/.

When it applies. Eight-connected moves, DiagonalRule.NoCornerCutting, agent size 1, every area with the same cost multiplier m (straight step m, diagonal step m * √2, the same values A* uses when all multipliers are equal), no step-cost or blocking callbacks, heuristic weight 1, heuristic octile or zero. The one-line API (GridOptions.Algorithm) falls back to A* when a query does not qualify (and GridPath.Algorithm says which ran); JPS+ also falls back to JPS when a side of the grid exceeds 32766 cells. Other rules (squeezing, allow-all, four moves) and agent sizes above 1 are A*'s. The default is A*.

Pruned successors (JumpRules.Successors). Let a node be reached by a step of sign (dx, dy) from its parent (the parent may be many cells away; only the direction matters). The start node searches all eight directions.

Diagonal arrival: the diagonal and its two cardinal components. A diagonal step into a cell needs both side cells free (no corner cutting), so no neighbour is forced.
Straight arrival: straight on; and on each side s (perpendicular to the step), if the cell beside the node on side s is free and the cell beside the previous cell on that side is a wall, that side cell is reachable at the optimal cost only through this node: the side's cardinal direction and the diagonal (step + s) are searched too. This is the forced neighbour of the 2011 paper moved one step along, because a diagonal step out of the previous cell is illegal when its side cell is a wall.

Jump (IJumper.Jump). From a node in a direction, walk until a cell is reached that is the goal or (straight) has a forced neighbour as above, or (diagonal) is the goal or has a straight scan in one of its two cardinal directions that finds such a cell; a wall stops the walk with no result. A diagonal step needs both side cells and the target free. The result is the cell and the number of unit steps.

Search (JumpSearch). A* over jump points with the grid core's OpenSet: smaller f, then larger g, then smaller cell index. f = g + octile(m) (or g for the zero heuristic); g adds steps * m or steps * (m * √2) per jump (so a path cost is a sum of one product per segment, not one addition per cell, and may differ from A*'s cell-by-cell sum in the last bits). A cheaper route reopens a node. Successors are generated in direction order 0..7 (north, east, south, west, north-east, south-east, south-west, north-west); on equal g the first parent found stays. The goal is tested when popped. One iteration pops and expands one node, so a sliced search equals an unsliced one; the iteration budget and expansion counts follow A*'s rules. The returned path lists every cell between the jump points (consecutive cells are neighbours). Jump points are not unique to the search: any valid optimal path is returned, and A*, JPS and JPS+ may return different paths of equal cost.

Block-based scanning (BlockMap, BlockJumper). The walkable cells are kept as bits, 64 per word, once by rows and once by columns (bit i of word k of a line is position 64k+i; positions past the line end are blocked). A straight scan reads whole words: stop bits are ~walkable | forced, where forced = `side & ~(side shifted by one position along the scan)` for the two neighbouring lines (a missing line counts as blocked), masked to positions beyond the start, and the first set bit (lowest bit forwards, highest backwards) is the stop; a goal on the line before the stop wins. The map follows grid edits immediately (a bit per edit in each orientation). It finds exactly the cells the cell-by-cell scan (OnlineJumper) finds.

JPS+ tables (JpsPlusIndex). Per cell and direction one signed 16-bit value, stored cell by cell (`table[cell * 8 + direction], so the eight values of a cell share a cache line;Tables` returns the same numbers as a direction-major copy, [direction * cellCount + cell]), direction order as above, cells row-major. Value d > 0: the next jump point is d steps away; d <= 0: no jump point before a wall, and -d is the number of walkable cells before it. A wall cell has all zeros. Straight direction: look at the next cell q; if q is a wall, 0; if q has a forced neighbour for this arrival, 1; else the value of q moved one step further (v + 1 if v > 0, else v - 1). Diagonal: if the step is illegal (side cell or target a wall), 0; if q's table for either cardinal component is positive, 1; else the same chain rule on the diagonal table. Build order: the four straight tables, then the diagonals, each from the far end. Size 16 bytes per cell.

Goal bounding at query time. Straight: the goal on the line ahead within |d| steps is returned directly (cost = distance). Diagonal: if the goal lies strictly inside the quadrant and min(|gx-x|,|gy-y|) <= |d|, the run stops at that many steps (the cell level with the goal in one axis), even if the stored jump point lies further. Otherwise a positive d returns the stored jump point and a non-positive one nothing. Stopping early adds nodes that plain JPS would not create; it never loses an optimal path (a superset of the nodes JPS visits) and never adds a cheaper one.
Incremental update. The index subscribes to the grid's IGridChangeListener; Refresh() (called by every query) applies the pending edits: for each edited cell recompute the east and west tables of its row and the rows above and below, the north and south tables of its column and the columns beside it, recording the cells whose sign (positive or not) changed; then for every edited cell and sign-changed cell recompute the four diagonal entries that read it (the cell itself, the cells one step behind it horizontally, vertically and diagonally), and follow each changed diagonal entry backwards along its diagonal until an entry comes out unchanged. The tables then equal a fresh build (checked on >1000 random edit sequences and in the fuzz target). More than max(256, cells/64) pending edits are answered by a full rebuild.

Cost with areas. JPS assumes one cost for every step. Distinct area multipliers make a query fall back to A*; the table index is independent of costs, so changing a multiplier needs no rebuild.

Cost model of preprocessing. O(8 · cells) time to build, 16 bytes per cell; the block map takes cells/4 bytes.

The specialised octile searches (one-line A*, JPS, JPS+; `Grids/Fast/`)

Grid.FindPath runs these when the query qualifies for JPS above (eight moves, no corner cutting, agent size 1, one cost for every area, no callbacks, weight 1, octile or zero estimate) with GridAlgorithm.AStar, Jps or JpsPlus. Everything else, sliced searches (AStar<,,>, JumpSearch<,>), snapshots and replanning use the generic cores, which are unchanged. Costs are optimal and equal to the generic cores'; the returned path may be another path of that cost.

Exact costs. A path costs a + b·√2 for a straight and b diagonal steps. The searches keep the integer pair (a, b) per node. Keys are computed from pairs: g = a + b·√2, f = (a + (max − min)) + (b + min)·√2 with min/max of the absolute column and row distance to the goal, each evaluated as one product and sums of doubles. Equal pairs give identical doubles, so nodes with equal f in exact arithmetic tie exactly (cell-by-cell double sums would differ in the last bit and break ties by noise); distinct pairs differ by more than 1e-6 for any grid that fits in memory, far above rounding, so double comparison orders them exactly. A path's reported cost is m · (a + b·√2) for the cell cost m. The estimate is consistent, so a closed node is final and never reopened.

Open list order. Smaller f; on equal f larger g (rounded to float32, which is IEEE-exact), then smaller node index (A*, with decrease-key in a 4-ary heap). The jump point searches use a 4-ary heap without decrease-key (an improved node is pushed again; the older entry is skipped when it pops, the node being closed) with one addition: entries whose f equals the f of the entry popped last go on a stack and pop first, last in first out, before the heap resumes (a heap entry with a smaller f than the current level wins). The order is therefore fully determined by the sequence of pushes. With this tie-break A* expands exactly the nodes that a (g descending) open list does: 3 594 911 expansions on dao-brc000d.

A* pads the map with a wall all round and keeps wall cells in the node array as permanently closed records, so a neighbour test is a load of the record the relaxation needs anyway. Node record 16 bytes: the pair, the heap slot, and a tag generation << 4 | arrival direction << 1 | closed; the generation increases per search so nothing is cleared between queries.

Jump point searches (OctileJump<TFinder>, finders BitFinder and TableFinder). Node record 16 bytes (pair, parent, tag). A neighbour byte per cell (OctileMap.Neighbors, bit d = neighbour in direction d walkable) and a table of 8 × 256 entries (OctileMap.Successors, JumpRules.Successors evaluated once for every arrival direction and neighbour byte) give the pruned successor set without cell lookups; a diagonal step is allowed when the neighbour byte has the step's two components and the diagonal itself. The bit rows and columns of OctileMap are padded with 64 blocked positions before each line and a blocked word after it, so scans never leave the array and the carry between words needs no test. A goal on the scan line is a stop bit of its own. To make a scan step one word read, the map also keeps four arrays in the layout of the bit rows and columns (RowStopForward, RowStopBackward, ColStopForward, ColStopBackward): bit i of word k is set when a scan along that line direction stops at that cell, that is when the cell is a wall (~w) or has a forced neighbour (a cell beside the line is free while the one beside the previous line cell is not; the neighbouring lines' words and the carry bit of the adjacent word are read once, when the array is built). Padding words and padding lines are all ones. A cell edit recomputes the words of the three lines around it and the words before and after the edited word. A scan masks the stop word with the positions beyond the start, adds the goal bit, and takes the first set bit; the result is a wall (no jump point, 0) or the step count, as before. The JPS+ finder reads JpsPlusIndex with the goal bounding above.

Improved pruning (BitFinder/TableFinder with improvedPruning; Harabor & Grastien 2014, section "Improved Pruning Rules"; not reachable from the one-line API). Without corner cutting every diagonal jump point is an intermediate turning point. A diagonal run from a node therefore does not stop at such cells: at each cell of the run it offers the straight jump points (or the goal) reached from it, with the node as their parent and the straight direction as their arrival direction, and it continues until a wall; the run's last cell is not a node. A hop from a node to such a successor is walked diagonal steps first, then straight, when the path is written out, which is obstacle free because it is the run followed by the scan. In a test on dao-brc000d this expands 83 678 nodes against 210 340 for JPS and 83 501 for the black-box reference's improved JPS.

The improved-pruning search is internal: the bar runner and GridOptima construct it directly, and no public option selects it. Should an option expose it, it ships marked [Experimental("ONEPATH0001")] (System.Diagnostics.CodeAnalysis.ExperimentalAttribute, diagnostic id ONEPATH0001) until a locked comparison confirms it is as fast as the black-box reference on every Moving AI row.

Bar driver. bench/Bar/OursGrid.cs loads the map and builds the bit maps and tables outside search_time (preprocess_time reports them), runs 40 untimed warm-up instances, then times one pass over the scenario (ONEPATH_GRID_PASSES=N takes the best of N passes in the process). The search loops are marked AggressiveOptimization so that short queries run fully optimised code from the first call.

Any-angle search (Theta, Lazy Theta)

Papers: Nash, Daniel, Koenig & Felner 2007 (Theta*: Any-Angle Path Planning on Grids; JAIR 2010) and Nash, Koenig & Tovey 2010 (Lazy Theta*). Code: src/OnePath/Grids/ThetaStar/.

Model. Nodes are cell centres (the same nodes as A*), not cell corners as in the papers, so every algorithm of this document shares one node set, start and goal definition and clearance rule. A waypoint list is a path; the agent moves in straight segments between consecutive centres.

Line of sight (GridLineOfSight). Two walkable cells see each other iff the closed segment between their centres touches no wall cell, where a wall is the closed unit square (touching a wall's corner blocks). Diagonal neighbours therefore see each other exactly when both beside cells are walkable: every legal NoCornerCutting move is a line of sight. Cells outside the grid are walls. Integers only. With dx = x1-x0, dy = y1-y0, nx = |dx|, ny = |dy|, steps sx, sy = sign:

nx = 0 or ny = 0: all cells on the row/column between the endpoints.
else walk from (x0, y0) with counters ix = iy = 0 until ix = nx and iy = ny; d = (2ix+1)*ny - (2iy+1)*nx (64-bit). d < 0: step in x (ix++); d > 0: step in y (iy++); d = 0: the segment passes through a lattice corner; the two cells beside it (x+sx, y) and (x, y+sy) must be walkable, then step in both. Every cell entered must be walkable.

Applies when (otherwise the query runs as A* and GridPath.Algorithm says so): eight-connected, NoCornerCutting, agent size 1, one cost multiplier m for every area, no StepCost/Blocked callbacks, heuristic Auto, Euclidean or Zero. The cost of a segment is m * sqrt(dx*dx + dy*dy) (dx, dy integer, the sum exact in 64 bits, one correctly rounded square root), so a straight cell step costs m, a diagonal one m * Sqrt2 as in A*. A path's cost is the sum of its segment costs added in path order from 0 (GridPath.Cost; Cells and Points list the waypoints only). Heuristic: m * sqrt(dx*dx + dy*dy) to the goal (EuclideanHeuristic), weight GridOptions.HeuristicWeight.

Search (ThetaSearch<THeuristic>, tier 2). The open set is the grid core's OpenSet (smaller f, larger g, smaller cell index); one iteration pops one node; the goal is tested when popped; budgets and slicing as in A*. Neighbours of an expanded node s are its legal grid moves in the order north, east, south, west, north-east, south-east, south-west, north-west; closed nodes are never reopened (as in the papers) and a neighbour's cost is replaced only when strictly lower, so the first parent found wins ties. The start has no parent (the papers make it its own parent). Let p be the parent of s, c(a, b) the segment cost.

Theta* (ThetaVariant.Theta): for each neighbour t that is not closed: if p exists and LOS(p, t), candidate g(p) + c(p, t) with parent p; otherwise g(s) + c(s, t) with parent s.
Lazy Theta* (ThetaVariant.Lazy, the paper): the candidate is always g(p) + c(p, t) with parent p (no test; the start uses s). When a node is popped, SetVertex: if it has a parent p and not LOS(p, node), the parent becomes the closed grid neighbour u (neighbour order, first on ties) minimising g(u) + c(u, node), and g(node) is set to that sum; then the node is closed and expanded.
Lazy Theta* with re-queue (ThetaVariant.LazyRequeue, the tier-1 GridAlgorithm.LazyThetaStar): as Lazy, but a node whose SetVertex changed its parent is pushed back into the open set under its corrected g and f and not expanded in this iteration (the pop still counts). After the repair the parent is an adjacent cell, so the next pop does not repair again. Why: the paper's order expands such a node under its optimistic cost, and on random grids that occasionally returns a path longer than the A* path (15 of about 50,000 queries, at most 13% longer); with the re-queue none was seen in the same checks. It costs a few more iterations.

The papers prove no optimality; paths are short, not shortest. Length lies between the visibility-graph optimum (shortest path turning only at cell centres) and, in all checks, the A* length.

Flow fields (many agents, one goal set)

Integration step of flow-field pathfinding (Emerson 2013, Crowd Pathfinding and Steering Using Flow Field Tiles; Pentheny 2013): Dijkstra's algorithm run outwards from the goals. Code: Grids/Flow/ (FlowField<TTopology, TCost> tier 2/3, GridFlowField tier 1 via Grid.CreateFlowField and HexGrid.CreateFlowField).

Integration field cost[n] (double, +∞ = unreachable or not walkable). Goals (sorted, deduplicated; a goal the agent cannot stand on is inactive) cost 0. Every other node costs min over neighbours u of (cost[u] + move(n, u)), move(n, u) being the cost of the move out of n (the topology's move cost passed through the cost hook; the same cost in both directions is required because the wave runs backwards along the neighbour lists). Sums are IEEE doubles formed as cost[u] + move. Square grids use the same neighbour set, diagonal rule, agent clearance and (m[from] + m[to]) / 2 costs as A*; hex grids the six hex moves. The tier-1 blocked filter isolates a cell (no move into or out of it); the step-cost delegate sees (from, to, grid cost).
Settling order. The open list is OpenSet with f = g = cost, so ties on cost pop by smaller node index. The field does not depend on that order: a node's final cost is the minimum, over neighbours, of the same rounded sums of their final costs (rounding is monotone and moves cost ≥ 0, so a neighbour settled later never beats one settled earlier).
Direction field next[n] (node index, −1 for goals and unreachable nodes): the first neighbour in the topology's neighbour order (square: N, E, S, W, NE, SE, SW, NW; hex: axial order) that attains the minimum of cost[u] + move(n, u). It is eight-way (six-way on hex), not a continuous gradient: GetDirection returns the unit vector from this cell's centre to the next one's, and following next from any reachable cell reaches a goal with total move cost equal to cost[n] (exactly, in the same arithmetic, up to the order of addition: a sum taken from the cell towards the goal can differ from the wave's sum in the last bits when move costs are not dyadic, because √2 is rounded). A continuous gradient and a line-of-sight shortcut near the goal are not provided.
Iteration budget. One iteration pops one node and relaxes its neighbours. Step(n) does at most n; a sliced field equals an unsliced one and reports the same Settled. GridOptions.IterationBudget bounds the constructor's run; call Step/Run to finish.
Incremental repair. Refresh() after cell edits (found through IGridChangeListener) recomputes only the affected region (Ramalingam & Reps 1996 style): the dirty nodes — the 3x3 block around an edited cell, widened up and left by the agent size − 1 for agents wider than one cell (hex: the cell and its neighbours) — are invalidated together with every node whose chosen next node is invalid, then each invalid node is seeded from its still-valid neighbours and the wave refills the region (improvements spread beyond it). Directions are recomputed for every node whose cost changed and its neighbours. The result is bit-identical to a field computed from scratch (cost bits and next). A change to an area multiplier, or Recompute(), recomputes everything. Changes the grid cannot report (a delegate answering differently) need Recompute().
Threads. A field is computed on one thread. Fields for different goal sets may be computed concurrently over one grid that is not being edited (listener registration is locked); results do not depend on the thread count. Nothing in the flow-field code uses thread-count-dependent scheduling.
Verification. Integration field equals a per-cell O(n²) Dijkstra over 10^4 random square grids (4- and 8-connected, all three diagonal rules, agent sizes 1 and 2, area costs, 1–3 goals; bit-exact for four-connected where the costs are dyadic, 1e-9 relative with √2) and 600 hex grids (bit-exact); following the direction field from every cell reaches a goal at the field's cost; repair equals recompute (bit-exact cost and next) over 600 edit sequences including agent sizes 2–3, hex and area-cost changes; sliced equals unsliced for budgets 1–50; fields on 8 threads equal sequential ones. On Moving AI maps GridOptima --alg flow (ALG=flow LIMIT=n sweep.sh) computes the whole-map field to each scenario's goal and checks the start's cost against the published optimum (relative 1e-6): dao, sc1, bg512 and room, 4000 scenarios each, 0 mismatches. Hash scenarios grids/flow/*; fuzz target grid-flow.
Tile edits and incremental clearance

Grid.SetRect(x, y, w, h, area) and SetRect(x, y, w, h, areas) (and the same on HexGrid) change a rectangle as one edit: cells are written in row-major order, Version goes up once if any cell changed (nothing happens otherwise), and the listeners hear about it once. A listener implementing IGridBatchListener gets OnRectChanged with the smallest rectangle containing every changed cell (cells inside it may be unchanged); any other listener gets OnCellChanged for each changed cell, row-major. The grid already holds the final state in both cases. A rectangle outside the grid throws ArgumentOutOfRangeException before any cell is written; a source of the wrong length throws ArgumentException.

Clearance repair. Clearance of a cell reads only the cells right of, below and diagonally below-right of it, so it can change only if the cell was edited or one of those three changed. The grid keeps the rectangles edited since the clearance was last current (more than 32 are merged into their bounding box). The next read repairs rows from the lowest edited row upwards, each row right to left: the cells of the row that lie in an edited rectangle, plus the cells one step left of and below the changed interval of the row below, are recomputed, and the sweep continues left past that range only while values keep changing. Edits made before the clearance was ever read cost nothing. The result equals the full recompute (checked on random edit sequences, SetRect included). JpsPlusIndex implements IGridBatchListener: a rectangle adds its cells to the pending edits (or schedules a full rebuild past the usual threshold). BlockMap updates per changed cell.

Incremental replanning (LPA, D Lite)

Papers: Koenig, Likhachev & Furcy, Lifelong Planning A* (2004); Koenig & Likhachev, D* Lite (2002), the version with the key modifier km. One engine (ReplanSearch<TTopology, TCost, THeuristic>) serves both. It searches from a root (LPA*: the start; D* Lite: the goal) towards a focus (LPA*: the goal; D* Lite: the start, which moves). g is the cost from the root and rhs the one-step lookahead, rhs(root) = 0 and otherwise the minimum over walkable neighbours v of g(v) + cost where the move cost is the move v -> node (LPA*) or node -> v (D* Lite) through the cost hook. Unreachable and non-walkable nodes have rhs = +inf.

Queue. Nodes with g != rhs are queued with key [min(g, rhs) + h(focus, node) + km, min(g, rhs)]. Order (ReplanOpenSet): first key, then second key, then node index; two keys within a relative 1e-11 count as equal.
Loop. While the top key is smaller than the focus's key, or the focus is inconsistent (g != rhs): pop u; if its stored key is smaller than its current key, re-queue it with the current key; else if g(u) > rhs(u) set g(u) = rhs(u), remove it and recompute rhs of its neighbours; else set g(u) = +inf and recompute rhs of u and its neighbours. Recomputing a node's rhs is a full minimum over its neighbours (not the paper's per-edge shortcut), then queue it if inconsistent, remove it if consistent. One pop is one iteration (the unit of IterationBudget/Replan(budget)); pops that change a g are expansions.
Tolerance. Costs are sums of doubles added in different orders by different repairs, so costs equal on paper can differ in the last bits. "Smaller key", "equal" and "consistent" therefore use a relative tolerance of 1e-11 (absolute 1e-11 below 1), and a node whose key ties the focus's key on paper is processed when its second key is smaller. Stopping late is harmless, stopping early leaves stale costs. Reported costs are exact sums along the returned path, in start-to-goal order.
Moving the start (D* Lite): km += h(old start, new start) and the heuristic's goal becomes the new start; the queue keeps all its work. For LPA* a moved start or changed goal restarts the search. D* Lite restarts on a changed goal.
Changes. The node set to re-examine for an edit at cell (x, y) with agent size s on a square grid is the cells [x - s, x + 1] x [y - s, y + 1] (for a rectangle edit [x - s, x + w] x [y - s, y + h]): a move between two nodes reads the two nodes' areas, the cells beside a diagonal move, and the s x s blocks both nodes occupy, all within one cell of both nodes, and the walkability of a node for size s reads the block starting at it. Both ends of every changed move are in the set, so recomputing rhs there is complete. On a hex grid the changed cell and its neighbours are re-examined. A change touching more than a quarter of the cells (or more pending nodes than the grid has) restarts the search instead. A change to AreaCosts (a multiplier) rebuilds the search (the heuristic's scale depends on the smallest multiplier). Changes the grid cannot see (a delegate that now answers differently) are announced with Invalidate.
Path. From the focus, repeatedly step to the neighbour minimising g + move cost, preferring neighbours with g == rhs (settled; a queued neighbour may hold an out-of-date cost), ties broken by neighbour order (see Movement); LPA* walks goal to start and reverses. Many equal-cost paths exist, so the path may differ from A*'s, but never the cost.
Requirements. The move graph must be undirected in structure (true for the square and hex topologies); the heuristic must be consistent and symmetric (octile, Manhattan, hex distance, zero); the heuristic weight must be 1; costs of +inf/NaN remove a move.
Slicing. Replan(budget) pops at most budget times; on BudgetExhausted the next call resumes, and any sequence of budgets ends with the result, expansion count and path of one unsliced call.

Tier 1: grid.CreateReplanner(start, goal, options) (GridOptions.Algorithm = LpaStar, else D* Lite) returns a GridReplanner (HexReplanner) that listens to the grid: Replan(), MoveStart, SetGoal, Invalidate, Dispose. Tier 2: ReplanSearch<,,> over any IGridTopology with struct cost and heuristic. Tier 3: ReplanOpenSet, the node-level MarkChanged/Replan/ExtractPath. A one-off FindPath with LpaStar or DStarLite runs A*.

HPA* (hierarchical path-finding over chunks)

Botea, Müller & Schaeffer 2004, one level. GridAlgorithm.Hpa (tier 1; HpaChunkSize default 16, HpaSmoothing default true), HpaHierarchy and HpaSearch (tier 2), the per-chunk data through ClusterNodes, IntraCost, GetInterEdges (tier 3).

Scope. Square grids, four or eight moves, rules NoCornerCutting and NoSqueezing, any agent size, area costs. Not supported (the query runs as A* and GridPath.Algorithm says so): step-cost or blocking callbacks, AllowAll with eight moves. The heuristic options and weight are ignored. Hex grids are not covered. No multi-level hierarchy. Clearance: one hierarchy is built over the cells walkable for one agent size (true clearance); tier 1 caches a hierarchy per (chunk size, agent size, moves, rule), at most eight, oldest dropped first. The paper's annotated variant (one graph for all sizes) is not used.

Chunks. Side C; chunk (cx, cy) holds cells [cx·C, min(W, cx·C+C)) × [cy·C, min(H, cy·C+C)), indexed cy · ClustersX + cx.

Entrances and transitions. For two chunks sharing a border, border position p is open when the two cells facing each other are both walkable. A maximal run [lo, hi] of open positions is an entrance. Width hi-lo+1 ≥ T (EntranceThreshold, default 6) and hi ≠ lo: two transitions at lo and hi; otherwise one at lo + (width-1)/2. A transition is the pair (cell in chunk A, cell in chunk B); both cells are abstract nodes joined by inter-edges in both directions at the move cost (m[a] + m[b]) · 0.5. Diagonal border moves get no entrances of their own: under both supported rules a diagonal crossing implies a walkable straight crossing beside it, and the cells of one run are connected inside each chunk, so abstract connectivity equals real connectivity.

Intra-edges. For every ordered pair of nodes of a chunk, the cost of the cheapest path that stays inside the chunk (Dijkstra over the topology's own moves, targets settled early; open order as in OpenSet, with the chunk-local cell index as last tie-break). +∞ when none. Moves between two cells of a chunk read only cells of that chunk, so a chunk's edges depend on its cells alone.

Canonical form. A chunk's nodes are sorted by cell index; its inter-edges by (node, target cell). The graph is a function of cells, costs and options only: ContentEquals and GetContentHash (FNV-1a 64 over node cells, cost bits and inter-edges in chunk order) compare it.

Query. Insertion: from the start, one chunk-restricted Dijkstra gives the cost to every node of its chunk (and to the goal when in the same chunk); the same from the goal gives the cost of the edges into the goal (move costs are symmetric). Abstract A* runs with cells as node ids (open order: smaller f, larger g, smaller cell index), the octile (eight moves) or Manhattan heuristic times the smallest area cost, and edges expanded in the order: start edges or intra-edges by node index, edge to the goal, inter-edges by target. One iteration is one pop of the abstract open set; IterationBudget and Step(n) count these. The abstract path is refined by repeating the chunk-restricted search that priced each intra-edge (so the cells match the edge's cost); a border crossing is one step.

Smoothing (paper section 5, on by default). Walking from path position i in each allowed direction (order: N, E, S, W, NE, SE, SW, NW) while moves are legal, a walk that meets a later path cell j > i+1 and costs less than the path from i to j by more than 1e-9 is a candidate. The candidate with the largest j wins, then the lower cost, then the lower direction; the path continues from j. A cell visited twice by the path maps to its last position. GridPath.Cost is always the sum of the final cells' move costs.

Guarantees. A path is found exactly when A* finds one; each step is a legal move; the cost is never below the optimum. It is not optimal: the paper reports a few percent over; Moving AI measurements are under Verification.

Incremental update. The hierarchy is an IGridChangeListener. A cell edit at (x, y) marks every chunk intersecting [x-(S-1)-1, x+1] × [y-(S-1)-1, y+1] (S the agent size: the edit changes clearance up and left by S-1, and entrances read the neighbouring chunk's cell), clipped to the grid. Refresh (called by every query) rebuilds marked chunks in index order; the result equals a full rebuild. Edits to the area cost table (AreaCosts.Version) mark everything. Grid notifies listeners on every edit, so batches of edits cost one Refresh.

Cost model. Build: one Dijkstra per node over at most C² cells; node count per chunk is roughly 4·C/T to 4·C/2. Memory: n² doubles per chunk.

3D voxel grids

VoxelGrid (root namespace) is a bounded block of voxels, one byte each: an area id 0..254 or 255 for solid, the same ids and AreaCosts table as the square grid. It is searched by the same AStar through VoxelTopology.

Storage (normative). The block is cut into 16 x 16 x 16 chunks. The chunk table is dense, `ceil(sx/16) * ceil(sy/16) * ceil(sz/16)slots, slot indexcx + ChunksX * (cy + ChunksY * cz)`. A slot is null (every voxel of the chunk has the grid's default area, fixed at construction: 0 for open space, 255 for a solid block to carve) or a 4096-byte array indexed (x & 15) | ((y & 15) << 4) | ((z & 15) << 8). An edit that differs from the default allocates the chunk, which then stays. Padding voxels past the size in an edge chunk are never read. At most 2^30 voxels.

Search nodes. A voxel's node is x + sx * (y + sy * z); it is the final open-list tie-break. State per node is cost 8, parent 4, mark 4, open-set position 4 (20 bytes). The one-line query (grid.FindPath) keeps that state in pages of 8 x 8 x 8 voxels (512 nodes, 10 KB), allocated when the search first reaches a voxel of the block and found through a dense table with one int per block (4 MB for 5x10^8 voxels); the parent is stored as a slot (page << 9 | in-page index), the in-page index is (x & 7) | ((y & 7) << 3) | ((z & 7) << 6), and the search reads each voxel's coordinates from its page, so no node index is ever divided. Search memory is therefore proportional to the blocks the search touches. The paged search is the same algorithm as AStar (same open-list order, strict-improvement relaxation with reopening, neighbour order), so cost, path, expansion order and iteration counts are equal (tested against the dense search). Pages are pooled between queries; a pool above 4096 pages (about 40 MB) is dropped after the query. The tier-2 AStar<VoxelTopology, ...> with GridSearchBuffers stays dense, 20 bytes per voxel of the block (a 518-million-voxel block needs about 10 GB).

Moves and costs. 6 (faces), 18 (+ edges) or 26 (+ corners) neighbours; the order is faces, then edges, then corners, each by z, then y, then x ascending from -1 to 1 (an 18- or 6-move view uses a prefix). Face moves have length 1, edge moves GridMath.Sqrt2, corner moves VoxelMath.Sqrt3 (the double nearest the true root, 1.7320508075688772). The cost of a move is length * ((m[from] + m[to]) * 0.5). The destination must be open.

Corner rule (VoxelCornerRule) for edge and corner moves. The swept cells are those inside the move's cube other than the start and the destination: two face cells for an edge move; three face cells and three edge cells for a corner move. NoCornerCutting (default, the Moving AI voxel convention): all swept cells open. NoSqueezing: some monotone route of face steps from start to destination through open cells exists (an edge move needs one of its two face cells; a corner move needs a face cell and an edge cell containing it). AllowAll: the destination only.

Heuristic. The exact empty-grid distance of the connectivity times AreaCosts.MinCost, so it is admissible and consistent. With sorted absolute offsets a <= b <= c and m = a + b + c: six moves, m; 26 moves, a*sqrt3 + (b-a)*sqrt2 + (c-b); 18 moves, e*sqrt2 + (m - 2e) with e = min(floor(m/2), a + b). A* tie-breaking and the open list are those of the square grid (OpenSet: smaller f, then larger g, then smaller node index, as documented above).

Changes. SetArea/SetWalkable notify IVoxelChangeListeners and bump Version; topologies read the live chunk table, so a query after an edit equals a query on a grid built from scratch with the final contents (tested). There is no cached state to repair.

API tiers. Tier 1: grid.FindPath(VoxelCell|VoxelPoint, ..., VoxelOptions?) with plain options and delegates (StepCost, Blocked), presets VoxelOptions.Default/SixConnected/EighteenConnected. Tier 2: AStar<VoxelTopology, TCost, VoxelHeuristic> with struct cost hooks, resumable Step(budget) equal to the unsliced run. Tier 3: VoxelGrid.GetChunk, VoxelTopology, VoxelHeuristic, GridSearchBuffers. World positions are doubles within +-2^21 (VoxelSpace: origin and cell size, voxel (i,j,k) spans origin + (i,j,k) * size); anything beyond throws ArgumentOutOfRangeException naming the value; a position outside the block gives StartInvalid/GoalInvalid.

Moving AI voxel files. VoxelMap.Parse reads .3dmap (voxel X Y Z, then one x y z line per solid voxel); VoxelScenarios.Parse reads .3dscen (version 1, the map name, then sx sy sz gx gy gz length ratio). Malformed input throws GridFormatException with the line. The published lengths of the Warframe set equal 26-move, no-corner-cutting costs with the constants above: the check allows an absolute 1e-6 (observed differences are below 1e-7: the files print eight decimals); the two looser rules give different costs on 95% of the first 2000 scenarios of Simple.

Moving AI files

MovingAiMap.Parse reads the .map format (type, height, width, map, then rows). . and G are walkable; @, O, T blocked; S (swamp) walkable and W (water) blocked by default (MovingAiOptions; the published optimal lengths of the wc3maps512 set need exactly this). MovingAiScenarios.Parse reads version 1 .scen files (9 whitespace separated fields per line). Both reject malformed input with GridFormatException (line number in the message); sizes are bounded (65536 per side, 2^28 cells) and a map's cells must be present in the file before they are allocated.

Verification

Costs equal an independent O(n²) Dijkstra written from the definitions on 10^4 random grids per variant (4-/8-connected, the three diagonal rules, area costs, agent sizes 1-3, the four hex layouts); returned paths are checked move by move.
Published optimal lengths of the Moving AI 2D sets (dao, da2, bg512, sc1, wc3maps512, street, maze, random, room), 8-connected, no corner cutting, via tools/GridOptima. The published numbers differ from exact octile sums by at most 1.7e-9 of the length (consistent with some being summed with a diagonal cost of 1.41421356); the check allows a relative 1e-6.
Hash-matrix scenarios grids/* write status, cost bits, expansion counts and paths for generated maps.
Fuzz targets movingai-map, movingai-scen, grid-query, grid-jps, grid-theta (fuzz/run.sh).
JPS and JPS+: costs equal Dijkstra on 10^4 + 4·10^3 + 600 random grids, on rooms with gaps, and A* on grids wider than a bitmap word; table entries equal the cell-by-cell scan; incremental tables equal a rebuild over 1200 edit sequences; the block scan equals the cell scan with goals anywhere; every Moving AI 2D set above equals the published optimal costs with both (ALG=jps sweep.sh, ALG=jps+ sweep.sh, or GridOptima --alg jps|jps+).

Any-angle verification

Line of sight equals an independent exact segment-versus-closed-square test (separating axes, integers) on 3,000 grids x 60 pairs and 300 grids up to 40 x 40, and is symmetric.
On 10^4 random grids up to 12 x 12 (and 2,000 with a unit cost of 2.5, 300 up to 30 x 30): same reachability as A*; every segment passes the exact test; the cost equals the segment lengths added in order, bit for bit; Theta* and LazyRequeue are never longer than A*; every variant is at least the visibility-graph optimum (Dijkstra over all line-of-sight links between walkable centres).
GridOptima --alg theta|lazytheta reports, on Moving AI scenarios, the ratio to the published eight-connected optimum (at most 1), re-verifies every 64th path with the independent test, and compares with the visibility-graph optimum on eight deterministic 40 x 40 windows per map (--random N does the same on random 24 x 24 grids).
Replanning: after every change in 10.8k random change/move sequences (LPA* and D* Lite; 4- and 8-connected, three diagonal rules, agent sizes 1-3, area costs, cell and tile edits, start moves) the replanned cost equals an independent O(n^2) Dijkstra and the library's A*, and paths are legal and sum to their cost; hex layouts the same; sliced equals unsliced; incremental clearance and JPS+ tables after tile edits equal a full recompute. On Moving AI dao and room (GridOptima --replan lpa|dstar): random wall toggles along the current path, costs equal fresh A*.
HPA*: refined paths are checked move by move against the brute-force move rules and priced independently on 10^4+ random grids (chunk 2-7, thresholds 1-8, both connectivities and rules, agent sizes 1-2, area costs): found exactly when Dijkstra reaches the goal, never cheaper than it, smoothing never longer; the hierarchy after random edit batches (agent sizes 1-3, area edits) equals a rebuild bit for bit; sliced equals whole for budgets 1-17. GridOptima --alg hpa [--chunk N] [--smooth 0|1] checks every Moving AI scenario's path and reports the mean and maximum percentage over the published optimum (chunk 16, smoothing on, 8-connected: dao 0.40% mean, bg512 0.33%, sc1 0.22%, room 0.08%; unsmoothed 4.9%, 4.1%, 3.2%, 1.6%; zero invalid or missing paths). Maxima are large only for very short scenarios (a few cells), where one detour through a transition is a big fraction. Fuzz target grid-hpa.
Voxel grids: costs equal an independent O(n²) Dijkstra (moves enumerated from the definition, corner rules evaluated over the move's bounding box) on 10^4 random blocks per connectivity (all three corner rules, area costs, both heuristics), on larger blocks across chunk borders, and the heuristic equals the empty-grid distance; edits equal rebuilds; sliced equals unsliced for budgets 1, 2, 7 and 50. Fuzz targets voxel-map, voxel-scen, voxel-query; hash scenarios grids/voxel/*; the Warframe set via tools/GridOptima/voxel-sweep.sh (GridOptima --voxel).

Host API: resumable handle, tick-path calls, hash, snapping, exact costs

For a lockstep or rollback host whose simulation ticks must not allocate.

GridSearch (Grid.CreateSearch(options)) is a non-generic resumable A*, JPS or JPS+: TryBegin(start, goal) returns InProgress, StartInvalid or GoalInvalid (the checks FindPath makes: inside the grid, clearance for AgentSize, Blocked; a refusal leaves the running search alone; Begin is the throwing twin), Step(n) pops at most n times and returns InProgress, Found or NoPath, CopyPath(Span<Cell>) / CopyPath(Span<int>) write the path, SaveState/RestoreState snapshot it (grids-state.md, kind 12). It supports GridAlgorithm.AStar, Jps and JpsPlus (the others throw ArgumentException). It chooses its engine exactly as FindPath does: for A* the specialised octile engine when the options allow it, otherwise the generic AStar<SquareTopology, ...> instantiation FindPath would build; for JPS and JPS+ the specialised octile jump point engine when the options allow it, otherwise the generic JumpSearch over the block map (JPS) or the JPS+ tables, and options a jump point search cannot honour (four moves, agent size above 1, area costs that differ, callbacks, a weighted or Manhattan estimate) run plain generic A*, as FindPath does. One iteration of a jump point search is one pop of a jump point (the scans that find jump points are not counted). FindPath(start, goal, o) is TryBegin then Step(o.IterationBudget), so for every slicing the handle returns cell for cell the path FindPath returns, with the same ExpandedCount and cost bits (tested on generated random, room, maze, cave and area-cost maps and eight option variants for A*, nine for JPS and JPS+). The grid must not be edited while a search is in progress (Step throws InvalidOperationException). After the first search TryBegin, Step, CopyPath, GetStateSize, SaveState(Span<byte>) and RestoreState allocate nothing on every engine; a state save costs a pass over the cells plus the visited cells (the generic engines serialise their own state into a buffer the handle keeps, which grows to the largest state seen).

Which engine breaks ties how. The specialised engine (Grids/Fast) keeps costs as exact integer pairs (straight steps, diagonal steps), orders its open list by f, then larger g rounded to float32, then smaller cell index, and relaxes neighbours in the order N, E, S, W, NE, SE, SW, NW. The generic engine sums double step costs and orders by f, then larger double g, then smaller node index, in the same neighbour order. Both are optimal, but on a tie between equal-cost paths they can choose different cells. We did not make the generic engine reproduce the pairs: its cost type is an arbitrary double (hooks, area multipliers), so no exact pair exists, and the specialised engine's speed depends on them. Instead GridOptions.SpecializedEngines = false forces the generic engine in FindPath and CreateSearch, and that is then cell for cell what a hand-built AStar<SquareTopology, DefaultStepCost, OctileHeuristic>(topology, default, new OctileHeuristic(width, Areas.MinCost)) returns (tested). A host that mixes tier-1 and tier-2 searches and needs one answer per request sets it for all of them; otherwise use one entry point per request kind. JPS and JPS+ honour the switch too (off means the generic jump search).

AStar.TryBegin(start, goal) (generic form) returns the same statuses as an integer-node check instead of throwing; AStar.Topology, Start and Goal are read-only views.

GridReplanner.TryReplan(budget) repairs like Replan(budget) but returns a PathStatus; on Found read PathLength, PathCost (summed from the start in path order, bit-equal to Replan().Cost) and CopyPath. Path buffers are reused, so a steady-state call allocates nothing. RecordExpansions is not kept by this form.

Grid.ContentHash() (64 bit): feed words w into h = rotl(h ^ (w * P2), 31) * P1 + P3, from h = P1 ^ P2, with P1 = 0x9E3779B185EBCA87, P2 = 0xC2B2AE3D27D4EB4F, P3 = 0x165667B19E3779F9 (all arithmetic mod 2^64). Words, in order: width | height << 32; the cells row-major, eight per little-endian word, the last zero-padded; the 255 area multipliers 0..254 as binary64 bit patterns. Finish: h ^= h >> 33; h *= P2; h ^= h >> 29; h *= P3; h ^= h >> 32. Version, world mapping and edit history are not part of it. Known answers are in the tests. The definition changes only with a note in the changelog. The value is cached: a cell edit (SetArea, SetRect), a state restore or any area-cost change (Areas[...], CopyFrom) invalidates it, and the next call recomputes; a repeated call with no edit in between is O(1) and returns the same bits a recompute would. HexGrid and VoxelGrid have no content hash.

NavMesh.Build2D(Grid, NavSettings?) builds the 2D mesh from a square grid: a cell is walkable when its area is not 255, cell size and origin come from Grid.Space (grid column x is world X, row y is world Z), and the result is byte-equal to Build2D(bool cells, width, height, cellSize, origin) on the same walkability. Area ids and multipliers are not carried into the mesh (the 2D builder gives every polygon NavSettings.Area); agent size comes from NavSettings.AgentRadius, not from grid clearance. A grid without walkable cells gives a mesh with no tiles.

Large agents. An agent of side s occupies the s × s block whose top-left cell is the position. CanFit(cell, s) is clearance >= s, the test FindPath applies to its end cells; MaxAgentSizeAt(cell) is the clearance without exceptions (0 outside the grid).

Grid.TryFindNearestWalkable(cell | world point, out cell, options) returns the cell that fits AgentSize and is not refused by Blocked, nearest by squared Euclidean distance between cell indexes, ties to the smaller row and then smaller column. The query may be outside the grid. NearestRadius bounds the search in Chebyshev rings. It scans rings outward and stops once a ring is farther than the best hit.

Exact integer costs. Grid.TryGetFixedCost(cells, out long) prices a path of adjacent cells in Q31.32: every step is the double the default search charges (the mean of the two cells' area multipliers; times 1.4142135623730951 for a diagonal), multiplied by 2^32 (exact) and rounded half to even, and the integers are added. GridPath.TryGetStepCounts gives the exact numbers of straight and diagonal steps. Both refuse a path with a non-adjacent step (any-angle, abstract) and StepCost hooks are not priced.

Host hooks

Snapshot and restore of grids, voxel grids, graphs, replanners, flow fields and sliced searches, the byte format, what one iteration of each family's budget is, and the debug geometry types are specified in grids-state.md.