Устранение эффекта запаздывания с помощью кубических сплайнов.

Автор: Nick Caldwell

Defeating lag with cubic splines.

В процессе написания сетевых приложений возникает общая проблема - как избежать запаздывания, которое свойственно всему, что работает в Интернете; игроки словно перемещаются рывками по полю битвы. Существует несколько способов решения данной проблемы: увеличение частоты пересылки пакетов, уменьшение их размеров за счет сжатия, и предсказание (dead reckoning). Эта статья - попытка разъяснить один из этих способов, а конкретно применение всей мощи кубических сплайнов в алгоритме предсказания.

Что такое предсказание (Dead reckoning)?

Перед тем, как мы перейдем непосредственно к кубическим сплайнам, давайте уясним суть техники предсказания. Она используется для компенсации задержек, возникающих при пересылке данных. Смысл в том, что мы пытаемся предсказать действие объекта исходя только из его характеристик. Например, используя элементарные выражения и, зная начальное положение и начальную скорость объекта, мы можем построить его траекторию. Эта траектория может использоваться для создания иллюзии плавного движения объекта. Для построения такой траектории с помощью кубических сплайнов необходимы две контрольные точки (в которых мы знаем и координату, и скорость).

Возможные формы предсказания.

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

Самый примитивный метод предсказания - это точечный (point-to-point) (прим. перев. - честно сказать, этот метод не является предсказанием). В соответствии с его названием,  игрок перемещается в новое положение только при получении данных об этом положении. И при среднем запаздывании пакетов, идущих через Интернет, 200-300 мс, "дерганье" игрока при перемещении очень заметно. Это самый плохой метод из всех. Вы видите реальное положение своего противника, только если он стоит на месте. Причина этой ошибки в том, что даже в быстрых Quake-подобных играх данные приходят 5-10 раз в секунду, а самая медленная игра обновляет экран, как минимум 30 раз в секунду. Единственный выход из этой  ситуации слать данные так, чтобы информация приходила при каждом обновлении экрана. Но это потребует ужасной нагрузки на сеть и практически неосуществимо. Поэтому, точечный метод непригоден для эффективного использования в играх, работающих в реальном масштабе времени.

Новое Положение = Старое Положение

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

Новое Положение =Старое Положение + Скорость*Время

Сейчас у сообразительного программиста может возникнуть вопрос: "Почему мы не используем ускорение для предсказания?". Такой метод возможен и дает более гладкую результирующую траекторию. Он называется квадратичным. Заметим, опуская математические детали, что этот метод также дает неверный результат, а именно, конечная скорость не будет соответствовать действительности. Причина этого в том, что квадратичные функции не могут описывать изменение траектории с течением времени. Остается единственный выход - кубические сплайны.

Новое Положение = Старое Положение + Скорость*Время + Ускорение*(Время)²

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

Использование кубических сплайнов

Для использования кубических сплайнов необходимо рассмотреть систему уравнений. Входными переменными для этих уравнений являются 4 пары координат - (x,y). Первая пара - начальное положение объекта. Аналогично, четвёртая - это конечное положение объекта. Обычно, конечное положение - это то положение, информация о котором только что доставлена. Но самые главные пары координат - это вторая и третья. Они описывают скорости объекта. Вторая координата описывает положение объекта, в котором он должен оказаться при текущей скорости через одну секунду. Третья координата - положение объекта, относительно конечного положения, при движении в течение одной секунды с конечной скоростью взятой с обратным знаком. Другими словами, возврат во времени на одну секунду (при постоянной скорости). В итоге:

A.

B. Параметрические уравнения, используемые для построения сплайна:

x = At3 + Bt2 + Ct + D


y = Et3 + Ft2 + Gt + H

С. После некоторых преобразований получим:

A = x3 - 3x2 + 3x1 - x0


B = 3x2 - 6x1 + 3x0


C = 3x1 - 3x0


D = x0

E = y3 - 3y2 + 3y1 - y0


F = 3y2 - 6y1 + 3y0


G = 3y1 - 3y0


H = y0

D. Теперь, когда у нас есть все нужные уравнения, решим вопрос о том, как встроить их в нашу игру. Сделать это достаточно просто.

1.  Обрабатываем перемещение объекта в соответствии с физическими законами (вычисляя скорость и ускорение)

2.  После прибытия данных о новом положении создаём сплайн от текущей до следующей позиции.

3.  Для первой и второй координаты сплайна используем текущую позицию и скорость.

Coord1 = xold


Coord2 = xold + vold

4.  Третью и четвертую координату получить немного сложнее. Необходимо решить, за сколько шагов наш объект достигнет конечного положения. Пусть их будет -  T. Используем только что пришедшие данные, чтобы вычислить позицию через t секунд(шагов). Аналогично вычисляем конечную скорость.

Coord3 = xpacket + vpacket*t + 0.5*apacket*t2


Coord4 = Coord3 - (Vpacket + apacket*t)

Этот метод сочетает две формы предсказания: кубический сплайн (cubic spline) и квадратичное движение (quadratic motion). Результат выглядит более реалистично.

5.  Используем траекторию для перемещения объекта на Т шагов

6.  При подходе к концу сплайна, начинаем всё снова с первого шага.

Полученный результат будет чем-то похож на следующий рисунок:

Заключение.

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

Happy coding,
Nick Caldwell
Массачусетский Технологический Институт

Перевод осуществлён с личного разрешения автора, оригинал статьи находится по адресу:
http://www.gamedev.net/reference/articles/article914.asp

#предсказание, #сплайны

18 февраля 2002 (Обновление: 17 июня 2009)

Комментарии [1]