Pathfinding

Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph. Pathfinding is closely related to the shortest path problem, within graph theory, which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc) between two points in a large network.

Pathfinding or pathing is the search, by a computer application, for the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph. Pathfinding is closely related to the shortest path problem, within graph theory, which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc) between two points in a large network. ===Dijkstra's algorithm=== A common example of a graph-based pathfinding algorithm is Dijkstra's algorithm. This algorithm begins with a start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path. Dijkstra's algorithm fails if there is a negative edge weight. In the hypothetical situation where Nodes A, B, and C form a connected undirected graph with edges AB = 3, AC = 4, and BC = −2, the optimal path from A to C costs 1, and the optimal path from A to B costs 2. Dijkstra's Algorithm starting from A will first examine B, as that is the closest. It will assign a cost of 3 to it, and mark it closed, meaning that its cost will never be reevaluated. Therefore, Dijkstra's cannot evaluate negative edge weights. However, since for many practical purposes there will never be a negative edgeweight, Dijkstra's algorithm is largely suitable for the purpose of pathfinding. ===A* algorithm=== A* is a variant of Dijkstra's algorithm with a wide variety of use cases. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined. A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance, as the same comparison result can often be reached using simpler calculations – for example, using Chebyshev distance over Euclidean distance in two-dimensional space.) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this is acceptable and even desirable, in order to keep the algorithm running quickly. ===Hierarchical path finding=== s can be used for hierarchical path finding]] The concept of hierarchical pathfinding predates its adoption by the video game industry and has its roots in classical artificial intelligence research. One of the earliest formal descriptions appears in Sacerdoti's work on ABSTRIPS (Abstraction-Based STRIPS) in 1974, which explored hierarchical search strategies in logic-based planning. Later research, such as Hierarchical A* by Holte et al., further developed the theory of abstraction hierarchies in search problems. In the context of video games, the need for efficient planning on large maps with limited CPU time led to the practical implementation of hierarchical pathfinding algorithms. A notable advancement was the introduction of Hierarchical Path-Finding A* (HPA*) by Botea et al. in 2004. HPA* partitions the map into clusters and precomputes optimal local paths between entrance points of adjacent clusters. At runtime, it plans an abstract path through the cluster graph, then refines that path within each cluster. This significantly reduces the search space and allows for near-optimal planning with much faster performance. Partial-Refinement A* (PRA*), developed by Sturtevant and Buro, takes a similar approach but emphasizes interleaved planning and acting. Instead of refining the entire path immediately, PRA* refines only the first few steps and continues refining the rest as needed during execution. This is especially useful in dynamic environments. Similar techniques include navigation meshes (navmesh), used for geometric planning in games, and multimodal transportation planning, such as in variations of the travelling salesman problem that involve multiple transport types. A hierarchical planner performs pathfinding in two phases: first, between clusters at a high level; then, within individual clusters at a low level. This structure enables guided local search with fewer nodes, resulting in high performance. The main drawback is the implementation complexity of maintaining abstraction layers and refinements. ====Example==== A map with a size of 3000×2000 nodes contains 6 million tiles. Planning a path directly on this scale, even with an optimized algorithm, is computationally intensive due to the vast number of graph nodes and possible paths. A hierarchical approach divides the map into 300×200 node clusters, forming a 10×10 grid (100 clusters total). The high-level abstract graph now contains only 100 nodes. A path is planned between these clusters, which is computationally cheap. Once the abstract path is found, each cluster on the path is processed using a regular A* planner to find the exact low-level route within. This two-stage process significantly improves efficiency while maintaining near-optimal path quality.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1357657507 under CC BY-SA 4.0; modifications have been made.