Pathfinding
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources (ideally, using inline citations). Unsourced material may be challenged and removed. (November 2008) |
Pathfinding generally refers to the plotting, by a computer application, of the best route between two points. It is a more realistic variant on solving mazes.
[edit] In Games
Pathfinding in this context concerns the way in which a moving entity finds a path around an obstacle; the most frequent context is real time strategy games (in which the player directs units around a play area containing obstacles), but may also be first person shooters. Pathfinding has grown in importance as games and their environments have become more complex.
Both genres pose different challenges in pathfinding. Strategy games typically contain large areas of open terrain which is often simpler to route across, although it is common for more than one unit to travel simultaneously; this creates a need for different, and often significantly more complex algorithms to avoid traffic jams at choke-points in terrain, or when units come into contact with each other. In strategy games the map is normally divided into tiles, which act as nodes in the pathfinding algorithm.
FPS games often have more enclosed (or a mixture of open and enclosed) areas that are not as simply divided into nodes - which has given rise to the use of waypoints. These are irregular and manually placed nodes in the map which store details of which nodes are accessible from it.
[edit] Algorithms
A common example of a pathfinding algorithm is A*. This algorithm begins with a startnode and adds all the nodes accessible from this node to an open list. The nodes on this list are then assigned a heuristic which is used to sort them in likelihood of providing the optimal route to the destination.
The algorithm then moves the best node on the open list to a closed list. All the nodes accessible from that node are added to the open list and their heuristics are calculated (or recalculated if they were already on the list). This process repeats until a path to the destination has been found.
Another algorithm is Dijkstra's algorithm, which is similar to A* except that it does not use a heuristic and is therefore generally slower.
At its core, a pathfinding method searches a graph, starting at one point, and exploring (adjacent) nodes from there until the destination node is reached, generally with the intent of finding the shortest route. Although graph searching methods such as a Breadth-first search would find a route if given enough time, other methods, which "explore" the graph, would tend to reach the destination sooner. 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.
