22 сентября 1999 (Обновление: 19.05.2012) [Вниз] [Обсуждение на форуме] [Спасибо автору!]
Архитектура Искусственного Интеллекта для симулятора спецназа
Этот документ писался как наброски к дизайну системы искусственного интеллекта для компьютерной игры Private Wars. Игра представляла из себя тактический симулятор боевых действий спецназа. Аналоги: Rainbow Six, Spec Ops, Delta Forces. Private Wars были реализованы в трехмерной графике с видом от первого лица. Игра состояла из двух десятков миссий, каждая из которых разворачивалась по одному из типичных сценариев проведения контртеррористических операций. Игрок получал в свое распоряжение команду спецназа до 8 человек и имел возможность непосредственно управлять одним из членов команды. Всеми остальными членами команды он мог управлять с помощью приказов. За террористов играл компьютер. Ниже описан подход к реализации искусственного интеллекта для такого класса игр.
Решаемые задачи
Поведение NPC в Private Wars должно удовлетворять нескольким требованиям.
В первую очередь его поведение должно быть логичным и правдободобным с точки зрения игрока. Это необходимо для придания правдоподобности происходящему т.к. Private Wars относится к разряду симуляторов, и вполне естественно, что игрок будет ожидать, что бандиты и террористы будут вести себя так же, как они ведут себя в реальной жизни, и не будут представлять из себя безмозглые, индифферентные ко всему подвижные мишени, как это часто бывает в аркадных играх.
Во вторую очередь поведение противника должно быть достаточно эффективным с точки зрения поставленных перед ним задач, чтобы он составлял достаточно сильную конкуренцию игроку. Иначе игровой процесс будет слишком прост, если врагов будет мало, или одноообразен, если их будет много. Игрок хочет потягаться силами с хорошо обученным, грамотным и коварным противником, чтобы каждая миссия бросала вызов не только его реакции, но и интеллекту.
В третью очередь поведение противника должно соответствовать сценарию миссии и разворачиваться в соответствии с тем, как это было задумано сценаристом. Т.е. миссии должны быть разнообразными не только по их стартовым условиям, но и по их прохождению. Игроку будет гораздо интереснее если в каждой миссии противник будет вести себя несколько иначе и это будет требовать продумывания и предварительного планирования каждой миссии.
Основные блоки AI
Для решения всех поставленных выше задач мы используем три уровня управления солдатами: уровень примитивов поведения, тактический уровень и стратегический.
Уровень примитивов поведения обеспечивает адекватность поведения каждого отдельного солдата в текущей, локальной для него ситуации. Это скорее даже не столько поведение, сколько набор элементарных поведенческих реакций на элементарные события. Этот уровень позволяет превратить солдат из бездушных индефферентных ко всему монстров в некое подобие живых людей с естественным для них поведением и реакциями на происходящее.
Уровень примитивов поведения работает только в терминах отдельного солдата и ничего не знает о роли этого солдата внутри его подразделения и о задачах подразделения в целом.
За поведение отдельных подразделений, групп солдат отвечает тактический уровень управления, который координирует действия нескольких человек для решения локальной, тактической задачи. Этот уровень управления позволяет добиться того, чтобы действие компьютерных персонажей не напоминало свалку по прнципу «каждый сам за себя», а соответствовало скоординированному поведению профессиональных команд.
Тактический уровень действует в терминах управления подразделением и ничего не знает о стратегических задачах и общем сценарии миссии.
Стратегический уровень управления координирует действия всех подразделений противника для решения стратегических задач миссии. Он же отвечает за соответствие происходящего сценарию и сюжетной канве.
Помимо уровней управления AI включает в себя еще два важных блока: это блок нахождения пути и блок сбора информации о противнике.
Cхема взаимодействия блоков 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. Идентификатор солдата (может быть неизвестным)
2. Состояние солдата (живой/мертвый). Если состояние неизвестно,
то, пока не найдем труп, считаем живым
3. Координаты (могут быть неизвестными)
4. Время получения последних данных о солдате
Когда блок сбора информации о противнике получает первое в течение миссии сообщение об обнаружении противника, он перед обработкой этого сообщения добавляет в свой список 8 солдат предполагаемого противника и передает сигнал тревоги стратегическому уровню. Число восемь обусловлено тем, что это максимальный размер команды игрока. При первом взгляде кажется, что можно было бы и ограничиться фиксированным массивом из восьми элементов. Но это не так. В процессе выполнения миссии список противников может пополниться например заложниками или другими компьютерными персонажами, которых необходимо уничтожить по сценарию.
При формировании списка солдат противника начальное состояние всех элементов массива таково:
1. Идентификатор солдата - неизвестен
2. Состояние солдата - живой
3. Координаты - неизвестны
4. Время получения последних данных – время формирования
списка
В процессе игры блок информации о противнике может получать от уровня примитивов или тактического уровня следующие сообщения: Alert, Tango_is_dead, Unidentified_Tango_detected, Tango_detected, Tango_is_lost.
Эти сообщения генерируются в следующих случаях:
| # | Event | Situation |
| 1 | Alert | Солдат видит труп своего; Противником уничтожен обьект; Солдат видит или слышит взрыв; Сработала сигнализация; Солдат видит/слышит рикошет или ранен из бесшумного оружия; Тактическим блоком обнаружена гибель своего: например часовой был бесшумно снят, а тактический блок через какое-то время пытается отдать ему команду |
| 2 | Tango_is_dead(ID,Point) | Солдат видит труп противника |
| 3 | Unidentified_Tango_detected(Point) | Солдат слышит противника; Солдат видит брошенную в него гранату |
| 4 | Tango_detected(ID,Point) | Солдат видит противника |
| 5 | Tango_is_lost(Point) | Солдат смотрит в точку известного местонахождения противника, но не находит его там |
Полученные сообщения обрабатываются следующим образом:
| # | Event | Processing |
| 1 | Alert | Служит только для передачи сигнала Alert стратегическому уровню |
| 2 | Tango_is_dead(ID,Point) | Если в списке есть противник с данным ID, то он помечается мертвым, иначе ищется неизвестный с неизвестными координатами и помечается мертвым, если таковой не находится, то мертвым помечается ближайший к трупу неизвестный. Сигнал передается далее тактическому уровню. |
| 3 | Unidentified_Tango_detected(Point) | Если в списке есть неизвестный с неизвестными координатами, то его координаты и время обновляются, иначе ищется ближайший к точке неизвестный, и его координаты и время обновляются, если такового нет, то ищется ближайший к точке из известных противников и его координаты и время обновляются. Сигнал передается далее тактическому уровню. |
| 4 | Tango_detected(ID,Point) | Если в списке есть противник с данным ID, то его координаты и время обновляются, иначе ищется неизвестный с неизвестными координатами и его координаты и время обновляются, если такового нет, то ищется ближайший к точке неизвестный, и его координаты и время обновляются. Сигнал передается далее тактическому уровню. |
| 5 | Tango_is_lost(Point) | В списке ищется противник с указанными координатами и его координаты сбрасываются в неизвестные. Сигнал передается далее тактическому уровню. |
Уровень примитивов поведения
Уровень примитивов поведения реализуется по схеме конечного автомата. Т.е. каждый солдат имеет некоторый набор внутренних состояний, в которых он может находиться, набор элементарных событий, на которые он должен реагировать, и набор элементарных реакций на происходящие события.
События, на которые реагирует солдат, можно условно разделить на «внешние», приходящие из игрового окружения, и «внутренние(служебные)», которые необходимы для реализации алгоритмов поведения и управления внутренними структурами данных. К внешним событиям относятся, например, следующие: увидел противника, увидел труп противника, увидел труп своего, противник в прицеле, услышал перемещение противника, услышал выстрел, столкнулся с подвижным препятствием, увидел летящую в меня гранату, пуля попала рядом со мной, пуля попала в меня, получил сигнал тревоги, кончились патроны в текущем оружии и т.д. К служебным событиям, например, относятся следующие: я ранен, я умер, пришел сигнал таймера, текущяя последовательность действий завершена, достигнута конечная точка маршрута и т.д.
В набор элементарных реакций входят, например, следующие: произвести выстрел, сменить оружие, поменять позу, повернуться, переместиться в заданную точку и т.д.
В соответствии с текущим состоянием солдата и значением его внутренних параметров по каждому поступившему событию принимается решение о какой- либо элементарной реакции, либо цепочке элементарных реакции. В связи с тем, что выполнение каждой элементарной реакции требует некоторого времени, вводится понятие последовательности действий и события «текущяя последовательность действий закончена».
Помимо этого учитывается, что события могут поступать гораздо чаще, чем успевают выполняться связанные с ними действия, и поступление некоторых событий либо лишает целесообразности продолжение выполнения текущей цепочки действий, либо требует незамедлительной реакции на них. Для снятия этой проблемы вводится понятие приоритета последовательности. Если поступившее событие порождает цепочку действий с более высоким приоритетом, то выполнение текущей цепочки корректно прерывается и начинает выполняться новая последовательность.
Для того, чтобы поведение солдат было более похожим на поведение реальных людей вводится понятие скорости реакции и времени принятия решения. Т.е. солдат как бы «задумывается» над каждым событием и не в состоянии мгновенно на него среагировать. Например, если игрок на секунду высунется из укрытия, то противник со слабой реакцией просто не успеет в него выстрелить даже если увидит его в своем прицеле.
Реализация примитивов поведения
Список событий, поступающих из игрового окружения:
| # | Event |
| 1 | Вижу противника |
| 2 | Вижу своего |
| 3 | Вижу труп противника |
| 4 | Вижу труп своего |
| 5 | Слышу противника |
| 6 | Вижу летящую гранату |
| 7 | Пуля попала в меня |
| 8 | Пуля попала рядом со мной |
| 9 | Столкнулся с подвижным препятствием |
| 10 | Сигнал тревоги |
| 11 | Кончились патроны в текущем оружии |
| 12 | Вижу обьект |
| 13 | Противник в прицеле |
| 14 | Слышу и/или вижу взрыв |
Список элементарных реакций уровня примитивов поведения:
| # | Action |
| 1 | Сменить позу |
| 2 | Повернуться |
| 3 | Переместиться |
| 4 | Сменить оружие |
| 5 | Сменить режим стрельбы |
| 6 | Произвести выстрел |
| 7 | Бросить гранату |
| 8 | Использовать устройство |
| 9 | Открыть дверь |
| 10 | Сесть в транспортное средство |
| 11 | Сойти с транспортного средства |
Тактический уровень
Схема работы тактического уровня гораздо сложнее и не укладывается в простую модель конечного автомата. Ее скорее можно назвать системой основанной на шаблонах поведения для решения различных тактических задач, каждая из которых требует своего отдельного алгоритма поведения группы. Тактический уровень управления получает задачи от стратегического и решает их согласно сложившейся ситуации и имеющихся ресурсов. При этом тактический уровень обрабатывает события, поступающие от уровня примитивов поведения, и отдает команды подконтрольным ему солдатам.
К задачам, которые решает тактический уровень относятся, например, следующие: зачистка здания от противника, скрытное проникновение на заданную позицию, преследование противника и т.д. Решение каждой из этих задач проводится по определенному сценарию или шаблону действий.
К подзадачам на которые разбивается выполнение тактических задач относятся следующие: оптимальное размещение своих солдат на позиции с учетом положения противника, безопасные перемещения своих солдат (выбор момента, перемещение одного, прикрытие его огнем с помощью других), правильная ориентация своих солдат для достижения максимального обзора, плотности огня или зоны обстрела, согласно требованиям текущей ситуации.
Использование тактического уровня позволяет максимально использовать преимущество скоординированных действий группы по сравнению со схемой «каждый сам за себя» и позволяет также избежать ситуаций, типичных для игры Rainbow Six, когда, например оба участника команды смотрят в стену, подставляя свои спины под огонь противника или когда один из солдат хладнокровно смотрит в сторону, пока другой вовсю отстреливается от игрока.
Реализация тактического уровня
Список событий, обрабатываемых тактическим уровнем:
| # | Event | Comments |
| 1 | Alarm | Обнаружен противник |
| 2 | Ready(ID) | Солдат успешно выполнил команду |
| 3 | Failed(ID) | Солдат не смог выполнить команду |
| 4 | Out_of_Ammo(ID) | У солдата закончились патроны в текущем оружии |
| 5 | I_am_wounded(ID) | Солдат получил ранение |
| 6 | I_am_dead(ID) | Солдат умер. Событие приходит только в ответ на команду отданную мертвому, не раньше. Это дает возможность бесшумно снимать часовых. |
| 7 | Tango_is_dead(ID,Point) | Описано выше |
| 8 | Unidentified_Tango_detected(Point) | Описано выше |
| 9 | Tango_detected(ID,Point) | Описано выше |
| 10 | Tango_is_lost(Point) | Описано выше |
| 11 | Grenade_detected(GrenadeID) | Описано выше |
Список команд передаваемых уровню примитивов поведения:
| # | Order | Comments |
| 1 | Alarm | Сигнал тревоги. Изменяет скорость выполнения действий и ряд внутренних параметров солдата. |
| 2 | Watch(direction) | Солдат следит за указанным направлением время от времени осматриваясь по сторонам |
| 3 | Set_Pose(pose) | Сменить положение: стоя, сидя, лежа |
| 4 | Watch(object) | Солдат следит за указанным объектом, оставаясь на месте |
| 5 | Hold_Position | Остановиться в текущей точке и не покидать ее |
| 6 | Patrol(route) | Патрулирование по заданному мршруту |
| 7 | Change_Weapon(weapon) | Сменить оружие на указанное |
| 8 | Look_around | Отменяет действие команд Watch(direction) и Watch(object) |
| 9 | Fire_at_Object(object) | Открыть огонь по указанному обьекту |
| 10 | Move_to(Point) | Переместиться в указанную точку |
| 11 | Fire_at_will | Включает режим стрельбы по собственному усмотрению. Солдат стреляет по ближайшему видимому противнику. |
| 12 | Cease_fire | Прекратить огонь. Солдат не открывает огонь ни под каким предлогом. |
Стратегический уровень
Схема работы стратегического уровня управления достаточна проста. На этапе дизайна миссии разработчики выделяют ключевые объекты, зоны и события существенные для протекания миссии. Далее они рассматривают все возможные сценарии поведения игрока и стадии протекания боя. Исходя из этих предположений строится алгоритм стратегического поведения для данной миссии. В отличие от остальных уровней управления AI алгоритм стратегического уровня пишется для каждой миссии индивидуально. Во время игры стратегический уровень получает события от тактического уровня, анализирует обстановку и принимает необходимые решения. Далее он спускает задачи на тактический уровень.
Реализация стратегического уровня
Список событий, обрабатываемых стратегическим уровнем:
| # | Event | Comments |
| 1 | Alarm(team) | Сигнал тревоги |
| 2 | Tango_dead(team,ID) | Обнаружен труп противника |
| 3 | Friendly_dead(team,ID) | Обнаружена смерть своего |
| 4 | Object_destroyed(team,ID) | Обьект уничтожен. Либо противником, либо своими |
| 5 | Enemy_moved(team,ID) | Обнаружено перемещение противника |
| 6 | Ready(team) | Подразделение успешно выполнило приказ |
| 7 | Failed(team) | Подразделение не смогло выполнить приказ |
| 8 | Enemy_detected(team,ID) | Подразделение засекло противника. Событие приходит ровно один раз от данного подразделения. Следующее событие Enemy_detected от этого подразделения может поступить только после события Enemy_lost |
| 9 | Enemy_lost(team,ID) | В зоне видимости подразделения противника больше нет. Событие приходит ровно один раз от данного подразделения. Следующее событие Enemy_lost от этого подразделения может поступить только после события Enemy_detected или Compromised. |
| 10 | Compromised(team) | Подразделение засечено противником. Событие приходит ровно один раз от данного подразделения. Следующее событие Compromised от этого подразделения может поступить только после события Enemy_lost. |
Список команд отдаваемых подразделениям:
| # | Order | Comments |
| 1 | Alarm | Перейти в состояние повышенной боевой готовности |
| 2 | Patrol(route) | Патрулировать по заданному маршруту. Подразделение перемещается по маршруту, останавливаясь время от времени и осматриваясь. |
| 3 | Guard(position) | Охранять обьект. Подразделение рассредотачивается по ключевым зонам обьекта и перемещается по нему таким образом, чтобы контролировать как можно больше площади одновременно. |
| 4 | Move_to(position) | Сменить дислокацию. В команде выделяется разведчик и замыкающий. Команда перемещается от точки к точке следующим образом: сначала выдвигается разведчик, после того, как он осмотрится в следующей точке, выдвигается вся остальная команда, кроме замыкающего, который охраняет ее тылы. Когда вся команда переместилась, перемещается и замыкающий. |
| 5 | Sneak_to(position) | Проникнуть на позицию. То же самое, что и предыдущий вариант, кроме того, что выбирается маршрут достаточно удаленный от противника, а там, где это не возможно, солдаты перемещаются либо за спиной у противника, либо ползком. Огонь без команды не открывается. |
| 6 | Destroy(object) | Команда преследует обьект и старается уничтожить его. Во время боя огонь по обьекту ведется в первую очередь. |
| 7 | Defend | Остановиться и оборонять текущую позицию. |
| 8 | Conduct(ID) | Экскортировать члена команды. Член команды, которого экскортиуют, во время боя находится в самом безопасном месте, а остальные солдаты обеспечивают его безопасность в первую очередь. |
| 9 | Fire_at_will | Режим стрельбы на усмотрение подразделения |
| 10 | Cease_fire | Прекратить огонь. Огонь без команды не открывать |
| 11 | Join(team) | Объеденить команду с другим подразделением. |
| 12 | Split(team,ID) | Перевести члена команды в другое подразделение |
| 13 | Cleanse(position) | “Зачистить” обьект. Команда обходит каждый угол и все закоулки обьекта в поисках противника. |
Пример написания стратегического уровня для миссии
Проиллюстрируем программирование стратегического уровня управления на примере несложной миссии.
Группа террористов захватила загородную виллу. Террористы удерживают двух заложников. Заложники находятся на втором этаже здания вместе с главарем банды (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);
}
}
