A* Pathfinding
Finds the shortest path on a grid using heuristics.
Free theory articleFinds the shortest path on a grid using heuristics.
Concept & interpretation
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.
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.