TY - JOUR AU - Nash, Alex AU - Koenig, Sven PY - 2013/09/18 Y2 - 2024/03/28 TI - Any-Angle Path Planning JF - AI Magazine JA - AIMag VL - 34 IS - 4 SE - Articles DO - 10.1609/aimag.v34i4.2512 UR - https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/2512 SP - 85-107 AB - In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses path-planning algorithms to find a shortest path on the resulting grid graph. 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. Any-angle 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). ER -