A* Search
An informed search algorithm that uses heuristics to guide the search. It guarantees the shortest path (if heuristic is admissible) and is usually much faster than Dijkstra.
A* (A-Star) Algorithm
Heuristic Function: Manhattan Distance
f(n) = g(n) + h(n)
Total estimated cost
h(n) = |x₁ - x₂| + |y₁ - y₂|
Manhattan distance to goal
Ready to start
g, h, or f?
Sort each description into the part of f(n) = g(n) + h(n) it describes.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
g(n) — cost so far
Drop items hereh(n) — heuristic
Drop items heref(n) — priority
Drop items hereTest your knowledge
What is the role of the Heuristic (h) in A*?
The short version
Think of driving with a GPS. It doesn't just look at road distance; it also estimates the remaining time to the destination (Heuristic) to guide you, avoiding paths that clearly lead away from the goal.
In more depth
Smart Search with Heuristics
A* (A-Star) is an extension of Dijkstra's algorithm. Instead of blindly exploring the closest nodes, A* uses a Heuristic to guess which nodes are more promising (closer to the goal).
f(n) = g(n) + h(n)
By prioritizing nodes with the lowest total estimated cost f(n), A* directs the search towards the target, often visiting far fewer nodes than Dijkstra.
Admissibility
For A* to guarantee the shortest path, the heuristic h(n) must be admissible, meaning it never overestimates the true cost to reach the goal. Common heuristics include Manhattan Distance (for grids) and Euclidean Distance.
When to reach for this
- Pathfinding in games/maps where you know the target location
- Grid traversal with obstacles
- Solving puzzles (like 8-puzzle) efficiently
Interview Questions
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required