HomeEssaysInterviewsProgramsBooksMediaSoftwareHardwareGamesFeatures
Discussion BoardAISolutionsCompetitionEducationProjectsGlossaryLinksSearch
Search:

A* for the Masses

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 Win95 application.

Theory

The theory behind the A* is relatively simple - it is the implementation with all its links and tranversal that gets complicated. Basically, each node (position) on the graph (board) has three main attribute: f, g and h. g is the cost of getting to the point. This is normally the cost of moving a space plus the cost of the parent. h is the distance from the goal - this does not have to be the physical distance (A* has many application - path finding being one). f (I like to use GA-terminology and refer to it as the fitness of the node) is g+h.

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

The maze we will look at is small, but has enough twists and turns to make it a little challenge for the A*. The black lines are impassable, the red square denotes the start (0,0), and the green denotes the end (2,2). Note that in the bottom-right corner there are two grey areas, one darker than the other. These are different cost areas, the darker grey being a higher cost. This will help demonstration back-propagation of lower g-values a bit later on.

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
This is inserted on to the Open list (since we haven't explored any of its child nodes yet), and the process is continued. Thing is, none of the other nodes are valid, so when we pick the best node off the Open list it is this one. The process then continues down the line.

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 longer, but less costly route by going through the light grey area.


  • CPathFinder - A* Path Finder Class breakdown.
  • Game Reviews - All platforms, even PlayStation2!

  • Gaming Essays - Essays on programming game AI.
  • Gaming AI Programs - Windows-based, full source code included.
  • Gaming AI Interviews

  • AISolutions


    All content copyright © 1998-2002, Generation5