Поиск пути — неотъемлемая часть игр, встречающаяся в большинстве
современных игровых жанров. Наиболее часто задача поиска пути возникает в
стратегиях, в которых игрок дает команды игровым юнитам двигаться через
область карты, которая содержит препятствия. Игры постоянно
усложняются, а поиск пути эволюционирует и развивается вместе с ними.
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), данная статья основана на данном алгоритме и содержит реализацию на JavaScript.
Статья ориентирована на людей, которые не имеют представления о подобных алгоритмах, но владеют (желательно) навыками работы с JavaScript для практической реализации, хотя статья и может быть адаптирована под любой язык программирования.
Принцип данного алгоритма для новичка возможно покажется сложным, но по мере чтения статьи будет приходить понимание.
Представим, что у нас есть поле, разделенное на сетку с ячейками. На котором отмечены начальная (зеленая) и конечная (красная) ячейки.
Каждая ячейка имеет состояние (открыта и закрыта), характеризующее её проходимость. В примере — открытые ячейки обведены точками, а закрытые пунктиром.
Принцип алгоритма состоит в том, что он постепенно просматривает все окружающие текущую позицию ячейки и выбирает ячейку с наименьшим «весом».
Стартовая ячейка по умолчанию является первойи единственной «открытой» ячейкой, с которой мы и начинаем поиск пути.
Теперь мы можем начать поиск пути.
Ищем у текущей ячейки все «открытые» соседние ячейки и добавляем их в «открытый» список, а текущую ячейку в «закрытый».
Нужно переместиться в «открытую» соседнюю ячейку, выбрав ту, у которой стоимость (F) минимальна.
В нашем примере стоимость (F) рассчитывается, как «прямое» расстояние до конечно точки, с учетом того, что ячейки по диагонали имеют вес в 1.5 раза больше, чем ортогональные (не по диагонали).
Стоимость ячеек для наглядности указана внутри.
Продолжаем повторение действий:
— Выставляем текущей ячейке статус «закрытой»
— Ищем «открытые» соседние ячейки
— Рассчитываем стоимость (F)
— Перемещаемся в ячейку с минимальной стоимостью.
В результате мы дойдем до конечной ячейки самым коротким путем.
В начале алгоритма, ячейки-преграды уже занесены вчерный «закрытый» список и при обходе игнорируются.
Реализация данного алгоритма выполнена на JavaScript (объект pfinder).
Посмотреть демонстрацию работы можно здесь.
Инициализация скрипта выполняется 4-мя строками.
создается поле размером 10х10 ячеек
устанавливаются начальные и конечные ячейки
запускается поиск пути
Препятствия создаются путем левого клика мыши по ячейки.
Также для создания преград вручную можно добавить строку:
Реализовано:
Не реализовано:
Код находиться в открытом репозитории, все желающие могут дополнить или внести предложения по доработке скрипта.
В описанном примере, для лучшего понимания алгоритм был нескольконе доработан упрощен.
Более подробное описание алгоритма и несколько заметок можно прочесть в статье Алгоритм A* для новичков.
Если вы ведёте свой блог, микроблог, либо участвуете в какой-то популярной социальной сети, то вы можете быстро поделиться данной заметкой со своими друзьями и посетителями. Для этого воспользуйтесь предлагаемыми ниже кнопками:
Блог: http://romanlovetext.blogspot.com/
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или 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* для новичков.
Если вы ведёте свой блог, микроблог, либо участвуете в какой-то популярной социальной сети, то вы можете быстро поделиться данной заметкой со своими друзьями и посетителями. Для этого воспользуйтесь предлагаемыми ниже кнопками:
Блог: http://romanlovetext.blogspot.com/
