Pathfinding Algorithms: How Computers Navigate Maps, Games, and Networks

The Pathfinding Problem

At its core, pathfinding asks: given a starting location and a destination, what is the best route between them? "Best" typically means shortest distance, but it can also mean lowest cost, fastest travel time, or fewest turns. The environment is modeled as a graph where nodes represent locations and edges represent connections with associated costs. Road networks, game maps, floor plans, and circuit boards are all pathfinding environments.

The challenge is efficiency. A road network for a country might contain tens of millions of nodes and edges. A real-time strategy game might need to compute paths for hundreds of units every frame. Naive approaches that explore every possible route are far too slow. Effective pathfinding algorithms use intelligent search strategies to explore only a small fraction of the graph while guaranteeing optimal or near-optimal results.

Dijkstra Algorithm for Pathfinding

Dijkstra algorithm finds the shortest path from a source to all other nodes in a weighted graph with non-negative edge weights. It maintains a priority queue of unvisited nodes ordered by their current shortest known distance. At each step, it removes the node with the smallest distance, marks it as visited, and updates the distances of its neighbors. When the destination is removed from the queue, its shortest path is known.

For pathfinding between two specific points, Dijkstra algorithm can be stopped early once the destination is reached. However, it explores nodes in all directions equally, expanding outward in concentric circles from the source. On a map, this means it examines nodes behind the source just as eagerly as nodes toward the destination, which wastes computation. This undirected exploration motivates the development of informed search algorithms.

A* Search: The Gold Standard

A* (pronounced "A star") is the most widely used pathfinding algorithm. It improves on Dijkstra by incorporating a heuristic function that estimates the remaining distance from any node to the destination. A* evaluates nodes by f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n, and h(n) is the estimated cost from n to the destination. By prioritizing nodes that appear closer to the goal, A* focuses its search toward the destination instead of expanding uniformly in all directions.

The heuristic must be admissible, meaning it never overestimates the true remaining distance. For grid-based maps, common admissible heuristics include Manhattan distance (sum of horizontal and vertical distances, appropriate when movement is restricted to four directions) and Euclidean distance (straight-line distance, appropriate for any-angle movement). When the heuristic is also consistent (the estimated cost from n to the goal is always less than or equal to the cost of stepping to a neighbor plus the estimate from that neighbor), A* never needs to revisit a node, guaranteeing efficiency.

With a perfect heuristic (one that exactly equals the true remaining distance), A* expands only the nodes on the optimal path and nothing else. With a zero heuristic, A* degrades to Dijkstra algorithm. The quality of the heuristic determines how much faster A* is than Dijkstra: a better heuristic means fewer nodes explored and faster pathfinding.

Grid-Based Pathfinding

Many pathfinding applications use grid representations: video games, robotics, and building floor plans. In a grid, each cell is a node, and edges connect adjacent cells (4-directional or 8-directional movement). Obstacles are marked as impassable cells. Grid pathfinding has special considerations.

Jump Point Search (JPS) accelerates A* on uniform-cost grids by identifying "jump points," nodes where the optimal path must change direction, and skipping over straight-line segments. JPS can be orders of magnitude faster than standard A* on open grids with few obstacles, while producing identical optimal paths. It exploits the symmetry of grid movement, where many paths of equal length exist between two points, by selecting a canonical representative from each equivalence class.

Navigation meshes (navmeshes) represent walkable areas as a mesh of convex polygons rather than a grid of cells. Pathfinding on a navmesh is faster because the graph has far fewer nodes (one per polygon instead of one per grid cell), and movement within each polygon is unrestricted. Navmeshes are the standard representation for character navigation in 3D video games and virtual environments.

Hierarchical Pathfinding

For very large environments, flat pathfinding algorithms become too slow. Hierarchical pathfinding divides the map into regions, precomputes paths within and between regions, and uses this multi-level structure to accelerate queries. The high-level search plans a coarse route through regions, and the low-level search refines each segment within its region.

Contraction Hierarchies are a preprocessing technique for road networks that precomputes shortcut edges, allowing queries to be answered in microseconds on continental-scale networks. The technique assigns an importance ranking to each node and contracts less important nodes by adding shortcut edges that preserve shortest-path distances. At query time, a bidirectional Dijkstra search on the augmented graph explores only nodes of increasing importance, drastically reducing the search space. Modern GPS navigation systems use contraction hierarchies or similar preprocessing techniques.

Real-Time and Anytime Pathfinding

Some applications cannot wait for a complete path computation before acting. Real-Time A* (RTA*) and Learning Real-Time A* (LRTA*) compute only the next few steps, allowing an agent to begin moving immediately while refining the path as it travels. These algorithms are useful in games where characters must respond instantly and in robotics where the environment may change during navigation.

Anytime algorithms like Anytime Repairing A* (ARA*) quickly find a suboptimal path and then iteratively improve it as computation time allows. They provide a usable result at any point and converge to the optimal path if given enough time. This approach is valuable when response time is more important than optimality, such as in autonomous vehicle navigation where a good-enough path right now is better than a perfect path computed too late.

Beyond Shortest Path

Not all pathfinding optimizes for shortest distance. Any-angle pathfinding algorithms like Theta* find paths that are not restricted to grid edges, producing smoother and shorter routes. Multi-agent pathfinding coordinates paths for multiple agents simultaneously, avoiding collisions, which is essential for warehouse robotics and autonomous vehicle fleets. Dynamic pathfinding handles environments that change over time, such as road closures or moving obstacles, by efficiently updating paths rather than recomputing them from scratch.