Элементы игрового ИИ на основе табличной логики и марковских цепей.

Автор: NavY

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

Предисловие

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

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

Статья предназначена в первую очередь для новичков в игростроении, ещё только размышляющих над реализацией схем работы AI (здесь и далее – англ. artifical intelligence – искусственный интеллект) в своих играх, но может быть полезна и опытным разработчикам.

Вступление

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

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

(для незнакомых с этим синтаксисом - через точку тут указывается обращение к какому-либо свойству или методу объекта)

Подпрограмма Идём_В_Атаку(<набор параметров>)
{
Если (персонаж.под_обстрелом)
         {
         Если (персонаж.не_вижу_врага) персонаж.осмотреться(<параметры>);
         персонаж.искать_укрытия(<параметры>);
         Если (персонаж.вижу_укрытия_рядом)
                  {
                  Если (персонаж.здоровье_меньше_трети) персонаж.спрятаться(<параметры>);
                  <…>
                  }
         }

Если (персонаж.вооружён_оружием_ближнего_боя)
         {
         Если (персонаж.моё_расстояние_до_врага > персонаж.радиус_действия_оружия)
                  {
    <……>

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

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

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

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

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

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

Одномерная табличная схема “стимул-реакция”

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

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

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

• Интерес
• Агрессия
• Осторожность
• Голод
• Усталость
• Страх

Чтобы как-то охарактеризовать степень (силу) воздействия того или иного стимула на дракона, введём характеризующий его численный показатель, значение
которого будет изменяться от 0 (стимул отсутствует) до 1 (максимальная сила воздействия).

Составим таблицу, характеризующую дракона на момент встречи с игроком:

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

(для простоты предполагаем, что вид игрока не оказал на дракона никакого эффекта, однако вид его оружия заставил дракона несколько насторожиться)

В таком случае, наиболее сильным стимулом для дракона становится Голод, и игрок, являющийся для дракона потенциально съедобным, будет им атакован:

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

Когда стимулы Усталость или Страх станут преобладающими, то дракон прекратит бой и попытается спастись бегством.

Скорость изменения силы воздействия стимулов, в свою очередь, задаётся разработчиком в соответствии с характеристиками и даже с характером конкретного
противника: задав высокую скорость роста Страха, можно легко создать оппонента-труса, предпочитающего спасаться бегством при первом же ранении;
установив скорость небольшой или нулевой, можно создать полную его противоположность. Также, населяя виртуальный мир животными, можно, к примеру,
заранее задать самке кабана, охраняющей своё потомство, заведомо завышенную Агрессию (при встрече с нею игрок будет сразу же атакован), а лесному оленю – высокое значение Осторожности (чуть заслышав игрока, тот бросится бежать, забыв о прочих своих делах).

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

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

Табличная схема “стимул-реакция” расширенной размерности

Заметным недостатком рассмотренного выше механизма можно назвать обилие коэффициентов, а также некоторую неопределённость в плане принятия решений. Если значения двух или более сил воздействия различных стимулов оказываются в определённый момент времени достаточно близки или равны, то поведение компьютерного оппонента вдруг может становиться достаточно странным. В любом случае, в действиях подобного AI могут прослеживаться некоторые “импульсивность” и прямолинейность. Так, возвращаясь к примеру с драконом, можно предположить ситуацию, что игрок, нанося дракону ряд несерьёзных ран, заметно повышает силу стимула Страх, после чего тот становится преобладающим - и дракон обращается в бегство. Однако через короткое время величина Страха естественным образом спадёт. Если на этот момент игрок всё ещё будет в поле зрения дракона, то дракон, находясь под действием иных стимулов (например, снова Голод) начнёт новую атаку.

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

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

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

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

То есть, если обозначить стимулы как (где k - от 1 до N – номер соответствующего стимула), то справедливо будет выражение , где - весовые коэффициенты, подбираемые специально для каждой из ячеек.

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

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

#движок, #математика, #матрицы, #скрипты

6 августа 2012 (Обновление: 24 дек 2018)

Комментарии [26]