Pathfinding

from Wikipedia, the free encyclopedia

Pathfinding or pathfinding 's computer science , the algorithms based search for the optimal routes or the (English path - path) from a given start point to one or more destination points. The areas of application range from network flow analysis and route planning to computer games .

Range of tasks

green: starting field
red: path
blue: target field
gray: obstacle

In many, but not necessarily all cases, the search for the optimal path between two points is also the search for the cheapest or shortest route with the fewest obstacles . Although this is the “classic learning example”, the correct answer to a path-finding problem is rarely actually the beeline between a given starting point and a given destination. The search is often influenced by other factors that distort the concept of the optimum and thus make other routes appear more meaningful, such as B .:

  • Obstacles that cannot be passed or are only passable to a limited extent and block the direct path
  • variable costs in locomotion, e.g. B. for increased fuel consumption against current
  • multi-dimensional cost models in transportation, e.g. B. Time vs. Fuel vs. Accident hazards
  • the grid or discretization of the environment, similar to a chess or playing field
  • the need to pass certain intermediate points on the route or to leave favorable options for aborting the route
  • not Cartesian coordinates

Algorithms

In order to meet the requirements of pathfinding depending on the context, a large number of algorithms have been developed in the past, almost all of which have their specific advantages and disadvantages.

A widely used path finding method is the A * algorithm , in which the environment is interpreted as a map as a graph and heuristics are used for the calculation . First of all, start and destination nodes must be specified. Afterwards, each field receives a value from the starting point that increases proportionally to the distance. The optimal way is the one where the target field gets the lowest value. Obstacles that have to be overcome but that waste time can easily be taken into account. (An example of this would be a swamp, where the value per field increases by 2 instead of 1 and therefore there may be a faster but longer way around the outside.)

If one does not have a heuristic to estimate the costs between nodes, one can use Dijkstra's algorithm instead of the A * algorithm . The Bellman-Ford algorithm can be used to be able to calculate all shortest paths from one node to all other nodes in a graph with negative edge weights . If one is not only looking for the cheapest paths from a node to all other nodes in the graph, but also the cheapest paths between all pairs of nodes, one can use the Min-Plus matrix multiplication algorithm or the algorithm of Floyd and Warshall .

Application examples

In the field of computer games, the history of pathfinding extends from classic games such as Pac-Man to the present day. While with Pac-Man z. For example, simple path-finding algorithms ensure that ghosts as computer opponents move through a virtual labyrinth ; today they are used in real-time strategy games for route planning for entire military units and in first-person shooters for the sophisticated orientation of computer-controlled bot opponents. Real-time strategy games are usually based on two-dimensional maps that are divided into individual tiles. Particular difficulties arise z. B. in paths that are dynamically blocked, such as when several units cross a narrow passage at the same time. In first-person shooters, where the third dimension plays a more important role in their maps, waypoints are often used to orient the artificial intelligence . "Good" path finding is almost always associated with a high level of complexity . In the computer game Age of Empires II z. B. Pathfinding alone on commercially available hardware at that time took up 60 to 70 percent of the total CPU performance during gaming.

Correspondingly great efforts are being made to optimize path-finding algorithms. The solution concepts range from precalculations (i.e. reducing the runtime at the expense of memory requirements ) to advantageous assumptions that a program can make in advance with regard to its specific application (e.g. "between A and B there is an insurmountable ravine over which only has a single bridge, so the route will inevitably go along there and not somewhere else ”).

Various algorithms are in the free Python - Library NetworkX implemented.

See also

Individual evidence

  1. ↑ Gamasutra , Dave C. Pottinger, 2000: "Terrain Analysis in Realtime Strategy Games" ( Memento from December 21, 2008 in the Internet Archive ) ( MS Word ; 980 kB)
  2. ↑ http://3dpathfinding.homeunix.org/ ( Memento from June 7, 2007 in the Internet Archive ) Technical University of Munich, Daniel Kastenholz, 2006: "3D Pathfinding"
  3. ^ Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Retrieved October 24, 2018 .