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.
Motion, sensing, control loops, and plans made visible as a field of forces and trajectories.
Interactive model
Frontier expansion on a grid
Switch heuristics to see how the explored cells and final path differ.
Live HTML simulation · adjust the controls and watch the computed output respond.
Interactive
A* expands likely paths first instead of flooding the whole grid
Expanded 36 cells; path contains 14 cells.
This is a simplified teaching model. Its displayed values are computed from the controls; the article explains where the model stops.
Site connection
The path finder project visualizes A* through grid cells, obstacles, heuristics, and the final path.
Implemented: The source documents a pygame grid visualizer with configurable obstacles, taxicab or Euclidean heuristics, visited-cell coloring, and a final path. Its exact priority-queue and tie-breaking implementation are not documented here.
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 |
Worked Example
Suppose S connects to A at cost 2 and B at cost 1. A connects to goal G at cost 3; B connects to G at cost 7. With h(A)=3, h(B)=4, and h(G)=0, both A and B initially have f=5.
If a tie-break selects A, expanding it proposes G with g=5 and f=5. Following parent pointers G←A←S reconstructs a path of total cost 5. The example shows that f controls exploration while parents encode the final route; equal f-scores may change expansion order without changing optimal cost under A*'s guarantee conditions.
When a route through the current node lowers a neighbor's g-score, update that score and parent. This relaxation step is essential.
Guarantees, Mechanics, and Limits
A* starts with g(start)=0, repeatedly selects a minimum-f open node, tests it for the goal, and relaxes traversable neighbors using tentative_g=g(current)+edge_cost. Expanded nodes enter the closed set; a correct implementation may reopen one if a later route improves it.
An admissible heuristic never overestimates true remaining cost. A consistent heuristic also satisfies h(n) ≤ c(n,n′)+h(n′), so f does not decrease along an edge and graph search is simpler. With h=0, A* becomes Dijkstra-style uniform-cost search.
The usual model assumes nonnegative edge costs and can consume substantial memory for the frontier, scores, parents, and closed set. The repository describes the teaching visualizer's behavior but not its exact queue structure or tie rule, so those details should not be inferred.
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.