I'm reading a section in a book dedicate to pathfinding. It shows the following diagrams: http://img369.imageshack.us/img369/5474/61664125rr0.jpg The bottom part of the image is intended to be the first part of the image with 2 more iterations completed. I can't seem to find out why the bottom diagram is at C. My impression was that A* is supposed to find a path based on a heurisitic, not the shortest path. Well, if that were the case, then the next steps that should have happend (as of the above diagram): 1. Select E to process, as it has the smallest estimated total cost so far out of all the open nodes 2. Once E has been processed, select G to process (since it is now in the open nodes list), as it has the smallest estimated total cost so far out of all the open nodes 3. Nothing to process, so finish with G. So why the hell does the bottom diagram show that C is getting processed after process E was processed? That doesn't make any sense since the LOWEST estimated total cost after E is 4.4 (which is associated with G), not 4.8 (which is associated with C). Am I right or have I just gone bonkers? - Kaz

It looks like the diagram is wrong to me. The heuristic is overestimating the cost to the goal, and as a result A* doesn't find an optimal path in this case.

Is my reasoning correct for WHY it's wrong??

My understanding is that you want to find a path that's okay using the heurisitc, not so much an optimal/minimal/shortest/whatever-you-want-to-call-it path. In this way it is supposed to help reduce the fill of the algorithm? because it considers less nodes out of the entire graph, yet still gives a pretty good result?

It depends on the heuristic. If the heuristic always underestimates the cost, A* is guaranteed to find an optimal path. If the heuristic overestimates, then an optimal path is not guaranteed.

For example, if you set the heuristic to always return 0, you will be simulating Dijkstra's algorithm, which will find the optimal path.

You mean if it under/over estimates in terms of the real total cost?

Regardless. am I right in my reasonings put in my initial post as to why that diagram is wrong????

I think you are correct. The next node to be expanded should be the one with lowest estimated total cost to the goal, and since the goal node has a lower estimated cost it should be expanded before node C.

does the book show (or tell) what is the heuristic function doing? I mainly ask this because the heuristics to the start node is 4.2, which to me sounds dead wrong since the f(x) of the start node should be 0 (at least the way I see it).

As it turns out:

The diagram isn't so much about the heuristic as it is about showing that a closed node can change if it gets encountered again. I showed the diagram to the author and he confirmed that C shouldn't have been accessed and that it should have gone straight to the goal node.

Trust me... as I finish up the last 2 chapters on my book on game AI, you would not believe how much of a pain it is to keep the text, formulas, images, and code all in sync as you putz around with examples.

*sigh*