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

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

Перемещение по вектору, один из способов реализации движения. Мир уже не разделен на клетки, и предоставляет куда больше свободы для передвижений. Координаты могут задаваться с большой точностью (не только целые, но и float значения), что позволяет реализовывать весьма реалистичные движения. Вектор – это направление, в котором будет осуществляться движение нашего агента. Проще всего его можно задать двумя значениями, например V(10,5). Это значит что при перемещении точки, находящейся в координате A(1,1) по вектору V(10,5) положение объекта будет находиться в A+V = C(1+10,1+5) = C(11,6). Значения вектора могут быть также отрицательными.

Для изменения направления движения достаточно сложить текущий вектор с новым. Например, имея вектор V1(2,6) мы хотим изменить его, прибавив вектор V2(3,-3), новый вектор движения будет V1+V2 = V3(2+3),6+(-3)) = V3(5,3). Графически это можно изобразить следующим образом:

Вернемся к передвижениям по вектору. Как уже говорил, чтобы переместить объект на определенный вектор, нужно сложить координаты объекта со значениями вектора: Pos(x,y)+V(a,b) = NewPos(x+a,y+b). Чем больше вектор – тем дальше переместиться наш объект. Это может создавать ряд трудностей, связанных с «проскакиванием» препятствий. Имея достаточно большой шаг, объект запросто может пропустить мелкие объекты. Существует много разных способов устранения этого недостатка, но они не входят в рамки статьи.

Все же такой подход вполне может иметь право на существование, и приведу пример реализации движения объекта по вектору. Сделаем класс вектор – содержащий два значения. И класс моб, который будет двигаться по заданному вектору. Для изменения вектора движения создадим функцию, куда будем помещать новый вектор.
class Vector {
public:
    float x, y;
};

class Mob {
public:
    float x,y;//координаты float, так как движения более точные
    Vector Way;//вектор движения
    
    void AddVector(Vector NewWay);
    void Move();
};

void Mob::AddVector(Vector NewWay) {//добавляем новый вектор
    Way.x+=NewWay.x;//прибавление нового вектора
    Way.y+=NewWay.y;
}

void Mob::Move() {//функция перемещения по вектору
    x+=Way.x;
    y+=Way.y;
}

В некоторых случаях вектор только указывает направление, а скорость задается дополнительной переменной. Тогда прибавлять вектор к координатам нельзя, да и сам вектор должен быть нормализованным, то есть длинной равной единице. Зададим, для примера, направление движения единичным вектором, а скорость будет лишь множителем, увеличивающим длину вектора. Чтобы добавить новый вектор к имеющемуся нужно проделать ряд шагов:
  1. Перевести вектор в ненормализованный вид (умножить значения вектора на скорость).
  2. То же сделать с новым вектором, если это не было сделано ранее.
  3. Сложить векторы обычным способом.
  4. Вычислить длину получившегося вектора – это наша новая скорость.
  5. Нормализовать вектор.

В таком случае наш класс и функции добавления вектора и движения приобретают вид:
class Mob {
public:
    float x,y;//координаты float, так как движения более точные
    float Speed;
    Vector Way;//вектор движения
    
    void Normalize();
    void AddVector(Vector NewWay);
    void Move();
};

void Mob::Normalize() {
    Speed = sqrt(Way.x*Way.x + Way.y*Way.y);//вычислили длину вектора
    Way.x *= 1/Speed;//нормализуем вектор
    Way.y *= 1/Speed;
}

void Mob::AddVector(Vector NewWay, float NewSpeed) {
    Vector MobVec, NewVec;//создаем временные векторы
    MobVeс.x = Way.x * Speed;//разнормализовали вектор моба
    MobVeс.y = Way.y * Speed;
    NewVec.x = Way.x * NewSpeed;//разнормализовали новый вектор
    NewVec.y = Way.y * NewSpeed;
    Way.x = MobVeс.x + NewVec.x;//сложили векторы
    Way.y = MobVeс.y + NewVec.y;//сохранили не нормализованный вектор
    Normalize();//нормализовали вектор
}

void Mob::Move() {//функция перемещения по вектору
    x += Way.x * Speed;
    y += Way.y * Speed;
}

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

Ситуативный способ

У нашего моба есть вектор движения, по которому он будет двигаться до тех пор, пока не столкнется с препятствием. Тогда он изменит его определенным образом и продолжит движение, уже в новом направлении. Это можно реализовать обычными условиями, нейронными сетями и т.д. Просчеты столкновений в векторном мире немного сложнее, чем в плиточном, поэтому опустим их расчеты. Предположим, что есть некая функция, которая говорит нам, есть впереди препятствие или нет (bool CanMove()). В таком случае набором действий нашего моба может быть прибавление вектора, поворачивающего его в какую-нибудь сторону от препятствия, со скоростью, пропорциональной расстоянию до преграды (float DistanceToBarrier()). Функция движения приобретет вид:
void Mob::Move() {
    if(CanMove()==true) {//если нет помехи - двигаемся
        x += Way.x * Speed;
        y += Way.y * Speed;
    }
    else {//если есть помеха - поворачиваем
        Vector Turn;//создаем вектор поворота
        Turn.x = 1;//повернем по часовой стрелке
        Turn.y = 0;
        AddVector(Turn, DistanceToBarrier());//добавляем вектор
    }
}

Конечно вектор поворота в моем примере не совсем верный, потому что направления поворота при прибавлении вектора V(1,0) будет зависеть от текущего направления движения. Но суть, я думаю, понятна.

Целевые способы

Для реализации целевых способов используются так же шаблоны (заготовки), ключевые точки (waypoints) и т.д. Шаблоны представляют собой обычный массив векторов, по которым движется наш объект. Но каждый шаг обозначать своим вектором неудобно из-за размеров пути, поэтому используют ключевые точки. Суть заключается в том, чтобы агент двигался по вектору определенное время (до определенной точки), затем сменил направление движения на новый вектор, и так до следующей точки. Добавим массив точек и массив направлений, для удобства будем использовать один и тот же класс Vector.
class Mob {
public:
    float x,y;//координаты float, так как движения более точные
    float Speed;
    Vector Way;//вектор движения
    Vector Points[10];//массив ключевых точек
    Vector PointsVec[10];//массив векторов ключевых точек
    int Position;//к какой точке идем
    
    void Normalize();
    void AddVector(Vector NewWay);
    void Move();
};

void Mob::Move() {
    if(x==Points[Position].x && y==Points[Position].y) {//если мы на месте
        Position++;//переключаем на следующую точку
        Way.x = PointsVec[Position].x;//меняем вектор на новый
        Way.y = PointsVec[Position].y;
    }
    else{//если не пришли - идем дальше
        x += Way.x * Speed;
        y += Way.y * Speed;
    }
}

Векторный способ имеет ряд преимуществ:
  1. Более плавные движения
  2. Естественные движения
  3. Возможность реализовать физику (трение, ускорение, вращения, притяжение, ...)

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


Этот метод достаточно широко используется, особенно там, где необходимо более точно и красиво передать движения. А это большинство современных 3D игр. В следующей, и последней, статье я расскажу о смешанных способах реализации движения, совмещающие как плиточные так и векторные перемещения.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 18

    0
    Как же вы вовремя =) Как раз на каникулах хотел в этой теме разобраться. Спасибо огромное
      0
      А когда следующая? :-)
        0
        Постараюсь сделать к завтрашнему дню, часам 18 00 по Москве.
        +1
        В таком случае набором действий нашего моба может быть прибавление вектора, поворачивающего его в какую-нибудь сторону от препятствия, со скоростью, пропорциональной расстоянию до преграды (float DistanceToBarrier())


        А вот здесь про полярные координаты как раз и надо. Функция atan2(x, y) вам в помощь.
          0
          Спасибо, путние статьи:) Как раз повторю курс геометрии за 10й класс:))
            0
            Маловато!!!.. Маловато будет!!!

            Все примеры рассчитаны на танк который прет прямо без цели, и даже как я понял WayPoint уже не координаты а векторы откланения, но что делать если мы движемся из пункта А в пункт Б? (напомню, что тут как раз вычитание вектора А из Б)
              0
              и вот еще тут (см. «Целевые способы»)

              if(x==Points[Position].x && y==Points[Position].y) {//если мы на месте
              


              если к примеру шаг у нас = 0.3f а до точки дистанция 0.5f то чистого равенства не случится и попрет наш персонаж в бескрайние просторы 3д пространства.
                0
                Код приведен для примера, точность просчета «достижения цели» может задаваться разными способами. В некоторых случаях применима формула, но только если мы двигаемся от меньшего значения к большему:
                if(x<Points[Position].x && y<Points[Position].y)

                Иногда нужно добавить доверительную зону, то есть «мы дошли если наши координаты совпадают с точностью +-ЗОНА»
                if((x>Points[Position].x-ZONE && x<Points[Position].x+ZONE) &&
                   (y>Points[Position].y-ZONE && y<Points[Position].y+ZONE))

                Много вариантов такой оптимизации и устранения потенциальных багов. Я не стал об этом писать, потому что цель статьи создать образное представление о способах передвижения.
                0
                Я специально сделал акцент на этом — суть статей рассказать как заставить двигаться «танк» по уже имеющемуся пути. Вопросы поиска пути, выбора алгоритмов обхода препятствий и т.д. я не брал. Для всех примеров нужно принять одно допущение — танк уже знает куда ему ехать. И тогда примеры покажут как это ему сделать.
                  0
                  Ну тогда нужно было делать акцент на то, что такое вектор вообще а не на сложение векторв, так как молодой юзер будет копипастить сказанное, недочитывать, и что главное делать неправильные выводы. А вы его сразу акунули на поворот на вектор.
                +1
                Первая часть статьи, имхо, совершенно некорректна с т.з. терминологии. Вектор с т.з. математики несет в себе не только направление, но и скорость(модуль вектора). В первой же части статьи речь идет вообще не о векторах, а о банальном передвижении по плоскости используя значения dx, dy. И только ко второй части статьи автор исправляется и приводит терминологию в соответствие с наукой )

                ЗЫ. Ну и вообще статья про движении некоего сферического объекта в вакууме…
                  0
                  Если погрузиться в терминологию, то вы правы. Вектор действительно несет в себе и направление и скорость (длина вектора), и значит вся первая часть статьи как раз правильна по терминологии — ибо там я использовал как раз термин «вектор» в правильном значении. В дальнейшем, с введением дополнительной переменной, вектор потерял свою функцию, оставив за собой лишь право указывать направление (нормализованный вектор), а значит там он стал недо-вектор, с чисто математической точки зрения. Но и это не совсем верно — так как у него все еще осталась длина, которая всегда равна единице (+ в вычислении новой скорости она так же использовалась), только она не используется для задания перемещений. Так что не будем вдаваться в тонкости терминологии — я думаю суть ясна и для понимания способов передвижения этого может быть достаточно.
                    0
                    Да я к тому, что у вас в первой части статьи модуль вектора используется в значении «шаг перемещения объекта», а не в значении «скорость»(или «импульс»). Что может и верно для игрушек типа TowerDefence, где перемещения объектов не учитывают его параметры(массу хотя бы), но не подойдет для физически приближенной к реальности игры. Короче не хватает в начале статьи дисклеймера о том, для какого типа объектов и в какой игровой реальности это все написано. Ибо тут нету ни физики, ни пасфайндинга, ни определения столкновений… только лишь метод складывания координат, когда уже все остальное известно и просчитано. По идее, если человек уже учел физику движений, поиск пути, столкновения, то сложить пару координат ему проблемы не составит?)
                      0
                      Статьи рассчитаны на новичков, которые еще только начинают свой путь реализации первого игрового ИИ. Чтобы они не закончили свою деятельность на первых же минутах кодинга я написал эти статьи. Те, кто уже знает все вышеизложенное, и даже больше, не станут читать, и уж тем более комментировать статьи. Есть множество специальных топиков по поискам пути, реализаций физики и т.д. Там они и проявляют свою активность. Лично я, начиная делать ИИ столкнулся с выбором — «плиточный vs векторный vs смешанный» способ реализации. Может кому-то поможет.
                  0
                  Не могли бы вы показать, где можно прочитать про расчет коллизий, которые случились за промежуток времени t в случае векторного перемещения? А то я даже гуглу не могу сформулировать внятный запрос.

                  Из того, до чего я додумался — только «растяжение» AABB по вектору. (как и куда тянуть — не додумался :) )
                    +1
                    Джоб Макар — Секреты разработки игр в Macromedia Flash MX — 2004г. Книга есть в свободном доступе в интернете. Там целая глава посвящена вопросам обнаружения столкновений — с.85-136

                    И кстати метод растяжения один из наиболее известных, когда объект как бы вытягивают по направлению его движения, создавая вытянутую копию его, с которой и проверяют столкновения.
                      0
                      Спасибо! Качаю. :)

                      В общем случае, все решилось просто: победить свою лень и правильно составить поисковый запрос.
                      Первая итерация дала название техник для расчета коллизий для быстродвижущихся объектов:
                      — swept-collision tests (wikipedia)
                      — multisampling.

                      Если со второй все более-менее понятно, то первая техника это именно то самое «растяжение» объекта вдоль вектора движения. Как это реализовать для простейшей геометрии рассказано, например, тут: http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php.

                    0
                    Рейкастинг (ray-casting) можно было бы осветить малость, именно его зачастую используют для обнаружения препятствий в векторном мире

                    Only users with full accounts can post comments. Log in, please.