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

Версия 18:16, 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 - т.е. неравенство не выполняется никогда - ч.т.д =))

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

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

следовательно <math>C1 + C2 = H</math>.

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

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

<math>\alpha_1 \cdot C_1 + \alpha_2 \cdot C_2 = 0</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>

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

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

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

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

Условие стабилизации:

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

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

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

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

[20:13:09] <droot@deeptown.org> получаем: Kp < 8*Kp / (T*Kv)^2 [20:13:33] <droot@deeptown.org> 1 < 8 / (T*Kv)^2 [20:15:02] <droot@deeptown.org> Kv < 2*sqrt(2) / T [20:15:54] <droot@deeptown.org> при T = 0.04 это получается что-то вроде Kv < 70.7 [20:17:43] <korvin> так...

[20:18:28] <droot@deeptown.org> ну и на Kp условие получается исходя из того что это рассматривается при Kv^2 = 4*Kp [20:24:10] <droot@deeptown.org> мм. тоесть Vx = Kv^2 / (4*Kp) [20:25:45] <droot@deeptown.org> мм блин =) [20:25:50] <droot@deeptown.org> как-то надо еще одно условие [20:26:07] <droot@deeptown.org> и вообще как-то странно что мы получили ограничение на Kv, когда рассматривали действие силы Fp =)

[20:27:24] <droot@deeptown.org> а, ну вообще правильно. на Kp ограничение мы написали: Kp < 2 / (T^2 * Vx), и оно зависит от Vx [20:28:47] <droot@deeptown.org> ну если взять Vx равным скажем 10 м/с, то получается Kp < 2 / (0.04^2 * 10) = 125 [20:29:26] <droot@deeptown.org> хотя, в принципе, Vx у нас каждый раз можно посчитать из конкретных Kp, Kv [20:29:29] <droot@deeptown.org> короче [20:29:38] <droot@deeptown.org> когда у нас есть Kp, Kv введенные пользователем [20:29:44] <droot@deeptown.org> то мы должны проверить [20:30:09] <droot@deeptown.org> во-первых, что Kv^2 / (4*Kp) больше некоторой минимально различимой скорости - типа 10 м/с [20:30:30] <droot@deeptown.org> Kv^2 / (4*Kp) > 10 [20:30:47] <droot@deeptown.org> во-вторых, то что Kv < 70 [20:31:28] <droot@deeptown.org> и в-третьих то Kp < 2 / (0.04^2 * Vx)

[20:40:39] <droot@deeptown.org> так [20:40:44] <droot@deeptown.org> а теперь - самое веселое [20:40:51] <droot@deeptown.org> все то же самое, но только для вращения =) [20:46:32] <korvin> мде.. [20:46:56] <droot@deeptown.org> там почти то же самое [20:47:00] <korvin> ну вообще там не должно быть сильно сложно [20:47:02] <korvin> то же самое по сути [20:47:09] <droot@deeptown.org> т.е. плоская задача там будет точно такой же [20:47:24] <droot@deeptown.org> только не y(t), а fi(t) - угол от времени [20:48:03] <droot@deeptown.org> я вот не могу сообразить, что будет являться трехмерным представлением этого угла [20:48:37] <korvin> в смысле? [20:49:14] <droot@deeptown.org> ну вот в случае движения, от нашей задачи можно легко перейти к трехмерной, просто взяв не y(t), а r(t) - вектор координаты [20:49:18] <droot@deeptown.org> мм.. [20:49:23] <droot@deeptown.org> ну точнее не совсем так [20:49:27] <droot@deeptown.org> там же надо разность брать [20:49:32] <droot@deeptown.org> а, ну да [20:49:44] <droot@deeptown.org> т.е. вместо y(t) мы пишем разность векторов между сервером и клиентом [20:49:45] <korvin> ну там вроде же просто 3 угла, которые можно точно так же линейно интерполировать [20:50:45] <droot@deeptown.org> Vx - это модуль серверной скорости [20:50:58] <droot@deeptown.org> ну а все остальное понятно [20:51:29] <droot@deeptown.org> что же касается углов [20:51:41] <droot@deeptown.org> ну если посмотреть на задачу с практической точки зрения [20:51:50] <droot@deeptown.org> т.е. у нас есть два кватерниона [20:53:24] <droot@deeptown.org> надо сообразить, что будет являться кватернионом вращения из одного положения во второе [20:53:50] <korvin> в смысле что будет? [20:54:12] <korvin> м... может проще представить кватернион в виде косинусов и дальше по частям? [20:54:21] <korvin> покомпонентно в смысле [20:54:23] <droot@deeptown.org> это долго считать [20:59:55] <droot@deeptown.org> мм ну вообще все понятно [21:00:19] <droot@deeptown.org> если сумма вращений задается кватернионом Q = q2 * q1 [21:00:47] <droot@deeptown.org> то разность вращений будет q2 = Q * q1^(-1) = Q * q1' [21:01:36] <droot@deeptown.org> т.е. мы легко можем посчитать кватернион, который является разностью между клиентским и серверным вращениями [21:03:54] <droot@deeptown.org> для того, чтобы повернуть тело этим кватернионом, нам нужно приложить к нему момент вращения, направление которого также можно посчитать [21:05:56] <droot@deeptown.org> а зависеть он будет от тех же модуля серверной угловой скорости, собсно кватерниона разности, момента вращения, ну и соответственно некоторого коэффициента [21:08:54] <droot@deeptown.org> ну а для стабилизации разности угловых скоростей все элементарно: момент вращения будет просто пропорционален разности векторов угловых скоростей (ну и направлен вдоль вектора этой разности) [21:11:22] <korvin> так, ну это понятно [21:11:32] <korvin> а с перерегулированием что делать? [21:11:37] <korvin> ну то есть если перестараемся [21:11:41] <droot@deeptown.org> (я вот щас мысленно пытаюсь себе это представить и думаю нсчет вектора разности...) [21:12:44] <droot@deeptown.org> там собсно соотношение этих коэффициентов точно такое же должно получиться [21:13:34] <droot@deeptown.org> т.е. W < Kw^2 / (4*Kr) [21:42:36] <droot@deeptown.org> хочешь почитать веселую книжку? =) [21:43:09] <droot@deeptown.org> я тут с аленкой попробовал проконсультироваться, и она мне оч посоветовала =) ландау-лифшиц "механика" называется =) [21:55:38] <droot@deeptown.org> вообще, вот что до ограничений сверху для этих всех коэффициентов - я думаю, что надо просто взять некую константу - скажем, 30 - и ей ограничиться [21:55:53] <droot@deeptown.org> т.е. Kv < 30 [21:56:10] <droot@deeptown.org> ну, для Kp можно ограничение чуть больше - скажем, Kp < 50 [21:58:57] <droot@deeptown.org> мм. а вообще, я бы даже не так сделал [21:59:22] <droot@deeptown.org> мне кажется что параметризовать надо не через Kp и Kv, а через Vx и Kp, а уже Kv выражать через них [21:59:36] <korvin> мм [21:59:39] <korvin> а смысл? [21:59:41] <droot@deeptown.org> (ну т.е. Vx - это максимальная скорость) [21:59:50] <droot@deeptown.org> а это более понятные пользователю числа [22:01:30] <droot@deeptown.org> хотя... ладно, фиг с ним, пусть будет напрямую [22:01:40] <droot@deeptown.org> надо еще подумать, какие значения по-умолчанию лучше всего взять [22:01:59] <droot@deeptown.org> ну Vx видимо надо брать где-то 10 как раз - это 36 км/ч [22:02:22] <korvin> 10 м/с не жирно ли? [22:02:24] <droot@deeptown.org> при большей уже вряд ли будут заметны эти силы [22:02:55] <droot@deeptown.org> ну 36 км/ч - это где-то как раз граница воспринимаемых скоростей имхо [22:04:02] <droot@deeptown.org> Kv предлагаю взять равным где-то 20 [22:04:46] <droot@deeptown.org> при этом будет хороший запас до сваливания из-за шага рассчета, но и время стабилизации будет достаточно малым [22:04:55] <droot@deeptown.org> ну а Kp щас посчитаем [22:05:11] <droot@deeptown.org> Vx = Kv^2 / (4*Kp) [22:05:26] <droot@deeptown.org> Kp = Vx * 4 / Kv^2 [22:05:37] <droot@deeptown.org> тьфу [22:05:57] <droot@deeptown.org> Kp = Kv&2 / (Vx*4) [22:06:31] <droot@deeptown.org> Kp = 20^2 / 40 = 10 [22:06:40] <droot@deeptown.org> ну, вполне себе круглые числа =) [22:06:48] <droot@deeptown.org> Vx = 10, Kp = 10, Kv = 20