Artificial intelligence · Search

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?

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 ≤ 2 finds the cost-32 route; w ≥ 3 finds 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*.