A* search
Use a heuristic to guide shortest-path search towards a goal instead of exploring equally in every direction.
Big idea
How it thinks about the graph
A* balances the cost so far with an estimate of the remaining cost. A good heuristic can make the search much more focused.
Useful when
Pathfinding in games, maps, grid worlds and problems where a sensible distance estimate is available.
Watch out: The heuristic needs to be chosen carefully. A bad heuristic can remove the advantage, and an over-optimistic-looking shortcut may not be safe.
Questions to investigate
What makes a heuristic useful?
How does A* differ from Dijkstra's algorithm?
When might a direct-looking route not be the cheapest route?
Open the interactive explorer
This algorithm already has a working prototype. Use it to build a graph, make a prediction, then step through the search.
Open A* search explorer