Any-angle path planning

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:

A* with an 8-connected discrete grid graph (2D; 26 for the 3D triple cubic graph) is very fast, but only looks at paths in 45-degree increments. This behavior gives on average 8% extra path length in 2D and 13% in 3D. A quick post-smoothing step can be used to straighten (thus shorten) the jagged output, but the result is not guaranteed to be optimal as it does not look at all the possible paths. (More specifically, they cannot change what side of a blocked cell is traversed.) The advantage is that all optimizations of grid A* like jump point search will apply.

A visibility graph with all the grid points can be searched with A* for the optimal solution in 2D space. However, the performance is problematic since the number of edges in a graph with

V

{\displaystyle V}

vertices is

O

(

V

2

)

{\displaystyle O(V^{2})}

. Such a graph does not always provide an optimal solution in 3D space.