🔒 Locked

A* Troubleshooting

Started by Anidem Mar 26, 2006 at 11:57 AM 5 replies 1.7k views

Original Post

Mar 26, 2006 at 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...


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

Timkin

Mar 26, 2006 at 6: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

Anidem

Mar 26, 2006 at 6: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.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]

Anidem

Mar 27, 2006 at 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?

Timkin

Mar 27, 2006 at 7: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...

(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

Anidem

Mar 30, 2006 at 9: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.

Kylotan

Apr 1, 2006 at 9:22 AM

Properly implemented, A* will find the best path that exists, so yes.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.