Архитектура Искусственного Интеллекта для симулятора спецназаЭтот документ писался как наброски к дизайну системы искусственного интеллекта для компьютерной игры Private Wars. Игра представляла из себя тактический симулятор боевых действий спецназа. Аналоги: Rainbow Six, Spec Ops, Delta Forces. Private Wars были реализованы в трехмерной графике с видом от первого лица. Игра состояла из двух десятков миссий, каждая из которых разворачивалась по одному из типичных сценариев проведения контртеррористических операций. Игрок получал в свое распоряжение команду спецназа до 8 человек и имел возможность непосредственно управлять одним из членов команды. Всеми остальными членами команды он мог управлять с помощью приказов. За террористов играл компьютер. Ниже описан подход к реализации искусственного интеллекта для такого класса игр. Решаемые задачиПоведение NPC в Private Wars должно удовлетворять нескольким требованиям. В первую очередь его поведение должно быть логичным и правдободобным с точки зрения игрока. Это необходимо для придания правдоподобности происходящему т.к. Private Wars относится к разряду симуляторов, и вполне естественно, что игрок будет ожидать, что бандиты и террористы будут вести себя так же, как они ведут себя в реальной жизни, и не будут представлять из себя безмозглые, индифферентные ко всему подвижные мишени, как это часто бывает в аркадных играх. Во вторую очередь поведение противника должно быть достаточно эффективным с точки зрения поставленных перед ним задач, чтобы он составлял достаточно сильную конкуренцию игроку. Иначе игровой процесс будет слишком прост, если врагов будет мало, или одноообразен, если их будет много. Игрок хочет потягаться силами с хорошо обученным, грамотным и коварным противником, чтобы каждая миссия бросала вызов не только его реакции, но и интеллекту. В третью очередь поведение противника должно соответствовать сценарию миссии и разворачиваться в соответствии с тем, как это было задумано сценаристом. Т.е. миссии должны быть разнообразными не только по их стартовым условиям, но и по их прохождению. Игроку будет гораздо интереснее если в каждой миссии противник будет вести себя несколько иначе и это будет требовать продумывания и предварительного планирования каждой миссии. Основные блоки AIДля решения всех поставленных выше задач мы используем три уровня управления солдатами: уровень примитивов поведения, тактический уровень и стратегический. Уровень примитивов поведения обеспечивает адекватность поведения каждого отдельного солдата в текущей, локальной для него ситуации. Это скорее даже не столько поведение, сколько набор элементарных поведенческих реакций на элементарные события. Этот уровень позволяет превратить солдат из бездушных индефферентных ко всему монстров в некое подобие живых людей с естественным для них поведением и реакциями на происходящее. Уровень примитивов поведения работает только в терминах отдельного солдата и ничего не знает о роли этого солдата внутри его подразделения и о задачах подразделения в целом. За поведение отдельных подразделений, групп солдат отвечает тактический уровень управления, который координирует действия нескольких человек для решения локальной, тактической задачи. Этот уровень управления позволяет добиться того, чтобы действие компьютерных персонажей не напоминало свалку по прнципу «каждый сам за себя», а соответствовало скоординированному поведению профессиональных команд. Тактический уровень действует в терминах управления подразделением и ничего не знает о стратегических задачах и общем сценарии миссии. Стратегический уровень управления координирует действия всех подразделений противника для решения стратегических задач миссии. Он же отвечает за соответствие происходящего сценарию и сюжетной канве. Помимо уровней управления AI включает в себя еще два важных блока: это блок нахождения пути и блок сбора информации о противнике. Нахождение путиДовольно важным элементом блока AI является алгоритм нахождения кратчайшего пути (или близкого к нему) из произвольной точки уровня А в произвольную точку B. При этом гарантируется, что точки A и B находятся вне препятствий, и можно считать, что пространство, на котором ищется путь, двумерное. Естественно уровень может содержать различные сооружения состоящие из более чем одного этажа, но все множество этажей можно представить как набор плоских площадок соединенных переходами (лифты, лестницы и т.п.). Все препятствия (стены, заборы, водоемы и т.д.) можно представить в виде произвольных плоских многоугольников. Особенностью Private Wars является то, что практически все уровни содержат довольно большие участки местности не содержащие никаких препятствий. В связи с этим и в связи с тем, что весь уровень нельзя представить одной плоскостью, использование классических алгоритмов поиска оптимального пути на регулярной сетке не представляется возможным. Кроме того поиск пути (или выявление его отсутствия) должен осуществляться за ограниченное время и требовать ограниченного количества памяти, что накладывает дополнительные ограничения на подходы к решению этой задачи. На данный момент в Private Wars мы используем следующий подход. Весь игровой уровень с помощью специального алгоритма покрывается нерегулярной сеткой. Сетка удовлетворяет следующим условиям. Она связана, т.е. из любого узла сетки существует путь в любой другой узел сетки по ее ребрам. И для любой произвольной точки уровня ближайший к ней узел сетки всегда «видим», т.е. прямая линия соединяющая их не пересекает никаких препятствий. По построенной сетке вычисляется таблица T размерности N*N, где N – это количество узлов в сетке, которая позволяет моментально определить кратчайший путь между двумя произвольными узлами сетки, не производя практически никаких вычислений. Путь находится следующим образом. Если A и B – это узлы сетки, то T[A,B] – это следующий узел C на кратчайшем пути из A в B. Далее мы переходим к D=T[C,B] и т.д. до тех пор пока не доберемся до узла B. Таким образом путь из произвольной точки уровня P1 в произвольную точку P2 находится довольно просто. Для точек P1 и P2 мы находим ближайшие к ним узлы сетки K1 и K2. По таблице T находим путь R из K1 в K2. Результирующий маршрут выглядит как: P1 -> K1 -> R -> K2 -> P2. С точки зрения математики этот путь не является кратчайшим, но он достаточно оптимален для практического использования. Внимательное изучение данного подхода выявляет несколько узких мест. Первое – это размер предварительно просчитанной таблицы T, которая должна всегда находиться в оперативной памяти. Размер таблицы напрямую зависит от количество узлов в сетке, а количество узлов в сетке, напрямую зависит от количества и топологии препятствий на уровне. Практика показывает, что на реальном уровне Private Wars количество узлов составляет порядка 200-300, что приводит к размеру таблицы порядка 80-180 килобайт. Второй проблемой является поиск ближайшего узла сетки для заданной точки плоскости. Фактически это задача быстрого поиска в двумерном пространстве. На данный момент ближайший узел ищется прямым перебором, но возможно, что скоро будет найден более быстрый алгоритм. Третьей проблемой является наличие перемещающихся в пространстве препятствий (люди, машины и т.д.). Данная проблема снимается тем, что столкнувшись с таким препятствием игровой объект просто обходит его по кругу. Блок сбора информации о противникеОсмысленные групповые действия невозможны без постоянного обмена информацией между отдельными солдатами и подразделениями. В связи с этим AI содержит отдельный блок, который реализует эти функции. Предполагается, что AI знает всю географию и топологию местности, на которой разворачиваются события и состояние и расположение всех своих солдат. Помимо этого от каждого солдата поступает информация об обнаруженных и уничтоженных солдатах противника. Вся эта информация скапливатся в отдельном списке и специальный алгоритм строит предположения о текущем количестве и расположении солдат игрока в соответствии с поступающей информацией. Стратегический и тактический уровни имеют полный доступ к этой информации и согласовывают с ней свои действия. Понятно, что ситуация постоянно изменяется в связи с необнаруженным перемещением противника, поэтому информация в этом списке не всегда соответствует действительности, как это и бывает в реальной жизни. Грубо говоря, данный список - это список уже обнаруженных или прогнозируемых солдат игрока, для каждого из которых указаны его текущие, либо предполагаемые координаты, либо указано, что его положение неизвестно. Реализация сбора информации о противникеВся информация о противнике хранится в в одном списке. Каждый элемент списка – это структура состоящая из следующих полей: 1. Идентификатор солдата (может быть неизвестным) Когда блок сбора информации о противнике получает первое в течение миссии сообщение об обнаружении противника, он перед обработкой этого сообщения добавляет в свой список 8 солдат предполагаемого противника и передает сигнал тревоги стратегическому уровню. Число восемь обусловлено тем, что это максимальный размер команды игрока. При первом взгляде кажется, что можно было бы и ограничиться фиксированным массивом из восьми элементов. Но это не так. В процессе выполнения миссии список противников может пополниться например заложниками или другими компьютерными персонажами, которых необходимо уничтожить по сценарию. При формировании списка солдат противника начальное состояние всех элементов массива таково: 1. Идентификатор солдата - неизвестен В процессе игры блок информации о противнике может получать от уровня примитивов или тактического уровня следующие сообщения: Alert, Tango_is_dead, Unidentified_Tango_detected, Tango_detected, Tango_is_lost. Эти сообщения генерируются в следующих случаях:
Полученные сообщения обрабатываются следующим образом:
Уровень примитивов поведенияУровень примитивов поведения реализуется по схеме конечного автомата. Т.е. каждый солдат имеет некоторый набор внутренних состояний, в которых он может находиться, набор элементарных событий, на которые он должен реагировать, и набор элементарных реакций на происходящие события. События, на которые реагирует солдат, можно условно разделить на «внешние», приходящие из игрового окружения, и «внутренние(служебные)», которые необходимы для реализации алгоритмов поведения и управления внутренними структурами данных. К внешним событиям относятся, например, следующие: увидел противника, увидел труп противника, увидел труп своего, противник в прицеле, услышал перемещение противника, услышал выстрел, столкнулся с подвижным препятствием, увидел летящую в меня гранату, пуля попала рядом со мной, пуля попала в меня, получил сигнал тревоги, кончились патроны в текущем оружии и т.д. К служебным событиям, например, относятся следующие: я ранен, я умер, пришел сигнал таймера, текущяя последовательность действий завершена, достигнута конечная точка маршрута и т.д. В набор элементарных реакций входят, например, следующие: произвести выстрел, сменить оружие, поменять позу, повернуться, переместиться в заданную точку и т.д. В соответствии с текущим состоянием солдата и значением его внутренних параметров по каждому поступившему событию принимается решение о какой- либо элементарной реакции, либо цепочке элементарных реакции. В связи с тем, что выполнение каждой элементарной реакции требует некоторого времени, вводится понятие последовательности действий и события «текущяя последовательность действий закончена». Помимо этого учитывается, что события могут поступать гораздо чаще, чем успевают выполняться связанные с ними действия, и поступление некоторых событий либо лишает целесообразности продолжение выполнения текущей цепочки действий, либо требует незамедлительной реакции на них. Для снятия этой проблемы вводится понятие приоритета последовательности. Если поступившее событие порождает цепочку действий с более высоким приоритетом, то выполнение текущей цепочки корректно прерывается и начинает выполняться новая последовательность. Для того, чтобы поведение солдат было более похожим на поведение реальных людей вводится понятие скорости реакции и времени принятия решения. Т.е. солдат как бы «задумывается» над каждым событием и не в состоянии мгновенно на него среагировать. Например, если игрок на секунду высунется из укрытия, то противник со слабой реакцией просто не успеет в него выстрелить даже если увидит его в своем прицеле. Реализация примитивов поведенияСписок событий, поступающих из игрового окружения:
Список элементарных реакций уровня примитивов поведения:
Тактический уровеньСхема работы тактического уровня гораздо сложнее и не укладывается в простую модель конечного автомата. Ее скорее можно назвать системой основанной на шаблонах поведения для решения различных тактических задач, каждая из которых требует своего отдельного алгоритма поведения группы. Тактический уровень управления получает задачи от стратегического и решает их согласно сложившейся ситуации и имеющихся ресурсов. При этом тактический уровень обрабатывает события, поступающие от уровня примитивов поведения, и отдает команды подконтрольным ему солдатам. К задачам, которые решает тактический уровень относятся, например, следующие: зачистка здания от противника, скрытное проникновение на заданную позицию, преследование противника и т.д. Решение каждой из этих задач проводится по определенному сценарию или шаблону действий. К подзадачам на которые разбивается выполнение тактических задач относятся следующие: оптимальное размещение своих солдат на позиции с учетом положения противника, безопасные перемещения своих солдат (выбор момента, перемещение одного, прикрытие его огнем с помощью других), правильная ориентация своих солдат для достижения максимального обзора, плотности огня или зоны обстрела, согласно требованиям текущей ситуации. Использование тактического уровня позволяет максимально использовать преимущество скоординированных действий группы по сравнению со схемой «каждый сам за себя» и позволяет также избежать ситуаций, типичных для игры Rainbow Six, когда, например оба участника команды смотрят в стену, подставляя свои спины под огонь противника или когда один из солдат хладнокровно смотрит в сторону, пока другой вовсю отстреливается от игрока. Реализация тактического уровняСписок событий, обрабатываемых тактическим уровнем:
Список команд передаваемых уровню примитивов поведения:
Стратегический уровеньСхема работы стратегического уровня управления достаточна проста. На этапе дизайна миссии разработчики выделяют ключевые объекты, зоны и события существенные для протекания миссии. Далее они рассматривают все возможные сценарии поведения игрока и стадии протекания боя. Исходя из этих предположений строится алгоритм стратегического поведения для данной миссии. В отличие от остальных уровней управления AI алгоритм стратегического уровня пишется для каждой миссии индивидуально. Во время игры стратегический уровень получает события от тактического уровня, анализирует обстановку и принимает необходимые решения. Далее он спускает задачи на тактический уровень. Реализация стратегического уровняСписок событий, обрабатываемых стратегическим уровнем:
Список команд отдаваемых подразделениям:
Пример написания стратегического уровня для миссииПроиллюстрируем программирование стратегического уровня управления на примере несложной миссии. Группа террористов захватила загородную виллу. Террористы удерживают двух заложников. Заложники находятся на втором этаже здания вместе с главарем банды (Maestro) и его телохранителями (команда №1). Несколько человек (команда №2) находятся на первом этаже. Основная группа (команда №3) находится во дворе. Логика действий террористов, которую нам нужно реализовать, такова. Всем членам банды дана команда охраны соответствующих локаций. Первая команда так же выполняет функции охраны босса. Всем разрешено открывать огонь на свое усмотрение. Если противник сумел проникнуть в здание, то босс вместе с первой командой скрываются в подвале в надежде уйти через канализацию. Все оставшиеся должны обеспечить смерть обоих заложников. Проиллюстрируем это программным кодом:
void Start_Mission()
{
team[1]->Guard(second_floor);
team[1]->Conduct(Maestro);
//Первая команда охраняет босса
team[2]->Guard(first_floor);
team[3]->Guard(court);
team[1]->Fire_at_will;
team[2]->Fire_at_will;
team[3]->Fire_at_will;
//стрелять при первой возможности
}
void Alarm(int)
//кто-то засек врага
{
for(int k=1; k<4; k++) team[k]->Alarm();//Тревога!
}
int stage=0;
void Enemy_Detected(int team_ID, int tango_ID)
{
if(((team_ID==1)||(team_ID==2))""(stage==0)){
//если противник уже в доме
stage=1;
team[1]->Sneak(basement);
//то первой команде прокрасться в подвал
team[2]->Destroy(hostage1);
team[3]->Destroy(hostage1);
//остальные две команды уничтожают заложников
//сначала первого, потом второго
}
}
void Tango_dead(int team_ID, int tango_ID)
{
if(tango_ID==hostage1){
team[2]->Destroy(hostage2);
team[3]->Destroy(hostage2);
}
}
|