Поиск пути: алгоритм A* для новичков

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

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

Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), принцип которого и реализация на JavaScript описана в статье.

Введение

Статья ориентирована на людей, которые не имеют представления о подобных алгоритмах, но владеют (желательно) навыками работы с JavaScript для практической реализации, хотя статья и может быть адаптирована под любой язык программирования.

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

Представим, что у нас есть поле, разделенное на сетку с ячейками. На котором отмечены начальная (зеленая) и конечная (красная) ячейки.

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

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

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

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

Шаг 1

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

Шаг 2

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

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

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

Шаг 3 и далее…

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

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

Результат

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

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

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

Практическая реализация

Реализация данного алгоритма выполнена на JavaScript (объект pfinder).
Посмотреть демонстрацию работы можно здесь.
Инициализация скрипта выполняется 4-мя строками.

pfinder.genArea(10, 10);
создается поле размером 10х10 ячеек

pfinder.setStart(2, 3);
pfinder.setEnd(5, 9);
устанавливаются начальные и конечные ячейки

pfinder.find();
запускается поиск пути

Препятствия создаются путем левого клика мыши по ячейки.
Также для создания преград вручную можно добавить строку:
pfinder.addBarrier(8, 8);

Реализовано:

• Генерация поля определенного размера
• Указание начальной и конечной точек
• Указание и установка препятствий
• Хранения списков открытых и закрытых ячеек, размера поля, начальных и конечных точек
• Расчет стоимости ячеек
• Выбор ячейки с минимальной стоимостью
• Ограничение выбора ячейки границами поля
• Обход «простых» препятствий (ячейка или линия)

Не реализовано:

• Обход сложных препятствий (например Г- и П- образных)
• Управление запуском и остановкой поиска пути
• Углубление и оптимизация алгоритма поиска

Код находиться в открытом репозитории, все желающие могут дополнить или внести предложения по доработке скрипта.

Заключение

В описанном примере, для лучшего понимания алгоритм был несколько не доработан упрощен.

Более подробное описание алгоритма и несколько заметок можно прочесть в статье Алгоритм A* для новичков.

Реализация на JavaScript (GitHub).