Jump to content

  • Log In with Google      Sign In   
  • Create Account


a* question


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Phyxx   Members   -  Reputation: 138

Like
Likes
Like

Posted 19 June 2000 - 12:28 PM

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?

Sponsor:

#2 Phyxx   Members   -  Reputation: 138

Like
Likes
Like

Posted 19 June 2000 - 12:35 PM

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

#3 dungdna   Members   -  Reputation: 122

Like
Likes
Like

Posted 19 June 2000 - 10:49 PM

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


#4 Kylotan   Moderators   -  Reputation: 3325

Like
Likes
Like

Posted 19 June 2000 - 10:53 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS