• ### Announcements

#### Archived

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

# Question concerning A* algorithm

## Recommended Posts

ares32585    121
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 on other sites
Timkin    864
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 on other sites
Are you sure it''s not just calling it once per itteration of a recursive function?

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

##### Share on other sites
ares32585    121
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 on other sites
botman    122
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 on other sites
I wish I would open this thread when I''m at the office instead of home so I can flip the book open. *sigh*

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

##### Share on other sites
ares32585    121
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 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 on other sites
ares32585    121
Here''s what my page looks like:

##### Share on other sites
Yours is hosed.

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

##### Share on other sites
ares32585    121
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 on other sites
fup    463
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

##### Share on other sites
Timkin    864
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