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

Текущая версия на 12:29, 31 октября 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>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 + ct^2 + dt^3 = x_1 \\ b = v_0 \\ b + 2ct + 3dt^2 = v_1 \end{cases} </math>

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

<math>\begin{cases}

x_0 + v_0t + ct^2 + dt^3 = x_1 \\ v_0 + 2ct + 3dt^2 = v_1 \end{cases} </math>

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

<math>\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} </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

  Синус

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

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

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

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

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

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

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

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

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

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

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

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

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

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