Pathfinding
Encyclopedia
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
for finding the shortest path on a weighted graph.
In video games
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 strategyReal-time strategy
Real-time strategy is a sub-genre of strategy video game which does not progress incrementally in turns. Brett Sperry is credited with coining the term to market Dune II....
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
Game artificial intelligence
Game artificial intelligence refers to techniques used in computer and video games to produce the illusion of intelligence in the behavior of non-player characters . The techniques used typically draw upon existing methods from the field of artificial intelligence...
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 shooter
First-person shooter
First-person shooter is a video game genre that centers the gameplay on gun and projectile weapon-based combat through first-person perspective; i.e., the player experiences the action through the eyes of a protagonist. Generally speaking, the first-person shooter shares common traits with other...
s 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 mesh
Navigation mesh
A navigation mesh is an abstract data structure used in artificial intelligence applications to aid agents in path-finding through large spaces...
es. These are constructed by placing nodes in the game world that store details of which nodes are accessible from it.
Algorithms
At its core, a pathfinding method searches a graphGraph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
by starting at one point and exploring adjacent node
Node (computer science)
A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...
s 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
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
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
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
. 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
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
, 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.
Sample algorithm
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:
- Create a list of the four adjacent cells, with a counter variable of the current element's counter variable + 1 (in our example, the four cells are ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
- Check all cells in each list for the following two conditions:
- If the cell is a wall, remove it from the list
- If there is an element in the main list with the same coordinate and an equal or lower counter, remove it from the list
- Add all remaining cells in the list to the end of the main list
- Go to the next item in the list
Thus, after turn 1, the list of elements is this: ((3,8,0),(2,8,1),(4,8,1))
- After 2 turns: ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
- After 3 turns: (...(1,7,3),(4,6,3),(5,7,3))
- After 4 turns: (...(1,6,4),(3,6,4),(6,7,4))
- After 5 turns: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
- After 6 turns: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
- After 7 turns: ((1,3,7)) - problem solved, end this stage of the algorithm - note that if you have multiple units chasing the same target (as in many games - the finish to start approach of the algorithm is intended to make this easier), you can continue until the entire map is taken up, all units are reached or a set counter limit is reached
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.
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
- StraightEdge Open Source Java 2D path finding (using A
* ) and lighting project. Includes applet demos. - python-pathfinding Open Source Python 2D path finding (using Dijkstra's Algorithm) and lighting project.