Алгоритм синхронизации — различия между версиями

Версия 17:29, 22 октября 2008

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

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

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

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

<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>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>

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

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

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

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

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

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

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

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

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

Вертикальная скорость точки:

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

и <math>V_y(0) = 0</math>

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

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

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

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

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

<math>F = m \cdot a, \ m = 1, \ \to \ a \equiv F</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 \geqslant 0</math>

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

Дискриминант характеристического уравнения: <math>D = K_v^2 - 4 \cdot K_p \cdot V_x; \quad Kv^2 \geqslant 4 * Kp * Vx, \quad Vx \leqslant Kv^2 / (4 * Kp)</math>

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

[14:45:15] <droot@deeptown.org> вот если ось y направлена вверх, т.е. положительное направление силы - вверх [14:46:06] <droot@deeptown.org> то Fp = - m * Kp * Vx * y(t), Fv = - m * Kv * y'(t) [14:46:35] <droot@deeptown.org> потому что в начальный момент времени y(t) > 0, а Fp < 0 - соответственно, чтобы коэффициент был положительным, ставим знак минус [14:47:06] <droot@deeptown.org> y'(t) в первый момент времени < 0, а Fv должна быть > 0 - соответственно, тоже ставим знак минус [14:47:35] <droot@deeptown.org> да, еще на массу таки умножать надо =) потому что F = m * a, т.е. все кроме массы имеет физический смысл ускорения [14:48:13] <droot@deeptown.org> кстати, я еще размерность посмотрел. странные какие-то штуки получаются: [Kp] = 1 / (м*с), [Kv] = 1 / c [14:48:49] <droot@deeptown.org> (впрочем, далее по выкладкам все размерности сходятся) [14:49:27] <droot@deeptown.org> уравнение такое (после сокращения на массу): y(t) + Kv * y'(t) + Kp * Vx * y(t) = 0 [14:50:14] <droot@deeptown.org> D = Kv^2 - 4 * Kp * Vx; Kv^2 >= 4 * Kp * Vx, Vx <= Kv^2 / (4 * Kp) [14:50:31] <droot@deeptown.org> т.е. тут все как и говорили [14:51:15] <droot@deeptown.org> alpha(1,2) = (-Kv^2 +- sqrt(D)) / 2 [14:52:05] <droot@deeptown.org> чтобы система схлапывалась, а не разлеталась, нам нужно чтобы оба коэффициента alpha были бы меньше нуля [14:52:31] <droot@deeptown.org> напомню: y(t) = C1 * exp(alpha1 * t) + C2 * exp(alpha2 * t) [14:53:21] <droot@deeptown.org> поскольку Kp > 0 и Kv > 0, то alpha2 (которая с -sqrt(D)) - всегда меньше нуля [14:54:20] <droot@deeptown.org> тьфу, там ошибка: alpha(1,2) = (-Kv +- sqrt(D)) / 2 (т.е. Kv, а не Kv^2) [14:54:40] <droot@deeptown.org> alpha1 < 0 => -Kv + sqrt(D) < 0 [14:56:51] <droot@deeptown.org> т.е. sqrt(D) < Kv, D < Kv^2, Kv^2 - 4*Kp*Vx < Kv^2, 4*Kp*Vx > 0, Kp > 0 [14:57:17] <droot@deeptown.org> получается интересная вещь: alpha[1,2] оба меньше нуля при любых Kp > 0, Kv > 0 [14:58:14] <droot@deeptown.org> (условие Kv > 0 было использовано в этих выкладках, когда обе части неравенства возвели в квадрат - если бы этого условия не было, там надо было бы рассматривать 2 случая) [14:59:26] <droot@deeptown.org> (причем кстати второй случай соответствовал бы sqrt(D) < Kv при Kv < 0 - т.е. неравенство не выполняется никогда - ч.т.д =))

[14:59:54] <droot@deeptown.org> далее, найдем C1 и C2 [15:00:37] <droot@deeptown.org> они находятся из начальных условий: y(0) = H (начальное расстояние между объектами) и y'(t) = 0 (конечно, это условие надуманное, но рассмотрим пока такой случай) [15:00:54] <droot@deeptown.org> из первого условия получаем: [15:01:16] <droot@deeptown.org> C1 * exp(alpha1 * 0) + C2 * exp(alpha2 * 0) = H, C1 + C2 = H [15:01:21] <droot@deeptown.org> из второго условия: [15:01:54] <droot@deeptown.org> alpha1 * C1 * exp(alpha1 * 0) + alpha2 * C2 * exp(alpha2 * 0) = 0 [15:02:02] <droot@deeptown.org> alpha1 * C1 + alpha2 * C2 = 0 [15:02:46] <droot@deeptown.org> (чтобы проще было писать в этой дурацкой консольке, я обозначу DD = sqrt(D)) [15:02:57] <droot@deeptown.org> подставляем alpha1, alpha2 [15:02:59] <droot@deeptown.org> получаем [15:03:47] <droot@deeptown.org> (-Kv - DD)*C1 + (-Kv + DD)*C2 = 0 // двойку в знаменателе сразу сократили ессно [15:04:07] <droot@deeptown.org> из первого уравнения: C2 = H - C1 [15:04:10] <droot@deeptown.org> подставляем: [15:04:41] <droot@deeptown.org> -Kv * C1 - DD*C1 - Kv*H + DD*H + Kv*C1 - DD*C1 = 0 [15:05:49] <droot@deeptown.org> короче не буду приводить все промежуточные выкладки - понятно что это просто решение системы двух линейных уравнений относительно C1 и C2 [15:05:53] <droot@deeptown.org> в итоге получается так [15:06:10] <droot@deeptown.org> C[1,2] = (1/2 +- Kv / DD) * H [15:06:52] <droot@deeptown.org> (кстати обрати внимание что размерность Kv / DD - единица. если бы это было не так - это было бы сигналом к тому что где-то ошибка)