Эвристика в поиске пути

Когда наша команда впервые столкнулась с задачей поиска пути, мы не смогли удержаться от попытки изобрести собственный "велосипед". Путь был тупиковым, что стало ясно уже через несколько недель экспериментов и поиск пути отложили почти на год. И вот через год задачу снова подняли и решили использовать обычный A*. Его описаний в интернете достаточно и в 99% случаев достаточно просто реализовать алгоритм по шаблону. В моем случае именно так и получилось, поиск пути занял свое место в Runserver.Math и в серверах на его основе. Через несколько месяцев появились сообщения, что траектория выходит не очень красивой - агенты довольно неестественно движутся под углами, кратными 45-ти градусам. Через некоторое время мне встретился сайт тов. Amit Pate с описанием и примерами эвристической функции. Вчитавшись я осознал, что в мой код прокралась критическая ошибка..

Теория

Говоря обобщенно, эвристическая функция отвечает за то, чтобы поиск шел в направлении конечной точки, а не во всех направлениях (в отличие от алгоритма Дейкстры, поиска в ширину и других). Неверный баланс этой функции может привести к не-оптимальным результатам, опросу ненужных областей и другим казусам. Функция должна быть сбалансирована со значением g - минимальным расстоянием, которое надо пройти от начала пути к текущей точке.

Манхэттенское расстояние

Достаточно часто используется т.н. Манхэттенский метод, который вычисляет минимальное расстояние, которое надо пройти вдоль осей координат, чтобы попасть в данную точку:

h = D * (|x-fx| + |y-fy|)

x, y - текущие координаты, fx, fy - координаты конечной точки пути, D - вес одного шага.
Главный недостаток этого алгоритма - "ступенчатость" траектории.

Диагональное расстояние

Более сложная разновидность Манхэттенской функции учитывает движение по диагонали между клетками. Формула учитывает, вдоль какой из осей путь будет длиннее:

ax = |x-fx|
ay = |y-fy|
if ax > ay then
   h = ax * D * √2 + D * (ax - ay)
else
   h = ay * D * √2  + D * (ay - ax)

D - вес шага вдоль осей координат, D * √2 - вес шага по диагонали. Такая функция идеально сбалансирована и не смотря на большое количество исследованных точек, выдает оптимальный путь за приемлимое время.

Евклидовое расстояние

Другой подход - использовать реальное расстояние до конечной точки. В этом случае функция получается не идеально сбалансированной, потому что расстояние g считается с учетом движения в 8-ми направлениях, а от точки до конца пути - напрямик. A* все-равно выдаст оптимальный путь, но проверит чуть большее количество точек:

         _________________
h = D * √(x-fx)² + (y-fy)²

Квадрат евклидового расстояния

Этот метод во многих источниках заклеймен как лженаучный и неверный. Проблема в том, что значение функции будет заметно больше пройденного пути g, потому алгоритм будет искать не оптимальный путь, а как-бы "притягиваться" к конечной точке. Формула выглядит так:

h = D * ((x-fx)² + (y-fy)²)

Именно такую ошибку я и допустил в своей реализации - забыл добавить квадратный корень, но при этом количество проверенных точек получилось в разы меньше, чем у других функций!

Ситуация усложняется при добавлении препятствий. Квадратичная функция:

Диагональная функция:

Во втором случае путь "правильнее", но было проверено очень много лишних точек. По-честному, первый вариант вообще не является A* - он выдает не самый оптимальный путь, а первый найденный. Меня такой вариант устраивал - в реальной жизни персонажи редко движутся идеально, потому для AI такой алгоритм вполне подходит. Нерешенной осталась только проблема, из-за которой я и начал копаться в эвристике - излишняя "геометричность" пути.

Алгоритм компаса

Я не придумал, как правильно сформулировать название этого алгоритма. Автор алгоритма (Amit Patel) описал его так:

A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal

Идея схожа с навигацией по компасу - имея некое направление, после обхода препятствия надо двигаться в том же направлении, что и раньше. Базовая формула эвристики остается прежней, но к ней добавляется еще небольшое смещение:

cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k

sx, sy - координаты начальной точки, k - коэффециент смещения, у автора алгоритма 0.001, cross - модуль векторного произведения вектора движения для текущей и начальной точки.
Для открытых пространств такая функция работает очень хорошо, а вот обход препятствий дает некоторую погрешность, которой можно управлять, меняя значение k. Я так и не нашел баланса этого коэффициента, при котором путь остается оптимальным и не появляется артефакт "возврата":

Алгоритм "наведения"

В результате всех экспериментов я вывел собственный алгоритм, схожий с "компасным", но стремящийся не к линии между начальной и конечной точкой, а к линии между предыдущей пройденой и конечной точкой:

cross = |(x-fx)*(y-py) - (y-fy)*(x-px)|
h = h + cross * k

px, py - координаты предыдущей пройденной точки. Такой подход дает не идеальную картину при движении без препятствий, зато при коэффициенте k = 0.5 обход препятствий смотрится вполне корректно:

Подобная эвристика дает оптимальный путь и решает большую часть проблем A*, особенно движение по ровной местности. На мой же взгляд эти плюсы так и не перевесили скорость вычисления "неправильной" квадратичной функции. К примеру, с тем же препятствием, без всяких дополнений она справляется вот так:
Потому я решил продолжить исследования в направлении смещенного баланса и оставить возможность выбора режима работы - "точный" и "быстрый".

"Жадный" алгоритм

Результатом дальнейших поисков стала функция, напрочь отрицающая баланс g и h. Это сделало алгоритм из A* явно выраженный Greed Search, который, как ни странно, работает очень быстро и для AI выглядит вполне естественно.
Формула такова:

ax = |x-fx|
ay = |y-fy|
if ax > ay then
   h = ax * D * n
else
   h = ay * D * n
cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k

n - весовой фактор, k - коэффициент "наведения".
В приведенной иллюстрации коэффициенты равны 100 и 1 соответственно.

Заключение

Это исследование не несет никакой агитационной цели. Для наших задач я решил использовать одновременно и обычный A*, и "жадный" алгоритм, но во многих ситуациях нужна максимальная точность и Greed алгоритмы не применимы. В любом случае, статья будет полезна тем, кто хочет понять работу А* и возможности его эвристической функции.

P.S. Напоследок несколько "живых" примеров работы Greed алгоритма.

Средняя плотность. Расчет занял 228мс, 2689 точек, 5289 проверок видимости:

Большая плотность. Расчет занял 274мс, 2177 точек, 4110 проверок видимости: