My game involves a level with deformable terrain and units that can travel in any direction but are slowed down by uneven terrain. Normal A-star should work fine in most cases, except on flat land where no matter how the general purpose pathfinder worked it would not send units on a direct path. Theta-star would work if the entire level was fairly flat, but would be much slower if it initially had to take uneven terrain into account.
I think a Manhattan-distance base A-star algorithm would be fast and give a good enough hint to allow other path finding or steering algorithms to take over, but I'm not sure what type of algorithm to use to look ahead and decide when to abandon the path, take a more direct route, and where to jump back on the path later.
(Theta-star seems like it would be too inefficient if it was adjusted to take things like slopes, obstacles, or roads into account. See the solution proposed to the comment about avoiding minefields at: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/ )
Edit: I did not mention that I already implemented and tested A-star on a similar grid. (I think I accidentally deleted something in this question.) Some of the more obvious cost/heuristic functions I considered just don't result in realistic paths on a grid when an obstacle blocks the most direct path (basically when path-finding is useful) (example pictures). The change to the cost function used by the Theta-star algorithm seems like an ideal solution (considering the constraint of using a grid), but it makes the assumption that tiles have the same travel costs (and it takes much longer).
My original reasoning behind using Manhattan distance was to outsource the "corner cutting" algorithm from the path-finding algorithm, since it was more important to have a fast path-finding algorithm in case the obstacle layout or terrain changed. It makes more sense to do the "corner cutting" algorithm once when the unit arrives than on every permutation of every search of path-finding algorithm (the results of which may end up being scrapped anyway.) A four-neighbor search with Manhattan distance is also interesting because you can see boxes of alternate paths and identify right triangles formed by the original path and the shortest path.
A better question would have been "What is a fast way to identify shortcuts in a path with 90 degree turns?"
No comments:
Post a Comment