Grid
Pre-built heuristic functions for A* pathfinding on a GridGraph. All are admissible on uniform-cost grids (cell costs all ≥ 1.0) under the appropriate movement rule:
| Heuristic | Movement rule | Notes |
|---|---|---|
| ZERO | any | A* degenerates to Dijkstra |
| MANHATTAN | VON_NEUMANN | tight for 4-way movement |
| CHEBYSHEV | MOORE | tight when diagonals cost 1 (not used by default) |
| OCTILE | MOORE | tight when diagonals cost √2 (the default) |
| EUCLIDEAN | either | always admissible but never tight on a grid |
Admissibility and cell costs. Every non-ZERO heuristic here assumes each step costs at least its geometric length — i.e. all cell costs are ≥ 1.0. If any cell cost is < 1.0 (and in particular 0.0), these heuristics overestimate the true cost and A* may return a sub-optimal path. For such grids, wrap the heuristic with scaled using the grid's GridGraph.minCellCost:
val h = GridHeuristics.scaled(graph.minCellCost, GridHeuristics.OCTILE)
val path = graph.shortestPath(start, goal, h)ZERO (plain Dijkstra) is always admissible regardless of costs.
Functions
Scale base by scale (typically GridGraph.minCellCost) so it stays admissible on grids with cell costs below 1.0. Since every step costs at least scale × stepLength, multiplying an otherwise-admissible geometric heuristic by scale keeps it a lower bound on the true cost. A scale of 0 yields ZERO.