• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# 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.

3 replies to this topic

### #1Phyxx  Members

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?

### #2Phyxx  Members

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

### #3dungdna  Members

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

### #4Kylotan  Moderators

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.