ABSTRACT
This chapter highlights the usefulness of any-angle pathfinding for efficiently finding short and realistic-looking paths. A* is guaranteed to find shortest paths on graphs, but shortest paths on graphs are not equivalent to shortest paths in the continuous environments. A* propagates information along graph edges and constrains paths to graph edges, which artificially constrains path headings. The key difference between Theta* and A* is that Theta* allows the parent of a vertex to be any visible vertex, whereas A* requires the parent to be a visible neighbor. In general, postprocessing techniques do improve paths, but they provide trade-offs between path length and runtime that are difficult to chose between, and they do not address the fundamental issue, namely, that the search only considers paths that are constrained to graph edges. The chapter addresses fundamental issue by describing a different approach to the search problem, called any-angle pathfinding.
