A* Search: Open Set, Closed Set, and f-score
A* finds paths by balancing the cost already paid with a heuristic estimate of what remains.
Site connection
The path finder project visualizes A* through grid cells, obstacles, heuristics, and the final path.
Visual model
Frontier expansion on a grid
Switch heuristics to see how the explored cells and final path differ.
Interactive
A* expands likely paths first instead of flooding the whole grid
The Mental Model
A* behaves like a careful explorer with a map estimate. It keeps a frontier of possible next cells, scores each candidate, and always expands the candidate that looks cheapest after combining what it already paid with what it still expects to pay.
- is the real cost from the start to node .
- is the heuristic estimate from node to the goal.
- is the priority score used to choose what to expand next.
Why the heuristic condition mattersIf the heuristic never overestimates the true remaining cost, A* keeps its shortest-path guarantee. If it overestimates, it may become faster but no longer reliably optimal.
| Choice | Effect |
|---|---|
| Manhattan distance | Fits four-direction grid movement and produces rectilinear search pressure |
| Euclidean distance | Fits continuous geometry or diagonal movement better |
| Zero heuristic | Degenerates toward Dijkstra's algorithm |
| Overconfident heuristic | Can be fast but may skip the optimal path |
The Score That Drives the Search
A* gives each candidate node an f-score: f(n) = g(n) + h(n).
g(n) is the known cost from the start to the node. h(n) is the estimated cost from the node to the goal. The algorithm repeatedly expands the node with the smallest f-score.
A* is powerful because h(n) gives the search a sense of direction without discarding the actual path cost.
Open and Closed Sets
The open set stores frontier nodes that might still lead to the best path. The closed set stores nodes already expanded.
Walls or obstacles are never expanded. The final path appears when the goal is reached and parent pointers are traced backward.
| Set | Meaning |
|---|---|
| Open | Candidates discovered but not fully expanded |
| Closed | Nodes whose neighbors have already been considered |
| Path | Parent chain from goal back to start |
| Wall | Blocked cell that cannot be traversed |
Common Pitfalls
- Using a heuristic that overestimates and breaks shortest-path guarantees.
- Forgetting to update a node when a cheaper route is found.
- Confusing visited cells with the final path.
- Using Euclidean distance on a grid where only four-direction movement is allowed without thinking through the movement model.
Quick check
Quiz
What does f(n) combine?
- Only distance from start
- Known cost plus estimated remaining cost
- Only wall density
- Random tie-breaking
A* uses f(n) = g(n) + h(n).