Question concerning A* algorithm

ares32585 · 2003-07-08T22:50:23

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

Artificial Intelligence Programming

Started by ares32585 July 06, 2003 11:18 PM

11 comments, last by ares32585 20 years, 9 months ago

ares32585

121

Author

July 08, 2003 01:30 PM

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]

fup

463

July 08, 2003 02:19 PM

That is truly bizarre. You can get steve at this address nowadays:

steve@aiwisdom.com

fup exits to the theme of the Twilight Zone...

My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

My Website: ai-junkie.com | My Books: 'Programming Game AI by Example' & 'AI Techniques for Game Programming'

Timkin

864

July 08, 2003 10:50 PM

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

Question concerning A* algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Question concerning A* algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines