Now that you understand the basic method, here are some additional things to think about when you are writing your own program.
1. Maintaining the Open List: This is actually one of the most time consuming elements of the A* pathfinding function. Every time you access the open list, you need to find the square that has the lowest F cost. There are several ways you could do this. You could save the path items as needed, and simply go through the whole list each time you need to find the lowest F cost square. This is simple, but really slow for long paths. This can be improved by maintaining a sorted list and simply grabbing the first item off the list every time you need the lowest F-cost square. When I wrote my own demo in Blitz Basic, this was the first method I used, saving the open list items as a sorted Blitz “type.”
This will work reasonably well for small maps, but it isn’t the fastest solution. Serious A* programmers who want real speed use something called a binary heap, and this is what I use in my code. In my experience, this approach will be at least 2-3 times as fast in most situations, and geometrically faster (10+ times as fast) on longer paths. If you are motivated to find out more about binary heaps, check out my article, Using Binary Heaps in A* Pathfinding.
2. Storing the Path: Once you have found a path, you will want to store it and access it as needed. In Blitz you can use arrays, types, or banks to store this data. I chose to use a combination that I call an arrayed bank (you will need to look at the commented source code to see how this is done). Like types, banks are flexible. They can be expanded or reduced in size, depending on the size of your path, thus conserving memory. They can also be accessed directly, like an array, which is a lot faster than going through each element in a type to find the information you want. With arrayed banks you end up getting the best of both worlds – speed and flexibility.3. Other Units: If you happen to look closely at my example code written in Blitz, you will notice that it completely ignores other units on the board. My pathfinding critters actually pass right through each other. Depending on the game, this might be okay or it might not. If you want to consider other units on the board and have them move around each other, I suggest ignoring other units in the path finding code itself and instead writing some new code that detects whether two units have bumped into each other. When that happens, you can generate a new path or use some standard movement rules (always move to the right, etc.) until the obstacle is no longer in the way, and then generate a new path. Why not include other units when you are calculating the initial path? Well, because other units can move, they may not be where they were by the time you get there. This can produce some weird results, where a unit swerves to avoid a unit that isn’t there anymore and bumps into units that have moved across its path after the path is calculated.
Ignoring other units in the pathfinding code, however, means that you will need to write separate code to handle collisions and what to do when they occur. This is fairly game specific, so I’ll leave its resolution to you. Bryan Stout’s article in the references section at the end of this article is worth checking out for some possible solutions (like robust tracing, etc.).
4. Some More Speed Tips: As you develop your own A* program, or adapt the one I wrote, you will eventually find that pathfinding is using a hefty chunk of your CPU time, particularly if you have a decent number of pathfinding critters on the board and a reasonably large map. If you read the stuff on the net, you will find that this is true even for the professionals who design games like Starcraft or Age of Empires. If you see things start to slow down due to pathfinding, here are some ideas that may speed things up:
- Consider a smaller map or fewer critters.
- Never do path finding for more than a few critters at a time. Instead put them in a queue and spread them out over several game cycles. If your game is running at, say, 40 cycles per second, no one will ever notice. But they will notice if the game seems to slow down every once in a while when a bunch of critters are all calculating paths at the same time.
- Consider using larger squares for your map. This reduces the total number of squares searched to find the path. If you are ambitious, you can devise two or more pathfinding systems that are used in different situations, depending upon the length of the path. This is what the professionals do, using large areas for long paths, and then switching to finer searches using smaller squares/areas when you get close to the target. If you are interested in this concept, check out my article Two-Tiered A* Pathfinding.
- Consider using a waypoint system for longer paths, or devising precalculated paths that are hardwired into the game.
- When groups of critters are all going to the same place, calculate one path for the group leader, and then have the other members of the group follow that leader.
5. Variable Terrain Cost: In this tutorial and my accompanying program, terrain is just one of two things – walkable or unwalkable. But what if you have terrain that is walkable, but at a higher movement cost? Swamps, hills, stairs in a dungeon, etc. – these are all examples of terrain that is walkable, but at a higher cost than flat, open ground. Similarly, a road might have a lower movement cost than the surrounding terrain.
This problem is easily handled by adding the terrain cost in when you are calculating the G cost of any given square. Simply add a bonus cost to such squares. The A* pathfinding algorithm is already written to find the lowest cost path and should handle this easily. In the simple example I described, when terrain is only walkable or unwalkable, A* will look for the shortest, most direct path. But in a variable-cost terrain environment, the least cost path might involve traveling a longer distance – like taking a road around a swamp rather than plowing straight through it.
An interesting additional consideration is something the professionals call “influence mapping.” Just as with the variable terrain costs described above, you could create an additional point system and apply it to paths for AI purposes. Imagine that you have a map with a bunch of critters defending a pass through a mountain region. Every time the computer sends somebody on a path through that pass, it gets whacked. If you wanted, you could create an influence map that penalized squares where lots of carnage is taking place. This would teach the computer to favor safer paths, and help it avoid dumb situations where it keeps sending troops and critters through a particular path, just because it is shorter (but also more dangerous).
6. Handling Unexplored Areas: Have you ever played a PC game where the computer always knows exactly what path to take, even though the map hasn't been explored yet? Depending upon the game, pathfinding that is too good can be unrealistic. Fortunately, this is a problem that is can be handled fairly easily.
The answer is to create a separate "knownWalkability" array for each of the various players and computer opponents (each player, not each unit -- that would require a lot more computer memory). Each array would contain information about the areas that the player has explored, with the rest of the map assumed to be walkable until proven otherwise. Using this approach, units will wander down dead ends and make similar wrong choices until they have learned their way around. Once the map is explored, however, pathfinding would work normally.
7. Smoother Paths: While A* will automatically give you the shortest, lowest cost path, it won't automatically give you the smoothest looking path. Take a look at the final path calculated in our example (in Figure 7). On that path, the very first step is below, and to the right of the starting square. Wouldn't our path be smoother if the first step was instead the square directly below the starting square?
There are several ways to address this problem. While you are calculating the path you could penalize squares where there is a change of direction, adding a penalty to their G scores. Alternatively, you could run through your path after it is calculated, looking for places where choosing an adjacent square would give you a path that looks better. For more on the whole issue, check out this (free, but registration required) article at Gamasutra.com.
8. Non-square Search Areas: In our example, we used a simple 2D square layout. You don’t have to use this approach. You could use irregularly shaped areas. Think of the board game Risk, and the countries in that game. You could devise a pathfinding scenario for a game like that. To do this, you would need to create a table for storing which countries are adjacent to which, and a G cost associated with moving from one country to the next. You would also need to come up with a method for estimating H. Everything else would be handled the same as in the above example. Instead of using adjacent squares, you would simply look up the adjacent countries in the table when adding new items to your open list.
Similarly, you could create a waypoint system for paths on a fixed terrain map. Waypoints are commonly traversed points on a path, perhaps on a road or key tunnel in a dungeon. As the game designer, you could pre-assign these waypoints. Two waypoints would be considered "adjacent" to one another if there were no obstacles on the direct line path between them. As in the Risk example, you would save this adjacency information in a lookup table of some kind and use it when generating your new open list items. You would then record the associated G costs (perhaps by using the direct line distance between the nodes) and H costs (perhaps using a direct line distance from the node to the goal). Everything else would proceed as usual.
For another example of searching on an isometric RPG map using a non-square search area, check out my article Two-Tiered A* Pathfinding.
Further Reading
Okay, now you have the basics and a sense of some of the advanced concepts. At this point, I’d suggest wading into my source code. It is heavily commented and should be fairly easy to follow, relatively speaking. I happen to be someone who thinks that code is aptly named, and that reading someone else’s code is usually too difficult to be worth the bother. As a result, my code is sensitive to this. It contains lots of comments and is written to be as easy to follow as possible.
You should also consider reading through the following web pages. They should be much easier to understand now that you have read this tutorial.
- Amit’s A* Pages: This is a very widely referenced page by Amit Patel, but it can be a bit confusing if you haven’t read this article first. Well worth checking out. See especially Amit's own thoughts on the topic.
- Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program written in Blitz. It also describes some alternatives to A*.
- Terrain Analysis: This is an advanced, but interesting, article by Dave Pottinger, a professional at Ensemble Studios. This guy coordinated the development of Age of Empires and Age of Kings. Don’t expect to understand everything here, but it is an interesting article that might give you some ideas of your own. It includes some discussion of mip-mapping, influence mapping, and some other advanced AI/pathfinding concepts. The discussion of “flood filling” was an inspiration for my own “dead ends” and “islands” map preprocessing code, which is included in my Blitz program.
Some other sites worth checking out:
Finally, in case you are interested, I keep the latest version of this article here. The version here on Blitzcoder is current as of December 14, 2002.Well, that’s it. If you happen to write a program that uses any of these concepts, I’d love to see it (I can be reached at pwlester@policyalmanac.org). Until then, good luck!
For a printable copy of this article, please click HERE.