Jump to content
  • Advertisement


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


a* question

This topic is 6605 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 have found the following pseudo c code for an a* search: priorityqueue Open list Closed AStarSearch s.g = 0 // s is the start node s.h = GoalDistEstimate( s ) s.f = s.g + s.h s.parent = null push s on Open while Open is not empty pop node n from Open // n has the lowest f if n is a goal node construct path return success for each successor n'' of n newg = n.g + cost(n,n'') if n'' is in Open or Closed, and n''.g <= newg skip n''.parent = n n''.g = newg n''.h = GoalDistEstimate( n'' ) n''.f = n''.g + n''.h if n'' is in Closed remove it from Closed if n'' is not yet in Open push n'' on Open push n onto Closed return failure // if no path found My problem is that the top node on the open list is supposed to be the one with the lowest f value. However (as far as I can see), nodes are added to the open list as they are evaluated, which is in the order that the child nodes of a partciular node are determined. i.e. If you have a square based tile map and the you check for child nodes in a clockwise fashion around the parent node the last node you will always evaluate will be the node with x = parent.x - 1 and y = parent.y, assuming you start with the top left hand child node. ------------- You start at 1 and the last child node you / 1 / 2 / 3 / evaluate is 8. ------------- / 8 / / 4 / ------------- / 7 / 6 / 5 / ------------- I can see no provision in the code to make sure that the top node on the open stack is the one with the lowest f value. It seems to always be the last child node you evaluate (in this case node 8 if it is valid and not already on either the closed or open list with a smaller f). Am I missing a really obvious step or implied step here? What am I not seeing?

Share this post

Link to post
Share on other sites
Sorry, that diagram sisn''t turn out like it shoudl have. I''ll try again.

[1] [2] [3]
[8] [ ] [4]
[7] [6] [5]

I hope this one displays properly

Share this post

Link to post
Share on other sites
Hello Phyxx,

I think that, the term
............ "pop node n from Open" .................
doesn''t mean that
"get the top node from Open"

Open is a [priority queue] not a [stack]. There''s a lot of way to implement a priority queue but the most common is using

So, you should understand that term like this :

"search and get the node with lowest f value out of Open"
(remove that node from Open)

Pls show me if I make something wrong.

Best Regards.
Email : dung.dna@extramedia.com

Share this post

Link to post
Share on other sites
DungDNA is right. The container ''Priority Queue'' implies that items are sorted upon insertion (by their priority, hence the name) and therefore the item popped is the one with the lowest f value.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!