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

Материал из Deeptown Manual

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

Содержание 1 Построение сплайна 2 Механизм коррекции ошибки 2.1 Поиск уравнения коррекции 2.2 Оценка параметров

[править] Построение сплайна

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

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): s(t_i) = f(t_i), \quad s'(t_i) = f'(t_i)\!

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): s(t) = a + bt + ct^2 + dt^3\!

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): s'(t) = b + 2ct + 3dt^2\!

Для нахождения коэффициентов Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): a, b, c, d

записываем систему уравнений:

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \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}

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \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}

Поскольку сплайн не зависит от конкретных значений Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): t_0

и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): t_1

, положим Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): t_0 = 0 , а Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): t_1 = t . В результате, пара уравнений становится тривиальной:

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \begin{cases} a = x_0 \\ a + bt + ct^2 + dt^3 = x_1 \\ b = v_0 \\ b + 2ct + 3dt^2 = v_1 \end{cases}

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \begin{cases} x_0 + v_0t + ct^2 + dt^3 = x_1 \\ v_0 + 2ct + 3dt^2 = v_1 \end{cases}

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \begin{cases} c = \frac{3x_1 - 3x_0 - 2v_0t - v_1t}{t^2} \\ d = \frac{2x_0 - 2x_1 + v_0t + v_1t}{t^3} \end{cases}

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

Экспонента

Парабола

Синус

[править] Механизм коррекции ошибки

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

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

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

[править] Поиск уравнения коррекции

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

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

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

Сила коррекции скорости, аналогично, направлена по разности векторов скорости, пропорциональна этой разности; пропорциональна массе тела и некоторому второму коэффициенту.

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

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

Пусть и серверная, и клиентская точки имеют горизонтальную скорость Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x , а по вертикальной оси они неподвижны. Никаких прочих сил на объект не действует. Поскольку никаких сил по горизонтали не действует, мы будем рассматривать только движение по оси y.

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): F_p = - K_p \cdot y(t) \cdot V_x \cdot m

где Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y

— это высота точки и 

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y(0) = H\!

Множитель Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x

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

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): F_v = - K_v \cdot V_y(t) \cdot m

и

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_y(0) = 0\!

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_y(t) = \frac{\partial y(t)}{\partial t}

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): 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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): F - F_p - F_v = 0\!

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y''(t) + K_v \cdot y'(t) + K_p \cdot y(t) \cdot Vx = 0

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y''(t) + A \cdot y'(t) + B \cdot y(t) = 0\!

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \lambda^2 + A \cdot \lambda + B = 0

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): D = A^2 - 4 \cdot B = K_v^2 - 4 \cdot K_p \cdot V_x

Для исключения колебательного процесса, необходимо условие Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): D \geqslant 0 . Следовательно:

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v^2 - 4 \cdot K_p \cdot V_x \geqslant 0

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v^2 \geqslant 4 \cdot K_p \cdot V_x, \quad V_x \leqslant \frac{K_v^2}{4 \cdot K_p}

Видно, что если Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x

будет больше чем эта дробь, то возникнут колебания (нарушается условие Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): D \geqslant 0

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

численно становится больше этой дроби, следует заменять ее на эту дробь (ограничение сверху).

В конечном счете, коэффициенты Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \alpha

выражаются как

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \alpha_{1,2} = \frac{-K_v \pm \sqrt{D}}{2}

Далее, найдем коэффициенты Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_1

и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_2

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y(t) = C_1 \cdot e^{\alpha_1 t} + C_2 \cdot e^{\alpha_2 t}

Зная начальные условия Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y(0) = H

(начальное расстояние между объектами) и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): y'(t) = 0
получаем уравнение:

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_1 \cdot e^{\alpha_1 \cdot 0} + C_2 \cdot e^{\alpha_2 \cdot 0} = y(0) = H

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_1 + C_2 = H\!

.

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \alpha_1 \cdot C_1 \cdot e^{\alpha_1 \cdot 0} + \alpha_2 \cdot C_2 \cdot e^{\alpha_2 \cdot 0} = 0

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \alpha_1 \cdot C_1 + \alpha_2 \cdot C_2 = 0

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \begin{cases} C_1 + C_2 = H \\ \alpha_1 \cdot C_1 + \alpha_2 \cdot C_2 = 0 \end{cases}

Решая систему относительно Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_1

и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_2

, получаем

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): C_{1,2} = \left ( \frac{1}{2} \pm \frac{K_v}{\sqrt{D}} \right ) \cdot H

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

[править] Оценка параметров

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

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

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

Итак, при моделировании, будем считать что в течение шага тело движется по прямой. Соответственно, сила, которая будет действовать на тело в течение первого шага, т.е. времени Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): T , будет равна

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): F_p = - K_p \cdot V_x \cdot H \cdot m

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): a = - K_p \cdot Vx \cdot H

Условие стабилизации — расстояние, которое преодолеет тело за первый шаг должно быть меньше Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): H

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p \cdot V_x \cdot H \cdot \frac{T^2}{2} < H, \quad K_p \cdot V_x \cdot T^2 < 2, \quad K_p < \frac{2}{V_x \cdot {T^2}}

Левая часть неравенства будет минимальной в случае, когда Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x

максимальна, т.е. равна Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \tfrac{K_v^2}{4 \cdot K_p}

.

Это означает, что в том случае когда модуль скорости тела меньше чем указанное значение, то коррекция будет происходить гладко; когда больше — в формуле для силы стабилизации положения Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x

заменяется на Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \tfrac{K_v^2}{4 \cdot K_p}

. Объяснение было дано выше, при оценке дискриминанта характеристического уравнения.

Из этого следует, что чтобы действительно сделать невидимым действие нашей силы на малых скоростях, необходимо, чтобы значение Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \tfrac{K_v^2}{4 \cdot K_p}

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

Осталось только численно оценить коэффициенты Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p

и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v

. Для Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p

конкретное значение получается, если подставить в условие 

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p < \frac{2}{V_x \cdot T^2}

значения Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x = 10

и Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): T = 0.04

. Получается, что Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p < 125 .

Для нахождения Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v

вместо Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): V_x
необходимо подставить наибольшее возможное для нее значение Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): \tfrac{K_v^2}{4 \cdot K_p}

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): 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}

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

Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v < \frac{2\sqrt{2}}{T}

При подстановке значения Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): T = 0.04 , получается, что Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v < 70 . В реальных условиях эти пределы взяты еще меньше, для защиты от граничных случаев. Конкретно, Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_p

по-умолчанию не может превышать 50, а Невозможно разобрать выражение (Не удаётся создать или записать во временный каталог математики): K_v
— 30