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

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

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

Плиточные движения кажутся очень «рваными», и если для пошаговой стратегии это допустимо, то в режиме реального времени смотрится откровенно убого. Чтобы остаться в рамках плиточных перемещений, но придать немного лоска, придумали один интересный подход: переходы между клетками осуществляется постепенно (попиксельно) с определенной скоростью, но прервать такое движение нельзя. То есть, если наш моб пошел вперед – то включилась «анимация» его движения, и он плавно перешел в нужную нам клетку. Это хорошо еще для того, чтобы была возможность задавать скорость передвижения, причем не только искусственному интеллекту, но и управляемым нами персонажем. Я столкнулся с таким способом в игре «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 в общем массиве мобов

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

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

Выводы

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

Автор: SpiritVL

Источник