Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A* (A-star) is the classic informed search algorithm for pathfinding
A* (A-star) is the classic informed search algorithm for pathfinding.
It expands nodes in order of f(n) = g(n) + h(n), where g is the real cost from the start and h is a heuristic estimate of the remaining cost to the goal.
With an admissible heuristic (one that never overestimates), A* is guaranteed to return an optimal path.
How It Works
Start with the start node in an open list.
Repeatedly extract the node with the smallest f, move it to the closed list, and examine its walkable neighbors: compute tentative g = g(current) + step cost, and if it improves the neighbor (or the neighbor is unseen), update g, f, and the parent, then add it to open.
Stop when the goal is extracted and reconstruct the path from parents.
The Manhattan distance on a 4-connected grid is admissible, so the result is optimal — and A* typically explores far fewer nodes than Dijkstra because the heuristic steers the search toward the goal.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Time (admissible heuristic) | O(bᵈ) worst case | O(bᵈ) worst case |
| On a grid with Manhattan h | O(V) typical | O(V) |
| Optimality | Guaranteed if h is admissible | — |
| vs. Dijkstra | A* = Dijkstra with h = 0 | — |
Best Use Cases
- Game AI pathfinding on tile maps
- GPS navigation and route planning
- Robot motion planning (grid and graph spaces)
- Puzzle solving (8-puzzle, sliding blocks) with admissible heuristics
- Parsing and speech recognition (Viterbi-style A*)
Worked Example
Find a path from S (0,0) to G (5,6) on a 6×7 maze grid
Input: grid rows 0–5, cols 0–6; walls in rows 1–5; start (0,0), goal (5,6); Manhattan heuristic- 1 f = g + h where g is the cost from S and h is the Manhattan distance to G.
- 2 The start (0,0) has f = 0 + 11. Its neighbors are expanded in increasing f order.
- 3 Because h never overestimates (it is admissible), the first time G is extracted, its path is optimal.
- 4 The chosen path runs along the top row to (0,6), then straight down column 6 to G.
- 5 Path: (0,0) → (0,1) → (0,2) → (0,3) → (0,4) → (0,5) → (0,6) → (1,6) → (2,6) → (3,6) → (4,6) → (5,6).
- 6 Length = 11 steps, exactly the Manhattan distance between S and G — the theoretical minimum, so no detour was needed.
Pseudocode
open = {start}; g[start] = 0
f[start] = g[start] + h(start, goal)
while open not empty:
cur = node in open with min f
if cur == goal: return reconstruct(cur)
move cur to closed
for each walkable neighbor nb:
tentative = g[cur] + cost(cur, nb)
if tentative < g[nb] or nb not seen:
g[nb] = tentative
f[nb] = g[nb] + h(nb, goal)
parent[nb] = cur; add nb to open
return "no path" A* Search on a Grid
A* expands the node with the smallest f = g + h, where h is the Manhattan distance to the goal.