Hi, I am trying to implement an A* pathfinding algorithm and it already works quite good. However, I want to improve it, and in the A* tutorial from http://www.policyalmanac.org/games/aStarTutorial.htm, it says the following:

quote: c) For each of the 8 squares adjacent to this current square … [...] If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

I don''t completely understand the last paragraph... it tells me to check if the path is better using G cost as the measure. Which G cost should I calculate? The cost of my "current square" or the cost of the adjacent square? Thanks for your help in advance!

You should be using/calculating the G-Cost of the adjacent square

Sounds like you are using the Recycle Redundant nodes approach to A*.

I''ll try to explain it best I can.

During an A* search you typically have nodes in either the open or the closed list, indicating whether they should not be evaluated again, or nodes "to be evaluated". I''m sure you understand that if you got this far.

It is very possible, and quite frequent, that when you are creating a new node around the "current node" that it has been created before, but not only that, the new cost of this node is better than the cost of when it was last considered. By coming at the node from a different direction it might be a better path to that particular node than the path that last had that node part of it. Hope that makes sense. But anyways, basically if this new path to that node is better than the last one, update the node over again, and resort your open list, or remove and re-insert it back into the open, depending on whether it is in the open or closed.

Thanks for the explanation. I think that I''ve now understood it, and although my pathfinding code still contains a bug (the parent relations aren''t ok, one tile isn''t the neighbour of another one), I think that I''ll be able to solve the problem. Thanks again!

quote: Original post by DrEvil
basically if this new path to that node is better than the last one, update the node over again,

I would hope that by this you mean remove the old version of the node from the open list and replace it with the new version of the node, remembering to update the appropriate child of the parent of the old version to the new version.

Furthermore, you must also consider this issue in your closed list. It is entirely possible with A* that you will create a new node that overlies a node in your state space that you have already moved to your closed list. In other words, you''ve created a loop in your tree. In this case, if the cost of the new node is lower than the cost of the old, closed node, you need to graft the new node into the tree, update parent and child relationships AND THEN run through the subtree under this node and recompute the costs of all nodes in the subtree.

I hope this helps.

Cheers,

Timkin

Yes, update the parent and given cost and re-insert it into the open list, which would mean removing it from the open or closed first depending on which it was in and re-inserting. Thats what I do in my implementation, since I have a smart insert function that inserts into the list based on its final cost. If you have a function that sorts the entire list you should just be able to update the parent, given cost, and sort the open list again(assuming it was in the open list), if it was closed list you will have to remove it from closed and reinsert to open.

quote: Original post by DrEvil
if it was closed list you will have to remove it from closed and reinsert to open.

That''s a very inefficient way of handling this scenario. Rather than removing the node from the closed list, adding it to the open list (and presumably then ignoring all nodes below the old node in the search tree), you simply replace the node in the closed list with the new node and traverse the subtree under the old node, updating costs given the new path cost to the new node in the closed list. Make sense?

Timkin