Any-angle path planning

[1] More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

Real-world and many game maps have open areas that are most efficiently traversed in a direct way.

Traditional algorithms are ill-equipped to solve these problems: An any-angle path planning algorithm aims to produce optimal or near-optimal solutions while taking less time than the basic visibility graph approach.

Fast any-angle algorithms take roughly the same time as a grid-based solution to compute.

So far, five main any-angle path planning algorithms that are based on the heuristic search algorithm A*[3] have been developed, all of which propagate information along grid edges: There are also A*-based algorithm distinct from the above family: Besides, for search in high-dimensional search spaces, such as when the configuration space of the system involves many degrees of freedom that need to be considered (see Motion planning), and/or momentum needs to be considered (which could effectively double the number of dimensions of the search space; this larger space including momentum is known as the phase space), variants of the rapidly-exploring random tree (RRT)[23] have been developed that (almost surely) converge to the optimal path by increasingly finding shorter and shorter paths: Any-angle path planning are useful for robot navigation and real-time strategy games where more optimal paths are desirable.