Jump to content
• Advertisement

# A* Troubleshooting

This topic is 4492 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## 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 &lt; 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

##### Share on other sites
Advertisement
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

##### Share on other sites
Quote:
 Original post by TimkinMy 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?

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

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

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

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

##### Share on other sites
Properly implemented, A* will find the best path that exists, so yes.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
17
5. 5
• Advertisement

• 14
• 11
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
631756
• Total Posts
3002110
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!