Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

Background

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.

Definitions

Algorithms

A*-based

So far, five main any-angle path planning algorithms that are based on the heuristic search algorithm A* have been developed, all of which propagate information along grid edges: O(1) . There are also A*-based algorithm distinct from the above family:

RRT-based

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) have been developed that (almost surely) converge to the optimal path by increasingly finding shorter and shorter paths:

Other algorithms

Applications

Any-angle path planning are useful for robot navigation and real-time strategy games where more optimal paths are desirable. Hybrid A*, for example, was used as an entry to a DARPA challenge. The steering-aware properties of some examples also translate to autonomous cars.