Алгоритм синхронизации — различия между версиями
Korvin (обсуждение | вклад) м (→Поиск уравнения коррекции) |
Korvin (обсуждение | вклад) м |
||
Строка 76: | Строка 76: | ||
где <math>y</math> — это высота точки и | где <math>y</math> — это высота точки и | ||
:<math>y(0) = H\!</math> | :<math>y(0) = H\!</math> | ||
+ | |||
+ | Множитель <math>V_x</math> мы добавляем специально, чтобы уменьшить влияние силы коррекции на малых скоростях (иначе еле движущееся тело будет менять свое положение заметными глазу рывками). | ||
Строка 112: | Строка 114: | ||
:<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>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>\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 \cdot e^{\alpha_1 \cdot 0} + C_2 \cdot e^{\alpha_2 \cdot 0} = y(0) = H</math> | + | |
следовательно | следовательно | ||
− | :<math> | + | :<math>C_1 + C_2 = H\!</math>. |
Строка 131: | Строка 132: | ||
:<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 \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>\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> | ||
Строка 149: | Строка 158: | ||
Итак, при моделировании, будем считать что в течение шага тело движется по прямой. Соответственно, сила, которая будет действовать на тело в течение первого шага, т.е. времени <math>T</math>, будет равна | Итак, при моделировании, будем считать что в течение шага тело движется по прямой. Соответственно, сила, которая будет действовать на тело в течение первого шага, т.е. времени <math>T</math>, будет равна | ||
:<math>F_p = - K_p \cdot V_x \cdot H \cdot m</math> | :<math>F_p = - K_p \cdot V_x \cdot H \cdot m</math> | ||
− | |||
− | |||
Версия 13:54, 23 октября 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_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 \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