Поиск пути под любым углом
Поиск пути, допускающий рёбра в любом направлении, а не прижимающий маршрут к сеточным «дорожкам» под 45 и 90 градусов.
Классический A* на сетке умеет шагать только в соседние клетки, поэтому путь петляет по восьми направлениям компаса, даже на открытой местности, где прямая была бы и короче, и естественнее. Алгоритмы any-angle это ломают: путевая точка может «видеть» мимо промежуточных клеток. Если из A виден C, точка B отбрасывается.
Theta* (Nash и др., 2007) проверяет прямую видимость прямо во время поиска; Field D* и Lazy Theta* жертвуют точностью ради скорости. Альтернатива — прогнать обычный A* и потом «натянуть нить» на путь, но так можно упустить сокращения, которые находит встроенный в поиск вариант. Результат — более прямые, менее роботизированные маршруты, особенно заметные у техники и летающих юнитов.