'Move in the direction we seek
tmpNode.x = curNode.x - 1
tmpNode.y = curNode.y
'Determine if this tile is walkable
If lngMap(tmpNode.x, tmpNode.y) = 0 Then
'Determine if this node is on the closed list
If Not clsClosed.MemberOf(tmpNode) Then
If Not clsOpen.MemberOf(tmpNode) Then
'Update the parents
tmpNode.parentx = curNode.x
tmpNode.parenty = curNode.y
'Update the heuristics
tmpNode.g = curNode.g + 10
tmpNode.h = (Abs(tmpNode.x - nGoal.x) + Abs(tmpNode.y - nGoal.y)) * 10
tmpNode.f = tmpNode.g + tmpNode.h
'Add the node to the open list
clsOpen.Add tmpNode
Else
'Set them equal
tmpNode2 = tmpNode
'Update the parents
tmpNode2.parentx = curNode.x
tmpNode2.parenty = curNode.y
'Update the heuristics
tmpNode2.g = curNode.g + 10
tmpNode2.f = tmpNode.g + tmpNode.h
'Determine if this is a better route
If tmpNode2.g < clsOpen.GetData(tmpNode).g Then
clsOpen.SetData tmpNode2, tmpNode
'Sort the list to make up for the changes
clsOpen.Sort
End If
End If
End If
End If
A* Troubleshooting
March 26, 2006 11:57 AM
Ok, so I'm making a pathfinder in VB. I'm having trouble finding complex paths (that do exist) and getting the shortest path to them (sometimes my pathfinder will make unnecessary trips). I think the problem is in the code where I search in four directions. Maybe I didn't understand what to do correctly, but here is what I am doing...
I think the problem comes when I check if a node lying on a different path has a lower g value then the one already on the open list. But I've seen many articles using many different ways of accomplishing this. I don't want anything fancy yet, just to make sure that it finds any path that exists. Maybe someone could just tell me in pseudocode what to do in the direction search. By the way thanks!
864
March 26, 2006 06:08 PM
Quote: Original post by Anidem
'Set them equal
tmpNode2 = tmpNode
...
'Determine if this is a better route
If tmpNode2.g < clsOpen.GetData(tmpNode).g Then
clsOpen.SetData tmpNode2, tmpNode
My VB is pretty much nonexistent, but if I read this correctly, you've first assigned tmpNode to tmpNode2 and then asked if they have different path costs from the root node. If that's what you've done, then this will cause you problems.
Cheers,
Timkin
March 26, 2006 06:43 PM
Quote: Original post by Timkin
My VB is pretty much nonexistent, but if I read this correctly, you've first assigned tmpNode to tmpNode2 and then asked if they have different path costs from the root node. If that's what you've done, then this will cause you problems.
Cheers,
Timkin
the thing is, I just set them equal so that their x, and y are the same then I update them...
'Update the parents
tmpNode2.parentx = curNode.x
tmpNode2.parenty = curNode.y
'Update the heuristics
tmpNode2.g = curNode.g + 10
tmpNode2.f = tmpNode.g + tmpNode.h
Then I check to see if they have a lower cost. Now I'm not totally sure that that makes a whole lot of a difference. Because when I debug the lower f-cost decision never runs. So how can I handle this different?
[Edit]
I may have found the error. But it might have just been a typo when I wrote this message. In this code what Timkim said was right. I'm effectivly comparing the same two things. But if I update the code to
tmpNode2.g = curNode.g + 10 tmpNode2.f = tmpNode2.g + tmpNode2.hIt might work. I'll have to go home and test it.
Although I'm still not sure if I'm supposed to be comparing the f or g values. And this is only for the open list. Would I ever take something off the closed list and put it back on the open?
[Edited by - Anidem on March 27, 2006 9:43:02 AM]
March 27, 2006 12:27 PM
Ok, yes, I had made that mistake. But it still doesn't completely find all paths. For some reason, not all objects placed on the open list are explored. Perhaps A* at it's most simplist doesn't find complex paths that do exist?
864
March 27, 2006 07:43 PM
You should not expect all nodes in the open list to be explored (that is, expanded to find successor nodes). It will always have nodes left over in its open list that it did not explore. However, A* is optimally efficient, which means that it will find the optimal path (under certain constraints about the cost function) and expand less nodes than any other graph-based algorithm on the same problem, so don't be worried by not searching them all.
Your comparison of nodes should be something like...
Your code should be able to achieve the same thing, even though you may do it differently. One point... in most domains, you should not find yourself having to splice into the closed list... but don't be alarmed if you do... it's because of unusual properties of the cost function... the cost of testing for this far outweighs the problems caused by ignoring this possibility and makes for a far more general A* implementation.
Cheers,
Timkin
Your comparison of nodes should be something like...
(1) Test if node is in closed list if it IS in closed compare 'g' costs of these two nodes if the new node has a lower 'g' cost set child of parent of old node to null set the children of the old node as the children of the new node update the cost of all nodes in the subtree below the new node delete the old node (and store the new node in closed list in its place)(2) Test if node is in open list if it is NOT in open then insert it into open list go to making next successor node (or remove best node from list and expand it) else compare 'g' cost of these two nodes if the new node has a lower 'g' cost set child of parent of old node to NULL (cut out old path to node) delete the old node insert new node into open list (ordered insert) else delete the new node (its not needed)Your code should be able to achieve the same thing, even though you may do it differently. One point... in most domains, you should not find yourself having to splice into the closed list... but don't be alarmed if you do... it's because of unusual properties of the cost function... the cost of testing for this far outweighs the problems caused by ignoring this possibility and makes for a far more general A* implementation.
Cheers,
Timkin
March 30, 2006 09:59 PM
Wow, thanks Timkin. Just implemented it, works great!
Let me ask you this though, will A* always find a path that exists (regardless of complexity like mazes)? I think the problem is, I havne't updated the subnodes, but I have yet to devise a way to do that.
Let me ask you this though, will A* always find a path that exists (regardless of complexity like mazes)? I think the problem is, I havne't updated the subnodes, but I have yet to devise a way to do that.
April 01, 2006 09:22 AM
Properly implemented, A* will find the best path that exists, so yes.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
