Is A-star guaranteed to give the shortest path in a 2D grid
I am working with A-star algorithm, whereing I have a 2D grid and some obstacles. Now, I have only vertical and horizontal obstacles only, but they could vary densely.
Now, the A-star works well (i.e. shortest path found for most cases), but if I try to reach from the top left corner to the bottom right, then I see sometimes, the path is not shortest, i.e. there is some clumsiness in the path.
The path seem to deviate from the what the shortest should path should be.
Now here is what I am doing with my algorithm. I start from the source, and moving outward while calculating the value of the neighbours, for the distance from source + distance from destination, I keep choosing the minimum cell, and keep repeating until the cell I encounter is the destination, at which point I stop.
My question is, why is A-star not guaranteed to give me the shortest path. Or is it? and I am doing something wrong?
Thanks.
Answer
A-star is guaranteed to provide the shortest path according to your metric function (not necessarily 'as the bird flies'), provided that your heuristic is "admissible", meaning that it never over-estimates the remaining distance.
Check this link: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
In order to assist in determining your implementation error, we will need details on both your metric, and your heuristic.
Update:
OP's metric function is 10 for an orthogonal move, and 14 for a diagonal move.
OP's heuristic only considers orthogonal moves, and so is "inadmissible"; it overestimates by ignoring the cheaper diagonal moves.
The only cost to an overly conservative heuristic is that additional nodes are visited before finding the minimum path; the cost of an overly aggressive heuristic is a non-optimal path possibl e being returned. OP should use a heuristic of:
7 * (deltaX + deltaY)
which is a very slight underestimate on the possibility of a direct diagonal path, and so should also be performant.
Update #2:
To really squeeze out performance, this is close to an optimum while still being very fast:
7 * min(deltaX,deltaY) + 10 * ( max(deltaX,deltaY) - min(deltaX,deltaY) )
Update #3:
The 7 above is derived from 14/2, where 14 is the diagonal cost in the metric.
Only your heuristic changes; the metric is "a business rule" and drives all the rest. If you are interested on A-star for a hexagonal grid, check out my project here: http://hexgridutilities.codeplex.com/
Update #4 (on performance):
My impression of A-star is that it staggers between regions of O(N^2) performance and areas of almost O(N) performance. But this is so dependent on the grid or graph, the obstacle placement, and the start and end points, that it is hard to generalize. For grids and graphs of known particular shapes or flavours there are a variety of more efficient algorithms, but they often get more complicated as well; TANSTAAFL.