Hi all, Hopeing someone might be able to send some light on this. I've implemented and A* solution, working on a basic 2D grid. For the most part it seems to work fine. But for a few ocassions, where it calcuates the values of G, H and F correctly, but the F score results in the wrong parent cell being chosen on the next iteration. Then it gets stuck. Here is a diagram of what is happening http://www.mxnet.f2s.com/AStarProblem.JPG. Green is the start and end points. Grey is are the cells that are being correctly selected. Red where the failure starts. Blue is unwalkable. Cells 15,13 and 14,13 both have as a parent 14,12. After 15,13 is selected I would expect 15,14 to be selected. I prevent the alg from cutting corners. If I allow it to cut corners it works ok. Just can't see what this fails. All it's really doing is delaying the inclusion of a cell with is on a diagonale with unwalkable space until T+1. Thanks for any thoughts. Can upload code if req. Mark

You really need to show what values for F and G are being yielded. Without that, it could be making the right choice for all we know. It doesn't look necessarily wrong to me. (15,14) is closer on the Y axis but further on the X axis than (14,13), and (14,13) will have had less cost to travel so far.

Remember that A* isn't expected to unerringly choose one right step after another and another until it reaches the goal. It is expected to explore alternatives which you may think are clearly wrong, but will still yield the correct path in the end. The heuristic helps it spend as little time as possible on exploring the incorrect branches but they still have to be explored.

Just thought I'd let you all know I found the problem. Not reading the alg spec properly :) My finding the lowest scored cell on the open list was restricting it to the lowest scored cell next to the current parent - not necessarely the actualy lowest cell. Modded the code and all works as expected :)

Cheers

Mark