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

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

i writing simple top down, 2d game. uses evenly spaced 2d grid of tiles collision data. each tile in grid either solid or empty.

for path finding using a* (a star), , have tried both manhattan , diagonal (aka chebyshev distance) heuristics.

it works in cases, becomes quite expensive when trying path find target sitting in recess of concave shape (eg. u shape).

for example, in image below, guy on right path find guy on left. grass (green, dark greenish , yellow) empty space. solid tiles brownish "wood" tiles, , gray "stone" tiles, making shape of sideways "u".

now here results of path search (in case a* manhattan heuristics):

the reddish , greenish debug draw squares show tiles visited during a* search. reddish in "closed" list , greenish in "open" list (as per a* specifications). bluish line in final path chosen (which correct).

as can see, search has been exhaustive, visiting lots of tiles, creating perfect circle.

i understand why happening based on a* algorithm, , chosen heuristics (as move passed target along wall, tiles farther away begin have improve f values, causing them explored before coming right path). don't know how create improve :)

any suggestions on possible improvements? perchance different heuristic? maybe different path searching algorithm together?

thanks!

based on suggestions, leaning towards updating a* implementation include improvements found in hpa*. based on initial reading, seems address cases 1 above quite well, given right amount of granularity in hierarchy. i'll update 1 time finish looking this.

you need break ties towards endpoint.

(without breaking ties towards endpoint)

(with breaking ties towards endpoint)

(example obstacle)

xna hierarchical-data path-finding a-star pathfinder