Игровой ИИ. Utility Based AI

Продолжаю мой цикл про игровой ИИ. В предыдущей части мы начали рассматривать ИИ, основанный на полезности (Utility Based AI). В этой части мы отойдем от темы выбора поведения и рассмотрим, как подход полезности может быть полезен для выбора инструментов и целей поведения. Также не забывайте подписываться на мой канал, чтобы не пропустить следующие части.

Выбор точки в пространстве

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

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

1. Генерация точек. Мы генерируем список точек вокруг объекта/объектов, определяемых дизайном или требованиями к перемещению нашего ИИ. Такие объекты можно называть контекстом нашей генерации. Например в роли контекста могут выступать текущая цель в бою, или пешка ИИ, или дверь, которую необходимо охранять. Для такой генерации можно использовать геометрический подход, когда мы выбираем точки внутри некоего заданного объема или поверхности. Например мы можем выбрать точки в кубе, который располагается в координатах нашего контекста. Затем мы разобьем куб на равные ячейки, и центр каждой ячейки будет результатом генерации. Альтернативой может служить получение точек из игрового окружения контекста. Например мы можем собрать все игровые объекты с меткой “Укрытие” и вернуть их координаты как результат генерации.
2. Проекция точек. После того как точки сгенерированы, чаще всего имеет смысл спроецировать их на нашу навигационную систему: это может быть NavMesh, NavGrid, или любая другая навигационная система.
3. Фильтрация точек. Теперь к каждой точке мы можем применить бинарную функцию полезности, чтобы определить, годится ли она для нашего поведения. Например, это может быть функция, проверяющая есть ли у агента путь до точки, или функция, которая проверяет есть ли видимость до цели в бою из этой точки.
4. Вычисление полезности. После того как неподходящие точки были отфильтрованы, мы вычисляем полезность для каждой точки. Для этого может быть использован разный набор функций полезности, очень сильно зависящих от требований конкретного дизайна и поведения. Кроме того, такие требования, а следовательно и функции, могут быть динамичными. Например не раненный ИИ предпочитает точки ближе к игроку, а раненый точки дальше от игрока.
5. Выбор лучшей точку. Если для ИИ чаще всего выбирают поведение с наивысшей полезностью, чтобы позволить игроку прогнозировать поведение ИИ, а ИИ - выглядеть умными, то для точек в пространстве часто лучше добавить эффект случайности. Для этого выбирается либо пороговое значение общей полезности (после чего выбирается случайная точка из числа тех, у кого полезность выше порога), либо выбирается доля точек (например 10% с наивысшей полезностью), после чего из получившегося топа точек выбирается случайная. Такой подход позволяет легко разнообразить поведение ИИ, и тем самым разнообразить геймплей.

Unreal Engine 5 Environment Query System

Отличным примером системы выбора точек с использованием полезности служит Environment Query System в Unreal Engine 5. Мы уже использовали эту систему для нашего тестового ИИ на Behaviour Tree. Теперь, когда мы знакомы с принципами полезности, давайте взглянем на неё подробнее.

Основой EQS служат запросы (Environment Query), которые в свою очередь состоят из последовательности генераторов. EQS подразумевает, что генератор с фильтрами может не вернуть ни одной точки, потому что нет подходящей проекции на навигационную систему, либо потому что фильтры не пропустили ни одной точки. В таком случае систему обращается к следующему генератору.

Генератор отвечает за проекцию точек на навигационную систему, поэтому в нем же находятся все настройки для такой проекции

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

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

В EQS результат каждого фильтра умножается на константу, настраиваемую для каждого фильтра, после чего суммируются. Результирующее значение полезности очевидно будет не нормализованным, но, поскольку мы анализируем набор из одинаковых объектов с одинаковым количеством фильтров, диапазон значений не должен повлиять на качество выбора. Один из минусов такого подхода - для линейных полезностей бывает тяжело настроить правильные коэффициенты, чтобы добиться естественного поведения ИИ. Мой опыт показывает, что для сложных запросов чаще бывает проще воспользоваться тем, что один EQ может иметь серию последовательных генераторов, а следовательно сложные запросы можно разбить на несколько простых. Например: вместо одного огромного генератора, который анализирует все точки вокруг снайпера, мы не пытаемся написать сложные фильтры с разными весами, а создаем несколько простых. Первый генератор анализирует точки вокруг снайпера. Потом мы ищем точки в большем радиусе, но с фильтром на высоту, пытаясь отфильтровать хорошие точки для обзора. Затем (и если они нам не подходят) мы ищем точки возвышенности вокруг нашей цели.

Выбор цели в бою.

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

Сразу можно выделить два подхода: первый - когда наш ИИ выбирает цель, реагируя на некоторые события из внешнего мира (например окончание атаки, или завершение некоторого поведения). Такой реактивный подход позволяет нам быть уверенным, что смена цели происходит в строго определенный дизайном момент, и позволяет нам не сильно переживать из-за оптимизации, так как такие события будут происходит редко, а следовательно мы можем улучшить качество выбора и усложнить наши фильтры и функции полезности. К минусам можно отнести медлительность нашего ИИ: может пройти заметное количество времени, пока ИИ решит поменять цели. У игрока может сложиться впечатление, что ИИ не реагирует на изменяющуюся ситуацию и выглядит глупо. Такой подход подойдет для пошаговых игр или игр с медленным геймплеем, либо если дизайн подразумевает некоторое упрямство в ИИ.

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

Теперь  разобьем алгоритм выбора целей для нашего ИИ на простые шаги:

1. Построение списка целей. Для начала наш ИИ должен собрать список всех доступных целей. В простейшем случае это может быть список всех игроков, в более сложных случаях мы можем использовать систему рецепторов (perception в UE5).
2. Выбор фильтров. Поскольку мы анализируем набор одинаковых объектов, логично считать, что мы будем использовать одинаковый набор фильтров и функций полезности для каждого объекта. Но вот состояние самого агента может влиять на набор фильтров и функций полезности. Например для ИИ с двумя фазами боя (ближнего и дальнего боя) выбор целей может отличаться в зависимости от фазы. Кроме того стартовый выбор цели может потребовать еще один набор фильтров и функций полезности, которые отличаются от наборов для изменения выбранной цели. Следовательно после составления списка мы выбираем набор фильтров и функций полезности для нашего анализа.
3. Применение фильтров. Следующим шагом будет отфильтровать неподходящие цели с помощью актуального набора фильтров. Здесь возникает первое отличие между реактивным и пассивным подходами выбора целей. Для пассивного подхода некоторые фильтры могут быть не актуальны для активной цели. Например мы можем игнорировать цели, с которыми у нашего ИИ нет прямой видимости. Но для активной цели это будет выглядеть глупо. ИИ будет терять интерес к игроку, который на пару кадров скрылся за углом.
4. Вычисление полезности. Теперь для оставшихся целей мы вычисляем полезность. Аналогично фильтрам, некоторые функции полезности могут иметь дополнительный коэффициент для текущей цели, либо мы можем добавить дополнительную функцию полезности, которая возвращает положительную полезность только для текущей цели.
5. Выбираем лучшую  цель. Последним шагом является выбор цели с максимальной полезностью.

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

В следующий раз мы попробуем реализовать выбор поведения, используя подход полезности.