Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Pathfinding

Как адаптировать алгоритм поиска пути A* к основанному на сетке 2D платформеру: Теория

by
Difficulty:IntermediateLength:MediumLanguages:
This post is part of a series called How to Adapt A* Pathfinding to a 2D Grid-Based Platformer.
How to Adapt A* Pathfinding to a 2D Grid-Based Platformer: Implementation

Russian (Pусский) translation by Alexey Malyutin (you can also view the original English article)

Поиск пути, основанный на сетке A*, хорошо работает для игр, в которых персонажи могут свободно перемещаться по обеим осям x и y. Проблема с приложением его к платформерам заключается в том, что перемещение по оси y сильно ограничено в связи с симулированными силами гравитации.

В этом уроке я дам широкий обзор, как модифицировать стандартный алгоритм A* для работы с платформерами, моделируя эти гравитационные ограничения. (В следующей части я проведу вас через реальное кодирование алгоритма). Адаптированный алгоритм может быть использован для создания искусственного интеллекта персонажа, который следует за игроком, или чтобы показывать игроку путь к его цели, например.

Я предполагаю, что вы уже знакомы с поиском пути A*, но если вам нужно введение, прекрасно подойдет Поиск пути А* для начинающих Патрика Лестера.

Демонстрация

Вы можете сыграть в демо Unity, или в версию WebGL (64MB), чтобы посмотреть в действии конечный результат. Используйте WASD, чтобы перемещать персонажа, левый клик мышкой на точке, чтобы найти путь, которым вы можете проследовать в нее, и правый клик в ячейке, чтобы переключить наличие земли в этой точке.

К концу серии этих уроков, мы также добавим односторонние платформы, расширим код для обработки разных размеров персонажа, и закодируем бота, который сможет автоматически следовать маршруту! Попробуйте это Unity демо здесь (или 100MB+ WebGL версию).

Определение правил

Перед тем, как мы сможем адаптировать алгоритм поиска пути, нам нужно четко определить, какие формы могут принимать сами пути.

Что может делать персонаж?

Давайте предположим, что наш персонаж занимает одну клетку и может прыгать на три клетки вверх.

Мы не позволим нашему персонажу перемещаться через клетки по диагонали, потому что мы не хотим, чтобы он проходил сквозь сплошной ландшафт. (То есть мы не позволим ему перемещаться через угол клетки, только через верхнюю, нижнюю, левую или правую сторону). Чтобы перейти на клетку, примыкающую по диагонали, персонаж должен перейти на одну клетку вверх или вниз, и на одну клетку направо или налево.

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

Основываясь на этих правилах, приведу пример пути персонажа, который он пройдет во время его прыжка на максимальное расстояние:

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

Представление путей прыжка значениями прыжка

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

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

Вот это правило, примененное к приведенному мной ранее прыжку на максимальное расстояние:

Клетка, содержащая 6 отмечает высочайшую точку пути. Это имеет смысл, так как в два раза превышает максимальную высоту прыжка персонажа, и он чередует перемещение на одну клетку вверх и на одну клетку вбок, в этом примере.

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

Давайте изменим наше правило, чтобы увеличивать значение прыжка на следующее четное число всегда, когда персонаж движется вверх. Далее, если значение прыжка четное, персонаж может двигаться дальше влево, вправо или вниз (или вверх, если он еще не достиг значения прыжка 6), а если значение прыжка нечетное, персонаж может двигаться только вверх или вниз (в зависимости от того, достиг ли он пика прыжка).

Вот как это выглядит при прыжке прямо вверх:

А здесь более сложный случай:

Вот как вычисляются значения прыжка:

  1. Начинаем на земле: значение прыжка 0.
  2. Прыгаем горизонтально: увеличиваем значение прыжка на 1, и оно становится равным 1.
  3. Прыгаем вертикально: увеличиваем значение прыжка до следующего четного числа: 2.
  4. Прыгаем вертикально: увеличиваем значение прыжка до следующего четного числа: 4.
  5. Прыгаем горизонтально: увеличиваем значение прыжка на 1; оно теперь равно 5.
  6. Прыгаем вертикально: увеличиваем значение до следующего четного числа: 6. (Персонаж больше не может двигаться вверх, поэтому доступны только правый, левый и нижний узлы.)
  7. Падаем горизонтально: увеличиваем значение прыжка на 1; теперь оно равно 7.
  8. Падаем вертикально: увеличиваем значение прыжка до следующего четного числа: 8.
  9. Падаем вертикально: увеличиваем значение до следующего четного числа: 10.
  10. Падаем вертикально: поскольку персонаж теперь на земле, устанавливаем значение прыжка в 0.

Как видите, при этом типе нумерования мы точно знаем, когда персонаж достиг его максимальной высоты прыжка: это клетка со значением прыжка, равным удвоенной высоте прыжка персонажа. Если значение прыжка меньше него, персонаж все еще может двигаться вверх; в противном случае мы должны игнорировать узел прямо над ним.

Добавление координат

Теперь, когда мы знаем о типе перемещений, которые персонаж может выполнять на сетке, давайте рассмотрим следующую ситуацию:

Зеленая клетка в позиции (3, 1) - это персонаж; синяя клетка в позиции (2, 3) - это цель. Давайте нарисуем маршрут, который может выбрать алгоритм А*, чтобы попытаться достичь цели.

Желтое число в верхнем правом углу клетки это значение прыжка в этой клетке. Как видите, при прыжке прямо вверх персонаж может подпрыгнуть не выше, чем на три тайла вверх. Это не хорошо.

Мы можем попытать удачи с другим маршрутом, поэтому давайте перемотаем обратно наш поиск и начнем заново с узла (3, 2).

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

По всей вероятности, первый маршрут, который выберет алгоритм, это первый из тех, которые мы рассмотрели. После его принятия, алгоритм продвинется не очень далеко и закончит опять на узле (3, 2). Затем он может искать через узлы (4, 2), (4, 3), (3, 3) (снова), (3, 4) (снова), (3, 5), и наконец в целевую клетку (2, 5).

В базовой версии алгоритма А*, если узел уже был посещен однажды, мы никогда не должны обрабатывать его повторно. Однако в этой версии мы это делаем. Это связано с тем, что узлы различаются не только координатами x и y, но и значениями прыжка.

В нашей первой попытке найти маршрут, значение прыжка в узле (3, 3) было 4; в нашей второй попытке, оно было равно 3. Так как во второй попытке значение прыжка в этой клетке было меньше, это означало, что мы можем потенциально попасть выше, чем мы могли во время первой попытки.

Это в основном означает, что узел (3, 3) со значением прыжка 4 это узел, отличный от узла (3, 3) со значением прыжка 3.

Мы не можем просто изменить значение прыжка узла (3, 3) с 4 на 3, потому что некоторые маршруты используют этот же узел многократно; если бы мы это сделали, мы бы практически отвергли предыдущий узел и это без сомнения испортило бы конечный результат.

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

Сильные и слабые стороны использования поиска пути, основанного на сетке

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

Сильные стороны

  • Очень хорошо работает с играми, основанными на тайлах.
  • Расширяет базовый алгоритм А*, поэтому вам не нужно использовать два абсолютно разных алгоритма для летающих и наземных персонажей.
  • Очень хорошо работает с динамическим ландшафтом; не требует сложного процесса перестроения узлов.

Слабые стороны

  • Неточность: минимальное расстояние равно размеру одной клетки.
  • Требует представление в виде сетки каждой карты или уровня.

Требования к движку и физике

Свобода персонажа против свободы алгоритма

Для персонажа важно иметь хотя бы столько свободы передвижения, сколько ожидает алгоритм - а предпочтительно немного больше.

Заставлять перемещение персонажа точно следовать ограничениям алгоритма - это не жизнеспособный подход в связи с дискретной природой сетки и размером клетки сетки.  Возможно запрограммровать физику таким образом, что алгоритм всегда будет находить путь, если он есть, но это потребует от вас построить физику для этой цели.

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

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

Когда персонаж имеет больше свободы, чем ожидает алгоритм

Давайте представим, что искусственный интеллект позволяет прыжки длиной в шесть клеток, а игровая физика позволяет семи-клеточный прыжок. Если есть маршрут, который требует более длинный прыжок, чтобы быстрее всего достичь цели, бот проигнорирует этот маршрут и выберет более консервативный, думая, что более длинный прыжок невозможен.

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

Когда алгоритм ожидает от персонажа больше свободы, чем у него есть

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

(Если не принимать во внимание эти две проблемы, предпочтительно позволять физике больше свободы передвижения, чем ожидает алгоритм).

Решение этих проблем

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

Второе решение этих проблем - это перенастроить алгоритм, физику, или и то и другое, чтобы убедиться, что они совпадают. Как я упоминал ранее, это не означает, что они должны совпадать абсолютно; например, если алгоритм думает, что персонаж может прыгать на пять клеток вверх, будет нормально установить реальный максимальный прыжок в 5.5 клеток высотой. (В отличие от алгоритма, игровая физика может использовать дробные значения).

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

Заключение

К этому моменту у вас должно появиться достаточное концептуальное понимание, как можно адаптировать к платформеру алгоритм поиска пути A*. В моем следующем уроке мы воплотим это в реальность, по настоящему адаптировав существующий алгоритм поиска пути A*, для того, чтобы реализовать его в игре!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.