A* Pathfinding
Finds the shortest path on a grid using heuristics.
By Riano · Published · Updated · Report a correction
A* Pathfinding Algorithm
Concept Overview
The A* search algorithm finds shortest paths by prioritizing frontier nodes according to f(n) = g(n) + w · h(n), combining the exact accumulated path cost g(n) from the start node with a heuristic estimate h(n) of the remaining distance to the goal. When the weighted heuristic w · h(n) is admissible (never overestimates true remaining cost), A* is guaranteed to return an optimal path while expanding far fewer nodes than an uninformed search.
Mathematical Definition
At each step, A* selects the open-set node n that minimizes the priority function:
Worked Example: Octile Grid Evaluation and Heuristic Weight
In this 8-neighbor grid, cardinal steps cost 10 (representing 1.0) and diagonal steps cost 14 (representing √2 ≈ 1.4). For a cell n = (x, y) and goal t = (xt, yt) with Δx = |x − xt| and Δy = |y − yt|, the octile heuristic is h(n) = 14 · min(Δx, Δy) + 10 · |Δx − Δy|:
- Start at (1, 1), Goal at (4, 3): Here Δx = 3 and Δy = 2, so h(1, 1) = 14 · min(3, 2) + 10 · |3 − 2| = 28 + 10 = 38.
- Compare neighbors of (1, 1) at w = 1.0: Moving diagonally to n1 = (2, 2) gives g(n1) = 14 and remaining (Δx, Δy) = (2, 1), so h(n1) = 14(1) + 10(1) = 24 and f(n1) = 14 + 24 = 38. Moving right to n2 = (2, 1) gives g(n2) = 10 and remaining (2, 2), so h(n2) = 28 and f(n2) = 38; moving left to n3 = (0, 1) gives g(n3) = 10 and h(n3) = 48, so f(n3) = 58.
- Effect of weight w: At w = 0.0 (Dijkstra), f(n2) = 10 = f(n3), so the search expands backward and forward equally. At w = 1.0 (Standard A*), f(n1) = 38 < f(n3) = 58, pruning away-from-goal expansions while keeping the path optimal.
Interactive Experiment: What to Enter and Observe
Open the A* Pathfinding module to compare uniformed Dijkstra search, admissible A*, and greedy weighted A* on the same obstacle map:
- Leave Grid Size at
30x30, Wall Density at25%, and Heuristic Weight (w) at1.0(w=1: Standard A* (Admissible)). Click Start Search and observe how the red closed set and green open frontier focus toward the bottom-right goal before drawing the blue shortest path. - Drag Heuristic Weight (w) to
0.0(w=0: Dijkstra's Algorithm) on the exact same map and click Start Search: notice the red closed set floods outward uniformly in all directions before reaching the goal, yet produces the same optimal path length. - Drag Heuristic Weight (w) to
3.0(w>1: Greedy Best-First Search) and click Start Search: observe a much narrower red closed set that races toward the goal and detours around walls only when blocked. - Click New Map or raise Wall Density to
40%to test how maze-like cul-de-sacs force weighted A* to backtrack.
Assumptions & Limitations
A* guarantees a minimum-cost path only when edge costs are strictly positive and the scaled heuristic w · h(n) is admissible (never exceeds the true shortest distance h*(n) to the goal). When Heuristic Weight (w) is set above 1.0, the scaled heuristic can overestimate h*(n), trading strict optimality for fewer expanded nodes (Weighted A*, which is bounded to at most w times the optimal cost). In high-density random grids where walls completely disconnect the start and end cells, A* must exhaust the entire reachable connected component before concluding that no path exists.
References
Hart, Nilsson, and Raphael proved the admissibility and optimality theorems for A* in 1968:
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive A* Pathfinding module.
Try A* Pathfinding on Riano →