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:
Every heuristic here is admissible under both movement rules, so any of them is safe on any grid (subject to the cell-cost caveat below). They differ only in how tight the bound is, which affects search speed and not correctness.
| Heuristic | Tightest under | Notes |
|---|---|---|
| ZERO | any | A* degenerates to Dijkstra |
| 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 |
Why there is no Manhattan heuristic. Manhattan distance is a lower bound only under VON_NEUMANN movement. Under MOORE — the default — a diagonal step costs √2 while Manhattan charges it 2, so the estimate exceeds the true cost and A* may return a sub-optimal path. That was not merely theoretical: a differential sweep against Dijkstra found sub-optimal results on roughly 17% of randomised Moore instances, which is why the heuristic was withdrawn rather than documented. Use OCTILE (or EUCLIDEAN) instead; both are admissible under either rule. Cell.manhattanDistanceTo is unaffected and remains the right metric for Von Neumann neighbourhood queries.
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.
Properties
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.