quote:Original post by Samith
Timkin: If I'm following you correctly, you are telling me I need to check all neighboring nodes to see if their g costs are lower, otherwise it won't find the fastest path.
Err, no, I don't believe I was saying that... but then I'm not sure what you're saying here... so I can't be certain that I wasn't saying what I think you thought I was saying. Confused? I am!
Anyway...
What I was saying was that assume you are expanding child nodes from your current node and it happens that one of these new nodes already appears in your closed list. This is a common problem with searches on regular grids/lattices. You've computed the path cost of that child node through its parent and find that this is a lower cost for that node than the path cost listed for that node in the closed list. This can happen because these two instances of the same node have different parents, representing different paths to this node. You need to decide which path to keep. Obviously you go with the path with the lower of the two costs. IF that happens to be the new node you generated, you need to look at the subtree below the node that is in the closed list, because you're about to tell that entire subtree that to get to the subtree, you need to go through a different parent node (the parent of the newly generated node, not the old one in the closed list). Since getting to the current node costs less than getting to the node in the closed list, then all the costs in the subtree below the old node need to be updated... AND, you need to tell each of the children of the old node that their parent is now the new node. This operation is called splicing. Essentially you've disconnected the subtree from the old node, stuck it under the new node, updated the subtree costs and deleted the old node (because we don't need it any more).
I hope this makes sense.
Cheers,
Timkin
[edited by - Timkin on June 2, 2004 3:31:24 AM]