Pathfinding
Pathfinding or pathing is the search, by a computer application, for the shortest route between two points.
This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.
An analogy would be a person walking across a room; rather than examining every possible route in advance, the person would generally walk in the direction of the destination and only deviate from the path to avoid an obstruction, and make deviations as minor as possible.
By eliminating impossible paths, these algorithms can achieve time complexities as low as
At each step, the node in the open set with the lowest distance from the start is examined.
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).
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.
Pathfinding has a history of being included in video games with moving objects or NPCs.
Chris Crawford in 1982 described how he "expended a great deal of time" trying to solve a problem with pathfinding in Tanktics, in which computer tanks became trapped on land within U-shaped lakes.
[6] The idea was first described by the video game industry, which had a need for planning in large maps with a low amount of CPU time.
The concept of using abstraction and heuristics is older and was first mentioned under the name ABSTRIPS (Abstraction-Based STRIPS)[7] which was used to efficiently search the state spaces of logic games.
The reason is, that such a map would contain 6 million nodes overall and the possibilities to explore the geometrical space are exceedingly large.
The first step for a hierarchical path planner is to divide the map into smaller sub-maps.
In the newly created graph the amount of nodes is small, it is possible to navigate between the 100 clusters, but not within the detailed map.
Multi-agent pathfinding is to find the paths for multiple agents from their current locations to their target locations without colliding with each other, while at the same time optimizing a cost function, such as the sum of the path lengths of all agents.
Many multi-agent pathfinding algorithms are generalized from A*, or based on reduction to other well studied problems such as integer linear programming.
[11] However, such algorithms are typically incomplete; in other words, not proven to produce a solution within polynomial time.
A different category of algorithms sacrifice optimality for performance by either making use of known navigation patterns (such as traffic flow) or the topology of the problem space.
