Исследование алгоритмов реализации игрового искусственного интеллекта

Размещено на http://www.allbest.ru/

Исследование алгоритмов реализации игрового искусственного интеллекта



Введение

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

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

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

Человек на протяжении многих лет стремится упростить свою жизнь, перекладывая обязанности на изобретения, будь то машины, роботы или компьютерные программы, создавая искусственный интеллект, по образу и подобию собственному. Искусственный интеллект (сокр. ИИ) - это симуляция человеческого интеллекта компьютерными системами [1]. Стоит, однако, сразу же отметить, что ИИ является лишь имитацией интеллекта человека, в большинстве случаев оставаясь лишь набором алгоритмов и правил [2].

Любому человеку требуется какое-либо увлечение, которым можно заняться в свободное время для развлечения и получения удовольствия; подобным увлечением могут являться и компьютерные игры [3]. Однако потенциальному игроку неинтересно играть самому с собой или со статическими объектами, так как это подразумевает отсутствие преодоления препятствий и испытаний на пути к победе - всего того, что доставляет человеку удовольствие, ведь для выигрыша в таком случае не нужно прилагать никаких усилий. Именно с этой целью был разработан первый игровой искусственный интеллект - чтобы имитировать реального сильного противника, бросая вызов игроку [4, 7]. Однако, как и в любом искусственном интеллекте, в используемых алгоритмах необходимо учитывать множество параметров, для более точной имитации человеческого интеллекта, и это будет подробно исследовано в данной работе.

Диаграмма, представленная на рис. 1, демонстрирует рост числа активных игроков в видеоигры с 2014 по 2021 год [5]. Числа представлены в миллионах. Можно легко заметить, что в наши дни насчитывается примерно 2.5 миллиардов геймеров по всему миру. К 2021 году ожидается увеличение этого колоссального числа до примерно 2.7 миллиардов, что представляет больше трети населения земного шара. Для того чтобы удержать интерес такого большого числа людей, разработчики стараются улучшить игровые алгоритмы, дабы сделать поведение оппонентов в видеоиграх реалистичнее [4, 9].

Рис. 1. Число игроков в видеоигры по всему миру с 2014 по 2021 (в миллионах)

компьютерный противник игрок

Новизна

Предыдущие исследования, затронувшие тему игрового ИИ, предлагают возможные решения, однако они являются узконаправленными [10, 11, 12]. Основной новизной данной работы является анализ большинства разработанных алгоритмов, реализующих ИИ в играх, и нахождение их недостатков, для формирования общей картины. Затем определяются параметры игрового ИИ, которые делают компьютерного оппонента в глазах игрока более “живым”, и предлагаются решения недостатков существующих алгоритмов. Рассмотренные алгоритмы наглядно демонстрируются в работе игрового приложения, разработанного в рамках данной ВКР.

Практическая значимость

Основным вкладом в исследуемую область является определение параметров, которые являются наиболее значимыми для игрового ИИ. Кроме того, данная работа представляет игровое интерактивное приложение (систему), которое реализует некоторые представленные решения и демонстрирует более реалистичное поведение компьютерного оппонента.

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

Задачи работы:

- проанализировать предметную область, исследовать историю развития игрового отечественного и зарубежного ИИ;

- провести исследование актуальных реализаций игрового искусственного интеллекта и выделить требования к нему;

- классифицировать и проанализировать применяемые в различных случаях ИИ алгоритмы;

- разработать систему с учетом рассмотренных ранее недостатков имеющихся алгоритмов;

- провести тестирование приложения.

В список основных разделов работы выходят:

- Описание предметной области: определение ИИ в играх, история развития игрового ИИ;

- Анализ существующих решений: классификация используемых алгоритмов-аналогов, определение их места применения, выявление недостатков, определение параметров реалистичного поведения противников;

- Разработка приложения: обоснование выбора средств, интерфейс приложения, разбор примененных алгоритмов;

- Тестирование приложения: пример работы программы, проверка соответствия поведения противника выделенным ранее критериям.

Средства реализации

Unity является межплатформенной средой разработки компьютерных игр и также именуется как так называемый “Игровой движок” [6]. Данная среда используется во множестве крупных игровых приложений и является одной из самых популярных в игровой индустрии [8]. Данный факт позволяет продемонстрировать работу алгоритмов в приложении, наиболее приближенном к уже существующим. Кроме того, движок является бесплатным для разработок, приносящих малую прибыль. Данные факторы повлияли на выбор Unity в качестве среды разработки для игрового приложения.

C# является основным языком программирования в среде Unity, поэтому он используется в скриптах, реализующих алгоритмы разработанного приложения.

Визуальная составляющая приложения (интерфейс, анимация, концепты персонажей, фоны) были созданы студенткой НИУ ВШЭ факультета “Коммуникаций, медиа и дизайна”, обучающейся по направлению “Анимация и иллюстрация”, Яной Князьковой в рамках выполнения ВКР “Компьютерная игра The second one: Camellia”. Статические изображения были созданы в Adobe Photoshop, рендер анимации производился в программе Adobe After Effects.

Результаты

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



1. Описание предметной области

1.1 Определение игрового искусственного интеллекта

Ни для кого не секрет, что искусственный интеллект является на данный момент очень популярной темой для обсуждения во всех сферах жизни, и едва ли он станет менее важным в грядущем будущем. Больше исследователей, чем когда либо, работают над ИИ в той или иной форме, и все больше людей других профессий интересуется данной областью. Когда-то настольные игры занимали центральное место в исследованиях ИИ с момента возникновения данной области, теперь же видеоигры в течение последних десятилетий все чаще становятся областью для тестирования и демонстрации новых алгоритмов. В то же самое время сами видеоигры стали более разнообразными и сложными, активно реализуя достижения в области ИИ для управления неигровыми персонажами, тем самым создавая для игрока преграды и адаптируясь под различные задачи [3]. Разработчики все больше осознают силу использования методов ИИ для анализа больших объемов данных игрока и оптимизации геймдизайна [9]. Благодаря этому появляется быстрорастущее сообщество разработчиков, которые экспериментируют с возможностями применения ИИ. Таким образом, видеоигры становятся не только увлечением и способом времяпрепровождения миллионов людей, но и формой выражения новых идей программистов и разработчиков.

Термин “искусственный интеллект” означает искусственное воспроизведение человеческого интеллекта компьютерными системами и машинами [1]. Важно понимать, что интеллект - неотъемлемая черта человеческого разума, и в частности в видеоиграх данную черту можно лишь имитировать с помощью различных методов, алгоритмов и правил [2]. Так, например, в игре крестики-нолики или “Ним” предпринимаемые компьютерным оппонентом действия сводятся к просчитыванию всех возможных ходов и выбору затем одного наиболее выгодного для себя. Подобная стратегия подробно изучается в таком разделе прикладной математики как теория игр. Также и более сложные задачи, такие как, например, зрение игровых противников и поиск пути к определенной точке, тоже, по сути своей, являются определенно описанными алгоритмами и наборами правил.

Под искусственным интеллектом в играх чаще всего подразумевается функционал т.н. “интеллектуальных агентов”, который те выполняют в целях имитации интеллекта человека. Интеллектуальные агенты в данном случае могут являться неигровыми персонажами (NPC), ботами, группами сущностей и т.д. [4]. При этом алгоритмы игрового ИИ можно разделить на три категории: восприятие среды вокруг агента, принятие решений на основе полученной от среды информации и выполнение принятых решений. Подобное разделение будет подробнее рассмотрено в главе “Исследование существующих решений” в разделе “Обзор алгоритмов” данной работы.

1.2 История развития игрового ИИ

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

Сначала в игры “учились” играть машины и устройства (рис. 2). Так, в 1912 году Леонардо Торрес Кеведо создал первое устройство El Ajedrecista, которое умело играть в шахматы [35]. Оно представляло шахматную доску, по которой две фигуры (белые король и ладья) передвигались электромагнитами. Машина могла ставить мат черному королю, находящемуся на любой позиции. Другой знаменитой машиной, реализующей ИИ в игре, можно считать “Ниматрон”, механизм, разработанный в 1940 году Эдвардом Кондоном, который мог играть в Ним [36]. Ним является математической игрой, в которой два игрока по очереди убирают предметы из нескольких кучек, победителем становится игрок, забравший последний предмет. Интересным фактом является то, что данная игра является одной из первых, для которых была построена математическая теория (1901 год).

Рис. 2. Первые устройства, реализующие игровой ИИ

Первой работающей с помощью игрового ИИ программой на компьютере считаются шашки, написанные в 1951 году Кристофером Стрэчи в Манчестерском университете с использованием Ferranti Mark I, а также шахматы Дитриха Принца [34]. Кроме того, эти программы были одними из первых, реализованных на компьютере. Не стоит забывать в том числе и об игре крестики-нолики “OXO”, разработанной А.С. Дугласом в 1952 году для компьютера EDSAC в Кембриджском университете [37]. В 1951 году компанией Ferranti был разработан специальный компьютер Nimrod, созданный для игры в Ним [37].

Стоит подробнее остановиться на реализации настольных игр, ведь именно они находились в центре многих ранних исследований в области игрового ИИ. Через несколько лет после разработки Стрэчи Артур Самуэль создал собственную программу для игры в шашки для IBM 701, используя альфа-бета-отсечение, обучение с подкреплением и игру против самой себя [44]. В 1989 году под руководством Джонатана Шеффера была разработана первая игра, выигравшая в 1994 году чемпионат мира по шашкам против оппонента-человека - программа “Чинук” [38].

Другим более известным примером победы игрового ИИ над человеком является победа суперкомпьютера Deep Blue над чемпионом мира по шахматам Гарри Каспаровым в 1997 году [39]. Следом за шашками и шахматами, в 2016 году программа Google DeepMind AlphaGo с алгоритмом Монте-Карло-поиска и свёрточной нейронной сетью выиграла у го-профессионала Ли Седоля несмотря на то, что специалисты прогнозировали выход подобной программы не ранее 2020 года [40]. Еще одной важной разработкой компании Google DeepMind является система ИИ, разработанная в 2014 году и способная обучаться играть в некоторые игры Atari 2600, имея в начале своего обучения в качестве входных данных лишь пиксели на экране и игровой счет [41].

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

Первые видеоигры, разработанные в 1960-е годы, были предназначены для двух игроков и не подразумевали наличие искусственного интеллекта, однако появление компьютерных оппонентов не заставило долго себя ждать. В 1974 появились такие игры как Speed Race от Taito и Pursuit от Kee Games [45]. Первая игра представляет гонки, где игроку требуется объезжать соперников, не задевая их, вторая - симулятор боя на самолетах. Не стоит забывать и про текстовые игры, разработанные в 1972 году, Hunt the Wumpus и Star Trek, в которых передвижение врагов основывалось на созданных шаблонах [46].

Во время т.н. золотого века аркадных видеоигр (1978-1984) идея противников с ИИ популяризировалась и была применена во многих разработанных впоследствии играх. Начальной точкой можно считать создание Space Invaders, в которой реализовался выбор уровня сложности, четкие шаблоны движения противников, а события основывались на входных данных от игрока [45]. Данная игра представляет аркадный шутер (“игра-стрелялка”), в котором игрок горизонтально управляет стреляющей внизу пушкой, уничтожая появляющиеся сверху волны врагов. В 1979 году игра Galaxian, реализующая похожий геймплей, сделала шаг вперед, демонстрируя более сложное движение врагов и в том числе маневры, из-за которых определенные единицы могли выходить из общей группы [45]. В 1980 году популярная игра Pac-Man реализовала шаблоны перемещения врагов в игре-лабиринте, наделяя каждого противника собственным поведением (алгоритм будет рассмотрен в следующей главе).

В тактической игре 1988 года First Queen были представлены персонажи, передвижение которых зависит от лидера. Компьютерная ролевая игра Dragon Quest IV в 1990 году представила тактическую систему, в которой игрок мог настроить программу поведения ИИ неигровых персонажей во время боя. В спортивных симуляторах вроде Madden Football (1988) искусственный интеллект основывается на копировании поведения реальных людей на тренировках, впоследствии в подобных играх появились возможности для игрока редактировать это поведение согласно выбранному курсу [35].

Новые жанры видеоигр начали появляться в 1990-х, что привело к использованию в игровом ИИ конечных автоматов. Стратегии реального времени, такие как Herzog Zwe и Dune II, имели новые проблемы для игрового ИИ того времени - отсутствие полной информации о происходящем на карте, поиск путей и др [35].

Первым знаменитым применением нейронных сетей стала серия игр Creatures разработчика Millennium Interactive под руководством Стива Гранда, появившаяся в 1996 году. Основной задачей этой серии было моделирование поведения живого существа, включая его эволюцию, и в свое время игра не имела аналогов. Подробнее разработка будет разобрана в следующей главе [47].

В 1998 игра Thief, разработанная Looking Glass Studios, продемонстрировала продвинутую систему восприятия стражников. Игра относится к жанру стелс-экшн, в которой игроку требуется действовать скрытно, минуя противников [27]. Подобная категория игр требует адекватного поведения и реагирования врагов, что и было реализовано разработчиками, с учетом освещенности, степени шума и типа поверхности, по которой персонаж двигается [48].

Первый заметный шутер, перевернувший требования к жанру, под названием Half-Life был выпущен в 1998 году компанией Valve Corporation. От выпущенных ранее шутеров данную игру отличала усложненная тактика поведения противников, в отличие от Doom, где противники просто поворачивались в сторону игрока и бежали к нему, атакуя [35]. В Half-Life были реализованы дружественные неигровые персонажи, а также бои, проходящие без игрока. Кроме того, имелась даже такая деталь, как обоняние у неигровых персонажей, из-за которого монстр мог прибежать к недавно убитому игроком противнику, а дружественный персонаж реагировал на неприятный запах фразами.

Техники машинного обучения, такие как персептроны, деревья решений и обучение с подкреплением удачно сочетаются с моделью убеждений, желаний и намерений в игре Black and White, разработанной Lionhead Studios в 2000 году. Подробное описание примененных алгоритмов будет приведено в следующей главе.

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

В 2001 году была выпущена игра-шутер Halo от Bungie Studios, которая продемонстрировала командные тактики, и в которой сцены боя походят очень достоверно [35]. Так, если командир отряда умирает, остальные неигровые персонажи в отряде разбегаются, оценивая опасность, помимо этого было реализовано использование персонажами транспорта, призыв союзников на помощь в трудных ситуациях, а также убегание от брошенных игроком снарядов. В 2004 году Halo 2 популяризировала использование дерева поведений в играх, кроме того было реализовано взаимодействие объектов между собой с помощью системы вещания. Так, два персонажа, наблюдающие за чем-то одним, могли начать обсуждать это.

Игра-шутер F.E.A.R. 2005 года, разработанная компанией Monolith Productions, до сих пор считается многими игроками примером одной из лучших реализаций игрового ИИ. В этой игре можно увидеть набор зависимых от происходящего поведений, основанных на специально разработанном методе, названном “Целеориентированное планирование действий” [49]. Так противники не только действуют вместе, но и прикрывают друг друга при отступлении, используют укрытия и двери, применяют различные тактики, разбивают окна, если те являются преградой, и т.д.

Ролевая игра The Elder Scrolls IV: Oblivion, выпущенная компанией Bethesda Game Studios в 2006 году, реализовала внутри себя неигровых персонажей, которые живут собственной жизнью 24 на 7, выполняя определенные действия в течение всего дня [50]. Происходящие на протяжении игры события, вызванные действиями игрока, могут полностью изменить поведение персонажей, а, следовательно, и выполняемые ими действия. Однако часто в алгоритмах реализации возникали сбои, в связи с чем в игре нередко наблюдались персонажи, стоящие подолгу на одном месте.

Вышедшая в 2007 году игра-шутер S.T.A.L.K.E.R.: Тень Чернобыля, разработанная компанией GSC Game World, продемонстрировала удивительные возможности собственного игрового движка X-Ray, а конкретно его отрасль искусственного интеллекта, которая называется A-Life [51]. Ключевыми аспектами своего игрового ИИ разработчики называют постоянное отслеживание и реализацию поведения персонажей, вне зависимости от того, находится ли рядом игрок или нет. Происходит это благодаря переходу объектов в разные режимы, с разной степенью детализации.

Сетевой кооперативный шутер Left 4 Dead, разработанный в 2008 году компанией Turtle Rock Studios, демонстрирует новую для игрового ИИ систему, которую назвали “Режиссёр” [52]. Данная система позволяет генерировать для игроков каждый раз новые, непохожие на остальные, прохождения. Реализуется это благодаря т.н. процедурному повествованию, когда система анализирует действия и степень успеха игроков и в соответствии с этим запускает различные события.

В 2014 игра жанра survival horror, в котором надо выживать в пугающей атмосфере, под названием Alien: Isolation от компании Creative Assembly продемонстрировала силу адаптивности игрового ИИ в поведении ксеноморфа (чудовища). ИИ монстра постоянно оценивает действия и напряженность игрока системой режиссера, как в игре Left 4 Dead, адаптируя свои атаки в зависимости от этого, а также постепенно раскрывая закрытые ранее узлы-вершины дерева поведений, которых в игре насчитывается около 30 [53]. Дерево поведений будет подробнее рассмотрено в следующей главе.

Игра космической тематики No Man's Sky компании Hello Games в 2016 году использовала процедурную генерацию для содержимого своей огромной вселенной [54]. Важно отметить, что данная игра имеет открытый мир, целиком доступный для исследования пользователем, и насчитывает 18 квинтиллионов планет, каждая со своим ландшафтом, флорой, фауной и погодными особенностями.

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



2. Анализ существующих решений

2.1 Обзор алгоритмов

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

Самым простейшим типом ИИ в играх является следование объекта заранее написанному сценарию (pre-scripted event) [14]. Выполнение какого-либо действия может быть продиктовано как определенным таймером, так и достижением игроком нужной точки в игре. При этом данный тип ИИ может быть использован в качестве проигрывания внутриигрового видео (cut-scene), срабатывания пугающего элемента или же просто запуска события. Кроме того ранее подобный алгоритм использовался для реалистичного уничтожения объектов, так как сложная физическая обработка была слишком дорогой для процессоров. Простейшим примером описанного типа ИИ может послужить падающий с неба незадачливый маг в игре “The Elder Scrolls III: Morrowind”, который начинает свое падение только когда игрок доходит до определенной точки (рис. 3).



Рис. 3. Пример pre-scripted event в игре “The Elder Scrolls III: Morrowind”

В центре каждого алгоритма более сложной реализации ИИ лежит принятие решений. Причем данная функция может быть реализована в двух различных системах: AI push (вещание ИИ) системы и Entity pull (запрос объектов) системы. Первая система подразумевает, что искусственный интеллект представлен отдельно от объекта, и когда ИИ принимает решение, оно передается игровым объектам. Данная схема чаще всего используется в стратегиях. Система entity pull применяется в шутерах и работает по принципу отправки запросов от объекта к ИИ. В данном случае объект, использующий ИИ, именуется интеллектуальным агентом (ИА).

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

Системы на основе правил (Rule-based system) являются простой и фундаментальной формой реализации интеллектуального агента [15]. Набор заранее заданных алгоритмов определяет поведение игровых объектов в предписанных ситуациях. Вот пример набора правил: “ЕСЛИ идет дождь И нужно выйти из дома ТОГДА нужно взять зонт” [16]. В простейших реализациях подобных систем, помимо того, что при детальной имитации интеллекта потребуется слишком много наборов правил, они будут требовать входные данные пользователя, что является нечестным и невозможным, будь объект реальным противником.

Самым очевидным примером системы на основе правил является игра “Pac-Man”, в которой поведение четырех противников описано определенными условиями [17]. Как говорил создатель игры Тору Иватани - «игра про еду -- не такое уж большое развлечение, поэтому мы решили вдохнуть немного волнения и напряжения и добавили врагов». Каждый противник в данной игре движется к клетке-цели, которая определяется в зависимости от того, к какому типу относится призрак и в каком режиме он находится в данный момент [18]. Всего режима три - погоня, рассеивание и испуг. При рассеивании каждый призрак начинается двигаться к определенной для него точке в углах карты (рис. 4, левый верхний угол), при испуге - к случайно выбранным точкам. Алгоритм определения пути к точке назначения рассматриваться в данном разделе, посвящённом системам на основе правил, не будет. Однако режим погони стоит рассмотреть поподробнее.

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



Рис. 4. Набор правил, управляющий противниками в игре “Pac-Man”

Еще одним простым примером системы на основе правил является принятие решений в игре “Sims” [19]. Алгоритм ИИ высчитывает, какое действие принесет персонажу больше всего очков счастья и, в зависимости от результата, выполняет самое “счастливое” действие. Учитываются сразу несколько факторов, такие как собственные пристрастия персонажа, расстояние до объекта, удовлетворяющего потребность, состояние потребности и пр. Сам создатель игры Уилл Райт для лучшего понимания алгоритма предлагает представить тебе так называемый “happyscape” (рис. 5), ландшафт, в котором горы растут и уменьшаются под объектами соразмерно очкам счастья, которые они принесут, при этом персонаж будет стремиться к наиболее высоким холмам [20].

Рис. 5. Реализация принятия решений в игре “Sims”.

Конечный автомат (Finite-state machine, сокр. FSM) в качестве ИИ является способом реализации объекта, обладающего несколькими разнообразными состояниями, в которых объект может находиться в течение своего существования [21]. Такой метод игрового ИИ возможно реализовать разными способами, например с помощью изменения состояния какой-либо переменной или же используя функции. На рис. 6 представлен простой конечный автомат, реализующий типичный для игр ИИ противника, стрелки символизируют переходы из одного состояния в другое [13].

Рис. 6. Схема состояний в простом FSM

Состояние Idle представляет спокойное состояние объекта, когда он ничем не встревожен и не ищет игрока. В состоянии Aware объект начинает искать враждебных персонажей, замечая больше чем в состоянии спокойствия. Объект переходит в состояние Intrigued, когда замечает что-то необычное, что стоит проверить. Будучи в состоянии Alert, объект осведомлен о нахождении игрока и выполняет предписанные действия (приближение, запуск сигнала тревоги, вызов подмоги). В состоянии Aggressive, объект настроен агрессивно по отношению к игроку и ведет бой, атакуя и уворачиваясь согласно алгоритмам. Объект в состоянии Fleeing пытается убежать от игрока. Состояние Dead является финальным для объекта с невозможностью перейти в какое-либо иное состояние. Использование FSM в качестве ИИ, в случае точной имитации, обязуется иметь огромное количество состояний, что нецелесообразно и затратно по памяти.

Говоря об игровом ИИ нельзя не упомянуть теорию игр - математическую теорию выбора оптимальных решений в играх, и минимакс алгоритм, относящийся к ней [23]. Минимакс алгоритм (Minimax Algorithm) - бэктрекинг алгоритм, использующийся в принятии решений и теории игр для нахождения оптимального действия для игрока, при условии, что противник тоже играет оптимально [24]. Пример применения минимакс алгоритма в игре в крестики-нолики приведен на рис. 7 [25]. В данном случае рассматриваются все возможные варианты ходов как для крестика, так и для нолика, при этом победа крестика добавляет 10 очков, а нолика - отнимает. При нахождении в первом состоянии, генерируются состояния 2, 3, 4, из которых начинает набираться счет. Становится понятно, что для 2 состояния это +10, для 3 = -10, и для 4 = -10, значит, самым оптимальным ходом является ход 2, он же выигрышный. Стоит сразу же заметить, что этот алгоритм подходит лишь для игр, где определено количество ходов, и известны все возможные решения игрока.

Рис. 7. Пример реализации минимакс алгоритма

Чертой более умного ИИ в играх является его адаптивность, что не раз подмечается во многих исследованиях [9, 10, 11]. Адаптивность противников позволяет добавить в игру большое разнообразие и заинтересовать пользователя способностью врагов приспосабливаться. Более конкретным случаем адаптивности является возможность ИИ в играх предсказывать (prediction) действия игрока. Однако подобная реалистичная черта используется чаще в тактических играх, где информация о предыдущих решениях игрока записывается и оценивается. Это же можно назвать и своеобразным минусом алгоритма - редкое использование адаптивности разработчиками в своих играх. Примером предсказывания может служить система реакции врагов и игре “Metal Gear Solid V: The Phantom Pain” (рис. 8). Так, если игрок стреляет противникам в головы - те начинают носить шлемы, если игрок предпочитает действовать скрытно - то ставятся ловушки, если предпочитает ночное время - враги используют очки ночного зрения и т.д.

Рис. 8. Система реакции врагов в игре “Metal Gear Solid V”.

Адаптивность возможно реализовать с помощью нейросетей, однако использование нейросетей в алгоритмах игр является, пожалуй, одним из самых редких методов, продемонстрированный в единицах игр. Одним из примеров может служить игра “Creatures”, созданная ученым Стивом Грандом. В данной игре игроку предстоит вырастить создание с самого его рождения, обучая словам, действиям, а также пониманию того, что хорошо, а что плохо с помощью наказаний и поощрений. Искусственный интеллект каждого существа реализован с помощью нейросети (рис. 9), в которой содержатся тысячи нейронов, а сама нейросеть поделена на разделы (lobe), отвечающие за различные задачи, например, за внимание, принятие решений, чувства и др. [22]. Обучаясь, существа ведут себя соответственно своим желаниям, полученным урокам от игрока и ощущениям.



Рис. 9. Общая схема нейросети в игре “Creatures”.

Стоит подробнее описать строение простейшей нейросети. В 1940 г. Уореном МакКалоком и Уолтером Питтсом были предложены математические модели нейрона - узла искусственной нейросети, и самой сети. Схема предложенной модели узла представлена на рис. 10. Так слева, под номером 1, расположены нейроны, сигналы от которых поступают на вход рассматриваемого узла. Под номером 2 находится сумматор полученных сигналов. f(S) обозначает вычислитель передаточной функции, которая в зависимости от типа нейросети может различаться, и определяет зависимость выходного сигнала от взвешенной суммы входных сигналов. В конце, под номером 5 расположены нейроны, которым передается выходной сигнал рассматриваемого узла. Наконец, wi обозначают веса входных сигналов, иными словами, значение, на которое умножается сигнал, прежде чем попасть в сумматор.

Рис. 10. Модель искусственного нейрона



Обучаемость ИИ хорошо реализована в игре “Black and White”, где существо, управляемое компьютером, обучается путем оценивания степени удовлетворения желания определенными действиями, наблюдения за игроком, а также получения от него отклика на свои действия (т.н. обучение с подкреплением) [32]. Со временем существо может реализовывать целый комплекс функций, которые подходят игроку. Для реализации подобного ИИ разработчики использовали модель убеждений, желаний и намерений (BDI). Данная модель описывает убеждения, желания и намерения существа и позволяет разделить процесс принятия решения от процесса исполнения решения. В данной игре убеждения представлены в виде списка, который содержит информацию о других объектах, желания (цели, которых существо хочет достичь) выражены в виде упрощенных персептронов, а варианты выполнения желаний формируются с помощью дерева решений (рис. 11). Таким образом, для каждого желания существо выбирает какое-либо убеждение как самый лучший вариант исполнения, таким образом формируя намерение [33].

Рис. 11. Пример дерева решений в игре “Black and White”

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

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



Рис. 12. Пример простого дерева поведения.

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

Одним из простых алгоритмов, реализующих в частности восприятие, можно назвать обнаружение столкновений (collision detection) - вычисление пересечения между собой нескольких объектов [26]. Простой пример определения столкновений изображен на рис. 13.

Рис. 13. Определение столкновений (collision)

Используется в играх как реализация зрения объекта, однако, делает при этом объект “всесильным”, способным видеть через стены, без учета препятствий, что является несомненным недостатком алгоритма. Возможна реализация подобного алгоритма вместе с созданием коллайдеров (colliders), отвечающих за безопасные зоны, где игрок считается спрятанным. Так зрение противников было реализовано в игре “Horizon Zero Dawn” (рис. 14). На скриншоте можно увидеть двухэтапное зрение врага в виде конуса и набор кустов с голубыми коллайдерами, в которых можно спрятаться. Желтая линия отвечает за Intrigued состояние противника, а красная - за Alert (см. описание FSM). На данном примере наглядно можно увидеть совмещение в игровом ИИ сразу нескольких алгоритмов. Основной недостаток использования обнаружения столкновений и коллайдеров заключается в том, что игрок может прятаться только там, где эти коллайдеры присутствуют, и не может остаться незамеченным, например, за ящиком.

Рис. 14. Реализация зрения врага в игре “Horizon Zero Dawn”

Помимо зрения, еще одним методом восприятия среды является слух объекта [27]. Конечно, можно реализовать его с помощью определения дистанции до точки звука. Однако, наиболее реалистично будет учитывать громкость звука (исходя из типа объекта, его издавшего), а также преграды на его пути и их материал (рис. 15). Кроме того, существуют и другие органы чувств, например, обоняние, и их тоже возможно достоверно имитировать.



Рис. 15. Алгоритм имитации слуха у объекта

Еще одной проблемой, с которой может встретиться ИИ в шутерах является определение возможного укрытия [28]. Причем определение состоит сразу из нескольких задач - важно правильно определить расположение укрытия относительно места стрельбы, оценить размер укрытия и возможность объекта полностью за ним поместиться, а также учесть тип укрытия (рис 16).

Рис. 16. Определение возможного укрытия

Последним для исследования, но от этого не наименее важным является поиск путей (pathfinding) [29]. Данный метод относится к третьему типу алгоритмов ИИ в играх, а именно к алгоритмам, отвечающим за выполнение принятых решений, основанных на воспринятой информации об окружающей среде. Поиск путей подразумевает определение объектом маршрута до точки назначения и может быть реализовано многими алгоритмами. Самым простым является алгоритм “столкнулся-свернул” и его смысл заключается в названии. Объект движется к цели, и как только происходит столкновение с препятствием, требуется повернуться в направлении ближе всего к цели. Однако данная реализация позволяет противникам застревать в углах в погоне за игроком. Возможно и усложнение описанного ранее алгоритма с помощью возврата объекта в начало пути, который привел к тупику, и выбору другого направления. Подобный алгоритм предоставляет малую нагрузку на вычисления, однако нерационально использует память, в связи с отслеживанием множества уже пройденных путей, кроме того, на достижение цели может уйти много времени.

Более применимым в поиске путей является алгоритм A*. В данном алгоритме анализируются наиболее подходящие пути, ведущие до цели, а затем выбирается оптимальный. При этом данный алгоритм используется вместе с самыми различными представлениями игрового пространства, два из которых (с помощью узлов и с помощью сетки) представлены на рис. 17. Можно наглядно увидеть, что использование навигационной сетки (navmesh) заметно улучшает результат работы алгоритма A* [30]. Навигационная сетка представляет набор полигонов, которые считаются поверхностью, возможной для ходьбы объекта в 3д пространстве. Важно помнить, что при использовании сетки используются статичные значения минимальной неровности земли, которые агент не может преодолеть, вне зависимости от самого агента. Данная особенность является недостатком, ведь нужно учитывать тип поверхности, размер интеллектуального агента, высоту его шага и многое другое, что позволит более точно имитировать реального противника.



Рис. 17. Сравнение разных представлений доступного пространства

2.2 Определение параметров реалистичного поведения

https://www.youtube.com/Для того чтобы понять, как сделать хороший игровой ИИ, нужно определить параметры реалистичного поведения объектов в игре, которые влияют на игрока. Прежде всего важно, чтобы объект имитировал поведение, свойственное ему, т.е. агрессивные противники должны сразу бросаться на игрока, а пугливые персонажи - стремиться убежать от него. Не стоит забывать и о поведении, реализованном у дружелюбно настроенных к игроку персонажей. Не менее важно реалистичное восприятие объектом окружающей среды с учетом множества параметров, влияющих на зрение, слух, обоняние и другие имитирующиеся чувства.

Кроме того, необходимо правильно подбирать параметры объектов, так как они тоже влияют на восприятие игроком противников. Так во время разработки игры “Halo” разработчики тестировали реакцию игроков на игровых оппонентов с неизменными алгоритмами ИИ, но разными показателями наносимого урона и здоровья [31]. Исследование показало, что слабый противник воспринимается как глупый, а сильный - наоборот (рис. 18).



Рис. 18. Фрагмент с презентации Bungie

Возможность обмануть ИИ тоже является плюсом в глазах игрока. Так, например, была встречена игроками возможность в игре “The Elder Scrolls V: Skyrim” надевать ведра на голову продавцам, тем самым блокируя им область обзора и позволяя безнаказанно обворовывать их лавки. Не стоит, однако, забывать, что на подобную попытку игрока искусственному интеллекту стоит реагировать негативно, что не было реализовано в данной игре.

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

Еще одним параметром реалистичного поведения является использование ИИ объектов окружающей среды. Так, например, в игре “The Legend Of Zelda: Breath of the Wild” противники подбирают с земли брошенное оружие, поджигают в костре деревянные палки и пр. Еще одним плюсом в ИИ будет взаимодействие персонажей друг с другом. Под этим могут подразумеваться как реакция дружественных объектов друг к другу, так и схватки последователей враждующих фракций.

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



3. Разработка приложения

3.1 Обоснование средств реализации

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

В целях демонстрации возможности улучшения алгоритмов с использованием аналогичного другим разработкам движка требовалось максимально приблизить будущее приложение к уже существующим. Именно из-за этого для разработки были рассмотрены только два наиболее популярных в игровой индустрии и часто используемые в крупных проектах игровых движка: Unity и Unreal Engine 4 [57]. Несмотря на превосходящие возможности графической составляющей движка Unreal Engine [56], разрабатываемое приложение является 2D платформером, поэтому при выборе движка подобный критерий не учитывался. Обе среды являются условно бесплатными, что позволяет спокойно их использовать в рамках проводимого исследования. Наиболее важным параметром при выборе среды являлась ее функциональная составляющая (физика, скриптинг и т.д.), так как реализуемое игровое приложение предназначено прежде всего для демонстрации алгоритмов. Оба игровых движка предоставляют практически аналогичный друг другу функционал, отличными являются лишь применяемые языки программирования и внутренние редакторы программного кода [56]. Наглядная сравнительная таблица продемонстрирована на рис. 19.



Рис. 19. Фрагмент сравнительной таблицы из работы [56]

Таким образом, оба сравниваемых движка одинаково хороши для реализации разрабатываемого приложения. Однако Unity имеет много удобных инструментов для 2D разработки (например, Sprite editor), в нем реализована специальная физика 2D объектов и, кроме того, среда имеет компонент Animator, работающий с анимациями, что заметно облегчило работу с исполнителем графической части приложения Яной Князьковой. По итогам проведенного анализа и найденных преимуществ в качестве игрового движка был выбран Unity.

В среде Unity для скриптинга основным языком программирования является C#, поэтому на нем написаны скрипты, реализующие все необходимые алгоритмы. Графическая составляющая разработанной системы (а именно: изображения всех игровых объектов, их анимация, внешний вид интерфейса, проработка концептов, фоновые изображения) будут создаваться студенткой НИУ ВШЭ факультета “Коммуникаций, медиа и дизайна”, обучающейся по направлению “Анимация и иллюстрация”, Яной Князьковой в рамках выполнения ВКР “Компьютерная игра The second one: Camellia”. С учетом условий реализации, для создания статических изображений была выбрана программа Adobe Photoshop, а для рендера анимации - Adobe After Effects.

Продукты компании Adobe объединяют в себе самые современные технологии. На данный момент, несмотря на наполненность рынка разными аналогами, ни один из них не может конкурировать с Adobe Photoshop. Исполнитель графической части разрабатываемой системы выбрал эту программу из-за мощных инструментов контроля, которые дают возможность проводить работу недеструктивно и процедурно. Система слоев в данном случае оказалась наиболее актуальной. Она позволяет управлять элементами изображения по отдельности друг от друга. В целом программа является мощным графическим редактором. В свою очередь Adobe After Effects (AE) предлагает уникальную систему иерархии и слоев, что концептуально объединяет АЕ с Photoshop и создает возможности для практически мгновенной интеграции файлов и работы между программами на основе принципа Bridge. АЕ является уникальным инструментом, который позволяет полностью покрыть задачи 2D аниматора, особенно в связке с Photoshop.

3.2 Интерфейс приложения

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

Рис. 20. Различные виды интерфейса разработанного приложения



Главное меню (рис. 20, а). Интерфейс имеет фоновое изображение 1920х1080, которое при уменьшении разрешения окна обрезается по ширине. Четыре текстовые кнопки расположены левее центральной точки (она же опорная, pivot), и при любом доступном на компьютере разрешении остаются видимыми. Интерактивность текста обозначается с помощью изменения цвета текста при наведении на него курсором, а при нажатии текст становится еще чуть темнее. Кнопка “Продолжить” загружает последнее сохранение игры, кнопка “Новая игра” позволяет игроку запустить прохождение с самого начала. Кнопкой “Опции” осуществляется переход в раздел настроек (см. ниже), а кнопкой “Выход” - завершение работы приложения. Кроме того, с помощью системы частиц (Particle System) в меню была реализована имитация светлячков, которые неспешно перемещаются в разных направлениях, бесконечно появляясь и исчезая.

Загрузочный экран (рис. 20, б). Данный интерфейс возникает в том случае, когда требуется занимающая некоторое время подгрузка данных и файлов (например, загрузка сохранения). Фоновое изображение имеет зацикленную анимацию, а расположенный снизу слайдер динамически отображает информацию о степени загрузки необходимой информации. Как только слайдер полностью заполняется, что обозначает окончание загрузки, происходит смена сцены с загрузочного экрана на то, что непосредственно загружалось. Все элементы интерфейса закреплены (pivot) относительно центральной точки.

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

Настройки (рис. 20, г). Интерфейс данного раздела похож по структуре на главное меню, кроме того здесь тоже имеется система частиц, реализующая светлячков. Отличие от интерфейса главного меню заключается в дополнительных элементах. Всего их восемь: 3 текстовых поля (описывающие элементы справа от себя), 2 выпадающих списка, слайдер, переключатель и текстовая кнопка. Первый список позволяет выбрать один уровень качества картинки из шести. Слайдер дает возможность настроить громкость музыки и звуков приложения. С помощью второго списка пользователь может выбрать необходимое ему разрешение окна. Доступные разрешения определяются автоматически, в зависимости от аппаратного обеспечения. Переключатель реализует переход между оконным и полноэкранным режимом приложения. Наконец, с помощью текстовой кнопки “Назад” можно вернуться в главное меню (см. выше). Все элементы закреплены (pivot) относительно центра.

Меню паузы (рис. 20, д). Меню паузы аналогично игровому интерфейсу, так как оно тоже отображается поверх игрового процесса. Отличие заключается в том, что данное меню появляется только после нажатия клавиши, отвечающей за паузу (по умолчанию “Esc”). При активации интерфейса, игровой процесс останавливается. Сам интерфейс представляет собой полупрозрачный прямоугольник, затемняющий игровой процесс на фоне, и фоновое изображение с двумя текстовыми кнопками слева. Изображение закреплено (pivot) относительно левого края, кнопки закреплены относительно центра этого изображения. Кнопка “Продолжить” или повторное нажатие “Esc” скрывает интерфейс меню паузы, возобновляя игровой процесс, а кнопка “В главное меню” производит переход в главное меню (см. выше). Аналогично выглядит меню смерти персонажа, но оно имеет более темный цвет, а активируется и останавливает игровой процесс, только если здоровье персонажа опустилось до нуля. Меню смерти нельзя закрыть, а вместо кнопки “Продолжить” в нем расположена кнопка “Загрузить сохранение”. Возможность перейти в главное меню остается.

...