Pathfinding

Pathfinding is the computational problem of finding a route between two points in a spatial or abstract environment, subject to constraints such as obstacles, cost functions, and resource limitations. It is the physical-world counterpart to graph search: where graph search operates on abstract nodes and edges, pathfinding operates on geometric or topological spaces where distance, collision, and continuity matter.

The problem appears in robotics (motion planning), video games, geographic information systems, and network routing. In each domain, the space is represented as a graph — a grid, a mesh, a visibility graph, or a roadmap — and the pathfinding algorithm searches this graph for an optimal or feasible route. A* search is the most widely used algorithm, but specialized domains require specialized variants: any-angle pathfinding for continuous spaces, hierarchical pathfinding for large environments, and multi-agent pathfinding for coordinated movement.

Pathfinding is not merely about finding shortest paths. It is about finding traversable paths — paths that respect the physical or institutional constraints of the agent doing the traversing. The shortest path through a minefield is not the best path if it cannot be walked. Pathfinding is the search for feasible optimality, not topological optimality.