Any-Angle Path Planning

This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Anyangle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths). In robotics and video games, (continuous) terrain is often discretized into grids with blocked and unblocked grid cells and from there into grid graphs (Tozour 2004; Rabin 2000; Chrpa and Komenda 2011; Björnsson et al. 2003; Nash 2012). Our objective is to find short unblocked paths from given start vertices to given goal vertices.