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

  • Tutorial
Это заключительная часть серии статей, описывающих перемещения компьютерных персонажей. Я расскажу о смешанных видах передвижений, которые сочетают в себе векторные и плиточные методы, небольшая оптимизация плиточных перемещений и ускорение просчетов добавлением сетки к векторам. А так же поведу общее сравнение всех описанных методов в виде таблицы.

Анимация плиточных перемещений



Плиточные движения кажутся очень «рваными», и если для пошаговой стратегии это допустимо, то в режиме реального времени смотрится откровенно убого. Чтобы остаться в рамках плиточных перемещений, но придать немного лоска, придумали один интересный подход: переходы между клетками осуществляется постепенно (попиксельно) с определенной скоростью, но прервать такое движение нельзя. То есть, если наш моб пошел вперед – то включилась «анимация» его движения, и он плавно перешел в нужную нам клетку. Это хорошо еще для того, чтобы была возможность задавать скорость передвижения, причем не только искусственному интеллекту, но и управляемым нами персонажем. Я столкнулся с таким способом в игре «Final Fantasy II» (на мобильном), но думаю это используется во всех плиточных RPG такого типа. Реализация такого движения мало чем отличается от обычного перемещения в плиточном мире. Будет два типа координат – в пикселях (для рисования персонажа – float x, y) и в клетках (для расчетов – int PosX, PosY). Нам нужно добавить флаг ходьбы (bool Walk) – который указывает находиться ли наш объект сейчас в движении или нет. Еще счетчик сделанных мобом шагов (int Steps). И немного доработать функцию перемещения. Покажу на примере движения влево – будет изменяться только переменная X:
void Mob::Move(int Direction) {
    switch(Direction) {
        case 0:
        if(Walk == true) break;//если двигаемся - пропустить
        x -=1;//двигаемся влево с шагом 1, координаты в ПИКСЕЛЯХ
        Steps++;//увеличиваем число шагов
        if(Steps>CellSize) {//если дошли до следующей клетки
            Walk = false;//перестаем двигаться
            Steps = 0;//сбрасываем число шагов
            PosX = int(x/CellSize);//вычисляем координаты в КЛЕТКАХ
        }
    }
}


Совмещение векторных и пиксельных перемещений



Если движения агентов осуществляется с использованием векторов, то мы сталкиваемся с рядом проблем, например просчета столкновений. Это можно оптимизировать и ускорить добавлением сетки, или невидимых плиток. Наиболее распространены два варианта: сетка проходимости и дублирование положения объектов на сетке. В обоих случаях надо чтобы столкновения и взаимодействия с объектами, как и само положение моба в клеточных координатах, определялось по всем его границам. Лучше всего использовать размеры сетки равные размерам объектов – тогда в худшем случае нужно будет проверить 4 соседних клетки, на которых расположился наш объект.

Сетка проходимости


В большинстве случаев препятствия можно очертить каким-то примитивом, а иногда и прямоугольником. В таком случае нет необходимости просчитывать столкновения со всеми выпуклостями и неровностями препятствия. Но все равно, если таких объектов много, приходится считать столкновение со всеми потенциальными объектами, что может быть ресурсозатратно. Тогда применяют сетку проходимости. На всю карту мира накладывается невидимая сетка, представляющая собой двумерный массив переменных типа bool. Если в какой-то клетке находится препятствие – то значение становится true, соответственно и наоборот. Сетка дублирует препятствия, но просчеты столкновений становятся куда более простыми, и даже если наш объект двигается по вектору – он легко может обратиться к этой сетке с запросом: нет ли там препятствия? Размер ячейки нужно подбирать так, чтобы оптимизировать точность и количество просчетов: слишком крупная приведет к грубым угловатым препятствиям, слишком мелкая – к большему числу просчетов. Чтобы определить, можно ли двигаться в следующую точку, нужно высчитать в какую клетку сетки проходимости мы попадем, и узнать ее состояние. Для этого нужно разделить координаты на размер клетки и отбросить дробную часть.
void Mob::Move() {
    int NewX, NewY;//переменные для хранения будущих координат
    NewX = int((x+Way.x)/CellSize);//вычисляем будущее положения в клетках
    NewY = int((y+Way.y)/CellSize);
    if(Map[NewX][NewY] == true) {//проверка на возможность перемещения
        x += Way.x;//если можно - двигаемся
        y += Way.y;
    }
}

Оптимизация векторных перемещений


Если у нас достаточно много объектов (больше 200), то просчеты столкновений «все со всеми» могут быть затратными. Как раз для этого можно применить очередную комбинацию векторных и плиточных миров. Как и в предыдущем примере, все объекты, особенно динамические, дублируются в сетке, но на этот раз вместо флага «свободно/занято» будет id моба, или даже указатель на него, чтобы можно было быстро к нему обратиться. Правда придется столкнуться с трудностью – если объект будет выходить за пределы ячейки (что вполне возможно), придется указывать его положение в нескольких смежных ячейках. Так же возможен вариант одновременного нахождения нескольких объектов в одной клетке, так что лучше использовать для этого динамические массивы. Вот пример класса «клетка», из которых потом состоит массив всех клеток карты.
class Cell {//класс клетка
    bool Free;//свободна ли клетка
    vector<int> MobsID;//динамический массив Id мобов, находящихся в этой клетке
};

Перемещения мобов осуществляется теми же способами как и раньше, только добавляется работа с массивом клеток — при каждом перемещении надо удалить себя из предыдущей клетки и записать в новую, чтобы нас можно было найти. Код представлен для лучшего понимания сути вопроса, он не претендует на оптимальный.
void Mob::Move() {
...
    int XCell, YCell;//переменные для хранения координат
    XCell = int(x/CellSize);//вычисляем положения в клетках
    YCell = int(y/CellSize);//оцениваем только один угол нашего моба
    Map[XCell][YCell].Free = false;//заняли клетку
    Map[XCell][YCell].MobsID.pop_back(ID);//добавляем в клетку свой ID
...
}

Доступ к конкретному мобу находящемуся в конкретной клетке можно получить так:
int Id = Map[X][Y].MobsID[0];//получаем Id первого моба в этой клетке
Mobs[Id].DoSomething;//обращаемся по Id в общем массиве мобов

Сравнение методов перемещения



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


Выводы


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

More
Ads

Comments 13

    +4
    Хорошая серия, неплохо бы и продолжить — плоский мир превратить в объемный.
      0
      В данный момент занимаюсь разработкой AI для своего сервера. Все мобы двигаются в трехмерном динамическом мире. Как раз думаю в итоге написать на хабр статью или цикл статей о передвижении, поиске пути и AI в трехмерном мире. Если меня, конечно, не опередят…
        0
        Я пока не планировал заниматься перемещениями в 3D, так что готовьте статью спокойно.
      0
      Кстати о поиске путей, есть еще вариант векторный несложный когда для карты уже заданы пути движения, далее игрок следует к ближайшей точке маршрута и идет по нему до указанной цели. Тут умирает 2 зайца сразу, простота реализации и главное ненадо делать множество проверок.

      О нем тоже стоило бы упомянуть.
        0
        На сколько я понял это разновидность Waypoint-ов, о которых говорилось в прошлой статье.
        0
        Не согласен по поводу позиции «Естественность и плавность передвижений» в плиточном методе. Можно придумать как задавать анимацию передвижения объекта. Я сужу со стороны реализации на Qt. Например, сделать что-то вроде «модель представление», где модель — двумерная матрица-мир, а представление — графическая сцена, в которой и идет отрисовка данных. Собственно в ней можно и реализовать плавность передвижения объекта с помощью анимации. Даже чтото вроде примитивной физики можно сделать с помощью easing curve, применимых к анимации.
          0
          В таком случае это будет смешанный вид передвижений. В таблице я указал особенности «чистых» методов, без примесей и дополнительной оптимизации.
            0
            иду читать прошлые две части. («прошлые части не читай, комментарий в последней пиши» :D )
          0
          Согласен с первым комментом, с удовольствием бы прочитал серию про 3d в духе — «на пальцах», и с комментариями типо — «эта операция затратна», «эта не очень затратна», «а вот эта халява».
            0
            Отличная серия. Можно продолжить ее, дополнив алгоритмами поиска кратчайшего пути.
              0
              Очень не хватает ссылочки на предыдущие части :)

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