Пользователь
0,0
рейтинг
1 января 2013 в 16:00

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

Все, кто начинал заниматься реализацией игрового искусственного интеллекта, наверняка сталкивались с проблемой реализации движений своих персонажей. Дело в том, что поведение и в реальном мире в большей степени определяет интеллектуальность того или иного существа. Даже люди друг друга зачастую оценивают по поведению (что немного неверно). Эта статья рассчитана на тех, кто только приступает к реализации своего первого игрового ИИ. Я расскажу о видах перемещений, их преимуществах и недостатках, а также покажу на примере как можно реализовать тот или иной способ на языке 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. Достаточно синтетические, неестественные, движения


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

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (14)

  • +2
    Спасибо, хорошая статья для новичков, с конкретными примерами. С нетерпением жду следующей части.
    • 0
      Спасибо, приятно слышать.
  • 0
    Спасибо. Как раз искал подобный материал.
    Но хочется вариантат с физикой. Подкинете литературу или поделитесь примерами?
    • 0
      Вариант с физикой, возможно, будет в качестве примера в следующей статье. Если не терпится, можете почитать книгу Д. Конгера — Физика для разработчиков компьютерных игр, она легко находится в сети (не буду ссылками спамить).
  • +2
    А как же Manhattan distance, Chebyshev distance, полярные координаты для расчетов?
    • 0
      Я осветил только те способы, что находил в доступной мне литературе. Спасибо за наводку, поищу то, что вы указали.
    • 0
      По вашей наводке я покопался в литературе и вот что выяснил:
      Manhattan distance — это кратчайший путь между двумя точками на клеточном пространстве, по сути является суммой горизонтальной и вертикальной траектории (например «двигаться вправо пока не сравняемся с X цели, потом двигаемся вверх пока не сровняемся с Y координатой»)
      Chebyshev distance — это также кратчайший путь, символично изображенный как количество шагов, необходимых шахматному королю, чтобы дойти до цели (возможны и диагональные ходы)
      Все это относится к способу поиска пути, но не его реализации. Пути, найденные этими способами, можно поместить в массив, и двигаться по ним как я и описал ранее.
      Полярные координаты трудно применимы в плиточном мире, а о векторном способе перемещения я еще не говорил.
      • 0
        А разве полярные не ложатся хорошо на шестиугольники?
        • 0
          Не знаком с этим. Расскажите подробнее, или ссылку на использование полярных координат в гексагональном мире.
          • 0
            Не могу ничего сказать, ибо это мое предположение. Дело в том, что считать расстояния в клетках и направлениях проще, чем как-то проецировать это в декартову систему.
        • +1
          Нет, не ложатся. Для гексагональных карт есть целая куча методов адеесации, но я ни разу не видел, чтобы использовали полярные координаты.
          • 0
            Куча? А названия у них есть?
      • 0
        Если брать за основу идею что передвижение персонажей реализовано с элементами физики, то всегда потребуется обнаружение столкновений. Нахождение минимального расстояния становится важным. Так же если оставить идею одного персонажа, и ему надо пройти от клетки (0,0) к (10^х, 10^x), надо рассчитать кратчайший путь.

        Полярные координаты трудно применимы в плиточном мире, а о векторном способе перемещения я еще не говорил.


        Здесь я с вами соглашусь, можно использовать полярные координаты в плиточном варианте, но не нужно.
  • 0
    Много плюсов и мало комментов — верный признак хорошей статьи. Спасибо.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.