Theta*
Вариант A*, позволяющий отрезкам пути идти под любым углом, а не только по восьми «компасным» направлениям сетки.
Обычный A* на сетке умеет шагать лишь с шагом в 45°, поэтому кратчайший путь к цели, лежащей под «неудобным» углом, выходит ступенчатым зигзагом, который потом приходится сглаживать. Theta* решает это прямо во время поиска: раскрывая вершину, он проверяет, есть ли прямая видимость от «дедушки» этой вершины до соседа, и если есть — пропускает промежуточный шаг. Пути получаются короче и ровнее — такими, какими пошёл бы человек.
Алгоритм предложили Кенни Дэниел, Алекс Нэш, Свен Кёниг и Ариэль Фелнер (JAIR, 2010). Плата — проверки прямой видимости, которые на узел тяжелее простого перебора соседей в A*. Lazy Theta* откладывает их до момента, когда вершина действительно извлекается из открытого списка, и убирает большую часть лишней работы.