Back

Pathfinding Dijkstra Astar

What you are seeing: the same shortest-path problem on a procedural city (streets cost 1, piazzas cost 4, buildings and the river are walls). Left, Dijkstra floods outward in all directions; right, A* uses a goal-direction heuristic and drives a tight beam toward the target. At heuristic weight 1, A* is still optimal and finds the same route as Dijkstra with far fewer cells. Push the weight above 1 and A* turns greedy: it reaches the goal scanning even fewer cells, but the path it returns is no longer the shortest, the classic speed-versus-optimality trade-off, while Dijkstra always proves the true optimum. Each panel fires its own bolt the instant that search reaches the goal, so A* can finish and rest while Dijkstra is still flooding; the solved map then holds for five seconds before a new city.

Figure 1. Uniform-cost search vs A* with an admissible Manhattan heuristic.
speed5
map seed7
A* heuristic weight1.00

WHAT TO TRY

  • Watch the two searches: Dijkstra (top) floods outward in all directions, while A* (bottom) drives a narrow beam toward the goal and finishes scanning far fewer cells.
  • At heuristic weight 1, A* is still optimal: it finds the exact same shortest path, just cheaper. The strip at the bottom shows how much less work it did.
  • Push the weight above 1 (greedy A*): it scans even fewer cells, but the path it returns can be longer than optimal, the classic speed-versus-quality trade-off.