A* (pronounced "A-star") is a pathfinding algorithm that combines the thoroughness of Dijkstra's algorithm with a smart heuristic that points it toward the goal. The result: it finds the optimal path while exploring far fewer cells than Dijkstra or BFS. Published in 1968, A* remains the most widely used pathfinding algorithm in games, GPS navigation, and robotics.
Core formula: f(n) = g(n) + h(n)
A* is the sweet spot: it's both optimal (guaranteed shortest path) and efficient (skips cells that are obviously too far from the goal). In our 1000×1000 maze benchmarks, A* explored only 25% of cells vs. Dijkstra's 60% — a massive speed advantage for real-time games.
A* powers NPC movement in StarCraft, League of Legends, and World of Warcraft. Google Maps uses a modified A* to route billions of queries. Tesla Autopilot uses it for lane planning. It's everywhere because it delivers the best balance of speed and accuracy.
| Time Complexity | O(b^d) — where b is branching factor, d is depth |
| Space Complexity | O(b^d) — must store open and closed sets |
| Finds Shortest Path? | ✅ Yes (with admissible heuristic) |
| Complete? | ✅ Yes (in finite graphs) |
| Data Structure | Priority queue (min-heap by f-value) |
| Heuristic (grid maze) | Manhattan distance for 4-dir, Octile for 8-dir |
| Best For | Single-source single-target shortest path, games, GPS |
See A* in action! Our maze solver visualizes the algorithm exploring the maze, showing you exactly which cells it visits and the optimal path it finds.
For finding a path to one specific exit, yes. The heuristic skips cells that are clearly in the wrong direction. But if you need shortest paths to all cells (like a heat map), Dijkstra is the right choice since A*'s heuristic only helps with a single target.
Manhattan distance (|x₁−x₂| + |y₁−y₂|) for 4-directional movement. It's admissible and consistent, guaranteeing optimality. For 8-directional movement, use Octile or Chebyshev distance.
Yes! g(n) tracks actual cost, so passages can have different weights (e.g., mud vs. pavement). As long as h(n) never overestimates, A* finds the cheapest path. This is what makes it perfect for games with varied terrain.