Grid
A 2D-lattice graph: cells are first-class nodes, edges represent allowed movement between adjacent cells, and cells carry movement costs and blocked / passable status. Separate from GridProjection, which places agents on a lattice but doesn't model the lattice's navigation structure.
Use GridGraph for:
Pathfinding: agents plan routes through an environment with obstacles (evacuation models, warehouse AGVs, robotics).
Distance fields: precompute "distance to goal" for every cell once via distanceField, then have agents follow the gradient — typical pattern for many agents sharing a target.
Terrain analysis: reachability, bottleneck detection, impact of removing cells from passability.
Dynamics on grids: state propagation where edge weights reflect transmission likelihoods (fire spread, contagion on a spatial substrate).
Composition with the other agent-layer primitives:
An agent's position lives in a GridProjection (
cellOf,placeAt,moveTo).GridGraphis the world the agent navigates. The agent'sprocess { }body callsgraph.shortestPath(currentCell, targetCell)to plan, thengrid.moveTo(agent, nextCell)to step. The two abstractions interact only throughCellvalues; neither owns the other.
Edge model:
Each cell has a
cellCost, default 1.0. Set via setCellCost (and read via cellCostOf).Edge cost from cell u to neighbor v is
cellCost(v) * stepLength, wherestepLengthis 1.0 for orthogonal moves and √2 for diagonal moves (Moore only).Blocked cells (set via block) have no incident edges and are unreachable from any other cell.
Boundary semantics:
Bounded (default) — coordinates outside
[0, columns) x [0, rows)throw. Cells on the boundary have fewer neighbors.Torus (
torus = true) — coordinates wrap; the top-right cell is a neighbor of the top-left cell.
Time complexity:
shortestPath / shortestPathLength: O((V + E) log V) with a binary-heap priority queue (Dijkstra), often dramatically better in practice with a tight A* heuristic.
distanceField: O((V + E) log V), one multi-source Dijkstra.
reachableFrom / isReachable: O(V + E) BFS.
Corner-cutting (Moore only):
By default (
allowCornerCutting = false) a diagonal move is permitted only when both orthogonally-adjacent "shoulder" cells it passes between are passable. This prevents agents from slipping diagonally between two blocked cells (clipping a wall corner) — the physically correct behavior for obstacle, evacuation, and warehouse models.Set
allowCornerCutting = trueto recover the looser rule where a diagonal move only requires its destination to be passable (faster, occasionally desired for abstract grids).Has no effect under VON_NEUMANN (no diagonal moves).
Parameters
lattice width
lattice height
if true, coordinates wrap at boundaries
MOORE (8-way) or VON_NEUMANN (4-way)
if true, diagonal moves ignore the passability of the two shoulder cells (default false)
Constructors
Properties
Number of cells currently marked as blocked.
The minimum cell cost across the grid: min(1.0, smallest explicitly-set cost). Equals 1.0 for a uniform grid. Pass this to GridHeuristics.scaled to keep an A* heuristic admissible when some cells cost less than 1.0.
Functions
Read the cost of entering cell. Default 1.0 for cells not explicitly set.
Multi-source distance field: for each passable cell, the shortest-path cost from the nearest source in sources. The canonical use case is "distance from any exit cell" for evacuation models — compute once at setup, then every agent follows the gradient toward zero in O(1) per step.
Single-source distance field: for each passable cell, the shortest-path cost from source to that cell. Unreachable cells are absent from the result map. Useful when many agents share the same goal; compute the field once via multi-source distanceField, then look up distances per-cell in O(1).
True if cell is in bounds (always true on a torus) and not blocked.
Passable neighbors of cell under the configured movement rule. Excludes blocked cells and (for non-torus grids) out-of-range cells. Returns the cells without their edge weights; use edgeWeight if you need the weight too.
Set the per-step cost of entering cell. Must be ≥ 0. Cells with no explicit cost have cost 1.0 implicitly.