Pathfinding generally refers to the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.
Contents |
Pathfinding in the context of video games 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 forms of this are found in most modern video games. Pathfinding has grown in importance as games and their environments have become more complex, and as a result, many AI software packages have been developed to solve the problem.
Real-time strategy games typically contain large areas of open terrain which is often relatively simple 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.
More open endedly structured genres such as first-person shooters 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 navigation meshes. These are constructed by placing nodes in the game world that store details of which nodes are accessible from it.
At its core, a pathfinding method searches a graph by starting at one point and exploring adjacent nodes 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.
A common example of a graph-based pathfinding algorithm is Dijkstra's algorithm. This algorithm begins with a start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all adjacent nodes are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path.
A* is a variant of Dijkstra's algorithm commonly used in games. Instead of looking at the distance from the start node, A* chooses nodes based on the estimated distance from the start to the finish. The estimate is formed by adding the known distance from the start to a guess of the distance to the goal. The guess, called the heuristic, improves the behavior relative to Dijkstra's algorithm. When the heuristic is 0, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance.) As the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many games this is acceptable and even desirable, to keep the algorithm running quickly.
This is a fairly simple and easy-to-understand pathfinding algorithm for tile-based maps. To start off, you have a map, a start coordinate and a destination coordinate. The map will look like this, X being walls, S being the start, 0 being the finish and _ being open spaces:
X X X X X X X X X X X _ _ _ X X _ X _ X X _ X _ _ X _ _ _ X X S X X _ _ _ X _ X X _ X _ _ X _ _ _ X X _ _ _ X X _ X _ X X _ X _ _ X _ X _ X X _ X X _ _ _ X _ X X _ _ 0 _ X _ _ _ X X X X X X X X X X X
First, create a list of coordinates, which we will use as a queue. The queue will be initialized with one coordinate, the end coordinate. Each coordinate will also have a counter variable attached (the purpose of this will soon become evident). Thus, the queue starts off as ((3,8,0)).
Then, go through every element in the queue, including elements added to the end over the course of the algorithm, and to each element, do the following:
Thus, after turn 1, the list of elements is this: ((3,8,0),(2,8,1),(4,8,1))
Now, map the counters onto the map, getting this:
X X X X X X X X X X X _ _ _ X X _ X _ X X _ X _ _ X _ _ _ X X S X X _ _ _ X _ X X 6 X 6 _ X _ _ _ X X 5 6 5 X X 6 X _ X X 4 X 4 3 X 5 X _ X X 3 X X 2 3 4 X _ X X 2 1 0 1 X 5 6 _ X X X X X X X X X X X
Now, start at S (7) and go to the nearby cell with the lowest number (unchecked cells cannot be moved to). The path traced is (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). In the event that two numbers are equally low (for example, if S was at (2,5)), pick a random direction - the lengths are the same. The algorithm is now complete.