How to optimize A* (AStar) Search for Concave Shapes? (includes screenshots)

Question

I am writing a fairly simple top down, 2D game. It uses an evenly spaced 2D grid of tiles for all collision data. Each tile in the grid is either solid or empty.

For path finding I am using A* (A Star), and have tried both Manhattan and Diagonal (aka Chebyshev distance) heuristics.

It works well in most cases, but becomes quite expensive when trying to path find to a target sitting in the recess of a concave shape (eg. a U shape).

For example, in the picture below, the guy on the right will path find to the guy on the left. All the grass (green, dark green and yellow) is empty space. The only solid tiles are the brown "wood" tiles, and grey "Stone" tiles, making the shape of a sideways "U".

Now here is the results of the path search (in this case A* with Manhattan Heuristics):

The red and green debug draw squares show which tiles were visited during the A* search. Red are in the "Closed" list and green are in the "Open" list (as per A* specifications). The blue line in the final path chosen (which is correct).

As you can see, the search has been fairly exhaustive, visiting lots of tiles, creating an almost perfect circle.

I understand why this is happening based on the A* algorithm, and my chosen heuristics (as you move passed the target along the wall, the tiles further away begin to have better F values, causing them to be explored before coming back to the correct path). What I don't know is how to make this better :)

Any suggestions on possible improvements? Possibly a different heuristic? Maybe a different path searching algorithm all together?

Thanks!

---

Based on some suggestions, I am leaning towards updating my A* implementation to include the improvements found in HPA*. Based on some initial reading, it seems that it will address cases like the one above quite well, given the right amount of granularity in the hierarchy. I'll update once I finish looking into this.

Answer 1

You need to break ties towards the endpoint.

(Without breaking ties towards endpoint)

(With breaking ties towards endpoint)

(Example with an obstacle)

Answer 2

I ended up using Dynamic HPA*. I have written details on the solution here:

http://www.matthughson.com/2013/03/05/dynamic-hpa-part-1/