Когда наша команда впервые столкнулась с задачей поиска пути, мы не смогли удержаться от попытки изобрести собственный "велосипед". Путь был тупиковым, что стало ясно уже через несколько недель экспериментов и поиск пути отложили почти на год. И вот через год задачу снова подняли и решили использовать обычный 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)|px, py - координаты предыдущей пройденной точки. Такой подход дает не идеальную картину при движении без препятствий, зато при коэффициенте k = 0.5 обход препятствий смотрится вполне корректно:
h = h + cross * k
Подобная эвристика дает оптимальный путь и решает большую часть проблем A*, особенно движение по ровной местности. На мой же взгляд эти плюсы так и не перевесили скорость вычисления "неправильной" квадратичной функции. К примеру, с тем же препятствием, без всяких дополнений она справляется вот так:
Потому я решил продолжить исследования в направлении смещенного баланса и оставить возможность выбора режима работы - "точный" и "быстрый".
"Жадный" алгоритм
Результатом дальнейших поисков стала функция, напрочь отрицающая баланс g и h. Это сделало алгоритм из A* явно выраженный Greed Search, который, как ни странно, работает очень быстро и для AI выглядит вполне естественно.Формула такова:
ax = |x-fx|n - весовой фактор, k - коэффициент "наведения".
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
В приведенной иллюстрации коэффициенты равны 100 и 1 соответственно.
Заключение
Это исследование не несет никакой агитационной цели. Для наших задач я решил использовать одновременно и обычный A*, и "жадный" алгоритм, но во многих ситуациях нужна максимальная точность и Greed алгоритмы не применимы. В любом случае, статья будет полезна тем, кто хочет понять работу А* и возможности его эвристической функции.P.S. Напоследок несколько "живых" примеров работы Greed алгоритма.
Средняя плотность. Расчет занял 228мс, 2689 точек, 5289 проверок видимости:
Большая плотность. Расчет занял 274мс, 2177 точек, 4110 проверок видимости:
Дальше..
