{h0 Amit's Thoughts on Path-Finding and A-Star} {set title "Amit's A* Pages"} {set meta-description "Thoughts on pathfinding, including discussions of performance, memory consumption, and path quality."} {set meta-keywords "pathfinding, A*, a-star, unit movement"} The problem we're trying to solve is to get a game object from the starting point to a goal. {emph Pathfinding} addresses the problem of finding a good path from the starting point to the goal---avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). {emph Movement} addresses the problem of taking a path and moving along it. It's possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else. At the other extreme, a movement-only system would not look ahead to find a path (instead, the initial "path" would be a straight line), but instead take one step at a time, considering the local environment at every point. Best results are achieved by using both pathfinding and movement algorithms. {h1 Pathfinding} {h2 Introduction} {filename AStarComparison.html} Movement for a single object seems easy. Pathfinding is complex. Why bother with pathfinding? Consider the following situation: {figure {img 450 318 concave1.png}} The unit is initially at the bottom of the map and wants to get to the top. There is nothing in the area it scans (shown in pink) to indicate that the unit should not move up, so it continues on its way. Near the top, it detects an obstacle and changes direction. It then finds its way around the "U"-shaped obstacle, following the red path. In contrast, a pathfinder would have scanned a larger area (shown in light blue), but found a shorter path (blue), never sending the unit into the concave shaped obstacle. You can however extend a movement algorithm to work around traps like the one shown above. Either avoid creating concave obstacles, or mark their convex hulls as dangerous (to be entered only if the goal is inside): {figure {img 450 318 concave2.png}} Pathfinders let you look ahead and make plans rather than waiting until the last moment to discover there's a problem. Movement without pathfinding works in many situations, and can be extended to work in more situations, but pathfinding is a more general tool that can be used to solve a wider variety of problems. {h3 Algorithms} The pathfinding algorithms from computer science textbooks work on {emph graphs} in the mathematical sense---a set of vertices with edges connecting them. A tiled game map can be considered a graph with each tile being a vertex and edges drawn between tiles that are adjacent to each other: {figure {img 246 246 ../game-programming/a-star/map-as-graph.png}} For now, I will assume that we're using {link http://www-cs-students.stanford.edu/~amitp/game-programming/grids/ two-dimensional grids}. Later on, I'll discuss {link {ref Polygonal maps} how to build other kinds of graphs out of your game world}. Most pathfinding algorithms from AI or Algorithms research are designed for arbitrary graphs rather than grid-based games. We'd like to find something that can take advantage of the grid nature of the map. There are some things we consider common sense, but that algorithms don't understand. For example, we know something about directions: we know that in general, as two things get farther apart, it will take a longer to move from one to the other; and we know that there aren't any secret wormholes that let you teleport from one spot on the map to another. (Well, I assume there aren't any; if there are, it becomes very hard to find a good path because you don't know where to look first.) {h3 Dijkstra's Algorithm and Best-First-Search} Dijkstra's algorithm works by visiting vertices in the graph starting with the object's starting point. It then repeatedly examines the closest not-yet-examined vertex, adding its vertices to the set of vertices to be examined. it expands outwards from the starting point until it reaches the goal. Dijkstra's algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost. (I write "a shortest path" because there are often multiple equivalently-short paths.) In the following diagram, the pink square is the starting point, the blue square is the goal, and the teal areas show what areas Dijkstra's algorithm scanned. The lightest teal areas are those farthest from the starting point, and thus form the "frontier" of exploration: {figure {img 526 376 ../game-programming/a-star/dijkstra.png}} The Best-First-Search (BFS) algorithm works in a similar way, except that it has some estimate (called a {emph heuristic}) of how far from the goal any vertex is. Instead of selecting the vertex closest to the starting point, it selects the vertex closest to the goal. BFS is {emph not} guaranteed to find a shortest path. However, it runs much quicker than Dijkstra's algorithm because it uses the heuristic function to guide its way towards the goal very quickly. For example, if the goal is to the south of the starting position, BFS will tend to focus on paths that lead southwards. In the following diagram, yellow represents those nodes with a high heuristic value (high cost to get to the goal) and black represents nodes with a low heuristic value (low cost to get to the goal). It shows that BFS can find paths very quickly compared to Dijkstra's algoritm: {figure {img 526 376 ../game-programming/a-star/best-first-search.png}} However, both of these examples illustrate the simplest case---when the map has no obstacles, and the shortest path really is a straight line. Let's consider the concave obstacle as described in the previous section. Dijkstra's algorithm works harder but is guaranteed to find a shortest path: {figure {img 526 376 ../game-programming/a-star/dijkstra-trap.png}} BFS on the other hand does less work but its path is clearly not as good: {figure {img 526 376 ../game-programming/a-star/best-first-search-trap.png}} The trouble is that BFS is greedy and tries to move towards the goal even if it's not the right path. Since it only considers the cost to get to the goal and ignores the cost of the path so far, it keeps going even if the path it's on has become really long. Wouldn't it be nice to combine the best of both? A* was developed in 1968 to combine heuristic approaches like BFS and formal approaches like Dijsktra's algorithm. It's a little unusual in that heuristic approaches like BFS usually give you an approximate way to solve problems without guaranteeing that you get the best answer. However, A* is built on top of the heuristic, and although the heuristic itself does not give you a guarantee, A* {emph can} guarantee a shortest path. {h3 The A* Algorithm} I will be focusing on the {strong {link http://en.wikipedia.org/wiki/A-star_search_algorithm A* Algorithm}}. A* is the most popular choice for pathfinding, because it's fairly flexible and can be used in a wide range of contexts. A* is like other graph-searching algorithms in that it can potentially search a huge area of the map. It's like Dijkstra's algorithm in that it can be used to find a shortest path. It's like BFS in that it can use a heuristic to guide itself. In the simple case, it is as fast as BFS: {figure {img 526 376 ../game-programming/a-star/a-star.png}} In the example with a concave obstacle, A* finds a path as good as what Dijkstra's algorithm found: {figure {img 526 376 ../game-programming/a-star/a-star-trap.png}} The secret to its success is that it combines the pieces of information that Dijkstra's algorithm uses (favoring vertices that are close to the starting point) {emph and} information that BFS uses (favoring vertices that are close to the goal). In the standard terminology used when talking about A*, {code g(n)} represents the cost of the path from the starting point to any vertex {code n}, and {code h(n)} represents the heuristic estimated cost from vertex {code n} to the goal. In the above diagrams, the yellow ({code h}) represents vertices far from the goal and teal ({code g}) represents vertices far from the starting point. A* balances the two as it moves from the starting point to the goal. Each time through the main loop, it examines the vertex {code n} that has the lowest {code f(n) = g(n) + h(n)}. {h2 Heuristics} {filename Heuristics.html} The heuristic function {code h(n)} tells A* an {emph estimate} of the minimum cost from any vertex {code n} to the goal. It's important to choose a good heuristic function. {h3 A*'s Use of the Heuristic} The heuristic can be used to control A*'s behavior. {list {hbox At one extreme, if {code h(n)} is 0, then only {code g(n)} plays a role, and A* turns into Dijkstra's algorithm, which is guaranteed to find a shortest path.} {hbox If {code h(n)} is always lower than (or equal to) the cost of moving from {code n} to the goal, then A* is guaranteed to find a shortest path. The lower {code h(n)} is, the more node A* expands, making it slower.} {hbox If {code h(n)} is exactly equal to the cost of moving from {code n} to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can't make this happen in all cases, you can make it exact in some special cases. It's nice to know that given perfect information, A* will behave perfectly.} {hbox If {code h(n)} is sometimes greater than the cost of moving from {code n} to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.} {hbox At the other extreme, if {code h(n)} is very high relative to {code g(n)}, then only {code h(n)} plays a role, and A* turns into BFS.} } {margin-note {vbox {strong Note:} {hbox Technically, the {strong A*} algorithm should be called simply {strong A} if the heuristic is an underestimate of the actual cost. However, I will continue to call it {strong A*} because the implementation is the same and the game programming community does not distinguish {strong A} from {strong A*}.} } } So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, we'll get shortest paths really quickly. If we're too low, then we'll continue to get shortest paths, but it'll slow down. If we're too high, then we give up shortest paths, but A* will run faster. In a game, this property of A* can be very useful. For example, you may find that in some situations, you would rather have a "good" path than a "perfect" path. To shift the balance between {code g(n)} and {code h(n)}, you can modify either one. {h3 Speed or accuracy?} A*'s ability to vary its behavior based on the heuristic and cost functions can be very useful in a game. The tradeoff between speed and accuracy can be exploited to make your game faster. For most games, you don't {emph really} need the {strong best} path between two points. You just need something that's close. What you need may depend on what's going on in the game, or how fast the computer is. Suppose your game has two types of terrain, Flat and Mountain, and the movement costs are 1 for flat land and 3 for mountains, A* is going to search three times as far along flat land as it does along mountainous land. This is because it's {emph possible} that there is a path along flat terrain that goes around the mountains. You can speed up A*'s search by using 1.5 as the heuristic distance between two map spaces. A* will then compare 3 to 1.5, and it won't look as bad as comparing 3 to 1. It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up up A*'s search by decreasing the amount it searches for paths around mountains---just tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker. The choice between speed and accuracy does not have to be static. You can choose dynamically based on the CPU speed, the fraction of time going into pathfinding, the number of units on the map, the importance of the unit, the size of the group, the difficulty level, or any other factor. One way to make the tradeoff dynamic is to build a heuristic function that assumes the minimum cost to travel one grid space is 1 and then build a cost function that scales: {snippet {line g'(n) = 1 + alpha * (g(n) - 1)} } If {code alpha} is 0, then the modified cost function will always be 1. At this setting, terrain costs are completely ignored, and A* works at the level of simple passable/unpassable grid spaces. If {code alpha} is 1, then the original cost function will be used, and you get the full benefit of A*. You can set {code alpha} anywhere in between. You should also consider switching from the heuristic returning the {emph absolute} minimum cost to returnin the {emph expected} minimum cost. For example, if most of your map is grasslands with a movement cost of 2 but some spaces on the map are roads with a movement cost of 1, then you might consider having the heuristic assume no roads, and return 2 * distance. The choice between speed and accuracy does not have to be global. You can choose some things dynamically based on the importance of having accuracy in some region of the map. For example, it may be more important to choose a good path near the current location, on the assumption that we might end up recalculating the path or changing direction at some point, so why bother being accurate about the faraway part of the path? Or perhaps it's not so important to have the shortest path in a safe area of the map, but when sneaking past an enemy village, safety and quickness are essential. {h3 Scale} A* computes {code f(n) = g(n) + h(n)}. To add two values, those two values need to be at the same scale. If {code g(n)} is measured in hours and {code h(n)} is measured in meters, then A* is going to consider {code g} or {code h} too much or too little, and you either won't get as good paths or you A* will run slower than it could. {h3 Exact heuristics} If your heuristic is exactly equal to the distance along the optimal path, you'll see A* expand very few nodes, as in the diagram shown in {link {ref Manhattan distance} the next section}. What's happening inside A* is that it is computing {code f(n) = g(n) + h(n)} at every node. When {code h(n)} exactly matches {code g(n)}, the value of {code f(n)} doesn't change along the path. All nodes not on the right path will have a higher value of {code f} than nodes that are on the right path. Since A* doesn't consider higher-valued {code f} nodes until it has considered lower-valued {code f} nodes, it never strays off the shortest path. {h4 Precomputed exact heuristic} One way to construct an exact heuristic is to precompute the length of the shortest path between every pair of points. This is not feasible for most game maps. However, there are ways to approximate this heuristic: {list {hbox Fit a coarse grid on top of the fine grid. Precompute the shortest path between any pair of coarse grid locations.} {hbox Precompute the shortest path between any pair of {link {ref Waypoints} waypoints}. This is a generalization of the coarse grid approach.} } Then add in a heuristic {code h'} that estimates the cost of going from any location to nearby waypoints. (The latter too can be precomputed if desired.) The final heuristic will be: {snippet {line h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)} } or if you want a better but more expensive heuristic, evaluate the above with all pairs {code w1}, {code w2} that are close to the node and the goal, respectively. {h4 Linear exact heuristic} In a special circumstance, you can make the heuristic exact without precomputing anything. If you have a map with no obstacles and no slow terrain, then the shortest path from the starting point to the goal should be a straight line. If you're using a simple heuristic (one which does not know about the obstacles on the map), it should match the exact heuristic. If it doesn't, then you may have a problem with scale or the type of heuristic you chose. {h3 Heuristics for grid maps} On a grid, there are well-known heuristic functions to use. {h4 Manhattan distance} The standard heuristic is the Manhattan distance. Look at your cost function and find the minimum cost {code D} for moving from one space to an adjacent space. Therefore, the heuristic in my game should be {code D} times the Manhattan distance: {snippet {line h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))} } You should use the scale that matches your cost function. {figure {img 526 226 ../game-programming/a-star/manhattan.png}} (Note: the above image has a {link {ref Breaking ties} tie-breaker} added to the heuristic.} {h4 Diagonal distance} If on your map you allow diagonal movement you need a different heuristic. The Manhattan distance for (4 east, 4 north) will be 8*D. However, you could simply move (4 northeast) instead, so the heuristic should be 4*D. This function handles diagonals, assuming that both straight and diagonal movement costs D: {snippet {line h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))} } {figure {img 526 226 ../game-programming/a-star/diagonal.png}} If the cost of diagonal movement is not D, but something like D2 = sqrt(2)*D, the above heuristic won't be right for you. You will instead want something more sophisticated: {snippet {line h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))} {line h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))} {line h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))} } Here we compute {code h_diagonal(n) =} the number of steps you can take along a diagonal, {code h_straight(n) =} the Manhattan distance, and then combine the two by considering all diagonal steps to cost D2, and then all remaining straight steps (note that this is the number of straight steps in the Manhattan distance, minus two straight steps for each diagonal step we took instead) cost D. {h4 Euclidean distance} If your units can move at any angle (instead of grid directions), then you should probably use a straight line distance: {snippet {line h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)} } However, if this is the case, then you may have trouble with using A* directly because the cost function {code g} will not match the heuristic function {code h}. Since Euclidean distance is shorter than Manhattan or diagonal distance, you will still get shortest paths, but A* will take longer to run: {figure {img 526 226 ../game-programming/a-star/euclidean.png}} {h4 Euclidean distance, squared} I've seen several A* web pages recommend that you avoid the expensive square root in the Euclidean distance by just using distance-squared: {snippet {line h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)} } {strong Do not do this!} This definitely runs into the scale problem. When A* computes {code f(n) = g(n) + h(n)}, the square of distance will be much higher than the cost {code g} and you will end up with an overestimating heuristic. For longer distances, this will approach the extreme of {code g(n)} not really counting anymore, and A* will degrade into BFS: {figure {img 526 376 ../game-programming/a-star/best-first-search-trap.png}} {h4 Breaking ties} In some maps there are many paths with the same length. For example, in flat areas without variation in terrain, using a grid will lead to many equal-length paths. A* might explore all the paths with the same {code f} value, instead of just one. (If you do have lots of such areas, there might be other techniques that are better than using A* on a grid.) {figure {vbox {img 491 351 ../game-programming/a-star/tie-breaking-off.png} {hbox Ties in {code f} values.} } } To solve this problem, we need to either adjust the {code g} or {code h} values; it is usually easier to adjust {code h}. The tie breaker needs to be deterministic with respect to the vertex ({emph i.e.,} it shouldn't just be a random number), and it needs to make the {code f} values differ. Since A* sorts by {code f} value, making them different means only one of the "equivalent" {code f} values will be explored. One way to break ties is to nudge the scale of {code h} slightly. If we scale it downwards, then {code f} will increase as we move towards the goal. Unfortunately, this means that A* will prefer to expand vertices close to the starting point instead of vertices close to the goal. We can instead scale {code h} upwards slightly (even by 0.1%). A* will prefer to expand vertices close to the goal. {snippet {line heuristic *= (1.0 + p)} } The factor {code p} should be chosen so that {code p <} {emph (minimum cost of taking one step)} {code /} {emph (expected maximum path length)}. Assuming that you don't expect the paths to be more than 1000 steps long, you can choose p = 1/1000. The result of this tie-breaking nudge is that A* explores far less of the map than previously: {figure {vbox {img 491 351 ../game-programming/a-star/tie-breaking-scale-1.png} {hbox Tie-breaking scaling added to heuristic.} } } When there are obstacles of course it still has to explore to find a way around them, but note that after the obstacle is passed, A* explores very little: {figure {vbox {img 491 351 ../game-programming/a-star/tie-breaking-scale-2.png} {hbox Tie-breaking scaling added to heuristic, works nicely with obstacles.} } } Steven van Dijk suggests that a more straightforward way to do this would to pass {code h} to the comparison function. When the {code f} values are equal, the comparison function would break the tie by looking at {code h}. Another way to break ties is to compute a hash of the coordinates, and use that to adjust the heuristic. This breaks more ties than adjusting {code h} as above. Thanks to Cris Fuhrman for suggesting this. A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal: {snippet {line dx1 = current.x - goal.x} {line dy1 = current.y - goal.y} {line dx2 = start.x - goal.x} {line dy2 = start.y - goal.y} {line cross = abs(dx1*dy2 - dx2*dy1)} {line heuristic += cross*0.001} } This code computes the vector cross-product between the start to goal vector and the current point to goal vector. When these vectors don't line up, the cross product will be larger. The result is that this code will give some slight preference to a path that lies along the straight line path from the start to the goal. When there are no obstacles, A* not only explores less of the map, the path looks very nice as well: {figure {vbox {img 491 351 ../game-programming/a-star/tie-breaking-cross-1.png} {hbox Tie-breaking cross-product added to heuristic, produces pretty paths.} } } However, because this tie-breaker prefers paths along the straight line from the starting point to the goal, weird things happen when going around obstacles (note that the path is still optimal; it just looks strange): {figure {vbox {img 491 351 ../game-programming/a-star/tie-breaking-cross-2.png} {hbox Tie-breaking cross-product added to heuristic, less pretty with obstacles.} } } To interactively explore the improvement from this tie breaker, see {link http://www.ccg.leeds.ac.uk/james/aStar/ James Macgill's A* applet} [if that link does not work, try {link http://www.vision.ee.ethz.ch/~cvcourse/astar/AStar.html this mirror}]. Use "Clear" to clear the map, and choose two points on opposite corners of the map. When you use the "Classic A*" method, you will see the effect of ties. When you use the "Fudge" method, you will see the effect of the above cross product added to the heuristic. Yet another way to break ties is to carefully construct your A* priority queue so that {emph new} insertions with a specific {code f} value are always ranked better (lower) than {emph old} insertions with the same {code f} value. You may also want to read about the {link http://home1.stofanet.dk/breese/papers.html AlphA* algorithm}, which has a more sophisticated way to break ties, yet still maintain bounds on the optimality of the resulting path. AlphA* is adaptive and is likely to perform better than either of the two tie-breakers I described above. However, the tie-breakers I described are extremely easy to implement, so start with them first, and try AlphA* if you need something better. {h4 Searching for an area} If you want to search for any spot near some goal, instead of one particular space, you could construct a heuristic {code h'(x)} that is the minimum of {code h1(x), h2(x), h3(x), ...} where {code h1, h2, h3} are heuristics to each of the nearby spots. However, a faster way is to just let A* search for the center of the goal area. Once you pull {emph any} nearby space from the OPEN set, you can stop and construct a path. {h2 Implementation notes} {filename ImplementationNotes.html} {set meta-description "Notes on pathfinding implementations including performance issues."} {set shortname Implementation} {h3 Sketch} The A* algorithm, stripped of all the code, is fairly simple. There are two sets, OPEN and CLOSED. The OPEN set contains those nodes that are candidates for examining. Initially, the OPEN set contains just one element: the starting position. The CLOSED set contains those nodes that have already been examined. Initially, the CLOSED set is empty. Graphically, the OPEN set is the "frontier" and the CLOSED set is the "interior" of the visited areas. Each node also keeps a pointer to its parent node so that we can determine how it was found. There is a main loop that repeatedly pulls out the best node {code n} in OPEN (the node with the lowest {code f} value) and examines it. If {code n} is the goal, then we're done. Otherwise, node {code n} is removed from OPEN and added to CLOSED. Then, its neighbors {code n'} are examined. A neighbor that is in CLOSED has already been seen, so we don't need to look at it (*). A neighbor that is in OPEN is scheduled to be looked at, so we don't need to look at it now (*). Otherwise, we add it to OPEN, with its parent set to {code n}. The path cost to {code n'}, {code g(n')}, will be set to {code g(n) + movementcost(n, n')}. (*) I'm skipping a small detail here. You do need to check to see if the node's {code g} value can be lowered, and if so, you re-open it. {snippet {line "OPEN = priority queue containing START"} {line "CLOSED = empty set"} {line "while lowest rank in OPEN is not the GOAL:"} {line " current = remove lowest rank item from OPEN"} {line " add current to CLOSED"} {line " for neighbors of current:"} {line " cost = g(current) + movementcost(current, neighbor)"} {line " if neighbor in OPEN and cost less than g(neighbor):"} {line " remove neighbor from OPEN, because new path is better"} {line " if neighbor in CLOSED and cost less than g(neighbor): **"} {line " remove neighbor from CLOSED"} {line " if neighbor not in OPEN and neighbor not in CLOSED:"} {line " set g(neighbor) to cost"} {line " add neighbor to OPEN"} {line " set priority queue rank to g(neighbor) + h(neighbor)"} {line " set neighbor's parent to current"} {line } {line "reconstruct reverse path from goal to start"} {line "by following parent pointers"} } (**) This should never happen if you have an admissible heuristic. However in games we often have inadmissible heuristics. {h3 Source code} My own (old) C++ A* code is available: {link path.cpp "path.cpp"} and {link path.h "path.h"}, but it's not particularly easy to read. There is also an even older (slower, but easier to understand) version of my code, as well as many other implementations of A*, on {link http://www.gameai.com/ai.html Steve Woodcock's Games AI Page}. On the Internet, you can find C, C++, Visual Basic, Java {link http://www.cuspy.com/software/pathfinder/doc/ "[1]"} {link http://wiki.gamegardens.com/Path_Finding_Tutorial "[2]"}, {link http://www.robotacid.com/PBeta/AILibrary/Pathfinder/index.html Processing}, Flash {link http://www.antimodal.com/astar/ "[1]"} {link http://proto.layer51.com/d.aspx?f=998 "[2]"}, C# {link http://www.codeproject.com/cs/algorithms/csharppathfind.asp "[1]"} {link http://www.tanis.dk/Articles/CSharpPathfind/ "[2]"}, Delphi, Lisp, Python, Perl, and {link http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/5_1.html Prolog} implementations of A*. Be sure to look at {link http://www.geocities.com/jheyesjones/astar.html Justin Heyes-Jones's A* implementation in C++}. {h3 Set representation} What's the first thing you'll think of using for the OPEN and CLOSED sets? If you're like me, you probably thought "array". You may have thought "linked list", too. There are many different data structures we can use, but to pick one we should look at what operations are needed. There are three main operations we perform on the OPEN set: the main loop repeatedly finds the best node and removes it; the neighbor visiting will check whether a node is in the set; and the neighbor visiting will insert new nodes. Insertion and remove-best are operations typical of a {link http://members.xoom.com/killough/heaps.html priority queue}. The choice of data structure depends not only on the operations but on the number of times each operations runs. The membership test runs once for each neighbor for each node visited. Insertion runs once for each node being considered. Remove-best runs once for each node visited. Most nodes that are considered will be visited; the ones that are not are the {emph fringe} of the search space. When evaluating the cost of operations on these data structures, we need to consider the maximum size of the fringe (F). In addition, there's a fourth operation, which is relatively rare but still needs to be implemented. If the node being examined is already in the OPEN set (which does happen frequently), and if its {code f} value is better than the one already in the OPEN set (which is rare), then the value in the OPEN set must be adjusted. The adjustment operation involves removing the node (which is not the best {code f}) and re-inserting it. These two steps may be optimized into one that moves the node. {h4 Unsorted arrays or linked lists} The simplest data structure is an unsorted array or list. Membership test is slow, O(F) to scan the entire structure. Insertion is fast, O(1) to append to the end. Finding the best element is slow, O(F) to scan the entire structure. Removing the best element is O(F) for arrays and O(1) for linked lists. The adjust operation is O(F) to find the node and O(1) to change its value. {h4 Sorted arrays} To make remove-best fast, we can keep the array sorted. Membership is then O(log F), since we can use binary search. Insertion is slow, O(F) to move all the elements to make space for the new one. Finding the best is fast, O(1) since it's already at the end. And removing the best is O(1) if we make sure the best sorts to the {emph end} of the array. The adjust operation is O(log F) to find the node and O(F) to change its value/position. {h4 Sorted linked lists} With sorted arrays, insertion was slow. If we use a linked list, we can make that fast. Membership in the linked list is slow, O(F) to scan the list. Insertion is fast, O(1) to insert a new link, but it was O(F) to find the right position for it. Finding the best remains fast, O(1) because the best is at the end. Removing the best also is O(1). The adjust operation is O(F) to find the node and O(1) to change its value/position. {h4 Sorted skip lists} Searching an unsorted linked list is slow. We can make that faster if we use a {link http://en.wikipedia.org/wiki/Skip_list skip list} instead of a linked list. With a skip list, membership is fast if you have the sort key: O(log F). Insertion is O(1) like a linked list if you know where to insert. Finding the best node is fast if the sort key is {code f}, O(1), and removing a node is O(1). The adjust operation involves finding a node, removing it, and reinserting it. If we use skip lists with the map location as the key, membership is O(log F), insertion is O(1) after we've performed the membership test, finding the best node is O(F), and removing a node is O(1). This is better than unsorted linked lists in that membership is faster. If we use skip lists with the {code f} value as the key, membership is O(F), insertion is O(1), finding the best node is O(1), and removing a node is O(1). This is no better than sorted linked lists. {h4 Indexed arrays} If the set of nodes is finite and reasonably sized, we can use a direct indexing structure, where an index function {code i(n)} maps each node {code n} to an index into an array. Unlike the unsorted and sorted arrays, which have a size corresponding to the largest size of OPEN, with an indexed array the array size is always {code max(i(n))} over all {code n}. If your function is dense ({emph i.e.,} there are no indices unused), then {code max(i(n))} will be the number of nodes in your graph. Whenever your map is a grid, it's easy to make the function dense. Assuming {code i(n)} is O(1), membership test is O(1), as we merely have to check whether {code "Array[i(n)]"} contains any data. Insertion is O(1), as we just ste {code "Array[i(n)]"}. Find and remove best is O(numnodes), since we have to search the entire structure. The adjust operation is O(1). {h4 Hash tables} Indexed arrays take up a lot of memory to store all the nodes that are {emph not} in the OPEN set. An alternative is to use a hash table, with a hash function {code h(n)} that maps each node {code n} into a hash code. Keep the hash table twice as big as N to keep the chance of collisions low. Assuming {code h(n)} is O(1), membership test is expected O(1), insertion is expected O(1), and remove best is O(numnodes), since we have to search the entire structure. The adjust operation is O(1). {h4 Binary heaps} A binary heap (not to be confused with a memory heap) is a tree structure that is stored in an array. Unlike most trees, which use pointers to refer to children, the binary heap uses indexing to find children. C++ STL includes an efficient implementation of heaps, which I use in my own A* code. In a binary heap, membership is O(F), as you have to scan the entire structure. Insertion is O(log F) and remove-best is O(log F). The adjust operation is tricky, with O(F) to find the node and suprisingly, only O(log F) to adjust it. A friend of mine (who does research in data structures for shortest-path algorithms) says that binary heaps are good unless you have more than 10,000 elements in your fringe set. Unless your game's map is extremely large, you probably don't need a more complicated data structure (like {link http://www-cs-students.stanford.edu/~csilvers/ multi-level buckets}). You should probably {link http://www.star-lab.com/goldberg/pub/neci-tr-96-062.ps stay away from Fibonacci heaps}, which have good asymptotic performance but have slow implementations unless F is huge. {h4 Splay trees} Heaps are a tree-based structure with expected O(log F) time operations. However, the problem is that with A*, the common behavior is that you have a low cost node that is removed (causing O(log F) behavior, since values have to move up from the very bottom of the tree) followed by low cost nodes that are added (causing O(log F) behavior, since these values are added at the bottom and bubble up to the very top). The {emph expected case} behavior of heaps here is equivalent to the {emph worst case} behavior. We may be able to do better if we find a data structure where {emph expected case} is better, even if the {emph worst case} is no better. Splay trees are a self adjusting tree structure. Any access to a node in the tree tends to bring that node up to the top. The result is a "caching" effect, where rarely used nodes go to the bottom and don't slow down operations. It doesn't matter how big your splay tree is, because your operations are only as slow as your "cache size". In A*, the low cost nodes are used a lot, and the high cost nodes aren't used for a long time, so those high cost nodes can move to the bottom of the tree. With splay trees, membership, insertion, remove-best, and adjustment are all expected O(log F), worst case O(F). Typically however, the caching keeps the worst case from occurring. Dijkstra's algorithm and A* with an underestimating heuristic however have some peculiar characteristics that may keep splay trees from being the best. In particular, {code f(n') >= f(n)} for nodes {code n} and neighboring node {code n'}. When this happens, it may be that the insertions all occur on one side of the tree and end up putting it out of balance. I have not tested this. {h4 HOT queues} There's another good data structure that may be better than heaps. Often, you can restrict the range of values that would be in the priority queue. Given a restricted range, there are often better algorithms. For example, sorting can be done on arbitrary values in O(N log N) time, but when there is a fixed range the bucket or radix sorts can perform sorting in O(N) time. We can use {link http://www.star-lab.com/goldberg/pub/neci-tr-97-104.ps HOT Queues} (Heap On Top queues) to take advantage of {code f(n') >= f(n)} where {code n'} is a neighbor of {code n}. We are removing the node {code n} with minimal {code f(n)}, and inserting neighbors {code n'} with {code f(n) <= f(n') <= f(n) + delta} where {code delta <= C}. The constant {code C} is the {emph maximum} change in cost from one point to an adjacent point. Since {code f(n)} was the minimal {code f} value in the OPEN set, and everything being inserted is {code <= f(n) + delta}, we know that all {code f} values in the OPEN set are within a range of {code 0 .. delta}. As in bucket/radix sort, we can keep "buckets" to sort the nodes in the OPEN set. With K buckets, we reduce any O(N) cost to an average of O(N/K). With HOT queues, the topmost bucket uses a binary heap and all other buckets are unsorted arrays. Thus, its membership test for the top bucket is expected O(F/K), and insertion and remove-best are O(log (F/K)). Membership for the other buckets is O(F/K), insertion is O(1), and remove-best never occurs!. If the top bucket empties, then we need to convert the next bucket, an unsorted array, into a binary heap. It turns out this operation ("heapify") can be run in O(F/K) time. The adjust operation is best treated as a O(F/K) removal followed by an O(log (F/K)) or O(1) insertion. In A*, many of the nodes we put into OPEN we never actually need. HOT Queues are a big win because the elements that are not needed are inserted in O(1) time. Only elements that are needed get heapified (which is not too expensive). The only operation that is more than O(1) is node deletion from the heap, which is only O(log (F/K)). In addition, if {code C} is small, we can just set K = C, and then we do not even need a heap for the smallest bucket, since all the nodes in a bucket have the same {code f} value. Insertion and remove-best are both O(1) time! One person reported that HOT queues are as fast as heaps for at most 800 nodes in the OPEN set, and are 20% faster when there are at most 1500 nodes. I would expect that HOT queues get faster as the number of nodes increases. A cheap variant of a HOT queue is a two-level queue: put good nodes into one data structure (a heap or an array) and put bad nodes into another data structure (an array or a linked list). Since most nodes put into OPEN are "bad", they are never examined, and there's no harm putting them into the big array. {h4 Comparison} It is important to keep in mind that we are not merely looking for asymptotic ("big O") behavior. We also want to look for a low constant. To see why, consider an algorithm that is O(log F) and another that is O(F), where F is the number of elements in the heap. It may be that on your machine, an implementation of the first algorithm takes 10,000 * log(F) seconds, while an implementation of the second one takes 2 * F seconds. For F = 256, the first would take 80,000 seconds and the second would take 512 seconds. The "faster" algorithm takes more time in this case, and would only start to be faster when F > 200,000. {emph You cannot merely compare two algorithms.} You should also compare the implementations of those algorithms. You also have to know what size your data might be. In the above example, the first implementation is faster for F > 200,000, but if in your game, F stays under 30,000, then the second implementation would have been better. None of the basic data structures is entirely satisfactory. Unsorted arrays or lists make insertion very cheap and membership and removal very expensive. Sorted arrays or lists make membership somewhat cheap, removal very cheap and insertion very expensive. Binary heaps make insertion and removal somewhat cheap, but membership is very expensive. Splay trees make everything somewhat cheap. HOT queues make insertions cheap, removals fairly cheap, and membership tests somewhat cheap. Indexed arrays make membership and insertion very cheap, but removals are incredibly expensive, and they can also take up a lot of memory. Hash tables perform similarly to indexed arrays, but they can take up a lot less memory in the common case, and removals are merely expensive instead of extremely expensive. For a good list of pointers to more advanced priority queue papers and implementations, see {link http://www.leekillough.com/heaps/ Lee Killough's Priority Queues page}. {h4 Hybrid representations} To get the best performance, you will want a hybrid data structure. For my A* code, I used an indexed array for O(1) membership test and a binary heap for O(log F) insertion and O(log F) remove-best. For adjustments, I used the indexed array for an O(1) test whether I really needed to perform the adjustment (by storing the {code g} value in the indexed array), and then in those rare cases that I did need an adjustment, I used the O(F) adjustment on the binary heap. You can also use the indexed array to store the location in the heap of each node; this would give you O(log F) for adjustment. {h3 Interaction with the game loop} Interactive (especially real-time) games introduce requirements that affect your ability to compute the best path. It may be more important to get {emph any} answer than to get the {emph best} answer. Still, all other things being equal, a shorter path is better than a longer one. In general, computing the part of the path close to the starting point is more important than the path close to the goal. The principle of {emph immediate start}: get the unit moving as soon as possible, even along a suboptimal path, and then {link {ref Recalculating paths} compute a better path later}. In real-time games, the {emph latency} of A* is often more important than its {emph throughput}. Units can be programmed to follow either their instincts (simple movement) or their brains (a precalculated path). Units will follow their instincts unless their brains tell them otherwise. (This approach is used in nature and also in Rodney Brook's robot architecture.) Instead of calculating all the paths at once, limit the game to finding one path every one, two, or three game cycles. Then let the units start walking according to instinct (which could simply be moving in a straight line towards the goal), and come back later to find paths for them. This approach allows you to even out the cost of pathfinding so that it doesn't occur all at once. {h4 Early exit} It is possible to exit early from the A* main loop and get a partial path. Normally, the loop exits when it finds the goal node. However, at any point before that, it can return a path to the currently best node in OPEN. That node is our best chance of getting to the goal, so it's a reasonable place to go. Candidates for early exit include having examined some number of nodes, having spent some number of milliseconds in the A* algorithm, or exploring a node some distance away from the starting position. When using path splicing, the spliced path should be given a smaller limit than a full path. {h4 Interruptible algorithm} If few objects need pathfinding services or if the data structures used to store the OPEN and CLOSED sets are small, it can be feasible to store the state of the algorithm, exit to the game loop, then continue where A* left off. {h4 Group movement} Path requests do not arrive evenly distributed. A common situation in a real-time strategy game is for the player to select multiple units and order them to move to the same goal. This puts a high load on the pathfinding system. {margin-note {strong See Also:} Putting paths together is called {link {ref Path splicing} path splicing} in another section of these notes. } In this situation, it is very likely that the path found for one will be useful for other units. One idea is to find a path {code P} from the center of the units to the center of the destinations. Then, use most of that path for all the units, but replace the first 10 steps and the last 10 steps by paths that are found for each individual unit. Unit {emph i} will receive a path from its starting location to {code "P[10]"}, followed by the shared path {code "P[10..len(P)-10]"}, followed by a path from {code "P[len(P)-10]"} to the destination. The paths found for each unit are short (approximately 10 steps on average), and the long path is shared. Most of the path is found only once and shared among all the units. However, the user may not be impressed if he sees all the units moving on the same path. To improve the appearance of the system, make the units follow slightly different paths. One way to do this is to alter the paths themselves, by choosing adjacent locations. Another approach is to make the units aware of each other (perhaps by picking a "leader" unit randomly, or by picking the one with the best sense of what's going on), and only find a path for the leader. Then use a {link http://www.red.com/cwr/boids.html flocking algorithm} to make them move in a group. Yet another approach is to take advantage of A*'s intermediate state. This state can be shared among multiple units traveling to the same goal, as long as those units share the same heuristic and cost functions. When the main loop exits, do not erase the OPEN and CLOSED sets; instead, start the next loop (with the starting position of the next unit) with the OPEN and CLOSED sets from the previous invocation of A*. (This can be considered a generalization of the Interruptible Algorithm and the Early Exit sections.) {h4 Refinement} If the map contains few obstacles, but instead contains terrain of varying costs, then an initial path can be computed by treating terrain as being cheaper than normal. For instance, if grasslands are cost 1, hills are cost 2, and mountains are cost 3, then A* will consider walking through 3 grasslands to avoid 1 mountain. Instead, compute an initial path by treating grasslands as 1, hills as 1.1, and mountains as 1.2. A* will then spend less time trying to avoid the mountains, and it will find a path quicker. (It approximates the benefits of an {link {ref Linear exact heuristic} exact heuristic}.) Once a path is known, the unit can start moving, and the game loop can continue. When spare CPU is available, compute a better path using the real movement costs. {h2 Variations of A*} {filename Variations.html} {set meta-description "Variations of A*."} {set shortname Variations} {h3 Beam search} In the main A* loop, the OPEN set stores all the nodes that may need to be searched to find a path. The {strong Beam Search} is a variation of A* that places a limit on the size of the OPEN set. If the set becomes too large, the node with the worst chances of giving a good path is dropped. One drawback is that you have to keep your set sorted to do this, which limits the kinds of data structures you'd choose. {h3 Iterative deepening} Iterative Deepening is an approach used in many AI algorithms to start with an approximate answer, then make it more accurate. The name comes from game tree searches, where you look some number of moves ahead (for example, in Chess). You can try to deepen the tree by looking ahead more moves. Once your answer doesn't change or improve much, you assume that you have a pretty good answer, and it won't improve when you try to make it more accurate again. In ID-A*, the "depth" is a cutoff for {code f} values. When the {code f} value is too large, the node won't even be considered ({emph i.e.,} it won't be added to the OPEN set). The first time through you process very few nodes. Each subsequent pass, you increase the number of nodes you visit. If you find that the path improves, then you continue to increase the cutoff; otherwise, you can stop. For more details, read {link http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html these lecture nodes on ID-A*}. I personally don't see much need for ID-A* for finding paths on game maps. ID algorithms tend to increase computation time while reducing memory requirements. In map pathfinding, however, the "nodes" are very small---they are simply coordinates. I don't see a big win from not storing those nodes. {h3 Dynamic weighting} With dynamic weighting, you assume that at the beginning of your search, it's more important to get (anywhere) quickly; at the end of the search, it's more important to get to the goal. {snippet {line "f(p) = g(p) + w(p) * h(p)"} } There is a weight ({code w >= 1}) associated with the heuristic. As you get closer to the goal, you decrease the weight; this decreases the importance of the heuristic, and increases the relative importance of the actual cost of the path. {h3 Bandwidth search} There are two properties about {emph Bandwidth Search} that some people may find useful. This variation assumes that {code h} is an {emph overestimate}, but that it doesn't overestimate by more than some number {code e}. If this is the case in your search, then the path you get will have a cost that doesn't exceed the best path's cost by more than {code e}. Once again, the better you make your heuristic, the better your solution will be. Another property you get is that if you can drop some nodes in the OPEN set. Whenever {code h+d} is greater then the true cost of the path (for some {code d}), you can drop any node that has an {code f} value that's at least {code e+d} higher than the {code f} value of the best node in OPEN. This is a strange property. You have a "band" of good values for {code f}; everything outside this band can be dropped, because there is a guarantee that it will not be on the best path. Curiously, you can use different heuristics for the two properties, and things still work out. You can use one heuristic to guarantee that your path isn't too bad, and another one to determine what to drop in the OPEN set. {h3 Bidirectional search} Instead of searching from the start to the finish, you can start two searches in parallel---one from start to finish, and one from finish to start. When they meet, you should have a good path. This sounds like a good idea, but I don't think it'll give you very much. The idea behind bidirectional searches is that searching results in a `tree' that fans out over the map. A big tree is much worse than two small trees, so it's better to have two small search trees. With A*, however, my experiments suggest that you {emph don't} get a tree. You get a path that has nearby map areas explored, but it doesn't fan out like Dijkstra's algorithm. In fact, that's what makes A* so fast---no matter how long your path is, it doesn't search like crazy, unless the path really is crazy. It tends to search only small areas of the map. Bidirectional search may be more useful if your map is complex. The {emph front-to-front} variation links the two searches together. Instead of choosing the best forward-search node---{code g(start,x) + h(x,goal)}---or the best backward-search node---{code g(y,goal) + h(start,y)}---this algorithm chooses a pair of nodes with the best {code g(start,x) + h(x,y) + g(y,goal)}. The {emph retargeting} approach abandons simultaneous searches in the forward and backward directions. Instead, it performs a forward search for a short time, chooses the best forward candidate, and then performs a backward search---not to the starting point, but to that candidate. After a while, it chooses a best backward candidate and performs a forward search from the best forward candidate to the best backward candidate. This process continues until the two candidates are the same point. {h3 Dynamic A* and Lifelong Planning A*} There are variants of A* that allow for changes to the world after the initial path is computed. D* is intended for use when you don't have complete information. If you don't have all the information, A* can make mistakes; D*'s contribution is that it can correct those mistakes without taking much time. LPA* is intended for use when the costs are changing. With A*, the path may be invalidated by changes to the map; LPA* can re-use previous A* computations to produce a new path. {emph However}, both D* and LPA* require a lot of space---essentially you run A* and keep around its internal information ({code OPEN/CLOSED} sets, path tree, {code g} values), and then when the map changes, D* or LPA* will tell you if you need to adjust your path to take into account the map changes. For a game with lots of moving units, you usually don't want to keep all that information around, so D* and LPA* aren't applicable. They were designed for robotics, where there is just one robot---you don't need to reuse the memory for some other robot's path. If your game has only one or a small number of units, you may want to investigate D* or LPA*. {list {link http://www.frc.ri.cmu.edu/~axs/dynamic_plan.html Overview of D*} {link http://www.frc.ri.cmu.edu/~axs/doc/icra94.ps D* Paper 1} {link http://www.frc.ri.cmu.edu/~axs/doc/ijcai95.ps D* Paper 2} {link http://idm-lab.org/project-a.html Lifelong planning overview} {link http://csci.mrs.umn.edu/UMMCSciWiki/pub/CSci3903s03/KellysPaper/seminar.pdf Lifelong planning paper (PDF)} {link http://idm-lab.org/applet.html Lifelong planning A* applet} } {h2 Dealing with moving obstacles} {filename MovingObstacles.html} {set meta-description "Pathfinding and how to avoid moving obstacles such as enemy units."} {set shortname Moving Obstacles} A pathfinding algorithm will compute a path around stationary obstacles, but what if the obstacles move? By the time a unit reaches a particular point, an obstacle may no longer be there, or a new obstacle may be there. One way to deal with this problem is to abandon pathfinding and instead use movement algorithms that do not look far ahead; this approach will be discussed in a later section. This section will cover modifications to the path finding approach that could be used to handle moving obstacles. {h3 Recalculating paths} As time passes we expect the game world to change. A path found some time ago may no longer be the optimal path. It may be worth updating old paths with new information. Listed below are some criteria that could be used for determining when a recalculation is needed: {list {hbox Every {emph N} steps: this guarantees that the information used to calculate the path is not more than {emph N} steps old.} {hbox Whenever extra CPU time is available: this allows dynamic adjustment of path quality; as more units are deployed, or if the game is running on a slower computer, CPU usage per unit can be decreased.} {hbox Whenever the unit turns a corner or passes a waypoint.} {hbox Whenever the world near the unit has changed.} } The main drawback of path recalculation is that a lot of path information is thrown away. For example, if the path is 100 steps long and it is recalculated every 10 steps, the total number of path steps is 100+90+80+70+60+50+40+30+20+10 = 550. For a path of {emph M} steps, approximately {emph M}^{super 2} path steps are computed over time. Therefore path recalculation is not a good idea if you expect to have many long paths. It would be better to reuse the path information instead of throwing it away. {h3 Path splicing} When a path needs to be recalculated, it means the world is changing. Given a changing world, nearby parts of the map are better known than faraway parts of the map. Thus, we should concentrate on finding a good path nearby and assume that the path farther away need not be recomputed until we get closer to it. Instead of recalculating the entire path, we can recalculate the first {emph M} steps of the path: {enumerate {hbox Let {code "p[1]..p[N]"} be the remainder of the path ({emph N} steps)} {hbox Compute a new path from {code "p[1]"} to {code "p[M]"}} {hbox {emph Splice} this new path into the old path by removing {code "p[1]..p[M]"} and inserting the new path in its place} } {figure {img 400 300 "mtn_path.png"}} Since {code "p[1]"} and {code "p[M]"} are fewer than {emph M} steps apart, it's unlikely that the new path will be long. Unfortunately, situations can arise in which the new path is long and not very good. The accompanying figure shows such a situation. The original red path is 1-2-3-4; brown areas are obstacles. If we reach 2 and discover that the path from 2 to 3 has been blocked, path splicing would replace 2-3 with the green path 2-3-5 and splice it in, resulting in the unit moving along path 1-2-5-3-4. We can see this is not a good path; the blue path 1-2-5-4 would be better. Bad paths can often be detected by looking at the length of the new path. If it is significantly longer than {emph M}, it could be bad. A simple solution is to add a limit (maximum path length) to the path finding algorithm. If a short path isn't found, the algorithm returns an error code; in this case, use path recalculation instead of path splicing to get a path such as 1-2-5-4. {margin-note {vbox {strong Implementation Note:} {hbox Store the path in {emph reverse} order: it is easy to remove the beginning of the path and splice in a new path with a different length; because both operations occur at the {emph end} of the array. Essentially you treat the array as a {emph stack} where the top element is the next move to make.} } } For cases not involving these situations, for a path with {emph N} steps, path splicing will compute {emph 2N} to {emph 3N} path steps, depending on how often a new path is spliced in. This is a fairly low cost for the ability to respond to changes in the world. Surprisingly, the cost is independent of {emph M}, the number of steps for splicing. Instead of affecting CPU time, {emph M} controls a tradeoff between responsiveness and path quality. If {emph M} is high, the unit's movement will not respond quickly to changes in the map. If {emph M} is too low, the paths being spliced out may be too short to allow the replacement path to go around the obstacle cleanly; more suboptimal paths (such as 1-2-5-3-4) will be found. Try different values of {emph M} and different criteria for splicing (such as every 3/4 {emph M} steps) to see what's right for your map. Path splicing is significantly faster than path recalculation, but it does not respond well to major changes in the path. It is possible to detect many of these situations and use path recalculation instead. It also has a few variables that can be adjusted, such as {emph M} and the choice of when to find a new path, so it can be adjusted (even at run-time) for different conditions. Note: Bryan Stout has two algorithms, Patch-One and Patch-All, inspired by path splicing but working much better in practice. He presented these at {link https://www.cmpevents.com/GD07/a.asp?option=C&V=11&SessID=4608 GDC 2007}; I'll link to them once he puts the notes online. {h3 Watching for map changes} An alternative to recalculating all or part of the path at certain intervals is to have changes to the map trigger a recalculation. The map can be divided into regions, and every unit can express an interest in certain regions. (All the regions that contain part of the path could be of interest, or only nearby regions that contain part of the path.) Whenever an obstacle enters or leaves a region, that region is marked {emph changed}, and all units that have an interest in that region are notified, so that paths can be recalculated to take into account the change in obstacles. Many variations of this technique are possible. For example, instead of immediately notifying the units, only notify them at regular intervals. Many changes can be grouped into one notification, so that excessive path recalculations are not needed. Another example is for the unit to poll the regions instead of the regions notifying the unit. Watching for map changes allows units to avoid recalculation whenever the obstacles on the map do not change, so consider it if you have many regions that do not change often. {h3 Predicting obstacle movement} If obstacle movement can be predicted, it is possible to take into account future position of obstacles for pathfinding. An algorithm such as A* has a cost function that determines how difficult it is to pass a point on the map. A* can be modified to keep track of the time required to reach a point (determined by current path length), and this time can be passed in to the cost function. The cost function can then take time into account, and use the predicted obstacle position at that time to determine whether the map space is impassable. This modification is not perfect, however, as it will not take into account the possibility of waiting at a point for the obstacle to move out of the way, and A* is not designed to differentiate between paths along the same route, but at different points in time. {h2 Space used by precalculated paths} {filename SpaceUsage.html} {set shortname Space} Sometimes, it's not the time needed to calculate a path, but the space used by paths for hundreds of units that is the limiting factor. Pathfinders require space for the algorithm to run, plus space to store a path. The temporary space required for the algorithm to run (with A*, the OPEN and CLOSED sets) typicaly is larger than the space required to store the resulting path. By restricting your game to compute only one path at a time, you can minimize the amount of temporary space needed. In addition, the {link {ref Set representation} choice of data structure} for your OPEN and CLOSED sets can make a big difference for minimizing temporary space. This section will instead focus on minimizing the space used by the resulting paths. {h3 Locations vs. directions} A path can be either locations or directions. Locations take more space, but have the advantage that it is easy to determine an arbitrary location or direction in the path without traversing the path. When storing directions, only the direction can be determined easily; the location can only be determined by going through the entire path, following the directions. In a typical grid map, locations may be stored with two 16-bit integers, making each step take 32 bits. There are far fewer directions, however, so they can take less space. If the unit can move in only four directions, each step takes only 2 bits; if the unit can move in six or eight directions, each step takes 3 bits. Either of these is a significant savings over storing locations in the path. Hannu Kankaanpaa suggests that you can further reduce the space requirement by storing the {emph relative} direction ("turn right 60 degrees") instead of the absolute direction ("go north"). Some relative directions may not make sense for some types of units. For example, if your unit is moving north, it's unlikely that the next step is to go south. In a six directional game, you have only five meaningful directions. On some maps, perhaps only three of those directions (straight, left 60 degrees, right 60 degrees) make sense, but on other maps, turning right 120 degrees may be a valid move (for example, when going up a steep mountain path with switchbacks). {h3 Path compression} Once a path can be found, it can be compressed in some way. A general purpose compression algorithm could be used, but will not be discussed here. A compression algorithm specific to paths could be used to shorten either location-based paths or direction-based paths. Before deciding, look at typical paths in your game to decide which kind of compression will work best. In addition, consider ease of implementation (and debugging), the size of the code, and whether it really matters. If you have a limit of 300 units and only 50 are walking at any one time, and paths are short (100 steps), the total memory requirement might only be <50k anyway, and not worth worrying about compression. {h4 Location storage} In maps where obstacles rather than terrain are the main influence in determining paths, there may be many straight-line segments in the path. If this is the case, then a path need contain only the endpoints (sometimes called {emph waypoints}) of those line segments. Movement consists of examining the next point on the path and moving in a straight line towards it. {h4 Direction storage} When directions are stored, it may be the case that a particular direction is followed many times in a row. You can take advantage of that common pattern to store the path in less space. One way to store the path is to store both a direction and a number which indicates how many times the unit should move in that direction. Unlike the optimization for location storage, this optimization can make things worse if a direction is not taken many times in a row. Also, for many straight lines where location compression is useful, direction compression is not, since the line may not be aligned with one of the walking directions. With relative directions, you can eliminate "keep going forward" as a possible direction. Hannu Kankaanpaa points out that with an eight direction map, you can eliminate forwards, backwards, and the 135 degree left and right turns (assuming your map allows it), and you can then store each direction with only two bits. Another way to store the path is to use variable length encoding. The idea is to use a single bit (0) for the most common step: go straight. Use a 1 to mark a turn, and follow the 1 by some number of bits to represent the turn. In a four directional map, you can turn only left or right, so you might use 10 for left and 11 for right. Variable length encoding is more general and may compress better than run length encoding for mixed paths, but not as well for long straight paths. The sequence (north, straight six steps, turn left, straight three steps, turn right, straight five steps, turn left, straight two steps) is represented as [(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)] with run length encoding. If each direction is two bits and each distance is eight bits, this path requires 40 bits to store. With variable length encoding, you use one bit for each step and two bits for each turn---[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]---a total of 24 bits. If the initial direction and each turn imply one step, you can save one bit per turn, resulting in 20 bits to store the path. However, longer paths can take more space with variable length encoding. The sequence (north, straight two hundred steps) is [(NORTH, 200)] with run length encoding, a total of 10 bits. The same sequence with variable length encoding is [NORTH 0 0 ...], a total of 202 bits. {h3 Computed waypoints} A {emph waypoint} is a point along a path. Instead of storing every step along the way, after pathfinding a post-processing step can collapse multiple steps into a single waypoint, usually at places where the path changes direction or at major locations like cities. The movement algorithm will then follow a path between waypoints. {h3 Limited path length} Given that map conditions or orders may change, it may not make sense to store a long path, since at some point the remainder of the path may not be of any use. Each unit can store a fixed number of steps at the beginning of the path, and then use path recalculation when the path has almost been traversed. This approach allows for control of the amount of data used per unit. {h3 Summary} Paths can potentially take up a lot of space in a game, especially when the paths are long and there are many units present. Path compression, waypoints, and beacons reduce the space requirements by storing many steps in a small amount of data. Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map. If paths still take up too much space, the path length can be limited, resulting in the classic time-space tradeoff: to save space, information can be forgotten and recalculated later. {h1 Other topics} There are many other topics related to pathfinding. {h2 Map representations} {filename MapRepresentations.html} Through most of this document I've assumed that A* was being used on a grid of some sort, where the "nodes" given to A* were grid locations and the "edges" were directions you could travel from a grid location. However, A* was designed to work with arbitrary graphs, not only grids. There are a variety of map representations that can be used with A*. {h3 Grid} A grid map uses a uniform subdivision of the world into small regular shapes called "tiles". Common grids in use are {link http://www-cs-students.stanford.edu/~amitp/game-programming/grids/ square, triangular, and hexagonal}. Grids are simple and easy to understand; thus, I have focused on them in this document. {h3 Polygonal maps} One form of graph that you may want to use if your game does not have terrain, and has polygonal obstacles, is based on "navigation points". {figure {img 400 300 polygon_graph.png}} In this diagram, I've marked the corners of every obstacle with a blue dot. In addition, the start and end points are blue dots. These navigation points are the nodes to feed to A*. In addition, A* needs to know which points are connected. To determine this, look at each pair and decide whether the straight line between the two points is unobstructed. In this diagram, these edges are the light blue lines. The third piece of information A* needs is distances between the points. Depending on how your units move, that can be {link {ref Manhattan distance} manhattan distance}, {link {ref Diagonal distance} diagonal grid distance}, or {link {ref Euclidean distance} straight line distance}. A* will then consider paths from navigation point to navigation point. The dotted green line is one such path. This is {emph much} faster than looking for paths from grid point to grid point, as you have only {code 2 + 4*(#obstacles)} navigation points, instead of {code xsize * ysize} grid locations. When there are no obstacles in the way, A* will do very well---the start point and end point will be connected by an edge, and A* will find that path immediately, without expanding any other navigation points. Even when there are obstacles to consider, A* will jump from corner to corner until it finds the best path, which will still be much faster than looking for a path from a grid location to another. You can read more about generating the links between vertices {link http://www.gamedev.net/community/forums/topic.asp?topic_id=459298 on this forum post}. {h3 Flat} A flat map has but one level in its representation. It's rare for games to have only one level---often there is a "tile" level and then a "sub-tile" level in which objects can move within a tile. However, it's common for {emph pathfinding} to occur on only the larger level. {h3 Hierarchical} Pathfinding algorithms tend to be worse than {emph linear}: if you double the distance needed to travel, it takes {emph more} than twice as long to find the path. You can think of pathfinding as searching some area like a circle---when the circle's diameter doubles, it has {emph four} times the area. One way to reduce the problem is to have multiple levels of searching. For example, to get from your home to a location in another city, you would find a path from your chair to your car, from the car to the street, from the street to a freeway, from the freeway to the edge of the city, from there to the other city, then to a street, to a parking lot, and finally to the door of the destination building. There are several levels of searching here: {list {hbox At the {emph street} level, you are concerned with walking from one location to a nearby location, but you do not go out on the street.} {hbox At the {emph city} level, you go from one street to another until you find the freeway. You do not worry about going into buildings or parking lots, nor do you worry about going on freeways.} {hbox At the {emph state} level, you go from one city to another on the freeway. You do not worry about streets within cities until you get to your destination city.} } Dividing the problem into levels allows you to ignore most of your choices. When moving from city to city, it is quite tedious to consider every street in every city along the way. Instead, you ignore them all, and only consider freeways. The problem becomes small and manageable, and solving it becomes fast. A hierarchical map has many levels in its representation. A heterogenous hierarchy typically has a fixed number of levels, each with different characteristics. Ultima V, for example, has a "world" map, on which are cities and dungeons. You can enter a city or dungeon and be in a second map level. In addition, there are "layers" of worlds on top of one another, making for a three-level hierarchy. A homogeneous hierarchy has an arbitrary number of levels, each with the same characteristics. Quad trees and oct trees can be considered to be homogeneous hierarchies. In a hierarchical map, pathfinding may occur on several levels. For example, if a 1024x1024 world was divided into 64x64 "zones", it may be reasonable to find a path from the player's location to the edge of the zone, then from zone to zone until reaching the desired zone, then from the edge of that zone to the desired location. At the coarser levels, long paths can be found more easily because the pathfinder does not consider all of the details. When the player actually walks across each zone, the pathfinder can be invoked again to find a short path through that zone. By keeping the problem size small, the pathfinder can run quicker. You can use multiple levels with graph-searching algorithms such as A*. One paper on this topic is {link http://www.csi.uottawa.ca/~holte/Publications/tr-95-18.ps Hierarchical A*: Searching Abstraction Hierarchies Efficiently}. You do not need to use the same algorithm at each level. A similar approach is to use varying resolution. First, plot a path with low resolution. As you get closer to a point, refine the path with a higher resolution. This approach can be used with {link {ref Path splicing} path splicing} to avoid moving obstacles. {h3 Wraparound maps} If your world is spherical or toroidal, then objects can "wrap" around from one end of the map to the other. In such a world, it's not clear how to give A* the information it needs. The shortest path could lie in any direction, so all directions must be explored. One approach is to restrict your world so that all paths will not wrap around more than once. With this restriction, you can treat the map as being adjacent to copies of itself. With a square map, create four neighboring copies adjacent to the original and perform pathfinding on this new map. Put the goal in the center (original) map and put a copy of the starting position on the original and each of the four copies. Then create a synthetic starting node that has an edge leading to each of the five starting positions with zero cost and find a path from the synthetic starting node to the goal. {h3 Road maps} If your units can only move on roads, you may want to consider giving A* the road and intersection information. Each intersection will be a node in the graph, and each road will be an edge. A* will find paths from intersection to intersection, which is typically much faster than exploring all possible directions, one grid space at a time. To save time, build the node/edge graph ahead of time instead of when you run A*. For some applications, your units may not start and end on intersections. To handle this case, each time you run A*, you will need to modify the node/edge graph. Add the starting and ending points as new nodes, and add edges between these points and their nearest intersections. After pathfinding, remove these extra nodes and edges from the graph so that the graph is ready to be used for the next invocation of A*. {figure {img 400 300 road_graph.png}} In this diagram, the intersections are blue circles. In addition, the start and end points are blue circles. These are the nodes in the graph for A*. The edges are the roads between the nodes, and these edges should be given the driving distance along each road (shown in black text). In the "roads as edges" framework, you can incorporate one-way roads as unidirectional edges in the graph. If you want to assign costs to turning, you can extend the framework a bit: instead of nodes being locations, consider nodes to be a pair (a point in {emph state space}), where the direction indicates what direction you were facing when you {emph arrived} at that location. Replace edges from X to Y with edges from to to represent a straight drive, and from to to represent a "turn". Each edge represents {emph either} a straight drive or a turn, but not both. You can then assign costs to the edges representing turns. If you also need to take into account turn limitations, such as "only right turns", you can use a variation of this framework in which the two types of edges are always combined. Each edge represents an optional turn followed by a straight drive. In this framework, you can represent restrictions like "you can only turn right": include an edge from to for driving straight, and an edge from to for the right turn followed by a drive, but {emph don't} include to anything west, because that would mean a left turn, and don't include anything south, because that would mean a U-turn. In this framework, you can model a large city downtown, in which you have one-way streets, turn restrictions at certain intersections (often prohibiting U-turns and sometimes prohibiting left turns), and turn costs (to model slowing down and waiting for pedestrians before you turn right). Compared to grid maps, A* can find paths in road graphs environment fairly quickly, because there are few choices to make at each graph node, and there are relatively few nodes in the map. {h3 Duals} The road network example shows that the representation of locations as vertices and edges as connections between locations is not necessary. You can swap vertices and edges in many cases. On a square grid map, you can make the vertices the center of the border between two adjacent squares. You can make the edges the connections within a square between the edges. This form of graph makes it easier to represent very thin objects like walls that are placed between squares. {h3 Skip links} A pathfinding graph constructed from a grid typically assigns a vertex to each location and an edge to each possible movement from a location to an adjacent location. The edges are not constrained to be between adjacent vertices. A "skip link" is an edge between non-adjacent vertices. It serves to shortcut the pathfinding process. What should the movement cost be for a skip link? There are two approaches: {list {hbox Make the cost match the movement cost of the best path. This preserves nice properties of A*, like finding optimal paths. To give A* a nudge in the right direction, {link {ref Breaking ties} break the tie} between the skip link and the regular links by reducing the skip link's cost by 1% or so.} {hbox Make the cost match the heuristic cost. This makes a much stronger impact on performance but you give up optimal paths.} } Adding skip links is an approximation of a hierarchical map. It takes less effort but can often give you many of the same performance benefits. {h3 Waypoints} A {emph waypoint} is a point along a path. Waypoints can specific to each path or be part of the game map. Waypoints can be entered manually or computed automatically. In many real-time strategy games, players can manually add path-specific waypoints by shift-clicking. When automatically computed along a path, waypoints can be used to {link {ref Computed waypoints} compress the path representation}. Map designers can {link {ref Marked beacons} manually add waypoints} (or "beacons") to a map to mark locations that are along good paths or an algorithm can be used to automatically mark waypoints on a map. Since the goal of skip links is to make pathfinding faster when those links are used, skip links should be placed between waypoints. This will maximize their benefit. If there are not too many waypoints, the shortest paths between each pair of waypoints can be precomputed beforehand. The common case will then be a unit following its own path until it reaches a waypoint, and then it will follow the precomputed shortest path between waypoints, and finally it will get off the waypoint highway and follow its own path to the goal. Using waypoints or skip links with false costs can lead to suboptimal paths. It may be possible to smooth out a bad path in a post-processing step or in the movement algorithm. {h2 Long and short term goals} {filename Goals.html} {set shortname Goals} I've concentrated on the task of finding paths from one place to another. However, an equally important question is: once I have a path, how do I move along it? The most obvious answer is moving in a straight line from one location to the next. However, you might also want to move in a curve, or have multiple levels of movement. You may want to treat the locations as a low-priority goal from which you deviate. A higher level question is: where do you want to go? Unless you first answer the higher level question, pathfinding is not very useful. Certainly, one form of goal setting is asking the user to click on the destination. However, you may have automated tasks as well---exploring, spying, attacking, and building are common ones. {h3 Unit movement} I've concentrated on pathfinding, which reduces the problem of moving from one location to another with the many smaller problems of moving from one space to an adjacent space. You could move in a straight line from one location to the next but there are alternatives. Consider the four movement paths on this diagram: {figure {img 400 300 "splines.png"}} The red path is the standard approach: move from the center of one square to the center of the next. The green path is somewhat better: move in straight lines between the {emph edges} between the tiles, instead of the center of the tiles. You might also try moving in straight lines between the {emph corners} of tiles. The blue paths use splines, with dark blue being low order splines and light blue being a higher order spline (which takes longer to compute). Lines between corners and edges of tiles will be the shortest solution. However, the splines can make your units seem less mechanical and more "alive". Gamedev has an {link http://www.gamedev.net/reference/programming/features/cubicsplines/page2.asp article about splines for movement}. If your units cannot turn easily, you may want to take that into account when plotting a movement path. Craig Reynolds has a great page about {link http://www.red.com/cwr/steer/ steering} that has a paper about steering and Java applets demonstrating various behaviors. If you have more than one unit moving along a path, you may also want to investigate {link http://www.red.com/cwr/boids.html flocking}. Craig recommends that instead of treating paths as a list of places your unit must visit, you treat paths as ``a guideline, from which you deviate reactively as conditions require.'' {h3 Behavior flags or stacks} Your units may have more than one goal. For example, you may have a general goal like "spying" but also a more immediate goal like "go to the enemy headquarters". In addition, there may be temporary goals like "avoid that patrol guard". Here are some ideas for goals: {list {hbox {strong Stop}: Stay in the current location} {hbox {strong Stay}: Stay in one area} {hbox {strong Flee}: Move to a safe area} {hbox {strong Retreat}: Move to a safe area, while fighting off enemy units} {hbox {strong Explore}: Find and learn about areas for which little information is known} {hbox {strong Wander}: Move around aimlessly} {hbox {strong Search}: Look for a particular object} {hbox {strong Spy}: Go near an object or unit to learn more about it, without being seen} {hbox {strong Patrol}: Repeatedly walk through an area to make sure no enemy units go through it} {hbox {strong Defend}: Stay near some object or unit to keep enemy units away} {hbox {strong Guard}: Stay near the entrance to some area to keep enemy units out} {hbox {strong Attack}: Move to some object or unit to capture or destroy it} {hbox {strong Surround}: With other units, try to surround an enemy unit or object} {hbox {strong Shun}: Move away from some object or unit} {hbox {strong Avoid}: Stay away from any other units} {hbox {strong Follow}: Stay near some unit as it moves around} {hbox {strong Group}: Seek and form groups of units} {hbox {strong Work}: Perform some task like mining, farming, or collecting} } For each unit you can have a flag indicating which behavior it is to perform. To have multiple levels, keep a {emph behavior stack}. The top of the stack will be the most immediate goal and the bottom of the stack will be the overall goal. When you need to do something new but later want to go back to what you were doing, push a new behavior on the stack. If you instead need to do something new but {emph don't} want to go back to the old behavior, clear the stack. Once you are done with some goal, pop it from the stack and start performing the next behavior on the stack. {h3 Waiting for movement} It is inevitable that the movement algorithm will run into obstacles that were not there during the pathfinding process. An easily implemented technique is based on the assumption that the {emph other} obstacle will move first. This is particularly useful when the obstacle is a friendly unit. When an obstacle is in the way, just wait some amount of time for it to move. If it still hasn't moved after that period of time, recalculate a path around it or to the destination. If the obstacle is detected ahead of time, your unit can simply walk slower to give the other unit more time to get out of the way. It is possible that two units will bump into each other, and each will wait for the other to proceed. In this case, a priority scheme can be used: assign each unit a unique number, and then make the lower numbered unit wait for the higher numbered unit. This will force one of the units to proceed if both are waiting. When obstacles are detected ahead of time, the lower numbered unit should slow down before reaching the expected point of collision. {h3 Coordinated movement} The technique described above does not work when units are trying to move through a narrow corridor. If one unit stands still while the other tries to go around, the corridor can't be used by both units. One unit will block it while the other one will take a long path around. It should be possible for the second unit to communicate with the first one, and ask it to back up. Once the corridor is clear, the second unit can pass through, and then the first unit can go through. This may be complicated to implement unless you can identify the corridors beforehand. For randomly generated maps, it could be very difficult to determine where the corridor is and how far the first unit needs to back up. {h2 Movement costs for pathfinders} {filename MovementCosts.html} {set shortname Movement Costs} When using a pathfinding algorithm, you may want to treat map spaces as something other than {emph clear} and {emph blocked}. Often there is more information available, such as the difficulty of moving through that area. For example, swamps and mountains may be more difficult to pass than grasslands and desert. With some algorithms, like A*, you can put this encode this information into the cost function. Listed below are some ideas for movement costs that might be useful. {h3 Altitude} High altitudes (such as mountains) can have a higher movement cost than low altitudes. With this cost function, your units will try to stay in the lowlands whenever possible. For example, if the source and destination are both at high altitudes, the unit might move downhill, travel for a while, and then move back uphill. {h4 Moving uphill} Instead of high altitudes having a high cost, {emph moving} uphill can have a high cost. This avoids the odd situation described above. With this cost function, units try to avoid moving uphill. Faced with the same situation, the unit will try to avoid moving back uphill at the end; it can do this by staying at a high altitude throughout its travels. A cost function such as this one may be good for units such as soldiers, which can move downhill easily but have a hard time going uphill. {h4 Moving up- or downhill} Some units, such as tanks, have a hard time moving uphill {emph or} downhill. You can assign a high cost to moving downhill, and an even higher cost to moving uphill. The units will try to avoid changing altitudes. {h3 Terrain} You may want different types of terrain to have different movement costs. {h4 Forests, mountains, and hills} Instead of using altitudes, you may want to use terrain types, as in Civilization. Each terrain type can have a movement cost associated with it. This movement table might apply to all units, or different movement tables could be associated with each unit type. For example, soldiers might have no trouble moving through forests, but tanks might have a very hard time. A fancier method is to assign movement costs to {emph changing} terrain. Going from grassland into mountains could be more expensive than going from hills to mountains, which could be more expensive than going from mountains to mountains. {h4 Roads} In many games, the primary purpose of roads is to make movement possible or easier. After choosing a movement cost function, you can add a road modifier to it. One possibility is to divide the cost by some constant (such as two); another is to assign a fixed cost to movement along a road. {margin-note {vbox {strong Note:} {hbox You can find an example of using roads in the movement cost in my A* code, in the {code UnitMovement} class.} } } I strongly advise that you do {emph not} make road movement free (zero-cost). This confuses pathfinding algorithms such as A*, because it introduces the possibility that the shortest path from one point to another is along a winding road that seems to lead nowhere. The algorithm has to search a very wide area to make sure that no such roads exist. Note that in the game Civilization, railroads had zero-cost movement, but when using the "Auto Goto" function, railroads had a non-zero cost. This is evidence that a pathfinding algorithm was being used. {h4 Walls or other barriers} Instead of checking both movement costs and for obstacles in your pathfinding algorithm, you can just use movement costs. Just assign a very high movement cost to any obstacle. When expanding nodes (in the A* algorithm), check if the cost is too high; if it is, then throw the node out. {h4 Sloped Land} {margin-note {vbox {strong Note:} {hbox You can find an example of using land slopes in the movement cost in my A* code, in the {code FlatCanalPath} class.} } } Instead of using {emph movement} up and down hills, you might want to make movement on any hill expensive. To do this, compute the overall slope of the terrain (by looking at the maximum difference between the current tail and its neighbors), and use that as part of the movement cost. Land that is very steep will have a high cost and land that is shallow will have a low cost. This approach differs from the movement uphill/downhill cost in that it looks for {emph land} that is steep, while the previous approach looked for units that {emph move} in a steep direction. In particular, if you're on a hill and can move left or right without going up or down, the uphill/downhill approach will consider it a low cost, while this approach will consider it a high cost (because the land is steep even if you aren't going up or down). Sloped land costs may not make sense for unit movement, but you can use pathfinding for more than finding paths for units. I use it for finding paths for roads, canals, bridges, and so on. If you want to build these items on flat land, you can take land slope into account when finding a path for a road or canal. See {link {ref Applications} the section on applications} for more ideas. {h3 Enemies and friendly units} Another modifier can help you avoid enemy units. Using {link http://www.gameai.com/influ.thread.html influence maps}, you can keep track of areas that are near enemy or friendly units, have recently killed soldiers, have been recently explored, are close to an escape route, or have been traversed recently. ({link http://www.ensemblestudios.com/news/devnews/terrain2.shtml Age of Empires 2 uses influence maps to influence pathfinding.}) An influence map might have a positive value for friendly units and a negative value for enemy units. By increasing the movement cost whenever you are in negative territory, you can influence your units to stay away from the enemy. Even more complicated (and perhaps not possible with influence maps) is to look at {emph visibility}: is your unit visible by an enemy unit? Is your unit detectable in some other way? Is it possible for that enemy unit to fire on you? {h3 Marked beacons} If your map is designed and not automatically generated, you can add extra information to it. For example, ancient trade routes often would pass particular points, which often became trading towns. These places are {strong beacons}, places that are known to be along good paths. The distance to a beacon would be added to the movement cost as a way to influence paths to favor beacons. Good choices for beacons include lighthouses, cities, mountain passes, and bridges. {h3 Fuel consumption} In addition to looking at the {emph time} it takes to go somewhere, you may want to consider the {emph fuel} it takes. The fuel consumption may be given more weight when the unit's fuel level is lower. {margin-note {vbox {strong Note:} {hbox To keep the state space small, you need to round off the fuel value to a coarse measurement unit. Unfortunately, this makes the search less effective.} } } To track the fuel usage through the map, you need to use state space, as described in {link {ref Road maps}}. The state would be the pair . However, state space can become very large, so it may be worth looking at alternatives to using ordinary A*. One alternative is {link ftp://ftp.cs.bham.ac.uk/pub/authors/B.S.Logan/aaai-98.ps.gz A* with Bounded Costs} (ABC). With ABC, you can assign a bound ("20 gallons") to a cost ("fuel"). {h2 User experience with shortest paths} {filename UserExperience.html} What's most important in the game is the user. You want the user to have fun! You don't want him (or her) to feel like the computer is cheating, or that the game units aren't behaving properly. {h3 Dumb movement} If the pathfinding doesn't work well, the user will end up moving the units manually. {emph Avoid this!} In Civilization, the rules for the game allowed for zero-cost movement along railroads. However, the pathfinder had a non-zero movement cost. The result was that users avoided using the pathfinder, and instead moved units manually on the railroads. In Command and Conquer, units could get stuck in "U" shaped traps so users would have to guide the units manually. A dumb pathfinder will annoy your users and make them move units themselves, so make your pathfinder decent! {h3 Smart movement} Making units too smart is almost as bad as making units too dumb. If the player has to deal with fog of war but the pathfinder has access to the entire map, the units will mysteriously know where to go even though the user does not. That's a clear sign to the user that something odd is going on. On the other hand, it gives better paths. A compromise is to scale up the movement costs on unexplored areas. For example, if your normal movement costs are 1 for grass, 3 for forest, and 7 for mountains, set them differently on unexplored areas: 5 for grass, 6 for forest, 7 for mountains. The unit will take mountains vs. grass into account, but not too much; it'll just be a subtle hint. Raising costs for moving through unexplored areas will also tend to make the unit stay in explored territory as much as possible. You might want to do the opposite for "scout" units: they should {emph prefer} unexplored areas. Try to keep your units balanced between too dumb and too smart. The goal should be to make it match what the user might have done to move the unit around. {h3 Multithreading} You can use multithreading to improve the user experience. When a unit needs a path, allow it to start moving in a straight line towards the goal, and add a request to a pathfinding queue. In another (low priority) thread, pull requests off the queue and find paths. Your units will start moving immediately, so the user won't be left wondering if something is wrong, and you won't have a high CPU load (which will slow down the rest of the game) while the path is being calculated. {h3 Multiple units} If your game allows multiple units in a group to move together, try to make the movement look interesting. You can find a single path for them all to follow, and then have them all follow the path individually, but this will lead to either a line of units or units trying to pass each other. Instead, vary the paths a little so that they can walk in parallel. Alternatively, pick one "leader" unit to move along the path and have the other units use a separately programmed "follow" behavior. This following could be as simple as moving towards the leader but stay some distance away, or it could be as involved as {link http://www.red.com/cwr/boids.html flocking}. {h3 Multiple waypoints} Even given the optimal path, the player may prefer a different path. You may allow the player to mark waypoints on the path: instead of simply clicking on a destination, the player would click on two or three points along the way to the destination. (Many real-time strategy games use shift-click for this operation.) You now have three or four smaller paths to compute, and you save some time. The player also has some control over the overall path---for example, your pathfinder may have found a path to the west of some mountains, but for safety's sake, the player wants to stay to the east of the mountains (near friendly guard towers). The main change in unit movement code will be that instead of a single destination, you will have a list of destinations. Find a path to the first destination. Once you get there, remove it from the list and find a path to the next destination. This reduces latency and improves throughput as well. {h2 Applications} {filename Applications.html} In addition to finding a path for a unit to move along, pathfinding can be used for several other purposes. {h3 Exploration} If part of your cost function penalizes paths that are on known territory, paths are more likely to go through unexplored territory. These paths are good for scout units. {h3 Spying} If part of the cost function penalizes paths near the enemy's watchtowers and other units, your unit will tend to stay in hiding. Note however that to work well, you may have to update the path periodically to take into account enemy unit movements. {h3 Road building} Historically, roads have been built along paths that are often used. As the paths are used more and more often, vegetation is removed and replaced with dirt, and later with stone or other material. One application of pathfinding is to find roads. Given places that people want to go (cities, lakes, springs, sources of minerals, and so on), find paths randomly between these important locations. After finding hundreds or perhaps thousands of paths, determine which spaces on the map most often occur on paths. Turn those spaces into roads. Repeat the experiment, with the pathfinder preferring roads, and you will find more roads to build. This technique can work for multiple types of roads as well (highways, roads, dirt paths): the most commonly used spaces would become highways and less commonly used spaces would become roads or dirt paths. {h3 Terrain analysis} Combining influence maps, pathfinding, and line of sight can give you interesting ways to analyze terrain. Using the same approach as road building, we can use pathfinding to determine what areas are the most likely to be traversed given some set of source and destination points. These points, and areas near them, tend to be strategically important. By further analysing the common paths we find, we can find ambush sites---locations along a path that do not have line-of-sight access to the location N steps further along the path. Placing an ambush at one of these points means the enemy will not see you until they are within distance N, so you can ambush with a large force. {h3 City building} Cities often form around natural resources such as farmland or sources of mineral wealth. As people from these cities trade with each other, they need trading routes. Use pathfinding to find their trading routes, and then mark a day's worth of travel on these routes. After a caravan travels for a day, it will need a place to stop: a perfect place for a city! Cities that lie along more than one travel route are great places for trading villages, which eventually grow into cities. A combination of the road building and city building may be useful for producing realistic maps, either for scenarios or for randomized maps. {h2 AI techniques} {filename AITechniques.html} Pathfinding is often associated with AI, because the A* algorithm and many other pathfinding algorithms were developed by AI researchers. Several biology-inspired AI techniques are currently popular, and I receive questions about why I don't use them. Neural Networks model a brain learning by example---given a set of right answers, it learns the general patterns. Reinforcement Learning models a brain learning by experience---given some set of actions and an eventual reward or punishment, it learns which actions are good or bad. Genetic Algorithms model evolution by natural selection---given some set of agents, let the better ones live and the worse ones die. Typically, genetic algorithms do not allow agents to learn during their lifetimes, while neural networks allow agents to learn only during their lifetimes. Reinforcement learning allows agents to learn during their lifetimes and share knowledge with other agents. {h3 Neural Networks} Neural networks are structures that can be "trained" to recognize patterns in inputs. They are a way to implement {link http://www-anw.cs.umass.edu/~rich/book/8/node1.html function approximation}: given y{sub 1} = f(x{sub 1}), y{sub 2} = f(x{sub 2}), ..., y{sub n} = f(x{sub n}), construct a function f' that approximates f. The approximate function f' is typically {emph smooth}: for x' close to x, we will expect that f'(x') is close to f'(x). Function approximation serves two purposes: {list {hbox {strong Size:} the representation of the approximate function can be significantly smaller than the true function.} {hbox {strong Generalization:} the approximate function can be used on inputs for which we do not know the value of the function.} } Neural networks typically take a vector of input values and produce a vector of output values. Inside, they train weights of "neurons". Neural networks use {emph supervised learning}, in which inputs and outputs are known and the goal is to build a representation of a function that will approximate the input to output mapping. In pathfinding, the function is f(start, goal) = path. We do not already know the output paths. We could compute them in some way, perhaps by using A*. But if we are able to compute a path given (start, goal), then we already know the function f, so why bother approximating it? There is no use in generalizing f because we know it completely. The only potential benefit would be in reducing the size of the representation of f. The representation of f is a fairly simple algorithm, which takes little space, so I don't think that's useful either. In addition, neural networks produce a fixed-size output, whereas paths are variable sized. Instead, function approximation may be useful to construct components of pathfinding. It may be that the movement cost function is unknown. For example, the cost of moving across an orc-filled forest may not be known without actually performing the movement and fighting the battles. Using function approximation, each time the forest is crossed, the movement cost f(number of orcs, size of forest) could be measured and fed into the neural network. For future pathfinding sessions, the new movement costs could be used to find better paths. Even when the function is unknown, function approximation is useful primarily when the function varies from game to game. If a single movement cost applies every time someone plays the game, the game developer can precompute it beforehand. Another function that is could benefit from approximation is the heuristic. The heuristic function in A* should estimate the minimum cost of reaching the destination. If a unit is moving along path P = p{sub 1}, p{sub 2}, ..., p{sub n}, then after the path is traversed, we can feed n updates, g(p{sub i}, p{sub n}) = (actual cost of moving from i to n), to the approximation function h. As the heuristic gets better, A* will be able to run quicker. Neural networks, although not useful for pathfinding itself, can be used for the functions used by A*. Both movement and the heuristic are functions that can be measured and therefore fed back into the function approximation. {h3 Genetic Algorithms} {margin-note {vbox {strong Note:} {hbox Function approximation can be transformed into a function optimization problem. To find f'(x) that approximates f(x), set g(f') = Sum of (f'(x)-f(x)){super 2} over all input x.} } } Genetic Algorithms allow you to explore a space of parameters to find solutions that score well according to a "fitness function". They are a way to implement {emph {link http://mathworld.wolfram.com/StochasticOptimization.html function optimization}}: given a function g(x) (where x is typically a vector of parameter values), find the value of x that maximizes (or minimizes) g(x). This is an {emph unsupervised learning} problem---the right answer is not known beforehand. For pathfinding, given a starting position and a goal, x is the path between the two and g(x) is the cost of that path. Simple optimization approaches like hill-climbing will change x in ways that increase g(x). Unfortunately in some problems, you reach "local maxima", values of x for which no nearby x has a greater value of g, but some faraway value of x is better. Genetic algorithms improve upon hill-climbing by maintaining multiple x, and using evolution-inspired approaches like mutation and cross-over to alter x. Both hill-climbing and genetic algorithms can be used to learn the best value of x. For pathfinding, however, we already have an algorithm (A*) to find the best x, so function optimization approaches are not needed. Genetic Programming takes genetic algorithms a step further, and treats {emph programs} as the parameters. For example, you would breeding pathfinding {emph algorithms} instead of {emph paths}, and your fitness function would rate each algorithm based on how well it does. For pathfinding, we already have a good algorithm and we do not need to evolve a new one. It may be that as with neural networks, genetic algorithms can be applied to some portion of the pathfinding problem. However, I do not know of any uses in this context. Instead, a more promising approach seems to be to use pathfinding, for which solutions are known, as one of many tools available to evolving agents. {h3 Reinforcement Learning} Like genetic algorithms, Reinforcement Learning is an unsupervised learning problem. However, unlike genetic algorithms, agents can learn during their lifetimes; it's not necessary to wait to see if they "live" or "die". Also, it's possible for multiple agents experiencing different things to share what they've learned. Reinforcement learning has some similarities to the core of A*. In A*, reaching the end goal is propagated back to mark all the choices that were made along the path; other choices are discarded. In reinforcement learning, every state can be evaluated and its reward (or punishment) is propagated back to mark all the choices that were made leading up to that state. The propagation is made using a value function, which is somewhat like the heuristic function in A*, except that it's updated as the agents try new things and learn what works. One of the key advantages of reinforcement learning and genetic algorithms over simpler approaches is that there is a choice made between {emph exploring} new things and {emph exploiting} the information learned so far. In genetic algorithms, the exploration via mutation; in reinforcement learning, the exploration is via exlicitly allowing the probability of choosing new actions. As with genetic algorithms, I don't believe reinforcement learning should be used for the pathfinding problem itself, but instead as a guide for teaching agents how to behave in the game world. {h2 References} {filename References.html} This section is quite incomplete. There is a little bit of information in {link http://www.cee.hw.ac.uk/~alison/ai3notes/subsection2_6_2_3.html the class notes for an AI course}. General graph searching algorithms can be used for pathfinding. Many algorithms textbooks describe graph searching algorithms that do not use heuristics (breadth-first search, depth-first search, Dijkstra's). Reading about them may help in understanding A*, which is a variant of Dijkstra's. Many AI textbooks will address graph searching algorithms that do use heuristics (best-first search, A*). Here are two that I have used: {list {hbox Russell and Norvig, {link http://www.cs.berkeley.edu/~russell/aima.html AI: A Modern Approach}} {hbox Ginsberg, {link http://www.mkp.com/books_catalog/1-55860-221-6.asp Essentials of Artificial Intelligence}} } For non-pathfinding algorithms, see {link http://web.archive.org/web/20020810205430/http://home.sol.no/~johncl/shorpath.htm John Lonningdal's web page} (via Wayback Machine, since his site is no longer up). For more about using non-grid graphs for pathfinding, see {link http://216.5.163.53/DirectX4VB/Tutorials/GeneralVB/GM_Dijkstra.asp this detailed tutorial on Dijkstra's algorithm}, which also includes some VB source code. To learn more about unit movement after a path has been found, see Pottinger's articles on {link http://www.gamasutra.com/features/game_design/19990122/movement_01.htm unit movement} and {link http://www.gamasutra.com/features/game_design/19990129/implementing_01.htm group movement}. Also highly recommended are Craig Reynold's pages on {link http://www.red.com/cwr/steer/ steering} and {link http://www.red.com/cwr/boids.html flocking}. Geoff Howland has a {link http://www.gamedev.net/reference/design/features/prac_ai_2/ great article} about unit movement in general. Patrick Lester has a page {link http://www.policyalmanac.org/games/twoTiered.htm describing a two-level pathfinder}. There's an interesting paper describing how to find {link http://citeseer.nj.nec.com/580850.html Simplest Paths} instead of Shortest Paths. Here are some other papers I haven't classified: {link http://games.cs.ualberta.ca/pathfind/publications/cig2005.pdf Fringe Search} {link http://www.maddocsoftware.com/pdf/I_Davis_00.pdf Path Planning for Star Trek: Armada}, with path smoothing {link http://games.cs.ualberta.ca/pathfind/publications/yap2002.ps Using hex grids for pathfinding}