Понятные движения: как предсказать действия игроков

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

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

Система прогнозирования важна для создания более реалистичного и интересного поведения ИИ. Благодаря ей, противники могут стать достойным испытанием для игрока: уворачиваться от гранат, отпрыгивать от несущегося на них транспорта и предугадывать передвижение пользователя, чтобы застать его врасплох.

Бартоломей Вашак (Bartlomiej Waszak) написал на сайте Gamasutra текст про реализацию системы прогнозирования в видеоиграх для трёх разных типов объектов: персонажей, снарядов и транспорта. Мы выбрали из материала главное.

Чтобы предсказать движение объекта, нужно выполнить некоторую физическую симуляцию. Лучше всего было бы смоделировать весь физический мир. Из-за ограниченной вычислительной мощности это пока не совсем разумно. Однако, в зависимости от задачи, можно выполнить упрощённое моделирование, чтобы получить прогнозируемое состояние отдельного объекта.

Система прогнозирования особенно важна для трёх типов объектов:

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

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

Однако подходит и формула для скорости во время постоянного движения, в которой не используется производная:

Скорость — это векторная величина, которая имеет направление и длину. Длина вектора скорости является скалярным значением и может называться скалярной скоростью.

Как уже было сказано, прогнозирование перемещения персонажа осуществляется на короткие промежутки времени — менее одной секунды. Для этого делается несколько допущений:

Здесь важна формула постоянной скорости из предыдущего раздела:

Но на этот раз ν, x₀ и ∆t известны, а x₁ неизвестна.

Далее нужно умножить обе стороны на ∆t:

Потом нужно перенести x₀ в левую часть:

В итоге необходимо поменять местами обе части уравнения:

Наконец, имеется финальная формула, где x₀ — нынешняя позиция персонажа, ν — его векторная скорость, ∆t — время прогноза, x₁ — предполагаемая позиция в будущем.

Эта формула имеет естественное геометрическое объяснение. Точка перемещается по вектору скорости v из точки x₀ в точку x₁.

Ниже представлен код в Unity Engine с простой реализацией окончательной формулы:

Vector3 LinearMovementPrediction(Vector3 CurrentPosition, Vector3 CurrentVelocity, float PredictionTime)

{

Vector3 PredictedPosition = CurrentPosition + CurrentVelocity * PredictionTime; return PredictedPosition;

}

В навигации процесс прогнозирования местоположения называется «dead reckoning» (счисление координат), в котором используется эта формула в качестве основного метода вычисления.

Это также простая формула для прогнозирования движения персонажа в многопользовательских играх во время ожидания поступления новых сетевых данных.

Векторная скорость является производной от функции положения, поэтому она лежит на касательной в точке x₀. Поскольку здесь предсказывается положение вдоль вектора скорости, более длительное время прогнозирования ∆t приведёт к неточностям. Более короткое время предсказания ∆t даёт лучший результат.

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

Формула прогнозируемой позиции x₁ с постоянным ускорением a имеет следующий вид:

Когда нет ускорения (a=0), эта формула всё ещё даёт тот же результат прогноза, что и уравнение из предыдущего раздела.

Формула может быть легко объяснена с помощью приведённого ниже графика для одномерного движения:

Графики показывают связь между скоростью и временем. Другими словами, они показывают, как скорость (синяя линия) изменяется со временем. Когда график имеет такой вид, область под линией скорости (отмечена синим цветом) является расстоянием, пройденным движущимся объектом. Можно рассчитать эту площадь как сумму двух фигур: прямоугольника A и прямоугольного треугольника B.

Используя обозначения для областей с начальным расстоянием s₀ и конечным расстоянием s₁, пройденным движущимся объектом, можно получить следующую формулу:

Площадь прямоугольника А:

Площадь прямоугольного треугольника B может быть вычислена как половина верхнего прямоугольника:

Если добавить сюда первую формулу этого раздела, то получится следующий вид:

Наконец, заменив A и B в первой формуле s₁, можно получить:

Если заменить переменные s₀ на x₀, а s₁ на x₁, получится:

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

Чтобы сделать такое предсказание, нужно выполнить цикл симуляции и проверить наличие коллизий на каждом этапе. Наименее трудный вариант — взять простую физику баллистики для движущегося снаряда в виде точки. Ниже приведен код с реализацией в Unity Engine:

Vector3 PredictProjectileMovement(Vector3 InitialPosition, Vector3 InitialVelocity, float TimeToExplode)

{

float Restitution = 0.5f;

Vector3 Position = InitialPosition;

Vector3 Velocity = InitialVelocity;

Vector3 GravitationalAcceleration = new Vector3(0.0f, -9.81f, 0.0f);

float t = 0.0f; float DeltaTime = 0.02f;

while (t < TimeToExplode)

{

Vector3 PreviousPosition = Position;

Vector3 PreviousVelocity = Velocity;

Position += Velocity * DeltaTime + 0.5f * GravitationalAcceleration * DeltaTime * DeltaTime;

Velocity += GravitationalAcceleration * DeltaTime;

// Collision detection. RaycastHit HitInfo;

if (Physics.Linecast(PreviousPosition, Position, out HitInfo))

{

// Recompute velocity at the collision point.

float FullDistance = (Position - PreviousPosition).magnitude;

float HitCoef = (FullDistance > 0.000001f) ? (HitInfo.distance / FullDistance) : 0.0f;

Velocity = PreviousVelocity + GravitationalAcceleration * DeltaTime * HitCoef;

// Set the hit point as the new position.

Position = HitInfo.point;

// Collision response. Bounce velocity after the impact using coefficient of restitution.

float ProjectedVelocity = Vector3.Dot(HitInfo.normal, Velocity);

Velocity += -(1+Restitution) * ProjectedVelocity * HitInfo.normal;

}

t += DeltaTime;

}

// Return the final predicted position. return Position;

}

Объяснение этого кода будет представлено в следующих трёх подразделах: цикл моделирования, обнаружение столкновений и реакция на столкновение.

Выбор шага по времени (DeltaTime) для каждой итерации зависит от требований к точности. Как правило, это будет то же значение, что и шаг по времени для физического движка (в Unity Engine значение по умолчанию составляет 0,02 с).

В начале цикла, перед оценкой уравнения движения, нужно сохранить положение и скорость в переменных PreviousPosition и PreviousVelocity. Это необходимо для обнаружения столкновений.

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

Position += Velocity * DeltaTime + 0.5f * GravitationalAcceleration * DeltaTime * DeltaTime;

Новая скорость рассчитывается с использованием ускорения:

Velocity += GravitationalAcceleration * DeltaTime;

Важной частью цикла является тест на столкновение, который описан на рисунке ниже:

Здесь используется позиция из предыдущего шага (переменная PreviousPosition) и только что вычисленная позиция (переменная Position), чтобы проверить, попадает ли отрезок линии между ними в какие-либо объекты. Тест столкновения выполняется методом Unity Engine Physics.LineCast:

Physics.Linecast(PreviousPosition, Position, out HitInfo)

Если есть столкновение, результат сохраняется в HitInfo:

Имея эти данные, можно рассчитать положение и скорость в точке столкновения.

Скорость рассчитывается в первую очередь, чтобы получить точное значение в HitPoint. Переменная HitCoef имеет значение от 0 до 1 и представляет собой отношение HitInfo.distance к общей длине отрезка линии. Скорость рассчитывается, используя то же уравнение движения, но масштабируя последний компонент с помощью HitCoef. Таким образом, DeltaTime масштабируется до момента столкновения, что даёт значение скорости в точке столкновения.

Новая позиция представляет собой точку удара.

Чтобы рассчитать рикошет объекта, необходимо использовать HitNormal и коэффициент реституции (сила отскока). Значение реституции должно быть в диапазоне от 0 до 1. Если переменная реституции равна 1, происходит идеальный отскок, при котором энергия не теряется. Если реституция равна 0, то вся энергия расходуется, а скорость вдоль нормали удара сводится к нулю.

Расчет скорости отскока (после удара) описан на рисунке ниже.

Чтобы вычислить скорость после удара, нужно представить импульс вдоль вектора n (HitNormal) с неизвестной величиной j:

Вычисления начинаются с основного уравнения, определяющего коэффициент восстановления как отношение между относительными скоростями:

Относительные скорости v₀ и v₁ рассчитываются, как проекция на нормаль столкновения разностей скоростей двух сталкивающихся объектов (символ ○ представляет собой скалярное произведение):

Так как речь идёт только о статической среде (объект B всегда имеет нулевые скорости), его можно упростить до:

Объединив три уравнения вместе, можно получить:

Теперь можно использовать первое уравнение и сделать замену для VelocityAfterHit:

Преобразование левой стороны:

Перемещение первого выражения в правую часть:

Поскольку нормаль столкновения n является единичным вектором, она имеет длину 1, а (n ○ n) также 1:

Наконец, можно упростить правую часть:

Теперь можно сделать замену для j в первом уравнении:

Это уравнение реализовано в коде в виде следующей строки:

Velocity += -(1+Restitution) * ProjectedVelocity * HitInfo.normal;

Подводя итоги этого раздела, можно заметить, что функция полностью вычисляет траекторию снаряда. Значение переменной Position может быть сохранено в конце каждой итерации, как последовательная точка кривой. Это можно использовать, чтобы нарисовать ожидаемую траекторию, когда игрок хочет бросить гранату. Также можно дать эту информацию ИИ, чтобы отметить места, которых следует избегать.

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

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

Чтобы рассчитать полное прогнозируемое состояние транспортного средства, нужно рассчитать оба компонента движения: линейный и вращательный. Линейный компонент (прогнозируемая позиция) может оцениваться так же, как и для персонажей. Для вращательной составляющей можно принять постоянное значение угловой скорости во время прогнозирования. Код представлен ниже:

Quaternion RotationalMovementPrediction(Quaternion CurrentOrientation, Vector3 AngularVelocity, float PredictionTime)

{

float RotationAngle = AngularVelocity.magnitude * PredictionTime;

Vector3 RotationAxis = AngularVelocity.normalized;

Quaternion RotationFromAngularVelocity = Quaternion.AngleAxis(RotationAngle * Mathf.Rad2Deg, RotationAxis);

Quaternion PredictedOrientation = CurrentOrientation * RotationFromAngularVelocity;

return PredictedOrientation;

}

В данном случае, кватернион вращения строится с помощью интерфейса оси и угла — метод Quaternion.AngleAxis (). Ось вращения берётся непосредственно из угловой скорости как нормализованный вектор:

RotationAxis = AngularVelocity.normalized;

Угол поворота рассчитывается как умножение скорости изменения и времени предсказания:

RotationAngle = AngularVelocity.magnitude * PredictionTime;

Поскольку длина вектора угловой скорости представляет собой скорость изменения ориентации, если умножить её на желаемое время прогнозирования, на выходе получится полный угол, на который нужно повернуть вокруг оси.

Для примера можно предположить, что машина вращается со скоростью 0,25 радиана в секунду. Если умножить его на 2 секунды времени предсказания, то получится 0,5 радиана в качестве значения переменной RotationAngle (приблизительно 28,6°). Это прогнозируемый угол поворота автомобиля через две секунды.

Имея ось вращения и угол поворота, можно построить кватернион по угловой скорости (используя преобразование из радианов в градусы, потому что в Unity в качестве входных данных используются именно градусы):

RotationFromAngularVelocity = Quaternion.AngleAxis(RotationAngle * Mathf.Rad2Deg, RotationAxis);

Наконец, нужно вычислить кватернион для формирования итогового прогноза. Для этого нужно умножить текущую ориентацию на кватернион вращения, который представляет изменение угловой скорости:

PredictedOrientation = CurrentOrientation * RotationFromAngularVelocity;

Результатом этого умножения является ориентация прогнозируемого состояния транспорта:

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

Для достижения лучших результатов, особенно для предсказания на более длительный период, можно выполнять как линейное, так и вращательное прогнозирование в цикле всего за несколько итераций. На каждой итерации нужно сопоставлять линейную скорость с новым направлением вперёд, чтобы лучше передать поведение физики транспорта. Код:

void VehicleMovementPrediction(Vector3 Position, Vector3 LinearVelocity, Quaternion Orientation, Vector3 AngularVelocity, float PredictionTime, int NumberOfIterations, out Vector3 outPosition, out Quaternion outOrientation)

{

float DeltaTime = PredictionTime / NumberOfIterations;

for (int i=1 ; i<=NumberOfIterations ; ++i)

{

Position = LinearMovementPrediction(Position, LinearVelocity, DeltaTime);

Orientation = RotationalMovementPrediction(Orientation, AngularVelocity, DeltaTime);

// Match LinearVelocity with the new forward direction from Orientation.

LinearVelocity = Orientation * new Vector3(0.0f, 0.0f, LinearVelocity.magnitude);

}

outPosition = Position; outOrientation = Orientation;

}

После выполнения цикла должен получиться такой же результат прогноза, как и на изображении ниже:

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