Искусственный интеллект

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

Мы обсудим следующие темы:

  - Обзор того, как мыслят видеоигры;
  - Алгоритмы Преследования и Уклонения;
  - Шаблонные мысли;
  - Случайные передвижения;
  - Автоматы с конечными состояниями;
  - Вероятностные автоматы;
  - Память и обучение;
  - Алгоритмы Поиска;
  - Теория игр.
  

КАК МЫСЛЯТ ВИДЕОИГРЫ: ОБЗОР

Придет тот день, когда компьютер станет таким же серьезным собеседником, как и лучшие человеческие умы. Однако сегодняшние компьютеры (по крайней мере, ПК) не обладают сложностью, необходимой для инициации мыслей и творческих процессов.Но на самом деле нас это и не должно волновать! Мы же делаем видеигры, а не андроидов. В игре у нас присутствуют некоторые создания и объекты. Все, что нам нужно сделать, это придать им видимость способности разумного мышления. Играющий может ощущать себя помещенным на короткое время в некое пространство, где он думает, что вражеская атака на корабль реальна! Для осуществления этих целей мы должны проанализировать, каким разумом мы должны наделить наши игровые объекты. Сложность этого "разума" зависит от того, какую разновидность существ мы конструируем. К примеру, создания из Pac Man большую часть своего времени тратят на преследование или убегание от вас. Будь мы теми людьми, что написали Pac Man, мы имели бы возможность загорать где-нибудь на Гавайях, но у нас в таком случае уже был бы алгоритмический инструмент для осуществления этих преследований и убеганий.

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

1. Продолжать движение в том направлении, в котором вы двигаетесь (вправо или влево);

2. Когда вы попадете на границу экрана, изменить направление и двигаться вдоль оси высоты;

3. перейти к п.1.

Не шибко обширный набор "интеллектуальных" функций для игры, прибыль от которой за все время ее существования составила от 50 до 100 миллионов долларов. Трехмерные видеоигры нам интересны не потому, что они "умнее" обычных "плоских" игр. Объемность дает только повышенное ощущение реальности, а алгоритмы, наделяющие персонажей разумом, в них те же, что и в двухмерных играх. К примеру, Terminator Rampage имеет действительно несложную систему искусственного интеллекта, примерно того же уровня сложности, что и в Pac Man. Однако, при наличии трехмерной графики вместе с изощренным звуком существа в ней кажутся вполне одушевленными. Итак, приведем к общему знаменателю характер большинства компьютерных игр: интеллект персонажей находится на пещерном уровне, но этот недостаток компенсируется за счет графики и звука. Разработчиков видеоигр идея искусственного интеллекта притягивает снова и снова на протяжении длительного времени, потому что игры, которые они пишут, в большинстве своем довольно агрессивны. Наша задача в этой части состоит в том, чтобы понять методы, используемые для моделирования интеллекта, и главные критерии, внутри которых существуют "мыслящие" алгоритмы. Запомните, игры не думают. Они только "делают умное лицо". Посему большую часть времени мы будем конструировать основной разумный вид деятельности вроде преследования и нападения. Как вы догадываетесь, на это большого ума не надо: обнаружить противника и уничтожить его, или, с точки зрения компьютерной программы, двигаться по направлению к врагу, взять его на мушку и открыть огонь из всех видов оружия.

АЛГОРИТМЫ ПРЕСЛЕДОВАНИЯ И УКЛОНЕНИЯ

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

---

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

Алгоритм 13.1. Алгоритм Преследования.

---

// Предположим, что px,py - координаты игрока,
// ex,ey - координаты противника

while ( игра )
    {
      программный код
      ......
      ......
      // Вначале рассматриваем перемещение по горизонтали (ось Х)
      if ex > px then ex=ex+1
      if ex  py then ey=ey+1
      if ey 
  - Если враг находится справа, то есть его Х-координата больше
    соответствующей коондинаты игрока, преследователь уменьшает свою
    собственную позицию по оси Х на единицу и тем самым приближается к
    игроку. Если же противник находится левее игрока, он, наоборот,
    увеличивает свою горизонтальную координату.
  - Та же самая логика применима и к перемещению по вертикали.
  
Используя этот алгоритм, противник преследует игрока почти столь же
неумолимо, как и Т1000 из Терминатора-2. Он не остановится до тех пор, пока
не поймает игрока. Мы могли бы несколько облегчить его задачу путем
добавления некоторой дополнительной логики, способствующей его движению к
позиции нанесения удара. Однако, перед тем, как это делать, давайте
посмотрим программу, моделирующую преследование. Листинг программы 13.1
рисует 2 точки: одну голубую (вы), а другую красную(противник). Что бы вы
ни предпринимали, красная точка пытается настичь вас. Для движения (или, я
бы сказал, бега!) нажмите клавишу U - перемещение вверх, N - вниз, H -
влево и J - вправо. Для выхода из программы нажмите Q.

Листинг 13.1. Программа Терминатор (TERM.C).
// I N C L U D E S////////////////////////////////////////////////////////////

#include 
#include 


// G L O B A L S /////////////////////////////////////////////////////////////

unsigned int far *clock = (unsigned int far *)0x0000046C;// pointer to internal
                                                         // 18.2 clicks/sec

//////////////////////////////////////////////////////////////////////////////

Timer(int clicks)
{
// this function uses the internal time keeper timer i.e. the one that goes
// at 18.2 clicks/sec to to a time delay.  You can find a 32 bit value of
// this timer at 0000:046Ch

unsigned int now;

// get current time

now = *clock;

// wait till time has gone past current time plus the amount we eanted to
// wait.  Note each click is approx. 55 milliseconds.

while(abs(*clock - now)  ex) ex++;
     if (px  ey) ey++;
     if (py 

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

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

Алгоритм 13.2. Алгоритм Уклонения.
// пусть (px,py) - позиция игрока и (ex,ey) - позиция противника
while (игра)
 {
 
 .....// код программы
 
 // Вначале - горизонтальная составляющая перемещения
 if ex > px then ex=ex-1
 if ex  py then ey=ey-1
   if ey 

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

  Шаблонные мысли
На заре создания видеоигр программисты сталкивались с серьезными
проблемами, пробуя нанести точки на экран. Они радовались по поводу удачной
  
имитации тактики боя и написания набора алгоритмов, управляющих существами
в их мире. 
Увы, они думали, что могут имитировать разумное поведение с помощью
шаблонов, то есть описывая рядом цифр траектории перемещения созданий. К
примеру, в игре Galaxian маленькие космические корабли делают несколько
кругов, стреляют в вас некоторое время, а затем возвращаются на прежнее
место в стаю своих сородичей. Посмотрим на рис.13.1.
Когда они выполняют эти движения, то всего лишь следуют командам, заранее
написанных шаблонов.
Конструирование шаблонов - чрезвычайно легкое занятие и они нашли
использование во многих сценариях. Как пример, используем шаблоны и
случайные числа для моделирования "разума", который можно использовать,
например, для управления небольшим космическим кораблем. Он пытается
уклониться от вас, и в то же время пробует прицельно стрелять. То, что
можно для этого сделать, показано в Алгоритме 13.3.

Алгоритм 13.3. Шаблоны со случайным выбором.
// Предположим, что pattern - это массив, содержащий набор команд
// для реализации десяти различных шаблонов поведения

while (идет игра)
   {
   
   .... код программы
   
       // Проверяем, закончена ли обработка текущего шаблона
       if (если обработка команд текущего шаблона закончена)
          {
          
       // Выбираем новый шаблон
       current_pattern = pattern[rand()%10];
       
       позиция противника = старая позиция +
                            следующий элемент текущего шаблона
                            
       Увеличим на единицу значение индекса элементов шаблона
       
       .... код программы
       
       }


Алгоритм 13.3 кажется сложнее предыдущих Алгоритмов Преследования и
Уклонения, но на самом деле это не так. В сущности:
  - Случайным образом выбирается некоторый шаблон;
  - Движение созданий в каждом проходе цикла изменяется в соответствии
    с направлением, указанным в шаблоне;
  - Затем мы переходим к следующему элементу шаблона. Каждый шаблон 
    может включать в себя произвольное количество элементов. Некоторые из
    них имеют 10 элементов, а иные - 1000.
Важно одно - когда "создание" исчерпывает набор команд, задаваемый одним
шаблоном - оно переходит к другому.
Наконец, мы могли бы связать выбор случайного номера шаблона с действиями
на основе некой другой логики - например, описываемой Алгоритмом 13.1.
Добавив к Алгоритму 13.3 последний шаг, мы придали ему некоторый аспект,
который придал ему большую комплексность. Появилось подобие мыслительного
процесса, состоящего из двух стадий. Случайное число подается на вход
селектора шаблонов, который затем выбирает новый шаблон для игры.
                         +----------------------+
                         ¦       Генератор      ¦     1-й уровень
                         ¦    случайных чисел   ¦   (мыслительный)
                         +-----------+----------+
                            +--------+---------+ 
                            ¦ Выбор шаблонов   ¦
                            +------------------+
                                     

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 +-----------+ +-----------+      +------------+     2-й уровень
 ¦           ¦ ¦           ¦      ¦            ¦  (функции моторики)
 ¦           ¦ ¦           ¦      ¦            ¦                                  
 ¦           ¦ ¦           ¦ ...  ¦            ¦
 ¦           ¦ ¦           ¦      ¦            ¦
 ¦           ¦ ¦           ¦      ¦            ¦
 +-----------+ +-----------+      +------------+
  Шаблон 1       Шаблон 2           Шаблон N
  
        Рис.13.2. Использование случайных чисел для выбора шаблона.
        
По аналогии с нервной системой, случайное число можно представить как
нервный импульс, а выбранный шаблон действий - как реакцию на него.
Посмотрите на рис. 13.2, чтобы увидеть тот процесс, о котором я говорю.
   Для усовершенствования тактики можно добавить измерение расстояния до
игрока: если существо находится за пределами некоторого радиуса,
используется Алгоритм Преследования, однако, когда оно оказывается
достаточно близко, то начинает перемещаться по шаблонным траекториям,
выбирая их случайным образом. Эта идея применена в Алгоритме 13.4.

Алгоритм 13.4. Преследование и Танец.
while (идет игра)
       {
       ....код программы
       
       if (игрок вне круга с радиусом 50 точек)  then  преследуем его
       else
       выбираем случайный шаблон и реализуем его
       
       .... код программы
       }


Для демонстрации использования шаблонов я переработал программу из Листинга
13.1 и привел ее в соответствие с Алгоритмом 13.4. Новая программа показана
в Листинге 13.2. Когда враг приближается к игроку, он выбирает один из трех
шаблонов и выполняет его до завершения. Далее, в зависимости от расстояния
до игрока, противник либо преследует игрока, либо выбирает другой шаблон.

Листинг 13.2. Муха (FLY.C).
// I N C L U D E S////////////////////////////////////////////////////////////

#include 
#include 
#include 

// G L O B A L S /////////////////////////////////////////////////////////////

unsigned int far *clock = (unsigned int far *)0x0000046C; // pointer to internal
                                                          // 18.2 clicks/sec


// the x and y components of the patterns that will be played, I just made
// them up

int patterns_x[3][20]= { 1,1,1,1,1,2,2,-1,-2,-3,-1,0,0,1,2,2,-2,-2,-1,0,
                         0,0,1,2,3,4,5,4,3,2,1,3,3,3,3,2,1,-2,-2,-1,
                         0,-1,-2,-3,-3,-2,-2,0,0,0,0,0,0,1,0,0,0,1,0,1 };



int patterns_y[3][20] = { 0,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,0,2,2,2,2,2,2,
                          1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,0,0,0,0,
                          1,1,1,2,2,-1,-1,-1,-2,-2,-1,-1,0,0,0,1,1,1,1,1 };


//////////////////////////////////////////////////////////////////////////////

Timer(int clicks)
{
// this function uses the internal time keeper timer i.e. the one that goes
// at 18.2 clicks/sec to to a time delay.  You can find a 32 bit value of
// this timer at 0000:046Ch

unsigned int now;

// get current time

now = *clock;

// wait till time has gone past current time plus the amount we eanted to
// wait.  Note each click is approx. 55 milliseconds.

while(abs(*clock - now)  ex) ex++;
        if (px  ey) ey++;
        if (py 

Когда вы запустите программу из Листинга 13.2, то поймете, почему я назвал
ее "Муха". Точка, бегающая по экрану и в самом деле напоминает муху. Она
приближается к вам и вдруг начинает быстро летать вокруг. И такое поведение
персонажа воплощено всего в нескольких строках программы с применением
описанных выше алгоритмов. (Гм, так как вы думаете, может быть люди - это и
в самом деле комплекс действий и реакций?)
Теперь рассмотрим случайные передвижения.

    Случайные передвижения
Что я понимаю под случайным передвижением? Это выполнение персонажем
какого-нибудь совершенно непредсказуемого действия. Нечто подобное мы уже
сделали в программе из Листинга 13.2. Однако, мы можем расширить эту
концепцию не только выбирая способ реагирования, но и определяя, нужна ли
реакция как таковая. Почему бы нам не добавить еще один тип поведения нашей
"Мухе" - случайное предвижение.
Случайные перемещения используются во многих видеоиграх как один из
способов реагирования виртуального мира на действия игрока. Такой образ
действий можно назвать "неявной логикой". Неявная логика помогает принять
решение при отсутствии части необходимой информации, или вообще информации
как таковой.
В видеоиграх мы можем использовать случайные перемещения и неявную логику
для выбора траекторий или действий наших созданий.
К примеру, когда вы сталкиваетесь с решением некоторого вопроса, такого как
обход препятствия, возникшего на вашем пути, вы попытаетесь избежать
встречи с ним, двигаясь направо или налево. Если все варианты равны между
собой и одинаково возможны, решение, скорее, случайно и, следовательно,
является "неявным решением". Если бы кто-нибудь спросил вас, например,
почему вы решили обойти столб справа, а не слева, то вряд ли вы сумели бы
внятно объяснить мотивы своего поведения. В другом случае мы можем
использовать случайные переменные для выбора направления движения нашей
маленькой "Мухи". Алгоритм 13.5 создает маленькую точку, которой теперь
полагается летать, двигаясь в случайном направлении.

Алгоритм 13.5. Случайное передвижение.
while (идет игра)
       {
       ... код программы
     
       if (перемещение точки по текущей траектории закончено) then
          {
          выбор новой траектории, иными словами,
                      выбираем новый фактор преобразования координат
    }
   двигаем точку несколько раз по новой траектории
... код программы
    }

Алгоритм 13.5 моделирует "грубый разум", который выбирает направление
дальнейшего движения случайным образом. Напишем программу, которая создает
одиноко летящую точку в пространстве с помощью этого алгоритма. Посмотрим,
как это работает, на примере программы из Листинга 13.3.

Листинг 13.3. Одинокая муха. (DFLY.C).
// I N C L U D E S////////////////////////////////////////////////////////////

#include 
#include 
#include 

// G L O B A L S /////////////////////////////////////////////////////////////

unsigned int far *clock = (unsigned int far *)0x0000046C; // pointer to internal
                                                          // 18.2 clicks/sec


//////////////////////////////////////////////////////////////////////////////

Timer(int clicks)
{
// this function uses the internal time keeper timer i.e. the one that goes
// at 18.2 clicks/sec to to a time delay.  You can find a 32 bit value of
// this timer at 0000:046Ch

unsigned int now;

// get current time

now = *clock;

// wait till time has gone past current time plus the amount we eanted to
// wait.  Note each click is approx. 55 milliseconds.

while(abs(*clock - now) 319) ex=0;
     if (ex199) ey=0;
     if (ey

Думаю, после запуска программы вы согласитесь с тем, что мы, наконец,
получили все необходимое для моделирования летающего "разумного существа".
Несколько простых правил, шаблоны и случайные числа помогли нам создать
довольно правдоподобную имитацию полета насекомого. Это просто чудесно!
Теперь настало время поговорить о конечных автоматах.

КОНЕЧНЫЕ АВТОМАТЫ
   
Конечные автоматы (КА) - близкие друзья самых разнообразных механизмов. Они
царствуют в виртуальном пространстве компьютеров. КА используются в
разработке аппаратного и программного обеспечения. Поскольку мы коснулись
этой темы, скажу, что КА - это программно моделируемая машина, которая
движется от состояния к состоянию, основываясь на входных данных. Кроме
того, КА обычно запоминает все состояния, в которых он побывал. Посмотрите
на рис 13.3, на котором изображена диаграмма простейшего КА. (Что именно
этот КА делает - не имеет никакого значения).
Как видите, КА имеет набор состояний, представленных кружками и
объединенных дугами переходов от состояния к состоянию. Эти дуги показывают
правила, по которым происходят переходы из одного состояния в другое.
КА могут быть использованы в видеоиграх как один из методов
высокоуровневого управления логикой, с помощью которого передаются команды
"низкоуровневой " логике.
Так же, как наш мозг имееткору, передающую наши желания в более
низкоуровневые моторные доли мозга,КА может быть использован для инициации,
управления и перехвата низкоуровневых действий, выполняемых имитатором
мозга. 
Как пример мы могли бы использовать все, что нам уже известно о
преследовании, уклонении, шаблонах и случайных передвижениях для
конструирования КА,




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

   Конечный автомат, управляемый окружающей средой
Теперь наступает приятная часть. Мы можем создать КА, в котором состояния
перехода представлены рядом переменных. Другими словами, мы управляем
конечным автоматом с помощью самой игровой среды, в которой он находится,
так же, как наш собственный мозг реагирует на окружающую обстановку.
Начнем создавать КА с того, что он будет случайным образом выбирать одно из
нижеперечисленных состояний:
- преследование;
- уклонение;
- случайное; 
- шаблон. 
  Но в настоящей игре для управления состоянием КА вместо случайных чисел
было бы лучше привлечь саму игровую ситуацию. Ниже приведен пример КА,
дейтвующего по обстоятельствам:
  - Если игрок близко, КА переключается в состояние Шаблон;
  - Если игрок далеко, можно заставить ПК охотиться за ним, используя
    состояние Преследование;
  - Если игрок обрушил на наше маленькое создание шквальный огонь, КА
    моментально переходит в состояние Уклонение;
  - Наконец, при любой иной ситуации КА отрабатывает состояние Случайное.

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

Листинг 13.4. Умная "Муха" (BFLY.C).
// I N C L U D E S////////////////////////////////////////////////////////////

#include 
#include 
#include 

// D E F I N E S ////////////////////////////////////////////////////////////

#define STATE_CHASE   1
#define STATE_RANDOM  2
#define STATE_EVADE   3
#define STATE_PATTERN 4

// G L O B A L S /////////////////////////////////////////////////////////////

unsigned int far *clock = (unsigned int far *)0x0000046C; // pointer to internal
                                                          // 18.2 clicks/sec


// the x and y components of the patterns that will be played, I just made
// them up

int patterns_x[3][20]= { 1,1,1,1,1,2,2,-1,-2,-3,-1,0,0,1,2,2,-2,-2,-1,0,
                         0,0,1,2,3,4,5,4,3,2,1,3,3,3,3,2,1,-2,-2,-1,
                         0,-1,-2,-3,-3,-2,-2,0,0,0,0,0,0,1,0,0,0,1,0,1 };



int patterns_y[3][20] = { 0,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,0,2,2,2,2,2,2,
                          1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,0,0,0,0,
                          1,1,1,2,2,-1,-1,-1,-2,-2,-1,-1,0,0,0,1,1,1,1,1 };


//////////////////////////////////////////////////////////////////////////////

Timer(int clicks)
{
// this function uses the internal time keeper timer i.e. the one that goes
// at 18.2 clicks/sec to to a time delay.  You can find a 32 bit value of
// this timer at 0000:046Ch

unsigned int now;

// get current time

now = *clock;

// wait till time has gone past current time plus the amount we eanted to
// wait.  Note each click is approx. 55 milliseconds.

while(abs(*clock - now)  ex) ex++;
                if (px  ey) ey++;
                if (py  ex) ex--;
                if (px  ey) ey--;
                if (py  5 && distance  25 && distance  30 && rand()%2==1)
                 {
                 clicks=10;
                 fly_state = STATE_RANDOM;

                 curr_xv = -5 + rand()%10; // -5 to +5
                 curr_yv = -5 + rand()%10; // -5 to +5

                 } // end if random
              else
                 {
                 clicks=5;
                 fly_state = STATE_RANDOM;

                 curr_xv = -5 + rand()%10; // -5 to +5
                 curr_yv = -5 + rand()%10; // -5 to +5

                 } // end else

              // reset need another state flag

              select_state=0;

              } // end if we need to change to another state

     // make sure fly stays on paper

     if (ex>319) ex=0;
     if (ex199) ey=0;
     if (ey
 
Запустив программу, вы наверняка обратите внимание на кажущуюся сложность
поведения "Мухи". А ведь для получения такого результата использована
весьма простая схема! Возможно, и вы заметите то, что увидел я - чуть ли не
человеческую способность мыслить.

  
Управление приоритетным состоянием
Можно еще усовершенствовать наш КА, если ввести управление сменой состояний
с помощью некоторых переменных и функций. На практике это означает
возможность изменения текущего режима, не дожидаясь полного завершения
программы, отвечающей за его выполнение.
В имитаторе движения "Мухи" каждое состояние выполнялось до полного
завершения. Но если включить в программу проверку выполнения или
невыполнения некоторых условий, это позволило бы КА "выпрыгнуть" из
состояния, не дожидаясь окончания его "отработки".
Этим заканчивается наш разговор о конечных автоматах, которые могут быть
использованы в наших играх для моделирования поведения существ и придания
им видимости наличия интеллекта. Теперь к имеющейся у нас системе
высокоуровневого управления не помешает добавить низкоуровневое
функционирование.

   
 Вероятностные автоматы
Наверное, вы уже поняли, как вероятность и случайные числа могут быть
использованы для выбора направлений и состояний. Мы научились использовать
случайные поледовательности для конструирования "характера" персонажей. Я
имею в виду, что "Муха" в нашем предыдущем примере могла самостоятельно
выбирать различные состояния, основываясь на окружающей обстановке. Если
несколько изменить метод выбора состояний, основанный на
генерации случайных чисел (то есть, создавать условия, при которых вход в
определенное состояние стал бы легче или тяжелее), то, в конечном счете,
нам удалось бы изменить "характер" "Мухи".
Скажем, нам захотелось иметь в игре две "мухи". Если одну и ту же программу
использовать для создания траектории движения каждой "мухи", они бы
действовали одинаково. Во многих случаях большего и не требуется. Однако
гораздо интересней иметь много "мух" с небольшими различиями в поведении.
Это можно было бы реализовать изменением диапазона случайных чисел во всех
строках программы, где выбираются состояния "мухи". Но такой подход будет
очень грубым. Мы пойдем другим путем - путем создания общего метода
управления характером персонажей, основанного на вероятности.
В искусственном интеллекте "индивидуальность" означает возможность существ
по-разному выполнять определенные действия при одних и тех же
обстоятельствах. Например, у меня есть несколько достаточно активных
друзей, которые захотели бы слегка проучить плута, попытавшегося их надуть.
Но у меня также есть друзья, которые более спокойны и предпочитают сначала
думать, а потом действовать. Скорее всего, мошеннику удалось бы как-то с
ними договориться. То, что мы видим на данном примере, и является
"индивидуальностью".
Каким именно способом это будет достигнуто, не принципиально, важен
конечный результат.
В видеоиграх мы могли бы иметь несколько противников, которые постоянно
преследуют нас, пока другие в это время неподвижны и стреляют. Третьи
трусливы и предпочитают убегать, а не сражаться. Анализируя ситуацию, мы
видим, что имеется все тот же набор состояний, но вероятности перехода в
них различны для каждого состояния. Для моделирования этого процесса мы
могли бы сослаться на "таблицу вероятностей" в той части программы, которая
выбирает новое состояние. Эта таблица могла бы содержать различные степени
вероятности переходов существ в то или иное состояние. К примеру, взгляните
на табл.13.1, в которой перечислены соотношения вероятностей для трех
различных существ в одной игре.

Таблица 13.1. Распределение вероятностей для трех существ в игре.
     Состояние          Существо1: Аннигилятор
    
     (А)Атака           50%
     (П)Преследование   5%
     (С)Случайное       10%
     (Р)Роение          20%
     (Ш)Шаблон          15%
                              - 532 -
      Состояние         Существо 2: Умник
      
      (А)Атака          20%
      (П)Преследование  30%
      (С)Случайное      20%
      (Р)Роение         20%
      (Ш)Шаблон         10%
      
      Состояние         Существо 3: Хныкалка
      
      (А)Атака          5%
      (П)Преследование  60%
      (С)Случайное      20%
      (Р)Роение         10%
      (Ш)Шаблон         5%



Как вы можете судить по распределению вероятностей, Аннигилятор
преимущественно атакует, Хныкалка предпочитает преследование, а Умник -
что-то среднее между ними. Прежде чем перейти к разговору о реализации
вероятностей, я хочу поговорить еще об одном принципе поведения игровых
объектов - о роении. Роение означает, что создания в игре сбиваются в кучи
и пытаются как-то сгруппироваться. Это похоже на то, как настоящие солдаты
или насекомые иногда стремятся собраться вместе и остаться рядом друг с
другом.
В действительности, это не что иное, как выбор общей точки встречи и
целеустремленное движение к ней. Мы можем использовать такой тип поведения
как совершенно новое состояние, при котором создания кажутся
группирующимися.
Моделирование этого состояния не очень сложно:
  - Выбрать существа, которые вы хотите сгруппировать вместе;
  - Выбрать среднюю относительно всех созданий позицию. Эта точка в 
    пространстве является центром и может быть использована для вычисления
    траекторий движения всех объектов, которые следуют к ней;
  - Вычислить траекторию так, чтобы каждое создание следовало к центру.
  
  
  В состояние роения имеет смысл переходить, когда слишком много
противников вдруг начинают одновременно изрыгать огонь, торпеды и прочие
средства уничтожения. Наверное, логичнее всего объединять существ по типам.


Теперь перейдем к тому, как мы могли бы составить справочные таблицы
вероятностей
У нас есть высокоуровневое управление состоянием, которое инициирует новые
состояния, основываясь на состоянии окружающей среды и вероятности. Это
новое состояние является "задействованным вовне" с помощью низкоуровневого
управления состоянием, которое, в конечном итоге, является аналогом
моторной доли человеческого мозга. Теперь мы двигаемся к тому, чтобы
добавить еще один уровень к "мозгу". Этот новый уровень принимает во
внимание и состояние окружающей среды, и распределение вероятности.
Отдельное распределение вероятности может существовать для каждого
создания, так что мы можем получить много разных "личностей" с одной и той
же общей  архитектурой "двигательного центра". Существуют миллиарды путей
составления справочных таблиц вероятности. Вам нужно перечислить все
состояния, которые есть в игре. К примеру, будем использовать те, которые
мы уже имеем. Вот они:
        - Преследование;
        - Уклонение;
        - Случайное;
        - Шаблон;
        - Роение;
        - Неподвижность.
Я добавил еще состояние "неподвижности", под которым подразумеваю полное
бездействие противника. Это состояние может показаться не интересным, но в
результате враг выглядит так, будто он думает, или поджидает игрока, чтобы
сделать выпад. Это создает в игре некоторое напряжение и беспокойство.
Нам необходимо определить переменные состояния окружающей среды, которые
управляют нашими решениями. С этой целью можно задать две переменные:
   - Дистанция до игрока;
   - Состояние и вооружение игрока: стреляет или нет.
   
   Теперь можно построить таблицы вероятностей. Чтобы сделать это, заполним
массивы цифрами от 1 до 6, которые представляют различные состояния.
У нас получится таблица из 20 элементов. Для выбора состояния
проиндексируем таблицу случайными числами от 0 до 19. Конечно, когда мы
выбираем случайное число таким способом, как показано здесь:

sel = rand()%20

числа от 0 до 19 получаются равноценными. Возникает вопрос, как сделать
так, чтобы переключение в то или иное состояние происходило чаще или реже?
Иначе, что вам делать, чтобы заполнить таблицу тем распределением
вероятностей, которое вы желаете. К примеру, ести вы хотите получить 50%
преследования, вам необходимо поместить в таблицу 10 единиц. Если роение
должно составлять 20%, то вам необходимо занести в таблицу четыре пятерки.
Начало вашей таблицы выглядело бы примерно так:

int table_1 [20] = {1,1,1,1,1,1,1,1,1,1,5,5,5,5,...
                                 остальные_состояния}

С точки зрения математики мы используем переменную, которая имеет равное
распределение вероятности от 0 до 19, чтобы переиндексировать таблицу,
которая представляет собой функцию плотности вероятности, где элемент
индексирует следующее состояние. 
Я надеюсь, что вы понимаете, о чем идет речь, но даже если нет, то поверьте
мне - все, о чем мы говорим, довольно круто! Теперь, когда вы видите форму
справочных таблиц, мы можем поговорить насчет выбора состояний. Как вы
видели в программе "Умная муха" (Листинг 13.4), дистанция до игрока и
случайные числа были использованы для выбора следующего состояния. Мы
подошли к тому, чтобы сделать для этого же значительно больше. Мы будем
учитывать как дистанцию, так и вооружение игрока для выбора одной из двух
плотностей вероятности: она используется, когда противники далеко, а другая
- когда они близко.
При таком подходе всеми врагами используется только одна модель
"характера", но, внося разнообразие в "индивидуальность" противников, мы
без особых дополнительных затрат заметно обогатим игру. Такой алгоритм
показан ниже.

Алгоритм 13.6. Использование плотности вероятностей в выборе состояния.
table_1 = {1,1,1,2,2,3,3,4,4,4,4,4,5,5,5,5,6,6,6,6};
table_2 = {1,1,2,2,2,2,3,3,3,3,3,3,4,4,5,5,5,5,5,6};

while  (идет игра)
       {
       
       ... код программы
       
       if (выполняются команды одного из состояний)
           {
           ...продолжать их выполнение
           }
      else  // Выбираем новое состояние
         {
       if (расстояние между игроком и противником > 100)
               {
               новое состояние=table_1[rand()%20];
               }
          else
              {
              if (расстояние 
Возможно, некоторые действия ваших созданий, реализующих Алгоритм 13.6,
будут выглядеть жутковато, но я гарантирую, что скучно не будет.
Если вы увеличите размеры таблиц вероятностей, то у вас появится
возможность получить вполне приличный результат. Далее, вы можете добавить
еще несколько операторов IF, усложнить окружающую среду и, наконец,
увеличить количество таблиц для достижения большего разнообразия в
характерах персонажей вашей игры.
Во всяком случае, пойдем дальше. В следующих разделах мы будем говорить о
том, что является частью, как я говорю, "эзотерической коллекции". Это
довольно интересно, хотя и совершенно не используются в играх сегодняшнего
дня. Быть может, игры завтрашнего дня опять вернутся к этой концепции.


 ПАМЯТЬ И ОБУЧЕНИЕ
  
Если бы мне было нужно определить термины "память" и "обучение", я вероятно
сказал бы, что они являются способностью использовать прошлый опыт для
решения новых проблем вместе со способностью накапливать и интерпретировать
новую информацию.
Вполне возможно наделить создания в наших играх способностью "учиться" и
"запоминать", хотя и в достаточно грубой форме. Все, что нам необходимо
сделать, это ввести несколько переменных и использовать их при выборе
состояния и в моторных функциях.
К примеру, мы могли бы позволить каждому существу в нашей игре иметь
внутреннюю карту игрового пространства. Если бы существо, войдя в комнату,
обнаружило там кучу смертельных врагов, то в следующий раз, когда оно
входит в комнату, мы могли бы увеличить его агрессивность. Другой пример:
если во время боя игрок двигался влево и потом стрелял, игровые существа
могли бы запомнить это путем интерполяции траектории игрока в определенном
направлении. Любые действия, которые игрок чаще всего предпринимает, могут
быть использованы против него, если наделить игровые существа способностью
использования этой информации для усовершенствования собственной тактики.
Это только несколько примеров, для чего могут быть использованы память и
обучение. Вообще, вполне можно научить игру запоминать информацию о вас в
том же объеме, в котором вы запоминаете информацию об игре, а затем
использовать накопленный опыт против игрока, хотя это и несколько
напоминает самоубийство.


 
 АЛГОРИТМЫ ПОИСКА. ВЫСЛЕЖИВАНИЕ ИГРОКА
   
"Мозги", которые мы сконструировали, получились достаточно умными, так что
существо даже получило шанс выжить. И теперь я хочу поговорить о другой
довольно простой вещи - как должен быть организован поиск.
Вспомним теорию Тезея с Минотавром. Жил когда-то давным-давно Минотавр
(человек с головой быка), который преследовал Тезея. В общем, Тезей украл у
Минотавра ... не помню точно - CD-ROM, или что-то там еще ... Тезей попал в
ловушку (в действительности, подрядчик, построивший ее, называл ее
лабиринтом), но успел выбраться наружу прежде, чем Минотавр его настиг.
Вопрос состоит в том, как нужно двигаться по лабиринту, чтобы найти путь к
выходу или любой произвольной точке лабиринта, и при этом не застрять в нем
навсегда? Давайте взглянем на рис.13.8, где изображен пример лабиринта.
Существует простой алгоритм, обозначенный здесь как Алгоритм 13.7, который
поможет вам найти выход из любого лабиринта. Будьте внимательны, в один
прекрасный момент он может вам сильно пригодиться!

Алгоритм 13.7. Путь наружу.
do
   {
   двигайтесь вдоль правой стены
   если встретился проход, поверните направо
   если попали в тупик, развернитесь на 180 градусов
   } пока не выйдете из лабиринта
                              
                              
                              
                              
                              

Этот алгоритм работает безупречно: попробуйте его у себя дома. Стартуйте из
любого угла вашей квартиры и следуйте алгоритму. Возможно, при известных
обстоятельствах вы даже найдете путь к каждой двери.
Так как нас интересуют видеоигры, попытаемся использовать этот алгоритм,
чтобы помочь созданиям в игре выследить игрока, не тыкаясь в стены (если
мы, конечно, не хотим обманывать игрока, позволив созданиям
беспрепятственно проходить сквозь стены). Использование этого алгоритма
может привести к затруднениям, если надо обходить объекты круглой формы.
Однако, мы можем или избегать такой ситуации, или добавить в программу
дополнительный алгоритм для предотвращения ходьбы по кругу.


  
 ТЕОРИЯ ИГР
Следующая тема не слишком тесно связана с видеоиграми, а, скорее, относится
к стратегическим играм типа шахмат. Тем не менее, я хочу осветить ее, чтобы
сообщить вам некоторые интересные идеи.
Теория игр является разделом математики, слишком трудным и слишком
абстрактным, для того чтобы применять ее в видеоиграх. Она оперирует
набором правил для вычисления оптимального решения или алгоритма,
позволяющего игроку победить. Обычно это делается с помощью множества
матриц, вероятностей и линейного программирования. Тем не менее, мы можем
извлечь из теории игр немало полезного.
Как правило, требуется решить проблему путем оценки текущего положения или
игровой ситуации, подразумевая, что игрок точно оценивает свои действия в
данной точке в данный момент времени и далее старается улучшить свою
позицию. Чтобы выполнить это на компьютере, нам надо:
   - Во-первых, мы создаем несколько видов целевых функций, которые могли
     бы оценивать нашу текущую позицию;
   - Далее мы пробуем применить новую тактику или изменить позицию с тем,
     чтобы посмотреть, улучшит ли это наше положение;
   - Если это достигается, мы выполняем это действие;
   - Если нет, испытываем следующую тактику.
   
Именно по такой схеме работают шахматные программы. Компьютер постоянно
ведет подсчет своих собственных очков и очков противника, зависящих от
текущего расположения фигур, и пытается найти наиболее оптимальный ход.
Этот "мыслительный процесс" может в действительности идти на многих
уровнях. Компьютер будет проверять каждую из возможностей: если я слелаю
так, то мой противник мог бы предпринять то-то..., а если я поступлю эдак,
соперник сделает следующее... Так может продолжаться до бесконечности, хотя
человек может проиграть даже в том случае, если компьютер будет делать
только два шага "проверка-действие".
В видеоиграх эта тактика может быть использована как самое высокоуровневое
управление всеми остальными функциями. К примеру, каждую минуту или около
этого, компьютер мог бы просчитывать ходы и оценивать, как он действует.
Если все его ходы удачны, он мог бы действовать так и дальше. Однако, если
какая-то попытка оказалась неудачной, значит, пришло время для пересмотра
тактики.


   ИТОГ
В этой главе мы затронули массу интересных тем и даже создали небольшой
"мозг", способный имитировать многие функции, присущие живым объектам.
Используя комбинации различных алгоритмов, описанных в этой главе, вы
сможете создать "виртуальный мозг" достаточно мощный для того, чтобы ваши
создания смогли бороться за выживание. Однако, я хочу вам дать пару
советов:
  - Старайтесь не усложнять "мозг" без необходимости;
  - Не пытайтесь сразу создать суперкомпьютер. Вначале пусть ваше простое
    произведение будет больше похоже на "Денди".
    
Мы обсудили большинство методов управления поведением, применяемых в
сегодняшних видеоиграх. Если вы смогли в них разобраться, вы сможете
создавать игры не хуже, а то и лучше чем те, которые существуют сегодня.
Индустрия компьютерных игр движется семимильными шагами по пути улучшения
графических и звуковых возможностей, часто забывая о такой маленькой детали
как интеллект. К счастью, теперь вы имеете возможность привнести "мозги" и
стратегию в следующее поколение компьютерных игр. 

Оставить комментарий

Комментарий: можно использовать BB-коды Максимальная длина комментария - 4000 символов.	CodeNet ВКонтакте Facebook Twitter Google Яндекс Чтобы оставить комментарий, необходимо авторизоваться. Можно ввести логин и пароль, или авторизоваться через социальные сети.

Комментарии