Pathfinding
From Wikipedia, the free encyclopedia
 |
This article or section may require cleanup to meet Wikipedia's quality standards. Please help improve this article or replace this tag with a more specific message. This article has been tagged since August 2006. (help, talk) |
| Graph search algorithms |
|---|
| Search |
Pathfinding is a term used mostly by computer applications to plot the best route from point A to point B. It is a more realistic variant on solving mazes.
Used in a wide variety of games, it refers to AI finding a path around an obstacle, such as a wall, door, or bookcase. In recent games, pathfinding has become more important as players demand greater intelligence from their own units (in the case of Real-time strategy games) or their opponents (as in the case of first-person shooters).
Both genres have different challenges in pathfinding. RTS games have to deal with a larger, more open terrain which is often simpler to find a path through, although they almost always have more agents trying to simultaneously travel across the map. In these 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 an heuristic which is used to sort them in likelihood of providing the optimal route to the destination.
The algorithm then moves to the best node on this list and moves it to a closed list. All the nodes accessible from this node are then added to the open list and their heuristic calculated. This process repeats until a path to the destination has been found.
Another algorithm is Dijkstra's algorithm, which is similar to A* except it always finds the optimal path (A* is a compromise of path length, and calculation time).
The basic idea behind pathfinding is to search a graph, starting at one point, and exploring (adjacent) nodes from their until the destination node is reached. The goal is of course, generally to obtain the shortest route to the destination. A naive way of pathfinding would be a Breadth-First Search of the graph (exploring nodes in order of distance from your starting point until you encounter the destination node). While this would eventually find a solution (given sufficient time), there are algorithms for exploring the graph which tend to reach the destination node sooner, which is important in realtime applications. A good way of imagining this is to think of walking across a room. You generally wouldn't turn around and examine every space (in order to increase distance from your starting point) that you would fit into until you "find" your destination; instead you would generally try to walk straight ahead to the destination, and only straying from that path if you see something that obstructs your path, and even then, you probably would look for a path that requires the shortest detour first, and so forth.
 |
This computer or video game-related article is a stub. You can help Wikipedia by expanding it. |
