Sign in to follow this  
Anidem

A* Troubleshooting

Recommended Posts

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

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!

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.h



It 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]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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...

(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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this