• Contribute
• What's New
• Submit News

This case study will introduce and demonstrate the A* algorithm working as a path finder in a simple maze. There will be a brief discussion of the theory of the A* algorithm, but most of the work will be done along side the maze solving. This essay accompanies the CPathFinder class and A* Demonstrator (now replaced by A* Explorer).

Theory

There are also two lists, Open and Closed. On the open list is all the nodes that have not been explored. By explored we mean all the adjacent positions have been opened (also moved on to the Open list), or cannot be opened. On the closed list are all the nodes that have been explored.

The aim of the game is to start at your destination, generate all the valid children and assign each of them their F,G and H scores. Now, select the best Open node and do the same. Keep on doing this until you get to your destination! Life would be simple if the nodes were all unique - but they are not, since (1,1) is adjacent to (1,0) and (1,0) is also adjacent to (1,1)! Therefore, when we generate our list of children we must do two checks - check whether the node is on the Open list, and check whether it is on the Closed list.

If we find the node on either of these lists, we check whether the path would be easier to follow if it came through the node we are checking. If it is, and the node is on the Open list, then it is merely a case of updating the values of the Open listed node. If the node is on the Closed list, then we have to change the value and propagate the changes back through the graph since this affects not only this node, but all of its parents.

I know this seems very confusing at first - it will take a while for the logic of it all to sink in. The following is an example to hopefully help you understand the algorithm. The best way is to look at the CPathFinder class that I wrote. Everything looks so much simplier as code for once!

Example: The Maze

Now, during the first couple of iterations we find the only the square that is open is the one directly beneath us. We therefore have no choice but to travel there. In fact, this happens right down the line - despite the 'fitness' of the node increasing and increasing (as distance increases). Nevertheless, let us look at the calculations are are taken. For the first loop, only (1,0) is open, so we create a node there - and the values are initialized:

	G:	1 + board value (0) = 1
	H:	(2-0)*(2-0) + (2-0)*(2-0) = 8
	F:	G + H = 9

Now, imagine that the algorithm continues down the initial line, from (0,0) to (0,19). Now, backtrack a little. When the algorithm assesses (0,18) which node do you think it would pick to move to next? (1,19) is the best since it is closer to the goal point than (0,19). It also involves less tiles in the long run. So, we are now assessing (1,19). During this time, we assess (0,19) again, since it is still an adjacent square. (0,19) is still on the Open list from when (0,18) assessed it. So, when the algorithm comes to check for (0,19) it finds the node on the Open list, and then adds it to its list of children. It then checks to see whether it would benefit by moving through (0,19) - it doesn't, so things are left alone.

After (1,19) has been fully assessed, (2,18) is chosen as the next best node to move to. This generates another scenario the algorithm needs to deals with. (2,18) assesses the nodes around it and finds that (1,19) is not on the Open list, but is on the closed list (all (1,19)'s child nodes have been put on the open list). It therefore adds it to its list of children and continues on its merry way since it would not benefit by going back through (1,19).

We will allow the algorithm to run for a little while. Another scenario arises soon though, at (3,5). When the algorithm assesses (3,5) it finds (4,4) on the closed stack. What it also finds is that its g-value is higher than its predicted g-value would be if the path went via (3,5). In short, this means that either a high-cost path had been explored, or simply more nodes were transversed to get to (4,4) than was necessary. We therefore update the node accordingly, and then propagate this change down its children. Luckily, in this case, none of the children required propagation.

A case arises later on when a huge propagation is required - at (21,15) it is found that by going through (22,16) a saving of 16 can be made (G(21,15) = 94, G(22,16) = 78). The intuitive reader can propagate the changes backward if they wish!

Finally, the algorithm zooms around the squiggly area, up and over and reaches its goal. Notice that the algorithm would chose to take the less costly route by going through the light grey area instead of straight through the dark-gray area.

Applying the A* to Other Problems

Think of it like this: given the initial state, there could be up to 4 moves (move a tile down into the space, up, left or right). Therefore, you have 4 possible moves, for the game tree branches into 4 sections. Now there are 3 moves (obviously one of these moves is stupid, since you'd be back to the start) for each of the 4 nodes, so we now have 17 game states (1 + 4 + 12). This continues until a final state is found. Although 17 states seems quite manageable, it soon grows out of proportion. Assume that each position can generate 3 positions:

                17 total states
12 * 3  = 36    53
36 * 3  = 108   161
108 * 3 = 324   485