Techniques for (literally) cutting corners on square grid maps

Question

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?"

Answer 1

Have you given A* a chance yet? Provided you weight your costs for different types of terrain appropriately, it will find a best path given the available nodes. It will not however find a straight line over open plains if you give it a square grid, which seems to be your problem with it.

If you want to be able to create straight-line paths across plains, you can collapse the edges of your path into segments wherever the new path is equal or lower cost (I.E. same or less distance and doesn't pass through rougher terrain.) Just take each two pairs of nodes in the path (A-B and B-C) and see if A-C is a better route. If A-C is equal or lesser cost, remove B from the list. Repeat over the list until the iteration where the list doesn't change anymore, and that will solve your plains problem. You do have to do some extra processing to ensure that A-C is a legal move, and to calculate the cost across an arbitrary distance. Or, you could have your units use the path as a general guideline, and move toward the node several positions of them, using simple obstacle avoidance at the same time.

You can also significantly improve your quality of your path by giving A* more options for nodes to traverse. For instance, just adding diagonals with a x√2 cost will produce a much better path than simple 4-direction traversal.

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.

A* handles this already. As soon as the node currently being explored is no longer the lowest cost+heuristic, it moves on to the lowest cost+heuristic node.