Pathfinding

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. Strategy games, both real-time and turn based, 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 which create a need for different, and often significantly more complex algorithms to avoid traffic jams. 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.

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 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.

The basic idea behind pathfinding is to search a graph, starting at one point, and exploring (adjacent) nodes from there 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 method to imagine 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.

External links

*http://www.policyalmanac.org/games/aStarTutorial.htm
*http://theory.stanford.edu/~amitp/GameProgramming/
*http://sourceforge.net/projects/argorha
*http://www.ai-blog.net/archives/000152.html