King, Witch and Dragon. DevLog #11

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

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

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

Давайте начну с простого и расскажу про ИИ.

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

У меня не было цели сделать Ultimate Ultra Realistic Sophisticated Platformer AI, но при этом хотелось, чтобы враги не были совсем уж тупыми и навязывали игроку ощутимый челлендж. Но давайте по-порядку.

Перед тем как начинать разработку ИИ, необходимо чётко обозначить, что этот ИИ должен уметь делать. Для своего первого тестового врага я составил такой список:

Этот список отлично ложится в концепт конечного автомата или стейт-машины (FSM, Finite State Machine). То есть у врага есть ограниченный набор состояний, но при этом в каждый момент времени враг может находиться только в одном из них. Каждое состояние имеет свою собственную внутреннюю логигу.

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

Получив такой список я приступил к реализации и сразу столкнулся с тем, из-за чего я так долго откладывал эту тему. Почти все состояния подразумевают перемещение врага по уровню, а CHASE так вообще заставляет следовать за игроком, куда бы тот не пошёл. А это значит, нужно делать поиск пути или pathfinding.

Мне уже доводилось сталкиваться с pathfinding'ом, в частности я знаком с алгоритмами A* и Dijkstra. Но проблема в том, что большинство подобных решений, будь то grid, graph или navmesh, все они подразумевают движение по плоскости (если совсем уж упростить, то они отлично работают для вида сверху). Но у меня платформер с видом сбоку, который подразумевает прыжки, падения, в общем физику и, в частности, гравитацию.

Это был первый проблемный момент.

Я начал изучать тему pathfinding'а в платформерах и, в принципе, нашёл примеры адаптации указанных алгоритмов для игр с видом сбоку. Самый, впечатляющий, пожалуй, это бот, написанный Робином Баумгартеном, для соревнования Mario AI:

Но это хардкор, я так не умею (к сожалению).

Я начал искать альтернативы. И нашёл. Большинство из них выглядит примерно так:

Многие из них написаны для игр, основанных на тайловой сетке, а это явно не мой случай. В других вариантах, ноды или way-point'ы расставляются руками и объединяются в граф, по которому в дальнейшем идёт поиск.

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

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

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

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

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

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

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

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

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

Аналогично главному герою, класс врага построен на основе Kinematic Character Controller, который, в свою очередь, обрабатывает все коллизии, разгон, торможение, гравитацию и всё остальное. Вместо того, чтобы напрямую задавать ему скорость и направление движения, я передаю ему "виртуальный инпут", на основе которого он обсчитывает передвижение. Грубо говоря, у врага есть 4 "воображаемых кнопки":

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

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

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

На этом затянувшаяся теоретическая часть закончена, теперь покажу, что из этого всего получилось.

Начну с простого и покажу как работают простые состояния.

Тут всё просто - эти 2 состояния работают по таймеру и чередутся друг за другом.

Сначала враг решает сколько секунд ему постоять в айдле (диапазон задаётся в конфигах на ScriptableObject'е). Затем, когда таймер айдла заканчивается, враг выбирает направление патрулирования (влево или вправо), выбирает время патрулирования, также из диапазона в конфигах, и "зажимает виртуальную кнопку" на это количество секунд.

Ареал обитания отображается относительно точки спауна врага и радиус считается по формуле: радиус обитания = максимальное время патрулирования * скорость ходьбы.

Чтобы враг не выходил за радиус, есть дополнительная логика выбора направления: если в момент выбора направления враг находится левее точки спауна, он пойдёт вправо, если находится правее, то пойдёт влево.

В конфигах врага задаются 2 основных параметра сенсора игрока:

В целях оптимизации я сделал так, что проверка сенсора происходит не каждый кадр, а с небольшим интервалом (по умолчанию 0,1 сек).

Также я сделал так, что сенсор имеет 2 набора параметров - один для состояний IDLE и PATROL, когда враг ещё "не знает" о присутствии игрока. Второй набор для состояния CHASE. В состоянии погони радиус и угол сенсора увеличиваются, чтобы от врага было сложнее скрыться.

При попадании игрока в сенсор производится проверка видимости - рейкаст для поиска препятствия между врагом и игроком. Если рейкаст успешно достиг игрока, то игрок становится целью врага, а сам враг переходит в состояние ALERT.

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

Длится это состояние очень недолго, в районе 1 секунды.

Когда таймер алерта заканчивается, враг переходит в состояние погони.

Если в состоянии PATROL враг неторопясь ходит, то в состоянии CHASE начинает быстро бегать.

Главная цель врага в этом состоянии - прблизиться к игроку на расстояние атаки и атаковать.

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

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

В определённый момент анимации отправляется ивент, который запускает HitScan. Более подробно о том, как он работает я писал в одном из вредыдущих девлогов.

Если HitScan задетектил игрока, тот получает урон.

Но игрок может дать сдачи. Если враг попадает в HitScan игрока, то тоже получает урон и уходит в состояние HITSTUN.

При получении урона, если у врага ещё осталось здоровье, включается таймер HITSTUN'а, проигрывается соответствующая анимация и прикладывается импульс, отбрасывающий врага немного назад (всё это кастомизируется в конфигах).

В этом состоянии все инпуты врага неактивны (не может двигаться и атаковать). По истечении таймера враг возвращается в состояние CHASE.

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

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

В зависимости от состояния, враг может повести себя по-разному при виде ямы.

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

В состоянии CHASE враг будет стараться продолжать двигаться в направлении врага и попытается эту яму перепрыгнуть.

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

Похожим образом работает и распознавание стен и препятствия перед врагом.

Сенсор представляет собой рейкас вперёд на заданное расстояние.

Если враг заметил стену в состоянии PATROL, то он поступит также как и с ямой - остановится и перейдёт в состояние IDLE.

Если же враг заметил стену в состоянии CHASE, то он проанализирует высоту препятствия с помощью череды горизонтальных рейкастов и, если высота прыжка позволяет ему запрыгнуть или перепрыгнуть препятствие, враг "нажмёт" виртуальную кнопку прыжка.

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

Это, пожалуй, была самая сложная и самая интересная задача с точки зрения поиска решения.

Допустим, враг стоит на земле, а игрок на небольшой платформе ровно над ним.

Тут нет ни ямы, ни стены и просто вверх прыгнуть не получится. Аналогичная ситуация если поменять врага и игрока местами. Враг должен понять как ему подняться на верхний уровень к игроку.

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

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

В итоге получилось так.

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

Пока делал вычитку понял, что, наверное, эта статья подходит больше для раздела Gamedev, чем Инди, но всё равно решил опубликовать как девлог, а не туториал. Хоть результат и получился достаточно интересным, он ещё не обкатан в "боевых" условиях.

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

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

Чтобы поддержать разработку игры, добавляйте King, Witch and Dragon в вишлист на Steam, это важно не только для моей мотивации, но и для алгоритмов Steam. Чтобы принять участие в обсуждении, вступайте в группу ВК, а также подписывайтесь на меня в Twitter и Instagram.

Спасибо за внимание!

#опыт #геймдизайн #ии #ai #pathfinder