Introduction

I will be focusing on the A* Algorithm. A* is probably your best choice for path-finding, since it can be significantly faster than Dijkstra's algorithm or Best-First Search (BFS). It was developed in 1968 to combine heuristic methods (which use information about the problem to be solved to make decisions) and formal methods (which don't use problem-specific information, but can be formally analyzed). The overall structure is a graph searching algorithm. Unlike most graph searching algorithms, A* utilizes a heuristic function that estimates how close any spot on the map is to the goal. By using the heuristic, it can guide its search to look in the best direction first. If that fails, it can look at other paths. I won't go into the details of the algorithm; instead I'll first describe the behavior of A*, then concentrate on my analysis of using this algorithm for games. I recommend looking up A* in an AI textbook to learn how the algorithm works in detail.

The A* Algorithm

Most path-finding algorithms are written 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.)


Note:
For most of this document, we will assume that A* is being used on a grid in a tile-based game. However, A* was designed for use with graphs, and it can be used in different ways in games -- see the section on polygonal obstacles for an example.

A* is like other graph-searching algorithms in that it can potentially search a huge area of the map. It is also like step-taking algorithms in that it starts out going straight for the goal. (This is the primary difference between A* and Dijkstra: A* has a heuristic function to guide its search towards the goal; Dijkstra has no such information, and searches in all directions.) Unlike the step-takers, however, A* can "backtrack" if going straight for the goal doesn't take you there. It does this as it's going by keeping track of possible grid spots that might lead to a good path. For example, if you were heading towards a town and came to a fork in the road, and decided to go left instead of right, you'd probably remember that if you didn't find the town, you could come back and try the other path. A* does the same thing.

So far, this sounds very much like Best-First Search. The main difference is that BFS will keep looking down one path as long as it thinks it's getting closer to the goal, until it gets to a dead-end. A* will go down several paths at once if they all look like they're getting closer to the goal. A* looks at the path that has the lowest "cost" from beginning to end, whereas BFS looks at the path that has the lowest cost from the current point to the end. BFS ignores the cost of the path taken so far, so it is possible for it to go off on a wild goose chase on some long expensive path that seems to be good. A* would look at other paths as soon as that path got expensive. In the next section we will look at the heuristic function, which is a guess of the cost from the current point to the end.

If you find the goal by going straight, then you don't really need to search the things in the backtrack list. That's why A* is pretty fast most of the time. It puts things on the list but it can throw them away if it finds the goal.

The Heuristic

The heuristic function h(p) tells A* an estimate of the cost from the current position p to the goal. To find the best path, A* uses both the heuristic and g(p), the cost of the best path from the start to p. The sum of these two values is called the estimated cost, f(p).

It's important to choose a good heuristic function. A bad heuristic can really slow down A* or make it produce bad paths. If you want A* to give you "perfect" paths, the heuristic function should be an underestimate of the actual cost of getting from one spot to the goal. Be careful that you don't underestimate too much however. A low heuristic won't give A* much information, and it'll keep telling A* that there are better paths available, so it will take longer to give you a path.

An interesting note: If your heuristic is exact, then A* will never stray from the best path. Of course, it's hard to get an exact heuristic, but it's nice to know that A* will act perfectly when you give it perfect information. (Also note that in the sometimes common case where you have no obstacles, the heuristic can be perfect.) Another thing that may be interesting is that as your heuristic gets closer to being perfect, A* has to search less and less. This gives me confidence that it's using the heuristic well -- if it wasn't, then a perfect heuristic probably would lead to an inefficient search. If there aren't any obstacles or nasty terrain squares in the way, then the heuristic (which is usually the number of steps to the goal) is perfect, and A* will head straight towards the goal and not look anywhere else on the map. The way to think about this is that the increase in the f value is related to how much is searched. When the heuristic is perfect, f never changes. When the heuristic underestimates too much, f increases quickly. The better the heuristic, the less f increases, and the less of the map is searched.


Note:
Technically, the A* algorithm should be called simply A if the heuristic is an underestimate. However, I will continue to call it A* because the implementation is the same.

You may not want "perfect" paths. You might want to get "reasonable" paths quickly instead of perfect paths take some time to find, especially if you are writing a real-time game. For this, there are several things you can do to speed up A*. First, you don't have to have an underestimating heuristic. If your heuristic function overestimates some of the time, it can find the goal quicker. Alternatively, you can adjust your "cost" function to more closely match your heuristic.

For example, if 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 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. You can also speed 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.

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.

Speed or Accuracy?

For most games, you don't really need the 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.

Computer speed

If your game is running on a slow computer, you can adjust your A* heuristic to approximate more. This will speed up A*, so your game won't slow to a crawl on those older computers. Conversely, if it is running on a fast computer, you can adjust the heuristic to give better paths. You have more CPU time, so why not use it to make the game run better? This seems to be a good situation -- players who have powerful computers can get more out of the game; yet you don't leave everyone else with an unplayable game.

Number of units

As the number of military units on the map increases, it's going to use up more CPU time. You can just adjust the heuristics to give more approximate paths as the unit count goes up. This will keep your game from slowing down too much. Also, it's realistic. A general with a large army doesn't have as much time to spend planning each unit's movement as a general with a small army. The result? The large army's general thinks less per unit -- the equivalent of A* searching less of the map. Human players aren't going to be able to think as well when controlling a large force, so a computer that thinks less per unit might be a more realistic opponent.

Implementation ideas

As the game is running, you can keep track of how much time is being spent on A* searches. If the time exceeds some threshold, you can adjust the heuristic function towards speed and away from accuracy. If it's lower than some threshold, you can make the heuristic more accurate. A self-adjusting heuristic takes care of both computer speed and number of units, and you don't have to spend time "tuning" it yourself.


Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel