Граф видимости
Граф, чьи вершины — углы препятствий, а рёбра соединяют углы, видящие друг друга; кратчайший путь по нему — это кратчайший путь в обход препятствий.
Введён Томасом Лосано-Пересом и Майклом Уэсли в 1979 году для планирования движения роботов. Поскольку кратчайший путь на плоскости, заполненной многоугольными препятствиями, всегда идёт по прямым между углами препятствий, достаточно построить граф из этих углов и запустить по нему A* или Дейкстру.
Путь жмётся к углам вплотную, что выглядит естественно, но может потребовать запаса, чтобы юниты не задевали стену. В сложном 3D навигационная сетка в основном вытеснила этот метод, но в 2D граф видимости живёт и здравствует.