Pathfinder

Shortest is not the same as cheapest. On terrain where moving uphill costs more, a route with fewer steps can be the expensive one, and a search that ignores cost will happily pick it.

Implemented breadth-first search, uniform-cost search (Dijkstra) and A* from scratch in Python. Each grid cell has an elevation, moving costs 1 plus any climb, obstacles block movement, and moves are four-directional.

A* runs with two admissible heuristics, Euclidean and Manhattan distance, and every algorithm runs on the same set of test maps, from a small maze to a 20 by 20 random terrain, so the comparison is fair.

On the same path, A* expanded 41 nodes against uniform-cost search's 75 and BFS's 112. On the 20 by 20 map, BFS's route cost 24% more than the optimal one, which is the whole argument for cost-aware search in one number.