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




Списки действий – это простой и вместе с тем мощный тип искусственного интеллекта (ИИ), о котором должен знать каждый разработчик игр. Несмотря на то, что их нельзя масштабировать для больших ИИ-сетей, они обеспечивают сложное непредсказуемое поведение и достаточно просты в использовании. Эта статья будет интересна как новичкам ИИ-программирования, так и опытным мастерам, желающим расширить свой инструментарий. Вы узнаете, что такое списки действий, и ознакомитесь с конкретными примерами их внедрения, которые пригодятся вам в разработке собственных решений. Итак, начнем.

В некотором царстве, в некотором государстве…

Несколько лет назад я начал разрабатывать игру King Randall’s Party, где нужно построить замок и защитить его от осады. Я должен был создать достаточно умный ИИ, способный придумать, как обойти защиту и разрушить замок, чтобы прибрать к рукам охраняемое игроком золото. Эта задача оказалась слишком объемной, поэтому как толковый программист я разбил ее на несколько частей. Во-первых, мне нужно было создать определенный набор поведений для юнитов.



Как и следовало ожидать, результаты поиска в интернете взорвали мой мозг. Запрос «Game AI» завел меня в самые настоящие дебри: планировщики, конечные автоматы, стайное поведение, алгоритм поиска A*, поиск пути – чего там только не было. Я совершенно растерялся, поэтому сделал то, что любой здравомыслящий человек сделал бы на моем месте: обратился за советом к своей собаке. Когда возникает проблема технического характера, я всегда консультируюсь со своей собакой. Вы, наверное, думаете, что я совсем чокнутый. Что собака может понимать в разработке? Что ж, думайте что хотите. Тем более, если я расскажу, как она долгие годы изучала запрещенные секретные технологии, вы мне все равно не поверите.

В общем, я спросил ее: «Фрэнки, ИИ – настолько обширная тема, что я совсем не знаю, с чего начать. Как мне создать искусственный интеллект для игровых юнитов?». Мой школьный учитель мистер Френсис говорил, что глупых вопросов не бывает. Но вопреки его словам, Фрэнки посмотрела на меня как на полного идиота. После многозначительной паузы она спросила в ответ: «Джесси, что ты делаешь каждое утро?».

По утрам я обычно составляю список всего, что мне нужно сделать за день, и определяю приоритеты в зависимости от срочности. Я рассказал об этом Фрэнки, и она ответила: «Короче говоря, ты составляешь список действий». Он представляет собой перечень задач или поведений, поочередно выполняемых игровыми юнитами. Это одна из форм системы конечных состояний, которая напоминает обычное дерево поведения с одной ветвью. По крайней мере, так утверждает моя собака.

Принцип работы

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



Затем расставим их в порядке приоритета – от самого низкого до самого высокого.



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

Первое действие в нашем примере – «Атаковать игрока» – будет выполняться при условии, что юнит находится рядом с игроком. Предположим, что это не так. Тогда начинается поочередная проверка остальных действий: можно ли (и нужно ли) построить лестницу на этом месте и так далее, пока не будет найдено действие, отвечающее условиям выполнения. Пускай это будет действие «Выбить дверь».



Здесь в игру вступает блокировка. Если действие «Выбить дверь» происходит мгновенно, оно не блокирует последующие действия, и они продолжают выполняться. Однако для большинства действий требуется несколько фреймов, так что это скорее исключение, чем правило. В нашем случае действие «Выбить дверь» вызывает unit.Attack(door), и тогда свойство юнитов CurrentState меняется с Waiting на BreakDoor и возвращает значение true до тех пор, пока дверь не будет сломана.

Простой конечный автомат

Итак, всё вполне осуществимо. Стоит отдать должное Фрэнки: списки действий как нельзя лучше подошли для моего проекта. Но меня по-прежнему смущало, что раньше я никогда о них не слышал. С другой стороны, в контексте ИИ часто упоминают конечные автоматы на основе переходов, похожие на систему анимации Mecanim в Unity3D. Вы определяете набор состояний и указываете, когда и каким образом между ними происходят переходы. В обмен на косточку Фрэнки объяснила, что при создании конечного автомата нужно не только определить все состояния, но и абсолютно все переходы для каждого из них. Здесь можно очень быстро запутаться. Например, если у вас есть состояние получения повреждений, вам нужно указать все состояния, из которых к нему можно перейти: при ходьбе, прыжке, приседании или атаке. Это может быть полезно, но в то же время чересчур сложно. Если у вас достаточно простые требования к ИИ, не стоит морочить себе голову.
Еще один минус конечных автоматов – сложная отладка. Если вы поставите точку останова, чтобы посмотреть на текущее состояние ИИ, вы не сможете узнать, какое состояние было до этого, пока не используете дополнительный отладочный код.

Недостатки списков действий

Познакомившись со списками действий поближе, я понял, что они идеально подходят для моего проекта, но также имеют некоторые минусы. Их основной недостаток, напрямую связанный с основным достоинством, – это простота. Из-за линейной структуры списков просто невозможно построить сложную иерархию приоритетов. Допустим, действие «Атаковать игрока» должно быть более приоритетным, чем «Выбить дверь», и менее приоритетным, чем «Двигаться к цели». Но при этом действие «Двигаться к цели» должно быть менее приоритетным, чем «Выбить дверь». Решать такие задачи с помощью списков действий очень сложно, в то время как конечные автоматы щелкают их как орешки.
В целом списки действий очень полезны для относительно простых систем ИИ, но чем сложнее искусственный интеллект, тем заковыристее становится их использовать. Тем не менее существует несколько способов расширить их функциональность.

Расширение функциональности

Некоторые юниты в моей игре могут двигаться и атаковать одновременно. Для них можно было бы сделать 2 списка действий – для движения и атаки. Но это было бы проблематично: что если при определенных движениях юниты не могут атаковать, или наоборот, для совершения определенных атак нужно стоять на месте? Здесь на помощь приходят полосы действий.

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

Каждое действие относится к одной или нескольким полосам. Следовательно, когда свойство Blocking возвращает значение true, действие блокирует только те элементы, которые находятся на одной или нескольких полосах вместе с ним. К примеру, «Атаковать игрока» относится к полосе действия, «Двигаться к цели» – к полосе движения, а «Построить лестницу» – к обеим, потому что во время строительства юнит не может двигаться и атаковать. Итак, теперь при выполнении действия все последующие элементы будут блокироваться, как задумано.



Пример реализации

А сейчас самое время попрактиковаться. Для начала настроим сам список и действия.



Вот так выглядит пример реализации IActionItem для действия BreakDoor («Выбить дверь»):



Список действий можно оформить в виде простого списка и наполнить его IActionItems.



Затем устанавливаем метод для поочередной обработки каждого фрейма (не забываем о блокировке).



С полосами действий всё немного сложнее. В этом примере мы зададим их в виде битового поля, а затем изменим интерфейс IActionItem.



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



Вывод

Спустя какое-то время Фрэнки попросила меня подытожить мои наработки. Хорошенько всё обдумав, я выделил несколько ключевых моментов:

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

Как правило, в программировании не бывает универсальных решений. Имея в своем арсенале множество инструментов, вы сможете подбирать оптимальные решения для конкретных проблем. Для игры King Randall’s Party идеально подошли списки действий. Кто знает, может, это именно то, что нужно и вашему проекту?