theta* pathfinding

An algorithm for the any-angle pathfinding problem:

http://idm-lab.org/bib/abstracts/papers/jair10b.pdf

For the Legacy world map I'd like to be able to find natural looking paths that avoid obstacles. I've got a lot of terrain and it's easy to turn that terrain into a potential field (bitmap) which can be used as a cost lookup for a pathfinding algorithm.. but.. there are some issues. In particular I don't want the paths to look like they are constrained to a grid. And if I make the grid cells small enough so that I get naturalish results, then the algorithm runs slowly. Theta* seems to be an interesting candidate; close to the speed of a grid-based A* but with more natural resulting paths, similar to results you'd get from path smoothing. I'd possible still want to round off the corners with post processing.. I don't know.

Assumedly, another approach would be based on steering, or a hybrid coarse grid A* with steering for local control. That sounds like it could take a long time to tune, but might give very good results. For the non-player actors, efficient paths are less important, and some kind of wandering/pheremone trail combination could be interesting. In particular, if you had such an emergent system, then you could use it to mark local paths, which then could become your nav grid. A lot of preprocessing I guess, but maybe that's ok.

You know what else sounds cool? Probabilistic roadmaps.