If diagonal movement is not permitted, and the manhatten method is used for calculating H. Will this ever occur... "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."

Yes.

If you don't have obstacles or differing terrain costs... No.
If you have obstacles or differing terrain costs... Yes, it's possible.

Dang, I left out a very important detail. [dead]

I don't have differing terrain costs, but I do have obstacles...

I'm gonna assume the answer is still yes... thanks.. [smile]

Even without different tile costs it can happen.



Even though Path A is obviously shorter, the estimate for tiles X and Y are exactly the same(12), so if your queue happens to pop out tile Y first, it will put in the open list the tile to it's left, and when X is poped out it will have to update that tile's cost.

In short, if you have a uniform cost function over state transitions and you always expand the node with the lowest combined path+heuristic cost AND your heuristic is admissible, then NO, it will never happen.

This scenario only ever happens (splicing a subtree) where you discover a new path to a leaf or branch node that has a lower cost from the root node, or where by considering the leaf node as a child of a new parent, the heuristic estimate drops significantly from the estimate of the parent node. If you have a good heuristic, this shouldn't happen.

Regards,

Timkin

I don't get it then, in the image i posted above i consider all tiles to have the same cost, the queue to allways return the tile with the lowest cost and the heuristic to be admissible, yet it seems to represent a situation where a node cost initially put in the open list would need to be updated.

Did i miss something?

Quote:Original post by xor
I don't get it then, in the image i posted above i consider all tiles to have the same cost, the queue to allways return the tile with the lowest cost and the heuristic to be admissible, yet it seems to represent a situation where a node cost initially put in the open list would need to be updated.

Did i miss something?

If you expanded Y first, then yes, you would contrive a situation in which the parent of Y's successor would need to be set to X, since subsequentyly expanding X would reveal a lower total cost to achieve the next node. While in theory you may expand either of two nodes with equal total cost in any order, in practice one always expands the one with lower path cost to the node from the root node (which necessarily has a higher heuristic estimate), specifically so you don't have this situation arise. The reason for this is the very example you contrived (a nice example by the way). If you have two nodes with identical total cost and a common child node, the parent with the lower cost from the root will always lie on the lower cost path through that child to the goal (assuming uniform node transitions of course).

Reading back on my previous statement, I did leave the door open for this confusion, since I didn't mention this bias on node expansions where the costs are equal. My apologies.

I wasn't aware of that pratice.
Thank you for clearing that up Timkin, as allways a big help. [smile]