Алгоритм синхронизации

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

Построение сплайна

Для синхронизации была выбрана форма кубических сплайнов, при которой за основу берутся значения функции и ее производной в двух точках.

Свойства сплайна:

<math>s(t_i) = f(t_i), \quad s'(t_i) = f'(t_i)\!</math>

Уравнения сплайна:

<math>s(t) = a + bt + ct^2 + dt^3\!</math>

<math>s'(t) = b + 2ct + 3dt^2\!</math>

Для нахождения коэффициентов <math>a, b, c, d</math> записываем систему уравнений:

<math>\begin{cases}

a + bt_0 + ct_0^2 + dt_0^3 = f(t_0) \\ a + bt_1 + ct_1^2 + dt_1^3 = f(t_1) \\ b + 2ct_0 + 3dt_0^2 = f'(t_0) \\ b + 2ct_1 + 3dt_1^2 = f'(t_1) \end{cases} </math>

Подставляем известные значения в правой части системы (даны по условию):

<math>\begin{cases}

a + bt_0 + ct_0^2 + dt_0^3 = x_0 \\ a + bt_1 + ct_1^2 + dt_1^3 = x_1 \\ b + 2ct_0 + 3dt_0^2 = v_0 \\ b + 2ct_1 + 3dt_1^2 = v_1 \end{cases} </math>

Поскольку сплайн не зависит от конкретных значений <math>t_0</math> и <math>t_1</math>, положим <math>t_0 = 0</math>, а <math>t_1 = t</math>. В результате, пара уравнений становится тривиальной:

<math>\begin{cases}

a = x_0 \\ a + bt_1 + ct_1^2 + dt_1^3 = x_1 \\ b = v_0 \\ b + 2ct_1 + 3dt_1^2 = v_1 \end{cases} </math>

Заменяем в оставшихся уравнениях известные теперь коэффициенты и получаем конечную систему:

<math>\begin{cases}

x_0 + v_0t_1 + ct_1^2 + dt_1^3 = x_1 \\ v_0 + 2ct_1 + 3dt_1^2 = v_1 \end{cases} </math>

После нехитрых манипуляций, получаем выражения для оставшихся коэффициентов:

<math>\begin{cases}

c = \frac{3x_1 - 3x_0 - 2v_0t - v_1t}{t^2} \\ d = \frac{v_1t - 2x_1 + 2x_0 + v_ot}{t^3} \end{cases} </math>

Ниже представлены графики оригинальной функции с наложенным на них графиком сплайна, построенного по точкам. Парабола и экспонента построены по фиксированному набору точек (-2.5, -2, -0.5, 0.5, 2, 2.5). Синусоида построена по точкам с интервалом 0.05.

• Ошибка создания миниатюры: По-видимому, отсутствует файл /var/www/man.deeptown.org/images/0/01/Exp.gif

  Экспонента

• Ошибка создания миниатюры: По-видимому, отсутствует файл /var/www/man.deeptown.org/images/a/aa/Parabola2.gif

  Парабола

• Ошибка создания миниатюры: По-видимому, отсутствует файл /var/www/man.deeptown.org/images/e/eb/Sin.gif

  Синус

Механизм коррекции ошибки

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

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

Поиск уравнения коррекции

Чтобы упростить себе жизнь, рассмотрим одномерный случай. Пусть серверная "траектория" тела находится в точке 0; клиентская "траектория" — в точке с координатой H. Графически, это выглядит как вертикальная линия, в нуле — серверная траектория, в точке на высоте H — клиентская. Горизонтальную и вертикальную компоненты скорости будем рассматривать отдельно.

Пусть серверная точка имеет горизонтальную скорость <math>V_x</math>. Клиентская, в самом начале — горизонтальную скорость <math>V_x</math> и вертикальную, равную нулю.

Сила коррекции высоты, по такой модели, будет направлена "вниз" на эту точку, и будет равна:

<math>F_p = - K_p \cdot y(t) \cdot V_x \cdot m</math>

где <math>y</math> — это высота точки и

<math>y(0) = H\!</math>

Множитель <math>V_x</math> мы добавляем специально, чтобы уменьшить влияние силы коррекции на малых скоростях (иначе еле движущееся тело будет менять свое положение заметными глазу рывками).

Сила коррекции вертикальной скорости точки:

<math>F_v = - K_v \cdot V_y(t) \cdot m</math>

и

<math>V_y(0) = 0\!</math>

Известно, что скорость — это производная координаты по времени:

<math>V_y(t) = \frac{\partial y(t)}{\partial t}</math>

Соответственно, сила, которая действует на объект:

<math>F(t) = m \cdot y(t) = F_p + F_v = - K_p \cdot y(t) \cdot V_x \cdot m - K_v \cdot V_y(t) \cdot m</math>

<math>F - F_p - F_v = 0\!</math>

Разделив на массу, и записав уравнение в дифференциальной форме, получим:

<math>y(t) + K_v \cdot y'(t) + K_p \cdot y(t) \cdot Vx = 0</math>

Перепишем параметрически:

<math>y(t) + A \cdot y'(t) + B \cdot y(t) = 0\!</math>

Характеристическое уравнение:

<math>\lambda^2 + A \cdot \lambda + B = 0</math>

Дискриминант характеристического уравнения:

<math>D = A^2 - 4 \cdot B = K_v^2 - 4 \cdot K_p \cdot V_x</math>

Для исключения колебательного процесса, необходимо условие <math>D \geqslant 0</math>. Следовательно:

<math>K_v^2 - 4 \cdot K_p \cdot V_x \geqslant 0</math>

<math>K_v^2 \geqslant 4 \cdot K_p \cdot V_x, \quad V_x \leqslant \frac{K_v^2}{4 \cdot K_p}</math>

Видно, что если <math>V_x</math> будет больше чем эта дробь, то возникнут колебания (нарушается условие <math>D \geqslant 0</math>). Поэтому, при малых скоростях используется само значение <math>V_x</math>, а когда <math>V_x</math> численно становится больше этой дроби, следует заменять ее на эту дробь (ограничение сверху).

В конечном счете, коэффициенты <math>\alpha</math> выражаются как

<math>\alpha_{1,2} = \frac{-K_v \pm \sqrt{D}}{2}</math>

Далее, найдем <math>C_1</math> и <math>C_2</math>:

<math>y(t) = C_1 \cdot e^{\alpha_1 t} + C_2 \cdot e^{\alpha_2 t}</math>

Зная начальные условия <math>y(0) = H</math> (начальное расстояние между объектами) и <math>y'(t) = 0</math> получаем уравнение:

<math>C_1 \cdot e^{\alpha_1 \cdot 0} + C_2 \cdot e^{\alpha_2 \cdot 0} = y(0) = H</math>

следовательно

<math>C_1 + C_2 = H\!</math>.

Из второго условия:

<math>\alpha_1 \cdot C_1 \cdot e^{\alpha_1 \cdot 0} + \alpha_2 \cdot C_2 \cdot e^{\alpha_2 \cdot 0} = 0</math>

<math>\alpha_1 \cdot C_1 + \alpha_2 \cdot C_2 = 0</math>

Получаем систему следующих уравнений:

<math>\begin{cases}

C_1 + C_2 = H \\ \alpha_1 \cdot C_1 + \alpha_2 \cdot C_2 = 0 \end{cases} </math>

Решая систему относительно <math>C_1</math> и <math>C_2</math>, получаем

<math>C_{1,2} = \left ( \frac{1}{2} \pm \frac{K_v}{\sqrt{D}} \right ) \cdot H</math>

Все коэффициенты найдены, задачу можно считать решенной. Однако, есть еще один немаловаждый момент.

Оценка параметров

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

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

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

Итак, при моделировании, будем считать что в течение шага тело движется по прямой. Соответственно, сила, которая будет действовать на тело в течение первого шага, т.е. времени <math>T</math>, будет равна

<math>F_p = - K_p \cdot V_x \cdot H \cdot m</math>

Соответственно, в течение первого шага тело будет двигаться с ускорением

<math>a = - K_p \cdot Vx \cdot H</math>

Условие стабилизации — расстояние, которое преодолеет тело за первый шаг должно быть меньше <math>H</math>:

<math>K_p \cdot V_x \cdot H \cdot \frac{T^2}{2} < H, \quad K_p \cdot V_x \cdot \frac{T^2}{2} < 2, \quad K_p < \frac{2}{V_x \cdot {T^2}}</math>

Левая часть будет минимальной в случае, когда <math>V_x</math> максимальна, т.е. равна <math>\tfrac{K_v^2}{4 \cdot K_p}</math>.

Это означает, что в том случае когда модуль скорости тела меньше чем указанное значение, то коррекция происходить гладко; когда больше — в формуле для силы стабилизации положения <math>V_x</math> заменяется на <math>\tfrac{K_v^2}{4 \cdot K_p}</math>. Объяснение было дано выше, при оценке дискриминанта характеристического уравнения.

Из этого следует, что чтобы действительно сделать невидимым действие нашей силы на малых скоростях, необходимо, чтобы значение <math>\tfrac{K_v^2}{4 \cdot K_p}</math> было бы достаточно большим. Мы взяли его по-умолчанию равным 10, но это значение можно бдет менять в свойствах каждого конкретного объекта.

Осталось только численно оценить коэффициенты <math>K_p</math> и <math>K_v</math>. Для <math>K_p</math> конкретное значение получается, если подставить в условие

<math>K_p < \frac{2}{V_x \cdot T^2}</math>

значения <math>V_x = 10</math> и <math>T = 0.04</math>. Получается, что <math>K_p < 125</math>.

Для нахождения <math>K_v</math> вместо <math>V_x</math> необходимо подставить наибольшее возможное для нее значение <math>\tfrac{K_v^2}{4 \cdot K_p}</math>:

<math>K_p < \frac{2}{\frac{K_v^2}{4 \cdot K_p} \cdot T^2}, \quad K_p < \frac{2 \cdot 4 \cdot K_p}{K_v^2 \cdot T^2}, \quad 1 < \frac{8}{K_v^2 \cdot T^2}, \quad K_v^2 < \frac{8}{T^2}</math>

Окончательно,

<math>K_v < \frac{2\sqrt{2}}{T}</math>

При подстановке значения <math>T = 0.04</math>, получается, что <math>K_v < 70</math>. В реальных условиях эти пределы взяты еще меньше, для защиты от граничных случаев. Конкретно, <math>K_p</math> по-умолчанию не может превышать 50, а <math>K_v</math> — 30