A*

A* is the definitive pathfinding algorithm that combines actual distance and heuristic estimates to find the shortest route with maximum efficiency.

Engineers at SRI International (Peter Hart, Nils Nilsson, and Bertram Raphael) debuted A* in 1968, and it remains the standard for efficient pathfinding. It calculates the best route using the formula f(n) = g(n) + h(n): g(n) tracks the cost from the start, while h(n) provides a heuristic estimate to the target. This logic allows the algorithm to ignore irrelevant paths, saving significant compute time in applications like StarCraft pathing or GPS navigation. As long as your heuristic is admissible (it never overestimates the distance), A* guarantees the shortest path every time.

https://en.wikipedia.org/wiki/A*_search_algorithm