Алгоритм поиска пути — на раз, два, три!

Поиск пути — это алгоритм, осуществляющий прокладку маршрута из точки 1 в точку 2, в обход препятствий.
Чаще всего находит применение в играх жанра стратегии и у военных роботов, для поиска пути к врагу.

На сегодня обладает неимоверной известностью алгоритм астар, иногда пишут как А*. Но на хабре была обнаружена статья рассказывающая о новом, революционном алгоритме «прыгающих точек», на английском выглядит так «Jump Point Search».

Введение

Эта статья направлена на тех, кто вообще никак не понимает данный алгоритм, но хочет его понять снова и снова.

Прочитав эту статью, вы сразу все поймете и сможете на любом языке объяснить его любому желающему.
И главное не забывайте, для закрепления материала, рекомендую рассказать о принципе работы этого хитрого алгоритма кому нибудь еще.

Представляю, что у меня есть некий полигон, с ячейками. Уважаемые читатели, смотрите на рисунок ниже. В нем вы должны увидеть зеленый кубик, а справа о него обнаружите красный кубик. Так вот, зеленый квадратик — начало пути нашего героя, красный квадратик — место где сидит дракон. Наш герой просто обязан найти путь к дракону и вальнуть его.

Каждая клетка имеет состояние (открыта и закрыта), характеризующее её проходимость. В примере — открытые ячейки обведены точками, а закрытые пунктиром.

Принцип алгоритма состоит в том, что он постепенно просматривает все окружающие текущую позицию ячейки и выбирает ячейку с наименьшим «весом».

Стартовая ячейка по умолчанию является первой и единственной «открытой» ячейкой, с которой мы и начинаем поиск пути.

Теперь мы можем начать поиск пути.

Раз

Ищем у текущей ячейки все «открытые» соседние ячейки и добавляем их в «открытый» список, а текущую ячейку в «закрытый».
Два

Нужно переместиться в «открытую» соседнюю ячейку, выбрав ту, у которой стоимость (F) минимальна.

В нашем примере стоимость (F) рассчитывается, как «прямое» расстояние до конечно точки, с учетом того, что ячейки по диагонали имеют вес в 1.5 раза больше, чем ортогональные (не по диагонали).

Стоимость ячеек для наглядности указана внутри.

Три

Продолжаем повторение действий:

— Выставляем текущей ячейке статус «закрытой»
— Ищем «открытые» соседние ячейки
— Рассчитываем стоимость (F)
— Перемещаемся в ячейку с минимальной стоимостью.

Результат

В результате мы дойдем до конечной ячейки самым коротким путем.

А как же преграды?

В начале алгоритма, ячейки-преграды уже занесены в «закрытый» список и при обходе игнорируются.

Заключение

Поздравляю вас мои дорогие читатели!
Теперь наш герой может смело дойти до дракона и завалить его!
А вы можете реализовать алгоритм поиска пути в вашем проекте.

Автор: Gexon

Источник ^[1]