Archived

This topic is now archived and is closed to further replies.

Question concerning A* algorithm

This topic is 5274 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m not sure if this is appropriate for this forum, but since this issue is causing me great frustration in my general understanding of the A* algorithm, I assumed that this question would be appropriate. My question is specifically concerned with the A* algorithm as implemented by Steve Rabin in his Game Programming Gems (1) essay entitled "(3.5) A* Speed Optimizations." What I have noticed with regards to his algorithm is that he only makes use of GetNodeHeuristic once. I was under the impression (one that I double checked with other implementations of the algorithm) that the estimated cost to goal, what he seems to call the NodeHeuristic, is necessary in order to help guide the A* search in the proper direction. What perplexes me is that in my understanding of the A* algorithm, *at some point* in the algorithm, a node''s estimated cost to goal must be calculated in order to show the A* algorithm the proper direction in which to move - the algorithm does not want to move to a node that actually takes it further away from the goal. However, the cost to goal does not seem to be calculated at all in Mr. Rabin''s code, except for the very first node. My question is this: am I misunderstanding something in Mr. Rabin''s code? Am I missing something in his code? Am I misunderstanding the A* algorithm in general? I''d appreciate any explanation or help that you could give me. Dan

Share this post


Link to post
Share on other sites
You''re understanding of the algorithm is correct in that yes, you need to compute the heuristic cost for each node. Go back to the source code and verify that this is not being done in his implementation. If you feel that this is the case, check out the publishers website for errata and bug-fixes for the code. If there are none, contact the author and ask whether this is a known issue and if a fix exists.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
quote:
Go back to the source code and verify that this is not being done in his implementation.


As far as I can tell, the heuristic cost does not seem to be computed for each node. However, in order to insure that I was not incorrect, I wanted to see if anyone else who had the book might be able to verify my claim.

My concern with the implementation is that when a node is placed on the open list, the "total cost" for that node does not include any sort of cost to goal approximation.

quote:
Are you sure it's not just calling it once per itteration of a recursive function?


There does not appear to be any recursion present in the algorithm.

Also, I have checked the site for errata or bug fixes, but found none for this particular chapter.

[edited by - ares32585 on July 7, 2003 3:05:20 PM]

Share this post


Link to post
Share on other sites
The code on page 285 has a ''while'' loop. This ''while'' loop goes through all the child nodes connected to a parent node. Inside the ''while'' loop is an ''if'' statement that starts out...

if ( bestnode->parent == 0) ||

...and inside that ''if'' statement he sets newnode.total = newnode.cost + GetNodeHeuristic(newnode.location, path.goal)

This is from the original publication. I''m not aware of a revised edition, so you should have the same code.

botman

Share this post


Link to post
Share on other sites
quote:
The code on page 285 has a 'while' loop. This 'while' loop goes through all the child nodes connected to a parent node. Inside the 'while' loop is an 'if' statement that starts out...

if ( bestnode->parent == 0) ||

...and inside that 'if' statement he sets newnode.total = newnode.cost + GetNodeHeuristic(newnode.location, path.goal)

This is from the original publication. I'm not aware of a revised edition, so you should have the same code.


Aha! I do not have that same code. This is that I have instead:

newnode.total = newnode.cost;

That's odd, though. I don't see any mention of this being a second edition of the book or anything...
The ISBN for my book is: 1584500492

I'd go report this to the publisher if I could get on their website, but it seems to be down right now...

[edited by - ares32585 on July 8, 2003 12:42:07 PM]

Share this post


Link to post
Share on other sites
I could give you Steve's phone number... but I don't think he would like that too much. His email should be in the book... shoot him a note... he's cool.

Anyway, are you sure you don't have that line? Mine is on page 286 and the "GetNodeHeuristic" is on a broken line.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

[edited by - InnocuousFox on July 8, 2003 1:06:40 PM]

Share this post


Link to post
Share on other sites
Well, I have sent Mr. Rabin an email at the address listed in his book: stevera@noa.nintendo.com

I just checked the sample code on the CDROM. It, too, has the same error.

Could I possibly have somehow received the wrong version of the book?

I'd also like to thank all of you for taking the time to help me out.

If anyone is willing to take the time, I'd be interested if anyone could email or in some other way send to me the corrected copy of the sample code from the CD for that chapter from the Game Programming Gems book. ares32585@comcast.net

[edited by - ares32585 on July 8, 2003 2:31:24 PM]

Share this post


Link to post
Share on other sites
Ares,

Contact the publisher directly. They will generally replace the copy you have for one that is correct. It is possible that a print run was performed on an earlier version of the text, rather than the final copy. This is really rare in publishing AFAIK, but it does happen (someone sends the wrong version of the manuscript to the printer... it gets printed and then some exec says ''stuff it, we have to sell them to recoup some costs. They''ll never notice''!)

Good luck,

Timkin

Share this post


Link to post
Share on other sites