Developing By Me

Project Development and Design

AI Pathfinding A*

OSPF is the most efficient way to find a path. However there are many techniques to creating the path. It is important to note that there are hundreds of different algorithms that could used to create a pathfinding AI each works with different environment or scenario. One of the more common methods is Dijkstra’s Algorithm [DA] and a derivative is A* which is tiled in nature. Since the concept is simple to explain and it is a basic algorithm the A* method is the first that any developer should look at when learning how to program a pathfinding AI.

The A* algorithm is simple. Take the map and break it into a grid map of tiles exactly the same height and width. The tile map will be used by the A* to generate the path. The simple example how this works is a mob is the center of a tile there are 8 tiles around him. Now, draw a line from the mob to the center point of each tile. Next, determine which tile is closest to the goal and move to that tile which is one space closer to the goal. Then, scan all of the new tiles and move until the goal is finally reached. This is normally done by choosing an arbitrary starting point and moving around in a circular manner until all locations are examined. In a typical tile based map each tile knows if one of its neighbors is passable. Some methods include just the four directly connecting sides, however others include all eight. It is also possible that some engines do not required neighbor data and more scans are required but for the examples this will not be the case. By using the method, eventually the entire path and all surrounding squares will be known as either passable or impassable. With this knowledge the algorithm can follow the known tiles through the shortest path to the goal. Table 1 displays the uncharted map the algorithm will use.

Table 1
X X X X X X X X X X
X X
X X X X X
X X X
X S X E X
X X X
X X X X X X
X X
X X
X X X X X X X X X X

The different Icons in the grid are as follows. X is an impassible wall. The S is the start space and the E is the end space. All empty spaces can be freely moved through. An * will illustrate the final path. The method is to move out in every direction that is empty, i.e. not an X, and then move closer to the target and repeat. The next table shows the scan path indicated by numbers for the order they were scanned with the final path shown.

Table 2
X X X X X X X X X X
X X
X X X X X
X 1 1 2 X X
X S *1 2 X *E 10 10 X
X 1 1 *2 X 10 *9 9 X
X 3 *3 X X X X *8 X
X 4 4 *4 *5 *6 *7 8 X
X 5 5 5 6 7 8 X
X X X X X X X X X X

The above pass is called a Right Handed Search [RHS] the advantage to this search is that the search moves toward the goal to the path of least resistance. In the event of a choice of direction, the RHS will always move right. This is commonly done within game development. However it is not always the most advantageous method. There is also the Left Handed Search [LHS] that could be used in a scenario like this as shown in Table 3.

Table 3
X X X X X X X X X X
X 4 *4 *5 *6 7 8 X
X *3 X X X *7 8 9 X
X *1 1 2 X 8 *8 9 X
X S 1 2 X 9 *E 9 X
X 1 1 2 X X
X X X X X X
X X
X X
X X X X X X X X X X

In this example, the path does generate a useless scan, number 2. Since those tiles are on the wall the algorithm has to backup and pick a different direction. Because of the LHS method, it moves to above the start point since it searches in a counter clockwise direction for an open space. It is obvious to note that in this example map the LHS has one less scan then the RHS and takes 2 less moves thus creating a shorter path. However, one method is not any more efficient then the other. There are countless examples that can demonstrate either being more efficient. In the end it is the developers choice as to which is used. Some developers will use both and choose the best of the pair but this does take twice as long to find the path.

So is A* restricted to tile based games? The simple answer is No. It can be done on any environment the only rule is that the center point of each block must be the exact same predefined distance away. This prevents bias that could be created accidentally. As an example if the tiles have a height and width of exactly 1 unit then distance between the four directly connected tiles is 1 unit from center to center and the diagonal distance between centers is 1.4142 units. The math is basic algebra and the example distances will always be true regardless of the actual size of the tiles.

What is obvious about the technique is that it scans every square around the current point. This costs CPU cycles and impacts the performance doing long searches. To create a faster method it is best to add one last metric into the mix. That is the direction of the goal. If the goal is on the right side of the map then there is no need to scan the left. Scanning only the 3 tiles in the direction of the goal reduces the number of scanned tiles up to 62%. If the engine has to do thousands of paths every second this is a significant performance increase. Table 4 shows the RHS without the extra scans.

Table 4
X X X X X X X X X X
X X
X X X X X
X 1 2 X X
X S *1 2 X *E 10 X
X 1 *2 X 10 *9 9 X
X *3 X X X X *8 X
X *4 *5 *6 *7 X
X X
X X X X X X X X X X

The original scan had 30 scanned tiles the above scan only used 17 that means 13 less tiles that were scanned reducing the overhead by 43%. The only oddity that is obvious is the #3 scan. The method searches the three tiles closest to the goal. From *2 they are all walls so it continues the scan in a clockwise rotation until the first free square is found then stops. The method is called Closest Path Method [CPM]. The algorithm is optimized for open environments but can be used for a closed or maze style layouts. Since it does not scan every direction in a maze environment there is potentially a lot of backtracking. But since most games use open terrain environments the method works well. Every method of utilizing the algorithm has its advantages but the CPM is ideal in most scenarios since it does reduce the amount of time required to generate the valid path. It also has the benefit of utilizing either RHS or LHS scanning methods for either primary or extended scans. This functionality allows it to do minimal work but have the extra options when a problem arises.

Related pages

  1. AI Pathfinding Ray Casting
  2. Pathfinding Basics
powered by Related Pages WP plugin

3 Responses to “AI Pathfinding A*”

%d bloggers like this: