Computer Science

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:

f(n) = g(n) + w · h(n)

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|:

  1. 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.
  2. 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.
  3. 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:

  1. Leave Grid Size at 30x30, Wall Density at 25%, and Heuristic Weight (w) at 1.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.
  2. 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.
  3. 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.
  4. 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:

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 →

More in Computer Science