me.neoascetic

Принципы современного игрового ИИ. Третий урок

В данном уроке рассматриваются вопросы представления данных, обрабатываемых интерактивными агентами: структуры данных, алгоритмы и так далее.

3.1 Представления

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

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

Для построения моделей реального мира используют структуры данных, которые получаются путём комбинирования скалярных значений того или иного типа. Для представления информации придумано огромное количество структур данных, в том числе специфичных и для ИИ. Обычно принято делить типы данных в зависимости от объёма хранимых в них значений, например, char, int16, float32 и так далее. Но при разработке интерактивных агентов чаще принята другая классификация.

Для целей символьного представления данных типы делятся на следующие.

Это, во-первых, символы - уникальные идентификаторы какого-то концепта внутри игры о котором, как предполагается, может размышлять интерактивный агент. Примерами могут служить: mana, health, door-B03, DRIVER_07 и так далее.

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

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

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

Вспомогательные значения (utility values) используются для хранения информации о степени предпочтительности чего-либо по сравнению с другими вариантами в списке. Например, число, характеризующее пригодность того или иного местоположения для того, чтобы спрятаться от игрока, является значением вспомогательного типа; соответственно, интерактивный агент хранит эти значения для того, чтобы позже сделать выбор о том, где укрыться.

Для целей нечёткой логики используются нечеткие символы (fuzzy symbols), которые описывают степень истинности некоторого предположения - например, того, успел ли увидеть игрок агента, пока тот прятался. Эти значения похожи на показатели вероятности, мы можем увеличивать или уменьшать их значения на основе каких-то фактов.

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

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

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

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

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

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

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

3.2 “Школьные доски” и “рабочая память”

В данном разделе идёт обсуждение способов организации архитектуры интерактивного агента. Рассматриваются такие компоненты, как blackboard, или, по-русски, школьная доска, и working memory, или рабочая память.

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

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

Для реализации “школьной доски” обычно используются структуры данных, подобные словарям, то есть с обращением к данным по имени, которые, в зависимости от нужд, могут быть как динамическими (собственно, dict в Python), так и статическими (struct из C). В качестве значений могут храниться любые типы данных - как скалярные, так и составные.

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

Для тех, кто знаком с паттернами проектирования “одиночка” (singleton), можно сказать, что blackboard является неким его аналогом, но не глобальным в рамках всей системы, а только для компонентов каждого интерактивного агента.

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

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

Итак, преимуществами “школьных досок” являются:

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

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

  3. Архитектура становится чуточку более модульной за счёт разрыва n-to-n связей

При этом к недостаткам относятся:

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

  2. Централизация всего не всегда является хорошим решением - например, в случае, когда различных компонентов слишком много, в плане модульности подход со “школьной доской” не сильно лучше n-to-n связей

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

Тем не менее, не смотря на недостатки, “школьные доски” являются удовлетворительным архитектурным решением для обмена статически типизированными данными между компонентами.

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

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

Итак, механизм рабочей памяти и модели мира, отдельной от реальной, обладает следующими преимуществами:

  1. Возможность простой подмены фактов о мире для каждого конкретного агента, что заставит агентов “верить” в их истинность

  2. Реализация более высокоуровневого, сложного и реалистичного поведения

  3. Отсутствие необходимости использовать специальные алгоритмы для создания реалистичного поведения

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

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

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

  1. Централизация/распределенность

  2. Статичность/динамичность

  3. Время жизни объектов

  4. Поток управления - синхронный/асинхронный

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

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

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

Вопрос контроля потока управления тесно связан с контролем за временем жизни значений. Преимущества и недостатки прямого и асинхронного контроля были описаны в предыдущем уроке. Вкратце, можно сказать, что при использовании синхронного подхода на каждом этапе вычислений значения, добавленные на предыдущем шаге, остаются доступными для обработки, а в случае с асинхронным подходом необходим некий механизм оповещений о добавлении/изменении значения (observer/callback).

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

3.3 Пространственная геометрия

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

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

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

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

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

Итак, основными примитивами, которые описывают одну дискретную область пространства, являются следующие.

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

Ячейки и прямоугольники. Представляются, опять же, двумя или тремя точками в зависимости от того, скольки-мерное пространство используется в игре, а также параметром, описывающим размер (в каждом направлении, если речь идёт о прямоугольнике). Главным преимуществом является отличное покрытие пространства, поскольку ячейки вплотную прилегают друг к другу.

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

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

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

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

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

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

Деревья используются для иерархичного разбиения пространства. Могут применяться во многих случаях за счёт быстрого доступа к любому элементу (см. Potentially visible set, Binary space partitioning).

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

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

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

Предыдущий урок