A* pathfinding is a graph search algorithm used to find a low-cost path from a start node to a goal node. It is common in games, robotics, maps, and AI because it combines actual distance traveled with an estimate of distance remaining. This cheat sheet helps students remember the cost model, the main data structures, and the update steps that make A* work.
It is especially useful when comparing A* with Dijkstra's algorithm and greedy best-first search.
The core formula is f(n) = g(n) + h(n), where g(n) is the known cost from the start to node n and h(n) is the heuristic estimate from n to the goal. A* repeatedly expands the open node with the lowest f(n), updates neighboring nodes when a cheaper path is found, and stores parent links to rebuild the final path. If the heuristic is admissible, A* can find an optimal path.
If the heuristic is also consistent, nodes usually do not need to be reopened after they are closed.
Key Facts
- A* ranks nodes using f(n) = g(n) + h(n), where lower f(n) values are explored first.
- g(n) is the exact known cost from the start node to node n along the current best path.
- h(n) is the heuristic estimate of the remaining cost from node n to the goal node.
- The open set stores discovered nodes that may still be expanded, usually with a priority queue ordered by lowest f(n).
- The closed set stores nodes that have already been expanded so the algorithm does not repeat unnecessary work.
- When checking a neighbor, update it if tentative_g = g(current) + cost(current, neighbor) is less than its stored g value.
- A heuristic is admissible if h(n) never overestimates the true remaining cost to the goal.
- A* is optimal when edge costs are nonnegative and the heuristic is admissible.
Vocabulary
- Node
- A point or state in a graph that the algorithm can visit, such as a grid cell or map intersection.
- Edge Cost
- The cost of moving from one node to a connected neighbor, such as distance, time, or energy.
- Open Set
- The collection of discovered nodes that are candidates for expansion but have not been fully processed.
- Closed Set
- The collection of nodes that have already been expanded and usually should not be expanded again.
- Heuristic
- An estimate of the remaining cost from a node to the goal, used to guide the search.
- Parent Link
- A stored pointer from a node to the previous node on the current best path, used to reconstruct the final route.
Common Mistakes to Avoid
- Using f(n) instead of g(n) when updating a neighbor is wrong because the actual path cost must be based only on the cost already traveled.
- Choosing a heuristic that overestimates the remaining cost is wrong because A* may skip the true shortest path and return a nonoptimal route.
- Forgetting to update a node already in the open set is wrong because a newly found path may have a smaller g(n) and should replace the old path.
- Treating the closed set as permanent when the heuristic is not consistent is wrong because a better path to a closed node may still appear.
- Ignoring tie-breaking rules is risky because nodes with the same f(n) can produce different search patterns and may affect efficiency.
Practice Questions
- 1 A node has g(n) = 14 and h(n) = 9. What is f(n)?
- 2 From the current node with g(current) = 12, moving to a neighbor costs 5. The neighbor's stored g value is 20. Should A* update the neighbor, and what is the new g value?
- 3 Two open nodes have scores A: g = 8, h = 7 and B: g = 10, h = 3. Which node should A* expand first if it chooses the lowest f(n)?
- 4 Explain why an admissible heuristic helps A* find an optimal path while still usually searching fewer nodes than Dijkstra's algorithm.
Understanding A* Pathfinding Algorithm Reference
A* works because it balances two kinds of information that have different jobs. The cost already paid tells the algorithm how expensive a route has been so far. The estimate ahead gives it a sense of direction.
A route that looks close to the goal is not automatically good if it took a costly detour to get there. In the same way, a cheap route so far may lead away from the destination. The combined score helps A* avoid these two mistakes.
The algorithm is not guessing the whole path at once. It makes a series of local choices while keeping records that allow earlier choices to be improved.
The quality of the heuristic strongly affects speed. On a square grid with movement only up, down, left, or right, Manhattan distance is often suitable. It counts the horizontal steps plus the vertical steps still needed.
If diagonal movement is allowed at the same cost as straight movement, a different distance estimate is needed. A heuristic must match the movement rules and edge costs. For example, straight line distance can be too optimistic or too weak depending on the map.
A heuristic of zero is always safe when costs are nonnegative, but then A* behaves like Dijkstra's algorithm and may inspect many more nodes. A heuristic that is too large can make the search faster, yet it can miss the lowest cost route.
Consistency is a useful stronger rule for a heuristic. It means the estimated cost from one node should be no greater than the cost of moving to a neighbor plus that neighbor's estimate. This is similar to the triangle inequality used in geometry.
When consistency holds, the estimated total score does not decrease along a path that is being explored. That property makes the closed set reliable. Once a node is removed from the priority queue for expansion, its best route is settled.
Without consistency, a better route to an already closed node may appear later. A correct program then needs to reopen that node rather than ignoring the improvement.
Students often lose marks on the bookkeeping rather than the main idea. Every discovered node needs a current best cost and a parent pointer. When a cheaper route reaches a neighbor, replace both pieces of information.
The parent pointer must change because path reconstruction follows these links backward from the goal to the start, then reverses the result. A priority queue may contain an old entry for a node after its cost improves. Many implementations leave the old entry in the queue and skip it when removed if its score no longer matches the stored best cost.
In a game map, blocked cells are omitted from the neighbors. In route planning, roads can have different costs because of distance, traffic, or terrain. The same algorithm works in each case, but the graph model and heuristic must represent the real rules accurately.