A Faster Implementation of the Standard A*
Before proceeding with turning and smoothing modifications to the A* algorithm, let's start with some basic optimizations that can speed up the standard A* algorithm by a factor of 40 or more. To start with, the standard A* algorithm uses a sorted linked list (or two linked lists) to track nodes that are checked. Instead, we'll use a 60x60 fixed matrix. When starting a search from point a to point b, we find the midpoint between those two and place it at point [30,30] on our matrix. Each point on the matrix stores:
We also keep a separate array of 1-bit Booleans, which store whether or not each node in our matrix has been touched yet during this search. That way, we can very rapidly initialize at the beginning of the search without needing to clear the entire matrix.
Whereas the original algorithm maintains a separate sorted Open list (actually a Priority Queue), we instead maintain basic list functionality simply by using Previous and Next pointers within the fixed array. Note that we do have the memory requirement for our 60x60 matrix, but our compacted data structure requires only 16 bytes per node, for a total of 57K. (Even expanding the matrix to 120x120 will only require 230K of memory.)
Note additionally that the "list" can be implemented as a binary tree (by having two Next node pointers at each element), but we've actually found it to be substantially faster to have a simple (non-priority) list. While this does result in time O(n) for the search for the lowest cost node at the top of the A* loop (rather than O(log n) for a priority queue), it excels in that all insertions and deletions, of which there are many, are only O(1). Best of all, it eliminates the inner loop search that checks if neighboring nodes yet exist on the Open or Closed lists, which otherwise would take O(n) (or maybe a bit better if a hash table is used).
Overall, by avoiding all memory allocations and list insertions, this method turns out to be dramatically faster. I have profiled it to be as much as 40 times faster than standard A* implementations.
Note that for the Directional search described later in this article, eight times the number of nodes are necessary, so the memory requirement will all increase by a factor of eight.
Smoothing the A* Path
The first and most basic step in making an A* path more realistic is getting rid of the zigzag effect it produces, which you can see in Figure 2a. This effect is caused by the fact that the standard A* algorithm searches the eight tiles surrounding a tile, and then proceeds to the next tile. This is fine in primitive games where units simply hop from tile to tile, but is unacceptable for the smooth movement required in most games today.
FIGURE 2. The common zigzag effect of the standard A* algorithm (a); a modification with fewer, but still fairly dramatic, turns (b); and the most direct -- and hence desired -- route (c). To achieve the path shown in Figure 2c, the four waypoints shown in red in Figure 2a were eliminated. |
One simple method of reducing the number of turns is to make the following modification to the A* algorithm: Add a cost penalty each time a turn is taken. This will favor paths which are the same distance, but take fewer turns, as shown in Figure 2b. Unfortunately, this simplistic solution is not very effective, because all turns are still at 45-degree angles, which causes the movement to continue to look rather unrealistic. In addition, the 45-degree-angle turns often cause paths to be much longer than they have to be. Finally, this solution may add significantly to the time required to perform the A* algorithm.
The actual desired path is that shown in Figure 2c, which takes the most direct route, regardless of the angle. In order to achieve this effect, we introduce a simple smoothing algorithm which takes place after the standard A* algorithm has completed its path. The algorithm makes use of a function Walkable(pointA, pointB), which samples points along a line from point A to point B at a certain granularity (typically we use one-fifth of a tile width), checking at each point whether the unit overlaps any neighboring blocked tile. (Using the width of the unit, it checks the four points in a diamond pattern around the unit's center.) The function returns true if it encounters no blocked tiles and false otherwise. See Figure 3 for an illustration, and Listing 1 for pseudocode.
LISTING 1. Pseudocode for the simple smoothing algorithm. The smoothing algorithm simply checks from waypoint to waypoint along the path, trying to eliminate intermediate waypoints when possible.
checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next
FIGURE 3. Illustration of the Walkable() function which checks for path collisions. |
The smoothing algorithm simply checks from waypoint to waypoint along the path, trying to eliminate intermediate waypoints when possible. To achieve the path shown in Figure 2c, the four waypoints shown in red in Figure 2a were eliminated.
Since the standard A* algorithm searches the surrounding eight tiles at every node, there are times when it returns a path which is impossible, as shown with the green path in Figure 4. In these cases, the smoothing algorithm presented above will smooth the portions it can (shown in purple), and leave the "impossible" sections as is.
This simple smoothing algorithm is similar to "line of sight" smoothing, in which all waypoints are progressively skipped until the last one that can be "seen" from the current position. However, the algorithm presented here is more accurate, because it adds collision detection based on the width of the character and also can be used easily in conjunction with the realistic turning methods described in the next section.
FIGURE 4. This smoothing algorithm will leave impossible paths alone. |
Note that the simple smoothing algorithm presented above, like other simple smoothing methods, is less effective with large units and with certain configurations of blocking objects. A more sophisticated smoothing pass will be presented later.