So, how do you get your player from point A to point B without falling off a cliff or climbing over too many mountains? Answer, A*
The A* (A-star) search algorithm is used for path finding, the system of finding the
least cost route from one point (node) to another. A* is said to be
optimal, by that we mean that it finds the best available path, at the lowest cost, every time.
Method
The basic idea behind A* search is the maintaining of two lists, an
Open list (or Fringe) and a
Closed list. The open list contains a list of nodes that you want to look at but haven't yet examined (expanded) whilst the Closed list contains a list of examined nodes.
The process is simply to remove the node from the Open list which has the least cost and add it to the Closed list. The search finishes with a solution when the target node is removed from the Open list. If the Open list ever becomes empty then no solution is possible..
Walk through
Let's work through a few simple examples of A* search.
We start with the following problem. We need to get from the start position, S, to the finishing point at F. The red squares at g & k are blocked and cannot be passed through. What is the best route for us to take?
The first thing we must do is add the starting node, 'e', to the Open List. Now we choose the node from the open list with the least cost. Since this is the only node currently on the Open list we remove it and add it to the closed list.
Now, we expand this node. This means looking for all possible next steps from here. This is illustrated in diagram to the left. The current node is in blue and it's possible next steps are in green.
These next steps are called it's
successors. The successors (a,b,f,i,j) are added to the Open list. We must now calculate a score, or cost, for each one.
Cost calculation
In A* the cost (F) of a node is made up of two separate parts. The actual cumulative cost to get here along the current path from the starting point (G) plus the estimated cost of getting to the target from here (N).
In this example when calculating G cost we'll say that all moves have a cost of 1. In other situations though this will not always be the case. For instance, if you wanted your player to move better over grasslands than hills, you would change the value of G depending upon the type of land being crossed. Increasing G for hills and decreasing it for grasslands. This will make your player prefer grasslands to hills. Depending on how much you penalise the cost of travelling over hills you may see that your player will choose to go a longer, but cheaper, way over grasslands rather than a shorter, but much more costly, path over hills.
The estimated cost (N) is referred to as the heuristic. The way you calculate the heuristic cost is up to you but in this simple case the best way is to use a measure called the 'Manhattan' distance from the node to the target. This is simply the number of rows plus the number of columns to the target. In this example the N cost for the node 'a' would be 5; 3 columns across plus 2 rows down.
| NODE |
G |
N |
F |
parent |
| a |
1 |
5 |
6 |
e |
| b |
1 |
4 |
5 |
e |
| f |
1 |
3 |
4 |
e |
| i |
1 |
3 |
4 |
e |
| j |
1 |
2 |
3 |
e |
This ends the first loop through the algorithm. At this stage the closed list contains 'e' whilst the open list looks like this.
Notice how we also add a note of each node's parent. This allows us to find a way back from the target node to the start
To continue, we repeat the process. Choose the least-cost node from the open list 'j', add it to the closed list and then expand it's successors. This results in the below Open list. The Closed list now contains 'e' and 'j'.
| NODE |
G |
N |
F |
parent |
| a |
1 |
5 |
6 |
e |
| b |
1 |
4 |
5 |
e |
| f |
1 |
3 |
4 |
e |
| i |
1 |
3 |
4 |
e |
| m |
2 |
4 |
6 |
j |
| n |
2 |
3 |
5 |
j |
| o |
2 |
2 |
4 |
j |
Choosing the cheapest node here poses a problem as we have three nodes with a cost of 4 (f, i and o). The method you choose to split ties has an effect on the performance of the algorithm. Here I'm going to use a Last-In First-Out (LIFO) method. This means that I'll choose the node that was added to the list last, in this case 'o'. So, we add 'o' to the closed list and expand it.
| NODE |
G |
N |
F |
parent |
| a |
1 |
5 |
6 |
e |
| b |
1 |
4 |
5 |
e |
| f |
1 |
3 |
4 |
e |
| i |
1 |
3 |
4 |
e |
| m |
2 |
4 |
6 |
j |
| n |
2 |
3 |
5 |
j |
| p |
3 |
1 |
4 |
o |
| l |
3 |
0 |
3 |
o |
Notice at this step that node 'j' was not re-added to the Open list. This is because it is already on the Closed list. Closed nodes are never re-added to the open list. Also, notice that node 'n', which was already on the list, was a successor of 'o'. This node was left, unaltered, on the Open list. However, if the cost of reaching 'n' via 'o' was less than the current cost of getting to 'n' then we would update n with the new, lower, cost and change it's parent to 'o'.
Finally we can see the target node ('l') on the open list. However the search is not finished. Only when the target node is removed from the Open list and added to the closed list is the search complete. This takes one more iteration of the loop.
| NODE |
G |
N |
F |
parent |
| e |
0 |
4 |
4 |
-- |
| j |
1 |
2 |
3 |
e |
| o |
2 |
2 |
4 |
j |
| l |
3 |
0 |
3 |
o |
The Closed list now contains 'e', 'j', 'o' and 'l' and looks like so.
By starting at the target node 'l' and following the parent nodes back to the start we get the following solution
e > j > o > l
This is the cheapest cost way of getting from 'e' to 'l'.
See here for a
slightly more difficult A* search problem . This second problem shows how A* can backtrack when finding it's path blocked.
SUMMARY
To perform A* search we follow this procedure:
- Select the cheapest node from the Open list and add it to the Closed List
- Expand all child nodes of the currently selected node.
- If a child node is already on the Closed list then ignore it.
- Calculate new G, H and F values for each child.
- If a child can be reached at less than it's current cost via the selected node then update it.
- Repeat until target node is removed from Open list or Open list becomes empty.
To see A* in action go over to the post on my
Isometric Strategy game and watch the video. Here you can see the player manoeuvre around the map avoiding obstacles such as mountains and preferring flat grasslands rather than hills.
A*, in this example, is simply finding the shortest path from A to B. More generally though A* is finding the best way to get from one
State to another future
State. You can think of a state as a snapshot containing all relevant information about how the world is now. The available
actions taken at each step can be large, not just the simple 8 directional choices in this example. This is where the full usefulness of A* comes into effect. A* is used in applications such as path-finding functions, computer games, resource planning problems, language analysis, machine translation and speech recognition.
