a* question
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?
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
[1] [2] [3]
[8] [ ] [4]
[7] [6] [5]
I hope this one displays properly
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement