I am writing a fairly simple top-down, 2D game. It uses a uniformly distributed 2D tile grid for all collision data. Each tile in the grid is either solid or empty.
To find the way, I use A * (A Star) and tried the heuristics of Manhattan and Diagonal (aka Chebyshev).
It works well in most cases, but it becomes quite expensive when trying to find a path to a target sitting in a concave recess (for example, in the shape of U).
For example, in the picture below, the guy on the right will look for the path to the guy on the left. All grass (green, dark green and yellow) is an empty place. The only solid slabs are brown “wood” tiles and gray “stone” tiles forming the shape of the side “U”.
Now here are the search results for the path (in this case A * with the Manhattan heuristic):
Red and green drawing sketches show which tiles were visited during A * search. Red is in the Closed list, and green is in the Open list (according to A * specifications). The blue line in the final path is selected (which is correct).
As you can see, the search was pretty comprehensive, visiting a lot of tiles, creating an almost perfect circle.
I understand why this is based on the A * algorithm, and my selected heuristics (as you move past the target along the wall, the tiles in the distance begin to have higher F values, causing them to be examined before returning to the correct path). I don’t know how to do it better :)
Any suggestions for possible improvements? Perhaps another heuristic? Maybe a different path finding algorithm all together?
Thanks!
Based on some suggestions, I tend to upgrade my A * implementation to include the improvements found in HPA * . Based on some initial reading, it seems that he will look at cases like the above quite well, given the right amount of detail in the hierarchy. I will update as soon as I finish studying this.