Archived

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

a* question

This topic is 6383 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
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
[HEAP].

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.
DungDNA
Email : dung.dna@extramedia.com

Share this post


Link to post
Share on other sites