Pathfinding and path finding in computer science is the search for the supported algorithms and the optimal paths ( englisch path - path) from a given start point to one or more destination points. The range of applications of network flow analysis on route planning, and computer games.
Range of tasks
In many, but not necessarily in all cases is the search for the optimal path between two points, the search for the lowest cost or shortest route with the fewest obstacles. This is true to the "classic example of learning ", but the correct answer to a pathfinding problem is rarely in practice actually get the air line between a given start and a given target point. The search is often influenced by other factors that distort the concept of the optimum and thus make it appear sensible other routes, such as:
- Not or only partially impassable obstacles that block the direct path
- Variable cost of transportation, such as increased fuel consumption with flow
- Multidimensional cost models in the locomotion, eg time vs. Vs. fuel. accident hazards
- The grid and discretization of the environment, similar to a chess game or field
- The need to pass on the route between certain points or favorable termination options for the route to leave open
- Non-Cartesian coordinates
→ see: Shortest path
To meet the requirements for pathfinding depending on the context, a variety of algorithms has been developed, of which almost all have their unique advantages and disadvantages in the past.
A common path finding method, the A * - algorithm, in which the environment map is interpreted as a graph and heuristics are used to calculate. First start and destination nodes must be specified. Thereafter, each field is replaced by from the start point a value which increases in proportion to the distance. The optimal way is one in which the target field receives the lowest value. Obstacles to be overcome, but a waste of time to apply, can be easily taken into account. ( An example would be a swamp in which the value of each field as 2 instead of 1 increases and, therefore, may exist a faster, but longer way around it. )
It has no heuristics to estimate cost between nodes can be used instead of the algorithm of Dijkstra A * algorithm. All shortest paths from one node to all other nodes to calculate a negative edge weights in a graph, the Bellman-Ford algorithm can be used. If one looks. , Not only the best paths of a node to all other nodes in the graph, but the best paths between all pairs of nodes, we can use the min -plus matrix multiplication algorithm, or the algorithm of Floyd and Warshall
In the computer games sector, the history of the Pathfindings of classic games such as Pac -Man goes back to the present. While Pac -Man, for example, simple pathfinding algorithms ensured that ghosts moving as computer opponents through a virtual maze, they are now used in real-time strategy games of the route planning of entire military units and in first-person shooters to the sophisticated guidance of computer-controlled bot opponents. Real -time strategy games are usually based on two-dimensional maps, which are divided into individual tiles. Particular difficulties arise, for example, in ways that are blocked dynamically, such as when multiple units pass through a narrow passage at the same time. In FPS games, at their cards, the third dimension plays a more important role, working frequently with waypoints at which the Artificial Intelligence oriented. Almost always "good" path finding is also associated with high complexity. In the computer game Age of Empires II, for example, taken alone, then pathfinding on commodity hardware 60 to 70 percent of the total CPU power while playing to complete.
Accordingly, great efforts are made to optimize pathfinding algorithms. The solutions range from pre-calculations (ie, reducing the running time at the expense of memory footprint ) to advantageous assumptions that can make a program with respect to its specific use case in advance (eg, " between A and B is an insurmountable ravine with the only performs a single bridge, so the route will inevitably lead there along and not elsewhere ").