Когда наша команда впервые столкнулась с задачей поиска пути, мы не смогли удержаться от попытки изобрести собственный "велосипед". Путь был тупиковым, что стало ясно уже через несколько недель экспериментов и поиск пути отложили почти на год. И вот через год задачу снова подняли и решили использовать обычный A*. Его описаний в интернете достаточно и в 99% случаев достаточно просто реализовать алгоритм по шаблону. В моем случае именно так и получилось, поиск пути занял свое место в Runserver.Math и в серверах на его основе. Через несколько месяцев появились сообщения, что траектория выходит не очень красивой - агенты довольно неестественно движутся под углами, кратными 45-ти градусам. Через некоторое время мне встретился сайт тов. Amit Pate с описанием и примерами эвристической функции. Вчитавшись я осознал, что в мой код прокралась критическая ошибка..
Теория
Говоря обобщенно, эвристическая функция отвечает за то, чтобы поиск шел в направлении конечной точки, а не во всех направлениях (в отличие от алгоритма Дейкстры, поиска в ширину и других). Неверный баланс этой функции может привести к не-оптимальным результатам, опросу ненужных областей и другим казусам. Функция должна быть сбалансирована со значением g - минимальным расстоянием, которое надо пройти от начала пути к текущей точке.Манхэттенское расстояние
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjXoXz5qDQLYj1weagnDHTRCbx-XkjjFJYDonTiN5AcpEMwHa3UQyjASTKVwzRtmuSlerAHcrzBiGOkOQuhUCdUsGtCQn12MPpAUJMHswUUsyksn_mGB1NEcDZh1Ojgzj7ax407CTuycy8/s320/heur_man.png)
h = D * (|x-fx| + |y-fy|)
x, y - текущие координаты, fx, fy - координаты конечной точки пути, D - вес одного шага.
Главный недостаток этого алгоритма - "ступенчатость" траектории.
Диагональное расстояние
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihGpmqlDqS1LcODDHFdirPAnoEk2U3Eosyu3QbhOCXczCOP3cgqxROZkRhG-x2CCWD6acbXfaISxg9w-vlMl2b39oIU3U5iXxGfveVDr28ecB5nwPtMMeZ2mxbO8UO4CFM6EBh8USgHWg/s320/heur_diag.png)
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 - вес шага по диагонали. Такая функция идеально сбалансирована и не смотря на большое количество исследованных точек, выдает оптимальный путь за приемлимое время.
Евклидовое расстояние
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTf0MywsAPcq_TrEB2hyi0lV193pX_TTwfV7C32oEJRMPpytEPza3yBaRTKoM-Kp_9MautgOtM4-GUlrx6qQ_vr4z2Npwq9jnkk0GTR7rW3ZYQO4AnCDZZ7XXiFWUt52efreDe8w3pkrU/s320/heur_dist.png)
_________________
h = D * √(x-fx)² + (y-fy)²
Квадрат евклидового расстояния
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixD9artk14g8VH1-kzc2lRQWolvrm6jYJWMc2Rj-jYp-Bi9AS1d72ahw_hNxYyZ9ZsM31j4igNl4BDuXO1nVUBOqzlB_FeZYJRbBa5JC6d-J0gpdcNDaJRahigEpShBHqMXg4lN7s4cAI/s320/heur_sqdist.png)
h = D * ((x-fx)² + (y-fy)²)
Именно такую ошибку я и допустил в своей реализации - забыл добавить квадратный корень, но при этом количество проверенных точек получилось в разы меньше, чем у других функций!
Ситуация усложняется при добавлении препятствий. Квадратичная функция:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhaaGhBmk2mmupy-_DK6wTHJsr0KzqVaNMUMOE3Mg9YOkts_d6hFeR1xQCIE0W500RNds5EIPzd7mZna_EsMKT7ah-H1ycH3jbe7R9ZoMk_rpFVmPE41DuPLklEbuuGaTbZw12KeSYraEA/s320/heur_obst.png)
Диагональная функция:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivmeGnsrzTXxYMqt7hUiNtJg-EerjLjwRIiw1j8wlAMJzxRynNhvpCkb0xhaa8xuLDWTVgkwY2QAEYBt-yes63vrJlFE59o0FMAkV2TKJZuKdlhSrFtRw2xkhOgWcDE2J42kHCfDXeMsk/s320/heur_obst_diag.png)
Во втором случае путь "правильнее", но было проверено очень много лишних точек. По-честному, первый вариант вообще не является A* - он выдает не самый оптимальный путь, а первый найденный. Меня такой вариант устраивал - в реальной жизни персонажи редко движутся идеально, потому для AI такой алгоритм вполне подходит. Нерешенной осталась только проблема, из-за которой я и начал копаться в эвристике - излишняя "геометричность" пути.
Алгоритм компаса
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAG8phEipkt1qH3MGQQPiWucVipsFqO86iRW-QOSgDqjUCSDoQM6x6vU2EWxUPYeWmf_hWDPwtpdVZ_kHGRwmNGVUxlr58s7WjbjQs8yPx5wtl-dA0mnVHHhqHj0CMfjvrROVYksjZtps/s320/heur_cross.png)
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. Я так и не нашел баланса этого коэффициента, при котором путь остается оптимальным и не появляется артефакт "возврата":
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFKZJTRdW0FQfwJyr5wl5jqjkabuKb0I_Rt12tnBmUNJ-O_uwd10gjxGwBYcjALZGzrl9KMHIKejWycikQfmVUgXBQu32uq1L8pT375f_Ti-FBmxg4rXnMguPmNkVl5qAi5UJxNVCf9E0/s320/heur_obst_cross.png)
Алгоритм "наведения"
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihWfr1CFScUuR_moztH8RwgdgKYXL_FmA_GWF0qIDKOZNjPh2XByXchQtBXd7rCbmWW5kgHgrSKUDzn6wQcntul5DWdORWnQYqxLlcj-UQ3k872yv814NWHdIsjM0mJuoCotW2W0ve9l4/s320/heur_cross.png)
cross = |(x-fx)*(y-py) - (y-fy)*(x-px)|px, py - координаты предыдущей пройденной точки. Такой подход дает не идеальную картину при движении без препятствий, зато при коэффициенте k = 0.5 обход препятствий смотрится вполне корректно:
h = h + cross * k
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEheislxPXW4pMLEu5PT3IGj-T6T-7ksE6wnJXjTE6qrmpf_DaWTueevrjAUfCC7bJ-p6Y0pJe_dGRN7-q9YMfuTcFa23V6J2m2iaRYd8QHBpk6RYjVWdUMtvu23olBY85IjKrehONc4BQg/s320/heur_obst_nav.png)
Подобная эвристика дает оптимальный путь и решает большую часть проблем A*, особенно движение по ровной местности. На мой же взгляд эти плюсы так и не перевесили скорость вычисления "неправильной" квадратичной функции. К примеру, с тем же препятствием, без всяких дополнений она справляется вот так:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi4ZrEK-bmsgZ_pD5i7u3IMzo9ZxePtKwWsfAGE9cau86LaCbeF18ZzxDW8I-JAvRX6PSeUsHW-eOR00pGIskxjFV3NhY_8XXxmya_YzrhkHJ9_SdOHY_7OEQfudGded0U78xkwon9FGh4/s320/heur_obst_sqrd.png)
Потому я решил продолжить исследования в направлении смещенного баланса и оставить возможность выбора режима работы - "точный" и "быстрый".
"Жадный" алгоритм
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6CH-sP69A5IeL37zrQhULTJN0px5DkbCHtSd0O4qVOaBkUzA0qgD0bKwwpwYtQO49UsfVAF3-ESKpNOtxx5mrd_gmMiNui_woyF08k69QjDOeSaJFBtCfXmm4mu-lpISBXR7iX6sGNlg/s320/heur_opt.png)
Формула такова:
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 проверок видимости:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiP1W4UWPVy6ARiJRC9gdi3lwNlYtUoCFkLScc_d4KUWrTnZeIa_Kvtwh5rOVXJKl51FDPDRxfwPdRJpjfUIuQyH3JdDg0J5wQ5DBk4O7wOciXSOf-KzY1o2hKYBH5SO2x0p6Pl4qVDvnE/s400/heur_sample.png)
Большая плотность. Расчет занял 274мс, 2177 точек, 4110 проверок видимости:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXjbRtUS2LZ3XT7Z0MUTx0ZNFNMYpHPp4-eh-ndwEgo1oF1zYgZJ_PQI-N8cvS3z-x6FExL71VsbKe1UyAMZQ__2HjPMdZdGnVZ_sBnYo0abRNh7wzQsiGU5PEuG_t8t-gzjZpuChTwEA/s400/heur_sample2.png)
1 коммент.:
Хорошая работа проделана, браво!
Отправить комментарий