Pathfinder: a good guess saves steps
How does a map app find the best route? Not by learning. By searching! Press Play and watch two searchers race across the same map.
Blind search no guess: spreads out evenly
A* uses a guess to aim at the goal
explored: cheap to reach
explored: costly to reach
on the frontier (next candidates)
mud
Squares explored, run after run
Blind searchThe guessing searcher
How it works
Keep a to-do list
Both searchers keep a list of squares to look at next (the frontier). They start with just the start square.
Add it up
For each square: how much did it cost to get here, plus (for the guesser) a guess of how far the goal still is.
Pick the smallest
They always look at the square with the smallest total next, then add its neighbours to the list.
Reach the goal
When the goal comes up, they follow the trail back to the start. That trail is the path.
What just happened?
- Both searchers found the cheapest path. The guesser found it by looking at far fewer squares.
- The guess ("the goal is that way") pulled the search toward the goal. The blind one spread out like ripples in a pond.
- With a hasty guess, it can be fooled: on the Mud lake it plunges straight through the slow mud.
- Nothing here was learned. This is classic AI: clever search with a hand-made guess. Machine learning could learn a better guess from examples.
For grown-ups: what's really going on
Both searchers are instances of best-first search with priority f(n) = g(n) + w·h(n), where g is the cost so far and h is a heuristic estimate of the cost remaining.
- Blind search = Dijkstra's algorithm (
w = 0). On a map without mud it is exactly breadth-first search. It is guaranteed optimal but explores a disc around the start. - A* (
w = 1) uses Manhattan distance, which never over-estimates the true remaining cost on a 4-connected grid with minimum step cost 1. That makes it admissible, so A* is still guaranteed to return an optimal path, while expanding far fewer nodes. - Weighted A* / greedy (
w > 1) trades optimality for speed. On the Mud lake preset,w ≤ 2finds the cost-32 route;w ≥ 3finds a cost-53 route through the mud but expands only 21 squares instead of 114. - Measured in Node: A* returned the same cost as Dijkstra on all five presets and on 60 random messy mazes (0 differences). Squares explored, Dijkstra vs A*: open map 286 vs 19, field 284 vs 21, city 291 vs 37, trap 383 vs 130, lake 394 vs 114.
- Implementation: a binary heap frontier with ties broken by lower
h, then insertion order. Stale heap entries are skipped when popped. Used in GPS routing, game AI (NPC pathing) and robot motion planning. - Further reading: Hart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths; Amit Patel's Introduction to A*.