Разработка интерактивного агента компьютерной игры

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

Название: Бездействие.

Акторы: пользователь, интерактивный агент.

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

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

Основной поток: Игрок находится вне зоны видимости агента. Агент выбирает случайное направление и начинает двигаться в нем. Через случайный промежуток времени агент останавливается и либо меняет направление и продолжает двигаться, либо проигрывает анимацию бездействия. Агент старается оставаться в пределах заданной для бездействия территории. Если агент выходит за пределы этой территории выполняется подпоток S1.

Подпоток (S1): если в процессе движения агент выходит за пределы отведенной для бездействия площади, он разворачивается к центральной точке этой площади и начинает движение к ней.

Название: Преследование противника.

Акторы: пользователь, интерактивный агент.

Описание: Игрок или враждебный агент появляются в зоне видимости агента

Триггер: в зоне видимости агента появляется игрок или враждебный агент. Раздражитель находится вне зоны поражения агента.

Основной поток: Игрок подходит к агенту и попадает в зону его видимости. Агент разворачивается к игроку и начинает движение. Скорость движения агента больше, чем скорость движения в состоянии бездействия. Агент продолжает движение до тех пор, пока не достигнет противника, либо пока не перейдет в более приоритетное состояние.

Название: Атака противника.

Акторы: пользователь, интерактивный агент.

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

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

Основной поток: Игрок подходит ближе к агенту. Агент экипирует оружие и наносит удар игроку, в это же время играет соответствующая анимация атаки.

Название: Побег от противника.

Акторы: пользователь, интерактивный агент.

Описание: Игрок или вражеский агент находится в поле зрения агента, агент решает избежать битвы и начинает удаляться от противника.

Триггер: в поле зрения агента находится более сильный игрок или агент.

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

Название: Реакция на урон.

Акторы: пользователь, интерактивный агент.

Описание: При получении урона агент реагирует на него, путем проигрыша анимации и звуков.

Триггер: Агент получает урон.

Основной поток: Игрок наносит повреждения агенту. Если агент находится в движении, то он останавливается. Далее агент проигрывает анимацию и звук получения урона. Здоровье агента уменьшается.

Название: Смерть.

Акторы: пользователь, интерактивный агент.

Описание: Получив большое количество урона, агент переходит в состояние смерти в котором он прекращает свою деятельность.

Триггер: Уровень здоровья меньше нуля или равен ему.

Основной поток: Игрок наносит повреждения агенту. Если агент находился в движении, он останавливается. Агент проигрывает анимацию смерти и останавливает свою деятельность.

1.3 Анализ литературы

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

Ян Милингтон в своей книге “Artificial Intelligence for Games” рассматривает большое количество подходов к разработке интерактивных агентов. Среди рассмотренных им методов есть, как и довольно распространённые такие как конечные автоматы, продукционные правила и деревья решений, так и менее известные, например, нечеткая логика, нейронные сети, деревья поведения с обучением. Ян считает, что выбор подхода к разработке интерактивного агента должен быть обусловлен жанром игры. Он так же приводит несколько примеров архитектур и алгоритмов, наиболее подходящих для каждого из рассмотренных жанров. В список рассмотренных им жанров попадают наиболее распространенные жанры игр, в этом списке находятся шутеры, стратегии (пошаговые и реального времени), гонки и спортивные игры. Из описанных им жанров для разрабатываемой игры наиболее подходящим является шутер. Миллингтон считает, что в данном жанре наиболее популярным является подход на основе конечного автомата, а гибкости или расширяемости системы агента можно добиться, увеличив количество конечных автоматов.

Мэт Букланд в своей книге “Programming AI by Example” рассматривает несколько меньше подходов чем Миллингтон. В основном он фокусируется на подходе, основанном на конечном автомате, но также упоминает нечеткую логику и целенаправленные системы. Мэт предлагает необычный подход к разработке конечного автомата, когда переходы в другие состояния содержатся внутри самого состояния, а не являются его отдельным атрибутом.

В своих ранних работах о разработке интерактивных агентов, одной из которых является книга “AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors”, Алекс Шампандар в основном фокусируется на создании агентов на основе нейронных сетей или генетических алгоритмов и лишь мельком упоминает нечеткую логику, конечные автоматы и системы продукционных правил, но в более поздних работах он уделяет большое внимание деревьям поведения, и считает их наиболее приоритетным направлением в развитии интеллектуальности интерактивных агентов. Среди основных преимуществ деревьев Алекс выделяет их гибкость, простоту реализации и реалистичность поведения основанных на них агентов.

Пол Тозу в его статье о эволюции систем интерактивных агентов, приведенной в книге “AI Game Programming Wisdom” обозревает наиболее популярные в последние года подходы. Среди упомянутых им подходов присутствуют системы не упоминаемые рассмотренными выше авторами. Среди таких систем находятся мульти-агентные системы, системы на основе логики первого порядка, экспертные системы. Несмотря на обзор такого большого количества систем, Пол утверждает, что наиболее эффективно себя проявляют популярные подходы, основанные на конечных автоматах, деревьях поведения и продукционных правилах.

Дэвид М. Бург, Гленн Симан в своей книге “AI for Game Developers” обозревают такие техники как конечные автоматы, системы продукционных правил, нечеткую логику, нейронные сети и генетические алгоритмы. Они разделяют данные алгоритмы на два вида - детерминированные и недетерминированные. Детерминированные алгоритмы, к которым относятся конечные автоматы, системы продукционных правил и нечеткая логика, просты для реализации и не требовательны к ресурсам, что с одной стороны позволяет легко их протестировать, переопределить и не беспокоиться о производительности, но с другой стороны, эти алгоритмы создают предсказуемое поведение, что сокращает время геймплея. Недетерминированные алгоритмы, такие как нейронные сети и генетические алгоритмы, позволяют получить разнообразное и непредсказуемое поведение агентов без написания дополнительного кода, но они сложны в тестировании и ресурсоемки. Тем не менее авторы считают, что будущее интерактивных агентов стоит именно за недетерминированными алгоритмами, потому что, обучаясь они создают все больше и больше моделей поведения, поддерживая интерес игрока.

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

Анализ литературы показал, что несмотря на большое количество разнообразных подходов к разработке интерактивных агентов и их постоянное развитие, некоторые подходы не теряют своей популярности. К таким подходам можно отнести конечные автоматы, системы продукционных правил, нечеткую логику и деревья решений. Помимо этого, довольно часто авторами упоминаются машинное обучение в виде нейронных сетей и генетических алгоритмов. Несмотря на то, что данные подходы считаются довольно перспективными, они очень редко используются в коммерческих играх, в виду их специфики. Данные подходы никогда не использовались в играх жанра Action RPG, поэтому они не будут включены в анализ подходов к разработке интерактивных агентов для игры Exoplanet: First Contact.

1.4 Анализ подходов к разработке интерактивного агента

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

Данные подходы будут проанализированы на основе следующих параметров:

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

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

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

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

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

Система на основе продукционных правил -- это подход, основанный на наборе правил IF…THEN. Данный подход один из самых старых подходов к разработке интерактивного агента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.1. Анализ подходов к разработке интерактивного агента