Archive for August, 2008

A* (astar) Pathfinding

Finally I am getting around to the A* post I promised more than a year ago. Better late than never I guess 🙂

A* is a state change optimization algorithm. It looks at a system in its current state and determines the lowest cost series of state changes needed to arrive at a target end state. Most commonly A* is used for pathfinding. I have never seen A* used for anything but pathfinding, but you could use it to do things like solve a Rubik’s cube or a picture slider puzzle.

Here is how it works. First, your map needs to be tile-based. A* will take a starting point and a target destination, run its logic, and kick out the lowest cost path to that destination tile. In most A* implementations that I’ve seen lowest cost means shortest distance.

I’ve mentioned cost a few times now. Let me explain what this means. When you want to get a path from point A to point B you probably want the shortest path right? Well, what if that short path takes you through a river? Or through a fire? You’d probably want to the shortest path around that water or fire. But if the path around those things gets to be way too long, then maybe going through the water or fire isn’t such a bad idea anymore.

What cost does is assign a value to the act of moving from one tile to another. Those tiles have a terrain associated with them, such as grass, water, or fire. The cost of moving from grass to grass would be low because that is something you’d like to do. The cost of moving from grass to water would be a bit higher because you don’t want to get wet, but not extremely high because getting wet won’t kill you. The cost of going from grass to fire would be extremely high because fire is dangerous.

Here are some example terrain transition values:
grass-to-grass = 1
grass-to-water = 10
grass-to-fire = 100000000000

The cost of moving from one tile to another is determined by multiplying the distance between the two tile centers by the terrain transition value. Since the tile size is consistent through the entire map you can just assume that tiles are 1-by-1 for cost calculation. Horizontal or vertical transitions are a distance of 1. Diagonal distances are the square root of 2, which is 1.414.

The algorithm
During the search each tile that is touched is assigned a total score called ‘f’.
f = g + h

f -the total score
g – the total transition cost of all tiles touched along a path up to this current tile
h – the total estimated cost from the current tile to the destination

The h value is called the heuristic. It is what allows A* to start looking in the right direction from the moment it starts its search. If h was set to always be zero, then the search would expand radially from the start node. This heuristic allows it to start moving in what is probably the correct direction.

What the algorithm does is this:

  • Starts at the current tile and puts all of that tile’s neighbors into an array and stores their f value. The act of doing this (storing tiles with total cost in an array) is known as expanding the tile.
  • That array is sorted based on f.
  • The lowest f tile is grabbed and expanded.

This process continues until the goal node is reached. By the very nature of the algorithm, the first time the goal tile is touched you have found the the lowest cost path. There is more to the algorithm than shown above, but that is the main idea.

What I think is so cool about A* is the terrain stuff. If you take the time to use actual terrains and assign appropriate transition costs, then you can get realistic paths that look like an intelligent creature would have walked.

In the demo below you’ll notice that you can click on either side of the water and the path will usually take you over the bridge. But, if you go far enough away from the bridge then the path starts to take you through the water instead. If in your game your character should never go through the water, then you’d crank up that cost.

I put in a little editor UI so you can try making your own simple maps to test the pathfinding.

Just click once to add a start position, and again to add a target position. The path will automatically be calculated. To do it again, just click and the path will reset. (Beware of Trogdor. He is burninating the country side!)

Download Source

click to view example

Some final notes
Code improvements
The source code is set up well with a separate package for A*. It is reusable. We’ve been using it across many projects for more than a year. The search time in general is not a problem. But, if you wanted to significantly improve it you can implement a true priority queue. I put in a poor man’s priority queue – an array that is searched every time we do an insert.

Intended usage
While pretty fast, this algorithm isn’t blazing. It isn’t intended to handle real-time continual path updates. So if you have baddies running around looking for people to slaughter, A* isn’t the best way for them to seek and destroy. A* is generally meant to be used rarely (no more than once or twice a second.)

The heuristic estimates the cost from the current tile to target tile. It doesn’t use terrain or walls when making this guess. So, if there is big concavity between the current tile and the target tile, A* might waste a lot of time going toward the target only to hit a wall, back track, and then eventually find the true best path. In my experience this does not prove to be an issue. In general the paths to be generated are on the order of 5 to 15 tiles and not massive.


Read Full Post »