A* pathfinding visualizer

The search runs as soon as anything changes; press Play to watch it, or Step through it one event at a time. Light cells are in the open set, waiting to be expanded; darker cells have been expanded; the path appears at the end. Click or drag on the grid to draw or erase walls, or switch the click mode to move the start or goal. The table beside the grid runs all four heuristics on the same grid.

Try these:

• On the Empty layout, compare None with Manhattan. Dijkstra's algorithm spreads out in a diamond until it reaches the goal; Manhattan A* walks almost straight to it.
• Load the U-shaped trap. The start sits inside a cup that opens away from the goal. The heuristic pulls the search into the back of the cup, and A* has to fill it before it finds the way round.
• Load Detour and pick 2 × Manhattan. It returns a path 10 steps longer than the shortest, and on this layout it does not even save work: it expands 136 cells against 133 for plain Manhattan. Overestimating breaks the guarantee.
• Wall the goal off completely. Every heuristic then has to expand every cell it can reach before it can say there is no path.

The search code is tested against breadth-first search on thousands of random grids: with None, Euclidean and Manhattan it always returns the shortest length; with 2 × Manhattan it never returns a path more than twice as long; and Manhattan never expanded more cells than Dijkstra's algorithm.

A* (pronounced "A star") is an algorithm for finding a shortest path between two points in a graph: cells on a grid, intersections on a road map, states of a puzzle. It works like Dijkstra's algorithm but adds an estimate of the distance still to go, called the heuristic, so that it explores toward the goal first.

The heuristic does not need to be exact. As long as it never overestimates the remaining cost, A* still returns a shortest path; the better the estimate, the fewer places it has to look. A heuristic of zero makes A* identical to Dijkstra's algorithm, and a perfect heuristic would let it walk straight down the shortest path.

A* keeps two sets. The open set holds nodes that have been reached but not yet explored, usually in a priority queue such as a binary heap. The closed set holds nodes already expanded. For each node it records g, the cost of the best path found to it so far, and a parent pointer to the node it was reached from.

1. Put the start in the open set with g = 0.
2. Take the node with the smallest f = g + h out of the open set. If it is the goal, stop.
3. Otherwise expand it: for each neighbour, compute g through this node. If that is lower than the neighbour's current g, record the new g and parent and put the neighbour in the open set.
4. Move the node to the closed set and go back to step 2. If the open set runs out, there is no path.

The path is read back by following parent pointers from the goal. Two details matter in practice. The test for the goal happens when the goal is taken out of the open set, not when it is first reached, because a cheaper route may still be waiting. And when several nodes share the lowest f, preferring the one with the larger g (further along its path) reduces the number of expansions on grids, where ties are common; the simulator does this.

A heuristic is admissible if it never overestimates the true remaining cost, and consistent if it never drops by more than the cost of a step: h(n) ≤ cost(n, m) + h(m) for every neighbour m. Admissibility guarantees a shortest path; consistency also guarantees that each node is expanded at most once, which is why simple implementations like this one can close a node for good.

On a grid the right heuristic depends on the moves allowed. With four-way moves of cost 1, Manhattan distance, |Δrow| + |Δcol|, is exact when there are no walls, so it is the best admissible choice. Euclidean distance is also admissible but smaller, so it guides the search less. With eight-way moves, octile or Chebyshev distance plays the role Manhattan plays here. A good general recipe is relaxation: drop a constraint of the real problem, such as walls, and use the cost of the easier problem as h.

The counts below come from running the simulator's code on its fixed layouts.

Multiplying the heuristic by a weight w greater than 1 makes A* greedier: it trusts the estimate more and the cost so far less, and usually expands fewer nodes. The price is optimality. The path found is never more than w times the shortest, a bound that goes back to Ira Pohl's work on weighted heuristic search in 1970. On the Walls layout, w = 2 expands 69 cells instead of 134 and still finds a shortest path. On the Detour layout it follows the estimate into a long way round: 39 steps instead of 29, after expanding 136 cells against 133 for plain Manhattan. The saving is likely, not guaranteed; the bound on path length is.

Anytime variants such as ARA* (Likhachev, Gordon and Thrun, 2003) start with a large weight to get a path quickly, then lower it and improve the path while time allows, reusing earlier work. They are used in robot motion planning, where a good path now is worth more than the best path later.

With h = 0, f equals g and A* is exactly Dijkstra's algorithm stopped at the goal. With a consistent heuristic, A* is equivalent to running Dijkstra's algorithm on a graph whose edge costs have been adjusted by the heuristic, which is one way to see why it stays correct. Rina Dechter and Judea Pearl showed in 1985 that, among algorithms given the same consistent heuristic, A* is optimal in the number of nodes it must expand, up to how ties are broken.

Dijkstra's algorithm is still the right choice when there is no useful estimate, or when the distances to many destinations are needed at once. A* is for one start and one goal with a sensible way to estimate the distance between them.

• Games. Game characters usually navigate over a navigation mesh, a graph of walkable polygons, rather than a grid. Recast Navigation's Detour library, used by several game engines, finds paths over such a mesh with A* and a straight-line heuristic, scaled by 0.999 in its source so that it stays slightly below the true distance.
• Robotics. A* was created for SRI's Shakey robot, and grid and lattice versions of it, along with D* Lite and anytime variants, remain common in mobile-robot planners.
• Road routing. Plain A* with straight-line distance helps little on continental road networks, because the estimate is weak. Routing engines rely on preprocessing instead, such as contraction hierarchies or landmarks (ALT), and search the resulting graph with bidirectional Dijkstra or A*.
• Puzzles and planning. Optimal solvers for sliding-tile puzzles and similar problems use A* or IDA* with heuristics computed from simplified versions of the puzzle (pattern databases).

A* was developed at the Stanford Research Institute for Shakey, a mobile robot that planned its own movements. Nils Nilsson first proposed a heuristic version of Dijkstra's algorithm (called A1), Bertram Raphael improved it (A2), and Peter Hart supplied the proof of when such an algorithm is guaranteed to find a shortest path. Their paper, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", appeared in IEEE Transactions on Systems Science and Cybernetics in 1968, and the best version of the algorithm became A*.

Later work refined the theory, including Pohl's weighted search in 1970, Korf's IDA* in 1985 and Dechter and Pearl's 1985 optimality results, and extended it to changing maps, limited memory and huge graphs.