{"id":2567,"title":"\u041f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0446\u0438\u044f Acer: \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0438, \u043c\u043e\u043d\u0438\u0442\u043e\u0440\u044b, \u043f\u0440\u043e\u0435\u043a\u0442\u043e\u0440\u044b... \u0434\u043e\u0436\u0434\u0435\u0432\u0438\u043a","url":"\/redirect?component=advertising&id=2567&url=https:\/\/vc.ru\/acer_russia\/317785-next-2021&placeBit=1&hash=a6b26590b22c52d427a370f69825609122f6156e016037e8049771ca0bfc8ad2","isPaidAndBannersEnabled":false}

King, Witch and Dragon. DevLog #11

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

Начиная начинай

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

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

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

Искусственный Интеллект и Конечный Автомат

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

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

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

  • Стоять на месте и ничего не делать.
  • Периодически патрулировать заранее заданную зону.
  • Замечать врага (в данном случае - игрока).
  • Преследовать врага.
  • Атаковать врага.
  • Получать урон от врага.
  • Умирать.
  • Возвращаться на исходную позицию, если враг сбежал.

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

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

  • IDLE - ничего не делание.
  • PATROL - патрулирование местности.
  • ALERT - заметил игрока. Это очень короткое промежуточное состояние, чтобы дать игроку фидбэк о том, что враг его заметил и сейчас начнёт преследование.
  • CHASE - преследование игрока. В этом состоянии активно использует алгоритм поиска пути, о котором расскажу чуть позже. Также в этом состоянии враг атакует игрока, когда приближается на минимальное необходимое расстояние.
  • HITSTUN - враг переходит в это состояние сразу после получения урона. Пока враг не выйдет из этого состояния он не может ни двигаться, ни атаковать.
  • DEATH - враг мёртв.

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

Поиск пути решения проблемы поиска пути

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

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

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

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

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

Yoann Pignole
Liam Lime
Chris F. Brown

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

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

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

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

  • Анализ окружения с помощью сенсоров
  • Изменение инпута вместо изменения позиции

Анализ окружения с помощью сенсоров

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

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

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

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

Изменение инпута вместо изменения позиции

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

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

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

  • Влево
  • Вправо
  • Прыжок
  • Атака

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

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

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

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

Рализация

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

IDLE и PATROL

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

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

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

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

Сенсор распознавания игрока

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

  • Радиус сенсора
  • Угол сенсора

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

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

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

ALERT

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

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

Анимация Alert'a

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

CHASE

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

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

Атака

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

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

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

Зона поражения или HitScan.

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

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

HITSTUN и DEATH

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

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

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

Распознавание ям

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

Луч для распознавания ям

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

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

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

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

Распознавание стен

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

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

Луч для распознавания стен и препятствий

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

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

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

Распознавание уступов

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

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

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

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

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

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

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

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

P.S.

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

Что дальше?

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

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

Раз уже это последний девлог в уходящем году, команда разработки King, Witch and Dragon
(то есть я) желает вам, чтобы 2020 год поскорее закончился и наступающий 2021 был как минимум не хуже (хотя казалось бы, куда уж дальше).

В общем, с наступающим! Увидимся в следующем году!

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

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

0
33 комментария
Популярные
По порядку
Написать комментарий...

Комментарий удален по просьбе пользователя

15

Я думаю, что если бы на то была воля разрабов, то так было во всех AAA играх.

1

Слишком мало Х

0

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

3

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

Не придётся ;)
Всё уже протестировано на наклонных поверхностях и с дверьми. Благо всё это уже реализовано в игре.

1

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

0

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

0

Я когда делал себе интеллект ботов в игре, они работали и на кинематическом контроллере, и на упрощённом графе уровня, и на навмеше
Случайным образом на карте назначалась точка из графа, в которую поедет бот. Затем он искал путь туда по навмешу. И с помощью контроллера по логике из 20 строчек старался этого пути придерживаться, находясь подальше от стен и разворачиваясь, если он в неё врезался

0
Абстрактный дебаркадер

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

Есть еще хорошая вероятность, что с 10 врагами фпс не станет проседать, а с 11-ю уже начнет, а заметить это будет довольно сложно

0

Просто ради интереса закинул в сцену 20 врагов. Профайлер показывает стабильные 60 фпс без спайков. Импакт от рейкастов минимальный.

0
Абстрактный дебаркадер

Я условно о 11 написал. Это не линейная зависимость. Не критикую выбранный подход, просто указал, что есть иные варианты реализации, более подходящие, на мой взгляд. Я просто привык на мобилках работать, там физика греет телефон и садит батарею) 

0

все правильно сделал, норм решение для инди, может создавать интересные ситуации на уровне, повышая реиграбельность и количество багов =)
еще советую добавить что то типа таймера злости. когда злость падает до 0 и игрок вне зоны видимости можно прекратить CHASE (и проиграть анимацию досады, что не догнал гг и отправить в патруль). злость всегда обновляется до максимума когда он видит игрока и отнимается когда игрок убежал/спрятался, таким образом враг продолжает бежать за гг какое то время, хотя возможно у тебя уже это сделано.
Для стреляющих я делал что враг спаунит точки в стороны от себя и проверяет рейкастом сможет ли он увидеть игрока с них, и находя одну из них бежит к ней и оттуда стреляет (иногда врагу нужно отойти от гг, чтобы его увидеть как в примере с потолком)
ps : с потолком кстати интересное решение, взял на вооружение, насчет производительности рейкаст самое низкотребовательное что есть на проверку коллизий.

1

CHASE сейчас и работает по таймеру ровно как описано в комментарии. Если враг видит игрока таймер не тикает. Как только игрок скрывается, начинается обратный отсчет. Если доходит до нуля, то враг ресетится. 

С поиском и анализом позиций для стрельбы интересная тема, надо будет попробовать. Спасибо!

2

@Шериф репост в @Gamedev сделаете?

1
Абстрактный дебаркадер

Комментарий удален по просьбе пользователя

0

Всё правильно понимаете.

1

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

0
Абстрактный дебаркадер

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

1

2 слова - наследование и полиморфизм.
А "программирование мышкой" ой как аукнется на этапе оптимизации, отладки и отлова багов. Так что спасибо, не надо.

0

Привет!
Как поживает проект?
Уже два месяца никаких новостей :(

0

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

1

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

0

Мы сейчас говорим про анимации ГГ или врага? Для врага все анимации взяты с Mixamo в качестве плейсхолдеров.

0

про анимацию ГГ. я не могу рассмотреть анимацию подробно. но она получилась "сжатой" персона как будто закреплен в одной точке. сгорблен (может это и задумывалось так конечно) как пример могу привести пикселявую игру Blasphemous. Там персонаж на бегу принимает особую стойку  и в idle состоянии стоит особым образом. персонаж на бегу нагибается и отводит клинок назад.  В idle -  стоит лицом к игрок давая очень узнаваемый силуэт. В вашей игре персонаж нарушает одно из главных правил  -  его силуэт не читается, И это с учетом выбора интересного оружия, но оно все время теряется в ногах ГГ 
+ посмотрите на анимацию самых первых игр из серии "Принц Персии"  - там при остановке и развороте у персонажа была инерция. Понятно что вам не нужна настолько ощутимая инерция, но без нее ГГ выглядит болванчиком.  ред.

0

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

2

Круто! Идея с анализом пола и потолка полезна.

0
Абстрактный дебаркадер

А как конкретно реализован FSM? Какое-то типовое решение?

0

Для ГГ сделано через ScriptableObject, для врагов тупо enum + switch. Там состояний мало, кода мало, решил не заморачиваться сильно.

0
Абстрактный дебаркадер

Понял, это не совсем фсм конечно) 

0

Шоу бенни-хилла выглядит забавно :)
Не уверен, что где-то видел настолько активных преследователей.

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

0

Будет зависеть от биома. На данный момент планируется 5 разных биомов и в них будут свои тематические враги. Скорее всего будут всякие около-фентезийные монстры.

0

Почему "Сенсор распознавания игрока" установлен по центру, а не на уровне глаз? Думаю, что так будет более реалистично, чем по центру.

0
Читать все 33 комментария
null