Разработка алгоритма для формирования поведения игрового агента
Анализ систем формирования поведения игрового агента и способов их применения. Описание систем Behavior Trees, Utility AI. Критерии сравнения жанров разработанных игр: форма, доступность, порог вхождения. Разработка алгоритмов поведения игрового агента.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 01.12.2019 |
| Размер файла | 2,8 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Пермский филиал федерального государственного автономного образовательного учреждения высшего образования
Национальный исследовательский университет «Высшая школа экономики»
Факультет экономики, менеджмента и бизнес-информатики
Кафедра информационных технологий в бизнесе
Образовательная программа «Бизнес-информатика»
Выпускная квалификационная работа
по направлению подготовки 38.03.05 Бизнес-информатика
Тема:
Разработка алгоритма для формирования поведения игрового агента
Студент Колесников Д.С.
Руководитель к.ф.-м.н.,
доцент, Е.Б. Замятина
Пермь, 2019 год
Аннотация
Колесников Д.С.
Разработка алгоритма для формирования поведения игрового агента: Выпускная квалификационная работа. - М.: Кафедра информационных технологий в бизнесе, 2019. - 72 с., в т.ч. 31 илл., 3 табл, 1 прил.
Выпускная квалификационная работа содержит пошаговое описание проведённой работы в отношении систем формирования поведения игрового агента и их применения в индустрии разработки компьютерных игр. Работа написана в сотрудничестве с компанией «Alternativa Games», которым требуется способ модификации их существующих моделей поведения игровых агентов. В ходе работы была выбрана система Behavior Trees для разработки и выбран алгоритм, который был смоделирован и реализован в среде разработки игрового движка Unity. Выпускная квалификационная работа состоит из четырёх глав.
Оглавление
- Введение
- Глава 1. Анализ систем формирования поведения игрового агента и способов их применения
- 1.1 Описание систем формирования поведения
- 1.2 Описание Behavior Trees
- 1.3 Описание Utility AI
- Выводы по главе 1
- Глава 2. Сравнение систем формирования поведения игрового агента
- 2.1 Краткий обзор исследований, касающихся систем формирования поведения игрового агента
- 2.2 Описание критериев сравнения
- 2.2.1 Жанры разработанных игр
- 2.2.2 Форма представления
- 2.2.3 Доступность инструментария
- 2.2.4 Порог вхождения
- 2.2.5 Модульность
- 2.2.6 Расширяемость
- 2.2.7 Способы принятия решений
- 2.2.8 Сложность проектирования
- 2.2.9 Сложность реализации
- 2.3 Проведение сравнительного анализа
- Выводы по главе 2
- Глава 3. Описание решений по разработке алгоритмов поведения
- 3.1 Описание предлагаемых к реализации алгоритмов
- 3.1.1 Поиск кратчайшего пути в полигоне
- 3.1.2 Определение успешности атаки метательным/огнестрельным оружием
- 3.1.3 Поиск пути на больших картах
- 3.1.4 Генерация навигационного меша
- 3.1.5 Выбор постановки алгоритма
- 3.2 Обзор инструментов для разработки на основе Behavior Trees
- 3.2.1 Платные Unity-плагины
- 3.2.2 Бесплатные Unity-плагины
- 3.2.3 Выбор подходящего инструмента
- Выводы по главе 3
- Глава 4. Разработка алгоритма поведения игрового агента
- 4.1 Проектирование алгоритма
- 4.1.1 Выявление требований
- 4.1.2 Построение модели поведения
- 4.2 Реализация алгоритма
- 4.2.1 Настройка игровой сцены
- 4.2.2 Создание шаблонов игровых объектов
- 4.2.3 Построение модели поведения в Unity
- 4.2.4 Генерация навигационного меша
- 4.2.5 Разработка скриптов
- Выводы по главе 4
- Заключение
- Библиографический список
- Приложение. Исходный код скриптов
Введение
Для компьютерных игр искусственный интеллект (ИИ) - один из способов моделирования виртуального мира, если стоит задача создать наиболее достоверный и соответствующий действительности аналог реального мира. Зачастую ИИ применяют при разработке игровых агентов - объектов, способных как-либо взаимодействовать с игроком. Использование ИИ в играх ограничено заданным разработчиком набором моделей поведения, которые агенты производят в присутствии или в ответ на действия игрока, чтобы у последнего возникло чувство правдоподобности виртуального мира [1]. Использование всех возможностей искусственного интеллекта, к примеру, самообучения, избыточно с точки зрения производительности конечного программного продукта.
В зависимости об области применения существует разделение агентов на следующие категории:
· неигровые персонажи (non-playable characters, NPCs) - простые модели персонажей или объектов в виртуальном мире, предназначенные для взаимодействия с игроком;
· боты - модели персонажей, поведение которых в большей степени повторяет таковое у игрока, и предназначенные преимущественно для противодействия игроку в соревновательных целях.
Первая категория агентов обычно обладает простейшими функциями, которые являются реакцией исключительно на действия игрока, исходя из чего, разработчики могут задать им ограниченное количество состояний, необходимых для этого конкретного агента. Этот метод, который называется «Машина с конечным числом состояний» [2,5], или конечный автомат, отлично подходит для агентов, которые самостоятельно не взаимодействуют с игровым миром, кроме как по команде игрока. Более сложное моделирование и разработку требует вторая категория игровых агентов, что обусловлено их назначением. Исходя из того, что ботам необходимо своим поведением быть максимально похожим на человека, использование подхода моделирования для NPC приведёт к огромному количеству состояний, «отладка которых становится крайне трудоёмкой» [2]. Для преодоления такой проблемы избыточности были разработаны несколько решений, т.н. систем формирования поведения игрового агента, задачей которых является приведение поведения игрового агента к некоторому алгоритму - вместо списка состояний используется ряд действий и условий, в зависимости от которых совершаются действия.
Использование систем формирования поведения игрового агента полезно при моделировании сложных действий, поскольку позволяют структурировать функциональные возможности для каждого из агентов. Действия искусственных «игроков» становится проще разрабатывать и тестировать. Тем не менее, одна подобная система не решает весь возможный ряд проблем, таких как ресурсоёмкость алгоритмов или недоработки в разработанной модели поведения. В современных условиях, когда «идеального» решения не существует, и исследования, призванные придумать новый стандарт разработки ИИ, проводятся до сих пор, разработчик должен уметь подбирать одну из имеющихся систем в зависимости от стоящих перед ним задач. В зависимости от разных критериев, например, жанра игры, концепции поведения игровых агентов и многих других, важно выбирать только необходимое решение, что в итоге положительно скажется как на сложности разработки компьютерной игры и степени аппаратной оптимизации алгоритмов, так и на впечатлениях от неё у конечного потребителя, игрока.
В индустрии разработки компьютерных игр сейчас существует конкуренция между студиями разработчиков, которые стремятся завлечь внимание к своим продуктам улучшениями в разных областях, в т.ч. искусственного интеллекта. В попытках создать «революционный» ИИ в течение нескольких десятилетий разные разработчики разрабатывали системы алгоритмизации действий персонажей, совершенствовали их и заменяли на более сложные. На данный момент существует множество систем формирования поведения игрового агента, сравнение и выбор которых - не менее самостоятельная работа, чем проектирование и разработка алгоритмов поведения персонажей внутри игры.
Объектом исследования является поведение игрового агента, в отношении которого применяется термин «искусственный интеллект». Предмет исследования - система формирования поведения игрового агента, а также способы их реализации на определённых игровых движках.
Цель исследовательской работы - изучить работу систем формирования поведения игрового агента, применив наиболее подходящую из них в реализации алгоритма поведения.
Для достижения цели были выделены определенные задачи, которым необходимо будет следовать при выполнении работы:
1. Изучить исследовательские работы, посвященные системам формирования поведения игровых агентов, а также документацию.
2. Провести сравнительный анализ систем формирования поведения на основе ряда выделенных критериев.
3. Провести краткий обзор инструментов для разработки на основе выбранной системы формирования поведения игрового агента.
4. Подобрать алгоритм для реализации определённого функционала игрового агента.
5. Спроектировать и реализовать выбранный алгоритм с помощью игрового движка Unity.
Исследовательская работа включает сравнительный анализ двух систем формирования поведения игрового агента, а именно:
· Behavior Tree - парадигма разработки алгоритмов ИИ с помощью иерархических деревьев, которая «даёт разработчику полный контроль над поведением агента и производительностью алгоритмов» [3];
· Utility AI - система, реализующая «теорию предельной полезности» [4], по которой все состояния игрового агента содержат некоторое значение «оценки полезности», и для действия агента выбирается комбинация условий с наибольшей суммой оценок.
Выбранная в ходе сравнения система будет использована для реализации какого_либо алгоритма, соответствующего жанру игры, с использованием игрового движка и имеющихся в свободном доступе инструментов разработки. Для подбора реализуемого алгоритма тоже следует провести сравнительный анализ, исходя из возможных критериев - сложности реализации, имеющегося времени и т.д. Реализация может быть проведена с помощью одного из следующих игровых движков - Unreal Engine 3/4, CryEngine, Unity. Для разработки на этих движках используются популярные языки объектно-ориентированного программирования, а также возможные расширения, уменьшающие объём работы с непосредственно кодом, что не должно доставить трудностей.
В предлагаемые к реализации задачи для игрового агента включены:
· поиск кратчайшего пути в полигоне - требуется найти путь между двумя заданными точками в сложном неконвексном полигоне;
· определение успешности атаки метательным/огнестрельным оружием - имеется геометрия сцены, необходимо определить какие данные нужны для проверки, создать алгоритм, позволяющий производить проверку на основе данных;
· поиск пути на больших картах - на больших картах поиск пути может быть долгим, поэтому необходимо разработать решение, которое позволит просчитывать путь не полностью и с минимальными потерями качества;
· генерация навигационного меша - требуется реализовать создание меша, который будет представлять собой поверхность, по которой могут перемещаться игровые агенты.
Глава 1 исследовательской работы будет содержать обзор исследовательских работ и разработок в области игрового искусственного интеллекта, в частности с использованием рассматриваемых систем. В результате будет сформировано представление об областях применения тех или иных решений, а также выделены некоторые сравнительные показатели.
В Главе 2 приведённые сравнительные критерии будут подлежать более подробному анализу и применены по отношению к каждой из двух систем. На основе этого будет сделан вывод о том, какая система подойдёт лучше для разработки требуемых алгоритмов.
Глава 3 должна содержать список требуемых для реализации алгоритмов поведения игрового агента, а также некоторых инструментов разработки, поддерживающих выбранную систему. В результате будет приведено описание инструментов и обоснование выбора одного из них.
Глава 4 будет содержать последовательное описание реализации алгоритма поведения игрового агента на выбранном игровом движке. По результатам этой главы получится программный код, а также работающая программа, моделирующая игровую среду и определённое поведение в ней персонажа.
Глава 1. Анализ систем формирования поведения игрового агента и способов их применения
Использование старых методов программирования игрового ИИ сопряжено с рядом проблем, которые становятся более явными с ростом масштаба будущей игры. В ходе главы необходимо определить, с какой целью игровая индустрия со временем перешла к более современным методам в лице систем формирования поведения игрового агента. Это должно позволить понять, в каких приблизительно задачах будет особенно эффективна та или иная система.
1.1 Описание систем формирования поведения
Рассматриваемые системы формирования поведения являются лишь логическим развитием искусственного интеллекта, созданные с целью обеспечить более простое формирование действий агента и реакций на события извне, а также обеспечить более легкий доступ к их отладке. Последнее достигается путём использования другого подхода к проектированию поведения, который заключается в как можно меньшей нагрузке на программиста и использовании методов визуализации - графиков, деревьев, таблиц и т.д. Такой подход позволяет сократить время на непосредственную разработку поведения, и посвятить больше времени проектированию, что позволить усложнить поведение агента и сделать его более убедительным.
Более традиционный метод формирования игрового ИИ - конечный автомат - берёт своё начало из теории вычислительных систем, что означает, что такой подход может быть применён к алгоритмам на любом уровне абстракции. Универсальность работы конечного автомата подтверждается в работе [5]: «…можно спроектировать алгоритм, который кажется разработчику наиболее простым. Имея этот алгоритм, он может преобразовать его в наиболее эффективную форму». Конечный автомат очень производительный, поэтому он подходит для разработки простого поведения, например, в автоматических устройствах и датчиках, которые постоянно сверяют небольшой ряд показателей вокруг себя.
Для более удобного графического представления, в т.ч. для представления дизайнерам, возможно применение детерминированных графов, как таких, который изображён ниже (см. рис. 1.1). Подобное представление зачастую является плодом работы дизайнером по разработке концепции поведения, поскольку показывает смену состояний через ребро, соединяющее грани, т.е. состояний. Конечно, поведение должно с чего-то начинаться, агент с момента появления на игровом поле должен всегда иметь какое-либо состояние, поэтому присутствует модификатор состояния, обозначающий, что оно является начальным. Обычно от начального состояния исходит больше всего условий перехода к другим, поскольку в концепции подразумевается, что начальное состояние - то состояние, в котором агент пребывает, подавляющее количество времени. Конечный автомат никогда не может быть замкнут - если существует входное условие, всегда должно быть хотя бы одно выходное условие, чтобы агент не застрял в бесконечном цикле одного состояний, и не было необходимости перезагружать ИИ.
К сожалению, из универсальности применения следует недостаток конечных автоматов - отсутствие единой формы представления, что выражается в отсутствии эффективных инструментов работы с ними. Конечно, элементы автомата - состояния, переходы и т.д. - легко подвергаются абстракции и могут быть преобразованы в сущности и наборы условных операторов с помощью любого объектно-ориентированного языка программирования. Тем не менее, это лишняя нагрузка на программиста, вместе с этим усложняется понимание алгоритма дизайнерами, не владеющими программированием. Как оказывается, это распространённая и достаточно важная проблема среди разработчиков компьютерных игр.
Рисунок 1.1 Возможная графическая форма представления конечного автомата
Разработка сложного поведения связана с рядом проблем, которые дизайнеры искусственного интеллекта должны решать, если они намерены разработать ИИ, отвечающий современным стандартам и ожиданиям игроков [2]. Проблемы, с которыми приходится сталкиваться при расширении и усложнении поведения игрового агента:
1. Технические недоработки - с ростом функционала игрового агента растёт и количество багов, которые должны быстро исправляться перед выпуском игры;
2. Плохое взаимодействие команды - разработчикам тяжело создавать сложный ИИ в соответствии с концепцией игры, а дизайнерам - передать свои идеи разработчикам в формализованном виде, при том, что на обе стороны обычно давят жёсткие дедлайны.
3. Низкое качество - в конце концов, под давлением разработчики внедряют урезанный ИИ, исполняющий минимальные требования и действия, но уступающий в правдоподобности аналогичным разработкам.
Указанные проблемы постепенно приводят к снижению качества выпускаемых игр в целом, поскольку ИИ стал крайне важен для разработки даже простых независимых игр. По этой причине разработчик должен стараться что-то изменить в своём подходе к разработке - изменить команду или изменить инструменты и методы разработки. Создание систем формирования поведения игровых агентов поспособствовали перераспределению времени во время разработки, отдавая больше времени проектированию, чем ручному программированию, не говоря о том, что способы представления этих систем позволяют сформировать представление о возможностях агента даже людям, не владеющим языками программирования.
Тем не менее, системы формирования поведения - это крайне сложные математические модели, требующие от разработчика полного понимания их возможностей, чтобы понимать, с чем в итоге будет практичнее работать. В таком случае, правильный подбор системы формирования поведения игрового агента является такой же важной задачей, как непосредственная разработка поведения. Далее будут рассмотрены самые популярные решения, между которыми часто выбирают и крупные студии разработки игр, а также будут выделены некоторые особенности, которые позволят поверхностно определить наиболее подходящую сферу применения каждой из систем формирования поведения игрового агента.
1.2 Описание Behavior Trees
Метод Behavior Trees на данный момент является самым популярным решением для разработки сложного поведения внутриигровых агентов, являясь логическим развитием конечного автомата, повсеместно использовавшегося до этого. Большую популярность среди разработчиков новый метод приобрёл после выхода компьютерной игры Halo 2, где ставка делалась на столкновения с очень правдоподобными и опасными врагами, которые способны адекватно отвечать на действия игрока, использовать окружение в свою пользу и эффективно взаимодействовать в группах, применяя тактику. В 2005 году на основе на основе этой игры было наглядно показано [3], насколько непростой стала бы разработка такого амбициозного ИИ традиционными средствами, в основном из-за сложностей с отладкой сотен разных состояний. Behavior Trees были призваны побороть проблему избыточного количества состояний конечного автомата, при которых было бы крайне сложно следить за выполнением системы в реальном времени и исправлять ошибки. Дальнейшие исследования [6, 7] показали большую гибкость поведенческих деревьев в плане расширяемости, что позволило подключать более сложные функции. Такие функции избыточны для использования в играх, поскольку ИИ в играх не должен полностью занимать ресурсы компьютера, которому необходимо в реальном времени обрабатывать графику, физику, звук и т.д. Behavior Trees нашли своё применение в робототехнике за счёт расширяемости, позволявшей подключить полноценное машинное обучение, ведь обучать роботов можно на основе множества данных из реального мира, а не совокупности упрощённых игровых механик.
Можно выделить несколько особенностей этой системы:
· древообразное представление, имеющее сходство с деревом решений [8], и оттуда же перенимающее иерархическую структуру;
· в отличие от дерева решений, Behavior Trees не обязательно являются бинарными, родительские узлы могут иметь сколько угодно детей, в том числе только одного;
· поведение проходит строго по дереву, узел за узлом, что позволяет легко установить порядок действий;
· поскольку ИИ в играх исполняется в реальном времени, проход по поведенческим деревьям визуализируется параллельно с исполнением, что заметно упрощает отладку;
· поведенческие деревья хранят не набор состояний и переходов между ними, а набор действий, делая алгоритм более понятным для чтения, например, вместо утверждения «Если (Условие), то перейти из (Состояние 1) в (Состояние 2)» используется «Если (Условие), то выполнить (Действие)».
Рисунок 1.2 Пример поведенческого дерева, демонстрирующий поведение солдата на патруле
На рис. 1.2 представлен пример поведения игрового агента с помощью Behavior Trees на примере патрулирующего солдата. Действия солдата в случае появления неприятеля на объекте строго регламентированы и в реальной жизни - позвать подкрепление, сообщить в штаб, начать атаку и т.д. Такое поведение легко задать в рамках строгости иерархических деревьев. Строгость Behavior Trees характеризует, в первую очередь, обязательный узел, с которого начинается исполнение агента - Root. После этого, в отличие от дерева решений, главным является не выбор из двух альтернатив, а просмотр последующего узла, который называется композитным. Проход по дереву идёт строго вниз до нижнего уровня, где располагаются узлы действий, предписывающие непосредственные действия агента. В таком случае возвращается сообщение о том, что действие успешно выполнено (Success). Возможна такая ситуация, когда действие агента задано на продолжительное время, например, патрулирование территории, и тогда по достижении нижнего узла наверх передаётся сообщение о том, что действие не окончено (Running). Если по пути к нижнему узлу встретились условия, которые не были выполнены, в композитный узел возвращается сообщение о неудаче (Failure).
Ниже приведено несколько наиболее часто используемых типов композитных узлов, характеризующих возможности прохода по его дочерним узлам:
· селектор (Selector) - выполнение узлов прерывается, когда один из них вернёт сообщение Success;
· последовательность (Sequence) - все дочерние узлы выполняются в строго указанном порядке, и если все они успешно выполнены, возвращает Success, в случае невыполнения хотя бы одного возвращает Failure;
· параллельный узел (Parallel) - используется принцип, как в последовательности, но все узлы выполняются одновременно.
С помощью обозначенных элементов невозможно построить сложное поведение для агента, поскольку это будет просто повторение одинаковых действий поэтому в Behavior Trees включены особые блоки - декораторы. Они способны определять те самые условия, которым может или не может соответствовать агент в данный момент, и разработчики преимущественно используют декораторы с этой целью. Важным ограничением является то, что у декоратора может быть исключительно один дочерний узел, тот, к которому должно перейти управление. Обычно модели Behavior Trees также могут включать вспомогательные декораторы, определённым образом модифицирующие выполнение дочернего узла или изменяющие результат, идущий из него. К наиболее используемым декораторам относятся:
· повторитель (Repeater) - декоратор, устанавливающий цикличное повторение всех узлов, следующих после него, постоянно или некоторое число раз;
· повторение до провала (Repeat Until Fail) - дочерние узлы бесконечно повторяются до тех пор, пока один из них не вернёт сообщение о неудаче;
· инвертор (Inverter) - возвращает результат, противоположный тому, который пришёл из дочерних узлов.
Рисунок 1.3 Пример взаимодействия игрового агента с дверью в представлении Behavior Trees
Как видно, на выбор для моделирования с помощью Behavior Trees представлено несколько функциональных элементов, которые, в свою очередь, разбиты на множество других элементов. Таким образом, предоставляется свобода в выборе функционала будущего агента, а назначение обобщённых элементов, например, декораторов, достаточно просто для понимания. На рис. 1.3, описывающем использование игровым агентом двери, можно проследить, в каком порядке происходят действия. Начальным узлом является последовательность, поэтому начинается просмотр всех дочерних узлов слева направо. Предположим, что вся последовательность была выполнена, в таком случае порядок выполнения дерева выглядел так:
1. Агент подходит к двери (Walk to Door), если она есть в зоне его досягаемости - успех, переход к узлу справа.
2. В последовательность передано сообщение «В процессе».
3. Агент пробует просто открыть дверь (Open Door).
4. В последовательность передано сообщение «В процессе».
5. Агент проходит через проход после открытия двери (Walk Through Door).
6. В последовательность передано сообщение «В процессе».
7. Агент закрывает за собой дверь (Close Door).
8. В последовательность передано сообщение «Успех», алгоритм использования двери успешно завершён.
По данной последовательности действия видно, что прописанное поведение завершается в тот момент, когда сообщение доходит до начального узла, в данном случае, родителя [9], из-за чего может возникнуть ощущение, что поведенческие деревья ограничены простыми алгоритмами. На самом деле, главное достоинство деревьев заключается в их простой расширяемости, позволяющей разработчику добавлять новые условия и узлы практически сразу же, как только ему захочется. Действия легко помещаются в конечные узлы, а для некоторых типовых условий поведения доступны декораторы. Behavior Trees предлагают такие возможности моделирования, что возможно прописать абсолютно всё предполагаемое поведение в одном дереве, разбивая разные действия с помощью декораторов. Рис. 1.4 представляет, каким образом это будет выглядеть, в частности, при добавлении взаимодействия с окном. Несмотря на то, что для упрощения восприятия на этом дереве не отображены декораторы с условиями, заметен главный недостаток Behavior Trees, заключающийся в самой графовой структуре - при расширении восприятие дерева сильно ухудшается из-за наличия множества узлов и связей. Отладка всё еще не представляет труда для разработчиков, но дизайнерам становится всё сложнее следить за порядком действий, смотря на простой граф.
Следующим значительным недостатком Behavior Trees строгость строения дерева и его связей, что приводит к множеству необходимых зависимостей в поведении игрового агента. Это хорошо работает при расширении, поскольку добавить новый узел нижнего уровня не составляет особого труда, это требует лишь добавления новой связи в конце дерева.
Рисунок 1.4 Сильно модифицированное поведенческое дерево, расширяющее функционал агента
Проблема состоит в том, что может понадобиться скорректировать уже существующее поведение, доходящее вплоть до самого верхнего уровня дерева. Достаточно сложный игровой ИИ, необходимый для больших коммерческих игр, разработанный с помощью Behavior Trees, может быть расширен до сотни уровней. Смотря на схемы поведенческих деревьев, можно понять, что чем ниже уровень, тем больше узлов, а, соответственно, и связей между ними. Всё это требует последовательного изменения всех нижних узлов, например, если в вычислениях участвует одна переменная, которая и была изменена. Таким образом, чтобы избежать таких изменений, нужно как можно точнее определять поведение агента ещё на стадии проектирования. Несомненно, это потребует больше времени и ресурсов, но всё же не так много, как в случае, когда разработчику приходится практически перестраивать дерево в случае малейших изменений.
Подводя итоги тому, какие особенности работы с Behavior Trees были выделены в этой работе, можно сделать некоторые выводы касательно применения поведенческих деревьев. На данный момент Behavior Trees выглядят самым универсальным средством формирования поведения игрового агента из-за их особенностей. Простая структура деревьев позволяет быстро строить достаточно простое поведение при том, что для этого не требуется слишком много элементов - как было показано в примерах выше, достаточно блока последовательности для базового поведения, например, патрулирование или взаимодействия с предметом. При построении сложного поведения, включающего более одного действия, сильно возрастают требования к проектировщикам. Более того, визуальное восприятие дерева, которое разрастается до нескольких десятков уровней, затрудняется. Тем не менее, проход дерева в реальном времени значительно облегчает исправление ошибок, позволяя разработчику проводить симуляцию с агентом на лету.
1.3 Описание Utility AI
Концепция системы Utility AI пришла из совершенно другой области, в отличие от Behavior Trees, которые были ответом на растущие требования конкретно к игровому ИИ. В основе этой новой парадигмы лежит теория предельной полезности - математическая модель из экономической теории, согласно которой итоговую ценность некоторого ресурса составляет его субъективная оценка потребителем в зависимости от того, сколько единиц было потреблено. Это и есть полезность, которая не связана с объективной оценкой ресурса - стоимостью - которая в условиях макроэкономической стабильности практически не меняется. Предельная полезность обычно представлена в виде нисходящего графика, который демонстрирует обратную зависимость полезности для потребителя от количества потреблённых единиц. Когда человек испытывает нужду в некотором ресурсе, его полезность достигает практически максимума, но с последующими приобретёнными единицами происходит «перенасыщение», причём обычно экспоненциальное - с каждой полученной единицей полезность падает всё больше, постепенно достигая нуля. Исходя из таких особенностей, теория получила широкое применение в тех сферах, где важно определять предпочтения людей на основе их личных приоритетов - в микроэкономике и теории игр [11]. Получается, что теория предельной полезности должна подходить при создании агентов - зачастую моделей реальных людей, для которых часто субъективная оценка является самой приоритетной.
Свою эффективность Utility AI продемонстрировала с выходом игр Killzone 2 и F.E.A.R. [2], в которых в боях сталкиваются обученные вооружённые части. Требования к поведению таких противников невероятно высоки не только потому что они должны показывать себя, как профессионалы ведения боя, но и как люди, которые в критической ситуации могут кардинально менять приоритеты.
Особенности системы на основе теории предельной полезности:
· поведение состоит из набора действия и условий, как внешних, так и состояний игрока, и каждому из условий причисляется численная единица, характеризующая полезность в данный момент;
· возможность описать поведение с помощью естественного языка, что упрощает взаимодействие команды разработки при необходимости непредвиденного изменения поведения;
· отсутствие строгих связей, что позволяет легко расширять поведение игрового агента без риска нарушить зависимости;
· полезность действий считывается в реальном времени с помощью уже указанных ранее кривых предельной полезности, и в любой момент времени просто выбирается действие с наибольшим значением.
Стоит расширить последний пункт, добавив к нему то, что Utility AI способен использовать кривые в обратную сторону, создавая восходящие графики полезности. В частности, это может быть полезно при моделировании повседневной деятельности человека достаточно правдоподобно. Например, полезность сна для человека может определяться временем его активности, оставаясь малой большую часть дня, но по прошествии 12 часов начинает повышаться в прогрессии.
На конференции GDC в 2010 г. продемонстрировали [11] крайнюю гибкость Utility AI в плане применения кривых через пример, изображенный на рис. 1.5. Здесь проиллюстрирована зависимость напряжённости человека, к которому приближается другой человек с оружием в руках.
Рисунок 1.5 Пример разных способов составления кривой полезности
Конечно, здесь использовался стандартный вид нисходящей кривой, когда ощущение опасности повышается с сокращением между людьми дистанции. Подход к построению кривых позволяет применять известные математические формулы для демонстрации разных обстоятельств в одном действии. Простейшая бинарная функция, изображённая здесь, не рекомендуется к применению в таком мощном методе, как Utility AI, поскольку это можно задать простым условным оператором. По этой же причине не стоит задавать с помощью кривых строгие назначения для игровых агентов, например, полный запрет на использование какого-либо взрывоопасного оружия в закрытом помещении. В случае, если у агрессора холодное оружие, вполне подойдёт простая линейная прогрессия, экспоненциальная или сигмовидная функции. За счёт коэффициентов и сдвигов кривой на примере экспоненциальной функции (см. рис. 1.6 и 1.7), возможна простая модификация поведения, к примеру, если агрессор владеет огнестрельным оружием. Оружие в рамках игровых механик может обладать эффективной дальностью, снижением урона с прохождением снарядом дистанции и т.д., за счёт чего можно подгонять одинаковый график под множества разных обстоятельств.
Рисунок 1.6 Пример возможности по изменения коэффициентов кривой полезности
Рисунок 1.7 Пример возможности по сдвигу кривой полезности
В этом же примере приведено применение нормализованной переменной полезности, т.е. переменной в определённых пределах, в частности, между 0 и 1, что часто используется, чтобы отличить абстрактную полезность, основанную на субъективном восприятии, от разных реальных показателей - дистанции, количества очков здоровья, патронов и. т.д. Конечно, нужно задействовать промежуточные значения полезности, отличные от 0 и 1, чтобы разнообразить поведение агента наиболее простым образом. Вполне возможно, что человек, перед тем как убежать со всех ног подальше от агрессора, захочет предпринять что-либо ещё. Если задействовать другие показатели в качестве зависимой переменной в функции предельной полезности, всё равно стоит проводить нормализацию, потому что «Используя нормализованные значения полезности, мы можем определить отношения и сравнения, которые в противном случае были бы неясны» [11]. Скажем, на основе предыдущего примера, атакуемый агент будет пытаться отдалиться от атакующего по мере его приближения. Жертва, скорее всего, не будет сразу же убегать, а попытается медленно отходить, чтобы не раздражать лишний раз агрессора. Жертва будет постепенно набирать скорость, переходя на широкий шаг и, впоследствии, на бег в обратную сторону. Когда дистанция сильно увеличивается, атакованный имеет возможность замедлиться и, например, передохнуть. В данном случае нормализацию будет, если считать в километрах в час, в пределах от 0 до ~44 - самой большой зафиксированной скорости бега человека.
К разным показателям могут применяться коэффициенты, которые показывают постоянную превосходящую важность одного показателя по сравнению с другим. К примеру, традиционно в игровом жанре шутеров существуют два ключевых показателя - здоровье и патроны. Первое зачастую ограничено значениями от 0 до 100, а второе может быть не ограничено, к тому же патроны гораздо доступнее расположены на игровом поле, чем аптечки, восстанавливающие очки здоровья. Логично в таком случае добавить коэффициент более одного к показателю здоровья, чтобы добавить элемент объективности и рациональности в поведение такого игрового агента. Тем не менее, это применимо только в случае, если эти показатели применяются для вычисления какого-то другого показателя - коэффициенты имеют смысл только в рамках одной формулы. В остальных случаях используется привычный для Utility AI метод подбора наиболее подходящей математической прогрессии, внутри которой уже могут использоваться иные показатели и их коэффициенты. К примеру, график полезности, относящийся к здоровью, может быть более крутым, чем у боеприпасов, и приоритет по его восполнению возникает гораздо раньше, чем нужда восстановить боеприпасы (см. рис. 1.8). Также, имея строгие ограничения по возможным показателям здоровья и фактическое отсутствие рамок у патронов, последние удалось подогнать под одинаковый промежуток, и, тем самым, нормализовать оба показателя для большей точности сравнения полезности. На практике, ограничение патронов не только не навредит игроку, но и является обязательным в некоторых жанрах для сохранения баланса.
Рисунок 1.8 Нормализованный график полезности пополнения здоровья и патронов
Приведённые ранее способы применения методики, основанной на теории полезности, показывают, что, несмотря на простоту их работы, они повсеместно задействуют математические формулы для определения полезности таким же образом, как это делается в экономической теории. Это означает, что очень сильная нагрузка ложится на разработчиков, ответственных за концепцию поведения будущего агента, которым, помимо формально описания, требуется правильно задействовать известные математические прогрессии, что требует не только применения шаблонов проектирования, но и должного знания математического моделирования. В работе [12] результат совокупности таких навыков называется так - «простые и ёмкие решения часто встречающихся проблем дизайна». Чтобы добиться такого решения, желательно следовать ряду рекомендации по математическому дизайну:
· выделить ряд общих показателей, применимых для большинства действий, чтобы распределение условий происходило быстрее (см. рис. 1.9);
· составить иерархию показателей, чтобы понимать, каким из них агент должен отдавать больший приоритет при прочих равных условиях;
· крайне желательно проводить нормализацию значений в пределах необходимых им рамок, если это вообще требуется;
· абстрактные показатели - эмоциональное состояние, мораль - всегда нормализуются, чаще всего в промежутке от 0 до 1;
· можно обратиться к приёмам распараллеливания процессов просчёта показателей, поскольку их может быть очень много.
Рисунок 1.9 Пример множества сгруппированных значений, применимых к показателю, отвечающему за приоритет солдата к отступлению
Исходя из представленных возможностей, можно сделать вывод, что Utility AI - крайне гибкий современный метод, который уже зарекомендовал себя в качестве сильного инструмента создания игрового ИИ. Его зависимость от использования математических формул делает Utility AI очень похожим на традиционный искусственный интеллект, применяющий методы машинного обучения. Отсутствие необходимости в исходных данных компенсируется требованиями, предъявляемыми к разработчикам касательно самостоятельно подбора нужной прогрессии. Таким образом, очень важным является вклад дизайнеров, которые должны максимально понятным способом составить приоритеты будущего игрового агента.
Особенности Utility AI позволяют выделить её отличия от Behavior Trees:
· Utility AI просчитывает все возможности агента в реальном времени, а не только то, за которое отвечает узел, в котором находится система Behavior Trees;
· подбирается тот вариант, который в этот момент времени имеет наибольшую значимость, без необходимости цикличного прохода по дереву;
· лучше справляется с какими-либо промежуточными решениями, например, на какой скорости перемещаться между ходьбой и бегом;
· проще управлять потенциально противоречивой логикой, т.е. нерациональным принятием решений на основе субъективных показателей;
· отличная расширяемость Utility AI, которая позволяет не только легко добавить новые возможности для агента, но и, наоборот, накладывать полный запрет при определённых условиях.
Выводы по главе 1
По итогам рассмотренных исследовательских работ, можно сделать выводы о том, что системы формирования поведения игрового агента, которым посвящена эта работа, были созданы в ответ на постоянно растущие требования к игровому искусственному интеллекту. При этом, прогресс коснулся и самих систем, т.к. та же самая Utility AI призвана заменить поведенческие деревья, которые уже на данный момент начинают устаревать. Однако Behavior Tress всё еще являются выбором большинства разработчиков из-за относительно небольшого порога обучения, в то время как Utility AI - сложная математическая парадигма, берущая своё начало из экономической теории. Так или иначе, можно сделать промежуточные выводы касательно того, где лучше применять ту или иную систему. Behavior Trees должны подойти начинающим разработчикам, работающим в популярных жанрах - аркады, шутеры, стратегии и т.д. Использование деревьев для построения относительно несложных, но исполняющих свои функции моделей поведения не составляет особого труда ввиду интуитивности структуры дерева. В свою очередь, Utility AI обладает большим потенциалом для расширения игрового ИИ в сторону чего-то более передового, но требует больше знаний и навыков ещё до непосредственной разработки. Вероятно, необходимость знаний математического моделирования оттолкнёт начинающих разработчиков, но для профессионалов Utility AI предлагает такие же методы, которые позволили реализовать один из самых впечатляющих игровых ИИ за всю историю - в игре F.E.A.R. в 2005 году.
2. Сравнение систем формирования поведения игрового агента
На основе только теоретической информации о системах формирования поведения игрового агента тяжело сделать однозначные выводы, поэтому в этой главе должны быть рассмотрены примеры их практического применения. Из докладов разработчиков игр компаний разных масштабов или их выступлений на конференциях необходимо выделить те преимущества, на которые докладчики ставили наибольший акцент. Таким образом получится выделить ряд критериев и сопоставить обе системы, после чего выбрать наиболее подходящую для поставленной в этой работе цели.
2.1 Краткий обзор исследований, касающихся систем формирования поведения игрового агента
В прошлой главе были обобщённо рассмотрены исследовательские работы, касающиеся областей применения Behavior Trees и Utility AI. В этом разделе предлагается продолжить обзор, но уже с точки зрения более субъективных факторов, согласно которым выбирается та или иная система формирования поведения игрового агента. Это позволит определить новый ряд критериев, которые ранее были недоступны при поверхностном рассмотрении работ. Сюда же, вероятнее всего, будут включены и субъективные суждения авторов касательно, например, удобства или доступности использования какой-либо системы.
В работе [14] выбор Behavior Trees для разработки коммерческой игры DEFCON обосновывается тем, что поведение, заданное в поведенческих деревьях, легко подлежит повторному использованию. Так как авторы разрабатывали стратегию в реальном времени, в которой участвуют несколько уникальных противоборствующих фракций, был применён метод генерации деревьев. Его смысл в том, чтобы задать вручную базовое поведение, характерное для всех игроков, а затем случайным образом генерировать более глубокие узлы дерева.
В работе [6] представлено продвинутое использование Behavior Trees в робототехнике, в ходе которого заметно усложняются принципы вычислений. Тем не менее, выбор такой системы в качестве основы авторы обосновывают простотой понимания и гибкостью по сравнению с конечным автоматом. В качестве примера приводится тот факт, что переход по узлам действует таким же образом, как если бы он был закодирован с помощью такого оператора как GOTO, вызывающего нужную функцию.
В презентации своей системы [10], в основе которой лежат Behavior Trees, авторы из компании Remedy крепко связывают некоторый набор сенсоров, небольшую базу данных и поведенческие деревья, таким образом, создавая что-то похожее на киберфизическую систему, черпающую данные из реального мира. Тем не менее, авторы подчёркивают, что итоговая система небольшая, и будет расширяться с использованием других техник формирования поведение игрового агента для достижения наилучшего результата. В работе подчёркиваются недостатки Behavior Trees, в т.ч. плохая совместимость деревьев при моделировании поведения, не подлежащего цикличному повторению. В работе подводится такой итог, что Behavior Trees рекомендуется использовать в как можно более простой форме, т.е. на самых верхних уровнях поведения.
В работах [11, 12] подчеркивается неоспоримое преимущество Utility AI, заключающееся в постоянных относительных вычислениях, благодаря чему, в теории, агент всегда выбирает наиболее подходящее действие. Если в Behavior Trees имеется исходное состояние, обычно это бездействие, то возможна ситуация, когда во время прохода по дереву ни одно условие не было выполнено. В таком случае, агент останется бездействовать, хотя ему может угрожать очевидная опасность в виде убывающих очков здоровья. В Utility AI сдвиги в показателях определяются в любой момент времени, поэтому, если полезность всех действий очень мала, при потере здоровья, полезность лечения значительно возрастёт относительно остальных.
В работах [12, 13] используются несколько разных принципов принятия решения - абсолютный и относительный. В первом случае выбирается одно действие с наибольшим значением полезности, во втором - используется псевдослучайная функция, выбирающая одно действие из ряда с наибольшими значениями. В работе [13] демонстрируется пример правильно подхода к дизайну поедания агента в игре Sims 3. Так как это симуляция жизни простых людей, в проектировании поведения использовалась пирамида потребностей Маслоу, в которой полезность нужд человека определялась по их категориям - физиологические, социальные и т.д.
2.2 Описание критериев сравнения
2.2.1 Жанры разработанных игр
У Behavior Trees гораздо более продолжительная история использования, что привело к тому, что разработчики научились эффективно применять систему для множества разных жанров и моделей поведения. Систему удавалось удачно применять в совершенно различных жанрах, таких как шутеры и стратегии, новые методики расширения появлялись настолько часто, что сам принцип системы вышел за рамки применения только лишь в компьютерных играх.
Utility AI появилась значительно позже обратным образом - за счёт множественных исследований в областях математики и экономики. Результаты привели к созданию уже по умолчанию хорошо расширяемой системы, способной осуществлять самые разные модели поведения, подключая к ним как объективные, так субъективные факторы. Система уже доказала свою состоятельность в период своего дебюта, когда разработчики таких различных жанров, как шутеры и симуляция, воссоздали невиданное ранее в играх поведение игровых агентов.
2.2.2 Форма представления
Этот критерий важен тем, что позволяет передавать одну и ту же информацию о поведении игрового агента между подразделениями команды разработки игр, не беспокоясь об их уровне знаний. Behavior Trees нашли решение в своей древообразной структуре, выстраиваемой в строгую иерархию. Тот же дизайнер, не так хорошо понимающий сущности в ООП, будет легче воспринимать структурированный граф. По уровням легко можно определить общие и частные действия, и добавлять в структуру новые при необходимости.
Utility AI не кажется таким простым для понимания из-за множества информации, касающейся математических прогрессий. Для каждого показателя требуется собственная кривая полезности, которая не так просто воспринимается в отрыве от иных важных показателей. Несколько переменных можно свести к одному графику, но для этого требуется провести правильную нормализацию множества значений.
2.2.3 Доступность инструментария
Надо сделать замечание, что в рассмотренных ранее исследовательских работах практически не уделялось время на обоснование инструментов для разработки. Связано это с тем, что обе системы формирования поведения игрового агента отлично формализуются и сводятся к абстракциям, и поэтому имеют своё применение во многих современных инструментах. Популярные игровые движки - Unity, Unreal Engine 4, CryEngine 3 - обладающие свободно распространяемым инструментарием, включают различные расширения, способные работать с конкретной системой на уровне высоких абстракций, т.е. с диаграммами или таблицами, практически без необходимости что-то программировать. Обычно это плагины для SKD, подключаемые отдельно, для Behavior Trees - Behavior Designer, изображённый на рис. 2.1, или встроенный инструментарий в UE4. Оба инструмента отлично реализуют все достоинства поведенческих деревьев, в т.ч. удобство отладки, поскольку при исполнении текущий узел в дереве подсвечивается. Разработчик сможет тут же узнать, в каком действии произошла ошибка.
Рисунок 2.1 Пример поведенческого дерева, построенного в Behavior Designer
...Подобные документы
Сбор и анализ сведений по предметной области по дисциплине "Астрономия" с целью разработки обучающего игрового приложения. Исследование алгоритмов и характеристик существующих программных систем аналогов. Разработка архитектуры программной системы.
курсовая работа [4,1 M], добавлен 27.11.2014Анализ и виды интеллектуальных агентов в системе дистанционного обучения и их характеристики. Построение интеллектуального агента глоссария на платформе Jadex с помощью XML формата. Среда разработки и описание интеллектуального агента с помощью BDI.
курсовая работа [113,6 K], добавлен 10.02.2011Изучение существующих подходов к использованию компьютерных игр в образовательном процессе. Разработка и реализация проекта игрового обучающего приложения на мобильной платформе. Выбор платформы и средств реализации игрового обучающего приложения.
дипломная работа [3,4 M], добавлен 12.08.2017Обзор системного и прикладного программного обеспечения используемого в ООО "Игровые системы". Описание компьютерной сети предприятия. Разработка игрового продукта для планшетов Apple iPad. Реализация визуального интерфейса и алгоритма работы модуля.
отчет по практике [1,4 M], добавлен 18.01.2015Разработка игрового проекта на игровом движке Unity 3D в среде программирования MS Visual Studio 2017. Блок-схема алгоритма работы приема сообщений с сервера на клиенте с упрощенным описанием выполняемых команд. Реализация пользовательского интерфейса.
курсовая работа [1,5 M], добавлен 10.07.2017Подбор игрового движка и описание его основных характеристик. Разработка структуры, алгоритма и интерфейса программы. Проектирование иерархии классов. Выделение типового приема визуализации. Тестирование правильности работы программного обеспечения.
курсовая работа [3,1 M], добавлен 19.01.2017Разработка программного продукта, предназначенного для имитации физического взаимодействия между объектами на основе игрового симулятора. Проектирование программы "LonelySpaceRanger", код которой представлен на языке VisualС++. Разработка интерфейса.
дипломная работа [3,2 M], добавлен 30.11.2011Структура Android-приложений. Особенности игрового движка. Алгоритмизация и программирование. Список игровых состояний. Настройка, отладка и тестирование программы. Разработка руководства пользователя. Тестирование инсталляции и отображения элементов.
дипломная работа [4,5 M], добавлен 19.01.2017Разработка компьютерных игр как зрелищная и наиболее сложная отрасль программирования. Рассмотрение основных особенностей конструирования классов CGame и Players, а также алгоритмов вычисления траектории полета снаряда. Анализ алгоритма PassivePlayer.
курсовая работа [5,1 M], добавлен 22.02.2013Технология программных агентов. Форматы метаданных, использующиеся для описания электронных ресурсов. Разработка интеллектуальных агентов. Среда разработки Jadex для построения интеллектуальных агентов. BDI модель интеллектуального агента ресурсов.
курсовая работа [279,8 K], добавлен 20.02.2011Базовые характеристики агента, требования к программированию. Особенности архитектуры, организуемой в виде нескольких уровней, представляющих разные функциональные характеристики. Проблемы многоагентных систем при реализации идеи коллективного поведения.
презентация [255,2 K], добавлен 25.06.2013Преимущества операционной системы Android. Проектирование интерфейса приложений. Визуальные редакторы и средства кроссплатформенной разработки. Оптимизация игрового процесса, выбор фреймворка и библиотек. Классификация и характеристика игр по жанрам.
дипломная работа [2,6 M], добавлен 10.07.2017Анализ игровых жанров для мобильных устройств и целевой аудитории. Разработка концепции игрового приложения, основной механики, меню и интерфейса игры. Описание переменных скриптов. Реализация выбора цели и стрельбы. Настройка работоспособности игры.
дипломная работа [1,4 M], добавлен 19.01.2017Изучение существующих подходов к использованию компьютерных игр в образовательном процессе. Особенности использования мобильного обучения. Методика и этапы закрепления полученных ранее знаний с использованием игрового приложения на мобильной платформе.
дипломная работа [813,0 K], добавлен 27.10.2017Анализ целевой аудитории. Функциональные характеристики пользовательского приложения. Разработка алгоритмов и интерфейса программного продукта, функций рабочей области. Написание скриптов на языке C#. Тестирование программы методом чёрного ящика.
дипломная работа [1,5 M], добавлен 09.11.2016Написание игры "Lines" на языке Object Pascal в среде Delphi. Алгоритм работы программы. Описание метода генерации поля. Используемые константы и переменные. Форма приложения после старта игрового процесса. Основные элементы формы и обработки событий.
курсовая работа [225,0 K], добавлен 12.04.2012Разработка инструментального средства для обнаружения уязвимостей веб-приложений на основе контроля поведения с функцией автоматического построения профилей нормального поведения. Основные методы обнаружения аномалий, анализ возможности их применения.
курсовая работа [865,8 K], добавлен 02.02.2015Знакомство с особенностями и этапами разработки приложения для платформы Android. Рассмотрение функций персонажа: бег, прыжок, взаимодействие с объектами. Анализ блок-схемы алгоритма генерации платформ. Способы настройки функционала рабочей области.
дипломная работа [3,4 M], добавлен 19.01.2017История создания компьютерных игр. Обзор современных игровых жанров. Выбор используемых инструментов. Руководство пользователя. Разработка игры в жанре 3D шутера от первого лица. Конструктор игр Game Maker. Создание уровня с несколькими регионами.
курсовая работа [961,8 K], добавлен 22.06.2015Анализ деятельности группы компаний "Инрэко ЛАН". Общая характеристика, основы проектирования и разработка операционной системы Android. Этапы разработки программного игрового приложения с использованием физики. Скриншоты, отображающие игровой процесс.
отчет по практике [2,7 M], добавлен 19.07.2012
