Most game developers these days know of the A* (pronounced A-star) algorithm as the preferred method of finding a path around obstacles on a map. A* is actually a general-purpose graph-search algorithm based on theories presented by Hart, Nilsson, and Raphael in a 1968 paper for the IEEE Transactions on Systems Science and Cybernetics entitled, "A formal basis for the heuristic determination of minimum cost paths."
Whew! Fortunately, although it may seem intimidating at first, the A* algorithm is quite simple and you don't have to be an IEEE fellow to understand it. My first introduction to it was in one of my AI classes in college in Nilsson's book, "Principles of Artificial Intelligence." Interestingly enough, that book doesn't even mention the algorithms use for pathfinding on a map. The example he provides uses the algorithm to traverse a search tree to solve the 8 puzzle.
However, it should be obvious (when you think about it) that pathfinding on a map is merely a specialized case of a generic graph-search. And, as it turns out, one that the A* algorithm is particularly useful for solving, provided you can determine accurate "costs" for moving between adjacent nodes on the map.
Overview
The basic idea of the A* algorithm is to divide a map into adjacent nodes. Some nodes are free of obstacles and can be entered. Other nodes can not be entered. Between any adjacent nodes, there is a cost associated with moving from one node to another.
The algorithm starts by looking at all of the nodes adjacent to the starting point. For each one, it determines an estimated total cost of moving from that node to the destination, generally based on distance without regard to possible obstacles (which aren't known yet).
It then chooses the node with the least estimated total cost and looks at all of the nodes adjacent to it. This time it tracks the actual cost of moving from the original node to the current one and then, again, adds an estimated cost to the destination to come up with a revised estimated total cost.
From all of these nodes, it again selects the node with the least estimated total cost and repeats the process. As it does so, it is continually refining the actual cost of moving into each node along various paths, always doing so by searching the lowest estimated costs first. When paths are discovered with actual costs that are worse than actual costs to the same node by other paths, they are eliminated from further consideration. The end result can be proven to be the shortest path between the start and destination nodes (assuming the heuristic for estimating total cost meets certain conditions).
For a more complete, and very readable, description, I highly recommend the article, A* Pathfinding for Beginners, by Patrick Lester. I couldn't hope to explain it in more understandable terms than he does.
An A* Implementation
I have created a sample "game" that demonstrates the implementation of A* that I used in Snowball Fight!. I created this as a separate sample application in order to make it easier to understand how the algorithm works and how to use this specific implementation. I stripped out almost all of the unnecessary code to focus as much as possible on the Pathfinding class.
In the sample, a Bug (er, insect) traverses the shortest available path around obstacles on a map towards a Flower. The Flower can be moved by the player using the keyboard or an Xbox 360 controller. Whenever the Flower is moved, the Bug uses the Pathfinder class to find the shortest path to its new location.
The sample is divided into two namespaces. The SwampLib namespace contains general purpose classes that can be reused in many games. The PathfindingSample namespace contains classes that are specific to the sample "game".
SwampLib
The main classes of interest in the SwampLib namespace are:
- IMap
- Defines an interface between a map and the Pathfinder class. This allows many map implementations to be used with the Pathfinder. The only restriction is that the map must be capable of being divided into "tiles". Note that this does not mean the map must be a traditional tilemap. In fact, the Map implementation in this sample is not a traditional tilemap.
- MapLocation
- A struct that represents a tile on an IMap.
- Pathfinder
- Any object that wishes to find a path through a map must create an object of this class. The constructor to the Pathfinder object takes an IMap object as a parameter. The map associated with the Pathfinder can later be changed, if desired, with the one restriction that the map must be of the same size as the original map.
The FindPath method is used to find a path from any starting tile to any destination tile. The path found is stored as a stack of destination MapLocation waypoints.
Traversing the path is done by calling Pathfinder's Complete method to make sure that the destination has not already been reached. If Complete returns false, the GetNextWaypoint method can be called to get the MapLocation of the next waypoint.
- PathNode
- PathNode is only of interest in understanding the A* implementation. It is not publicly accessible outside of the SwampLib namespace and is used internally by the Pathfinder class to keep track of the status of each node (tile) on the map while finding a path.
- Sprite
- The Sprite class is not related to pathfinding, or the A* algorithm, but is provided as a reusable class for managing on-screen sprites. It provides collision detection and handling capabilities via the BoundingCircle and BoundingRectangle classes, although these are not used in this sample.
- XnaGame
- The XnaGame class is a subclass of Microsoft.Xna.Framework.Game class that is intended as a parent to other Game classes. It provides access to a number of commonly needed resources and methods.
PathfindingSample
The classes that make up the PathfindingSample itself are:
- PathfindingGame
- The game itself, which inherits from SwampLib.XnaGame. This class creates the GameComponents and Sprites, and loads all game content. It also manages updating and drawing the player's target Reticle.
- InputComponent
- This GameComponent manages the state of the keyboard and gamepad input controls. It is implemented as a singleton to make it easier for all of the other classes to access its properties.
The SetTarget property is true if the user has requested to change the target's position via the A button on the gamepad or the Spacebar on the keyboard.
The ToggleBlockedTiles property is true if the user has requested to toggle whether or not blocked tiles are highlighted on the map.
- MapComponent
- This DrawableGameComponent handles the majority of the game logic. It maintains a list of Sprites associated with the map (although in this case, that is only the Bug and Flower). It is responsible for updating all active Sprites and drawing the map and all visible Sprites.
- Bug
- The Sprite that uses the Pathfinder class to find the shortest route to the Flower's current position. Look at this class to understand how to use the Pathfinder class.
- Flower
- The Sprite that represents the target the Bug is seeking. Its location is set by the Reticle class when the user changes the target's position via the SetTarget property of the InputComponent class.
- Reticle
- The Sprite that represents the player's targetting reticle. It is under the control of the user via the left thumbstick on the gamepad or the arrow keys on the keyboard. When the user selects the SetTarget input, it raises the TargetMovedEvent which notifies the Flower and Bug of the Flower's new location.
- Map
- The game's implementation of the IMap interface. It is responsible for actually drawing the map background and fixed objects when directed by the MapComponent. It is also responsible for keeping track of which tiles are clear and which are blocked by fixed objects. Finally, it provides a number of helper methods that are used by the other classes that need to query the status of map tiles.
Conclusion
That's it! You can download the full source here:
Pathfinding Sample
I tried to make the code as readable and well-documented as possible. If you have any questions, feel free to leave a comment or email me at SwampThingTom at bayougames dot com.
