Any-angle path planning

The path found by A* on an octile grid vs. the shortest path between the start and goal nodes.

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.[1] More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

  1. ^ Tansel Uras and Sven Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms. Proceedings of the Eighth International Symposium on Combinatorial Search.