Pathfinding finds a route from a start to a goal through obstacles. It is BFS with a map: every GPS, every game unit and every robot runs a variant of it.
The eight algorithms differ in what they know: BFS knows nothing and floods evenly, Dijkstra knows the cost so far, A* also guesses the cost to go, so it heads straight for the goal.
All algorithms
9Each card runs its own algorithmA*, Dijkstra and BFS on the real streets of Cascavel, from OpenStreetMap.
Expands in rings from the start. Shortest path on unweighted grids.
Dives down one corridor before backing up. Finds a path, not the shortest.
Always expands the cheapest known cell. Shortest path with weights.
Dijkstra plus a heuristic estimate to the goal. Optimal and focused.
Follows the heuristic only. Fast, but the path can be far from shortest.
Two frontiers, from start and goal, meet in the middle.
A* that skips straight runs of open cells on uniform grids.
Any-angle A*: parents can be any visible cell, so paths are not grid-bound.