Поиск пути — неотъемлемая часть игр, встречающаяся в большинстве современных игровых жанров. Наиболее часто задача поиска пути возникает в стратегиях, в которых игрок дает команды игровым юнитам двигаться через область карты, которая содержит препятствия. Игры постоянно усложняются, а поиск пути эволюционирует и развивается вместе с ними.
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или 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).
Автор: newpdv
