A* Path Planning · Octile Heuristic on a Grid

Abstract

A* is the classical best-first graph-search algorithm: it expands nodes in order of f(n) = g(n) + h(n), where g is the cost-to-come and h is an admissible heuristic estimating the cost-to-go. With an admissible and consistent heuristic, A* returns an optimal path and is optimally efficient (no other algorithm with the same heuristic expands fewer nodes). This implementation uses 8-connectivity with the octile heuristic and runs in single-digit milliseconds on a 30×30 grid against four environments shared with three other planners.

Algorithm

f(n)  =  g(n)  +  h(n)
g(n)  =  shortest known cost from start to n
h(n)  =  heuristic estimate of cost from n to goal
       (admissible: h(n) ≤ true cost-to-go, never over-estimates)

For 8-connected grids the octile distance is the tight admissible heuristic, equal to the shortest 8-connected path on an empty grid:

octile(a, b)  =  (√2 − 1) · min(|Δx|, |Δy|)  +  max(|Δx|, |Δy|)

Loop: pop the node with smallest f from a min-heap, mark it expanded, relax all 8 neighbours, push improved neighbours back into the heap. Diagonal moves cost √2; cardinal moves cost 1.

Diagnostic: Expanded Nodes and Final Path

Cyan dots are the cells A* expanded. The dark line is the recovered optimal path. The expansion frontier is biased toward the goal because of the heuristic; without h(n) (Dijkstra) the frontier would expand uniformly outward.

Headline Numbers Across Four Environments

A* is the path-length floor against which the other three planners on this site compare themselves: optimal by construction, fastest by 1–3 orders of magnitude, but constrained to the grid. Sub-millisecond plans on the cluttered environment because the heuristic prunes most of the search space.

Where A* sits in the planner stack

A* is a global, complete, optimal planner on discrete grids. The other three planners on this site sit at different points in the design space and the cross-planner comparison below makes the trade-offs explicit:

• RRT samples continuous space and trades optimality for the ability to handle high-dimensional or non-grid configurations.
• DWA is reactive: it has no global view and is typically run on top of A*'s output, tracking waypoints under kinematic constraints.
• Genetic algorithm is a metaheuristic that finds good paths without an admissible heuristic, at the cost of orders of magnitude more compute.

When to use, when not to use

• Use A* when the configuration space discretises naturally to a grid, the planning horizon is short, and you need the optimal path.
• Don't use A* when the state is continuous and high-dimensional (RRT or PRM are better), when the robot has non-trivial kinematics that the grid hides (Hybrid A* or RRT* with steering function), or when the environment changes faster than re-planning can keep up (D* Lite, lifelong-planning A*).