Способы передвижения компьютерных персонажей (Часть 1)

Введение

Все, кто начинал заниматься реализацией игрового искусственного интеллекта, наверняка сталкивались с проблемой реализации движений своих персонажей. Дело в том, что поведение и в реальном мире в большей степени определяет интеллектуальность того или иного существа. Даже люди друг друга зачастую оценивают по поведению (что немного неверно). Эта статья рассчитана на тех, кто только приступает к реализации своего первого игрового ИИ. Я расскажу о видах перемещений, их преимуществах и недостатках, а также покажу на примере как можно реализовать тот или иной способ на языке C++. Замечания и критика, а так же свои точки зрения приветствуются.

Способы перемещений

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

1. Отдельный объект. Наиболее часто встречающийся способ реализации, когда движущийся объект является представителем отдельного класса(Mob), а на уровне они хранятся в массиве этого класса (Mobs[]). Чаще всего используют динамические массивы. Таким образом, доступ к конкретному мобу обеспечивается обращением к элементу массива (Mobs[15].DoSomething). Это весьма удобно, хотя при очень больших значениях массива возникают трудности в просчетах взаимодействий объектов друг с другом, и требуется дополнительная оптимизация этого просчета.
2. Объект может быть состоянием мира. Например, если создать двумерный массив значений (bool Map[][]), то наличие или отсутствие в этой клетке объекта может задаваться состоянием ячейки массива (если в клетке 15,10 есть объект, то Map[15][10] = true). По такому принципу реализована игра «Life».
3. Можно применять смешанные способы. Когда массив отдельных объектов дублируется двумерным массивом на карте, куда может заноситься не только маркер наличия или отсутствия персонажа в клетке, но и его id или указатель, чтобы можно было легко к нему обратиться в общем массиве.

Виды перемещений

1. Плиточный. Весь мир представляет собой двумерный массив клеток, и перемещение осуществляется строго по ним. Пример – игра шахматы, шашки, и т.д.
2. Векторный. Перемещение осуществляется по какому-то вектору, и может быть направлена в любую сторону и под любым углом (кроме случая с препятствиями).
3. Смешанный. Совместное использование плиточного и векторного способов.

Способы перемещений

1. Ситуативный. У персонажа есть текущее направление движения, и оно постоянно до тех пор, пока он не столкнется с чем-либо, что изменит его состояние, а значит и направление. Он просто реагирует на внешние и внутренние воздействия изменением поведения.
2. Целевой. Здесь есть план или маршрут действий, которому следует персонаж.
3. Смешанный. Ясно из названия – имея общий план и следуя ему, объект может реагировать ситуативно, если столкнется с неожиданной преградой, и после ее устранения возвращается к своему плану.

Плиточные перемещения

Плиточный способ, как я уже писал ранее, это когда весь мир разделен на клетки одинакового размера и все движения осуществляются строго по этим клеткам. Наиболее часто используются квадраты и шестиугольники. Он применяется в стратегиях (особенно пошаговых), RPG и т.д.
Реализовать такой способ перемещения достаточно просто. Делаем класс «клетка» (class Cell), создаем двумерный массив этих «клеток» нужного размера (Cell Map[width][height]). Дальше генерируем карту, присваивая клеткам определенные параметры. Создаем класс «моб» (class Mob) и динамический массив всех живых существ нашего мира (vector Mobs). Вот исходный код заготовки для нашего плиточного ИИ:

class Cell {    bool Free;//проходима ли клетка    //можно добавить тип клетки 0-препятствие, 1-трава, 2-песок,...    int Type;    //и стоимость прохождения по клетке    int Cost; }; Cell Map[20][20];//массив клеток на карте class Mob { … }; vector<Mob> Mobs;//динамический массив всех мобов

Теперь надо заняться нашими мобами. Как уже упоминалось, перемещение можно реализовать двумя основными формами – ситуативной и целевой.
При ситуативной, должно быть какое то направление или действие, которое будет выполняться в текущий момент. Весь интеллект направлен на то, чтобы в ответ на внешние или внутренние воздействия изменить это текущее действие, на более оптимальное. Это можно сделать нейронными сетями, простым условным алгоритмом и т.д. В любом случае у моба есть органы чувств (например «видение» на несколько клеток вперед) и набор действий («повернуться влево, повернуться вправо, сделать шаг» или «шаг влево, шаг вправо, шаг вперед, шаг назад»). Его «мозг» реагирует на данные от органов чувств, выдавая соответствующее поведение.
Вот примерный исходный код, реализующий простое плиточное движение. Наш моб идет по прямой до тех пор, пока не упрется в стенку, тогда он поворачивается в случайную сторону и продолжает движение:

const int CellSize = 10;//размер клетки class Cell { public:     bool Free;//проходима ли клетка };  Cell Map[20][20];//массив всех клеток карты  class Mob { public:     int Direction;//направление движения: 0-влево, 1-вверх, 2-вправо, 3-вниз     int X, Y;//координаты в пикселях          void ChangeDirection();//изменение направления     bool TestStep();//если можно двигаться дальше возвращает true     void Move();//само движение в текущем направлении };  void Mob::ChangeDirection() { //изменение направления     int Random = rand()%2;//случайное число от 0 до 1     if(Random==0){         Direction++;         if(Direction>3) Direction = 0;//проверяем выход за пределы допустимых значений         }     else {         Direction--;         if(Direction<0) Direction = 3;//проверяем выход за пределы допустимых значений         } }  bool Mob::TestStep() {//если можно двигаться дальше возвращает true     int _x = int(X/CellSize);//вычисление координаты в массиве     int _y = int(Y/CellSize);     switch(Direction) {         case 0: return Map[_x-1][_y].Free; break;         case 1: return Map[_x][_y-1].Free; break;         case 2: return Map[_x+1][_y].Free; break;         case 3: return Map[_x][_y+1].Free; break;         } }  void Mob::Move(){//само движение вперед     switch(Direction) {         case 0: if(TestStep()==true) X-=CellSize; else ChangeDirection();//если можно двигаться вперед - двигаемся         case 1: if(TestStep()==true) Y-=CellSize; else ChangeDirection();//если нет - изменяем направление движения         case 2: if(TestStep()==true) X+=CellSize; else ChangeDirection();         case 3: if(TestStep()==true) Y+=CellSize; else ChangeDirection();         } } vector<Mob> Mobs;//динамический массив мобов  for(int i=0;i<Mobs.size();i++) Mobs.at(i).Move();//перемещение всех мобов в массиве

И хотя код не самый лучший, он достаточно показателен для лучшего понимания алгоритма перемещения.

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

class Mob { public:     int Direction;//направление движения: 0-влево, 1-вверх, 2-вправо, 3-вниз     int X, Y;//координаты в пикселях     int Steps;//кол-во сделанных шагов персонажем      vector<int> Path;//массив пути, в нем хранятся значения Direction для всего пути          void ChangeDirection();//изменение направления     bool TestStep();//если можно двигаться дальше возвращает true     void Move();//само движение в текущем направлении      void PathStep();//шаг по намеченному пути };  void Mob::PathStep() {//шаг по намеченному пути     switch(Path.at(Steps)) {//значение направления берется из массива пути         case 0: if(TestStep()==true) X-=CellSize; else ChangeDirection();//если можно двигаться вперед - двигаемся         case 1: if(TestStep()==true) Y-=CellSize; else ChangeDirection();//если нет - изменяем направление движения         case 2: if(TestStep()==true) X+=CellSize; else ChangeDirection();         case 3: if(TestStep()==true) Y+=CellSize; else ChangeDirection();         }         Steps++;//увеличиваем кол-во сделанных шагов }  for(int i=0;i<Mobs.size();i++) Mobs.at(i).PathStep();//перемещение по шаблону всех мобов в массиве

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

• 1. Легкость в реализации
• 2. Меньшее кол-во просчетов
• 3. Легко получить информацию об окружающем мире

Основные недостатки:

• 1. Невозможность реализации реалистичной физики
• 2. Достаточно синтетические, неестественные, движения

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