Внимание, разработчики: обход сетевых лагов!!!

[Chist]

Разработчикам LockOn'а и других симуляторов!!
У меня есть схема алгоритма обхода сетевых лагов. Пока только в голове, но эта беда поправима, как тоявится свободная минута. Хотите - отдам здесь, хотите - приватно. Только реализуйте!!! Больше ничего не прошу.

[<Danila-M>]

Сергей, поделись идеей, pls !
Пиши на мыло: danila@DP2627.spb.edu

[Freddie]

Это, случаем, не вычисление задержки и интерполяция? Такой способ используется на Warbirds Free Host. Сейчас они со своего сайта убрали описание алгоритма, но если интересно, могу запостить его текст сюда, у меня дома эта страничка сохранилась.

[Chist]

Да, схема такая. Я не знаю, насколько моя задумка похожа или не похожа на алгоритм Warbirds Free Host, я, честно, его не видел. Как только позволит время - выложу свою идею сюда. Просто надо еще нарисовать иллюстрации.

[Freddie]

Вот, нашел таки.
================ CUT =================
Синхронизация времен клиентов в сервере WarBirds

Как это осуществляется?
На сервере есть свое системное время, счетчик системного времени который увеличивается на 1 единицу каждую миллисикунду. Считаем это серверное время, в котором существуют все остальные клиенты. У каждого клиента есть свой счетчик, который так же синхронно (более менее) изменяется на 1 единицу каждую миллисикунду. Задача синхронизации - перенести все клиентские счетчики в одну систему координат. В сисиему координат серверного времени. Для этого каждый клиент один раз в 500 мс посылает серверу пакет, в одном из полей которого как раз и записывается текущее показание счетчика этого клиента. Вреия доставки пакета от клиента к серверу может меняться от десятков до тысяч единиц. Поэтому при передаче информации от сервера к клиенту все местоположения других игроков должны быть скорректированы.
Как это выполнить?
При поступлении пакета от клиента к серверу, происходит вычисление разницы между текущим серверным временем (время когда был принят пакет) и тем показанием которое хранится в пакете клиента. Происходит вычисление коэффициента, который будет согласовывающей величиной между клиентским временем и временем сервера.
Tserver = Tclient + Kclient.
Tserver текущее время сервера.
Tclient время клиента указанное в пакете.
Kclient поправочный коэффициент.
Эта величина K для каждого клиента своя.
Теперь как формировать пакет местоположения каждого клиента?
Предположим ко времени формирования этого пакета пришли информации от N клиентов. У всех из них есть N коэффициентов и у все из них N своих внутренних "времен". Для каждого клиента поправочный коэффициент (время от настоящего момента до того времени когда был получен последний пакет с координатами и указанным в этом пакете внутренним временем клиента) будет раваен:
Tadjust = Tnow_server-Tclient-Kclient.
Tadjust поправочный коэффициент который передается в пакете местоположения.
Tnow_server время в кторое формирутеся пакет местоположения для всех клиентов.
Tclient время указанное в пакете клиента (тот что пришел от клиента).
Kclient коэффициент ссответствия серверного и клиентского времени.
Как вычисляется K?
Берется последние 20 пакетов (10 секунд) и происходит нахождение согласовывающего коэффициента по формуле для каждого из пакетов:
Kclient=Tserver-Tclient
Среди этих коэффициентов выбирается минимальный по значению. Надо сказать что Tclient величина дискретно изменяющаяся и кратно 500 (или близка к этому) А величина Tserver вероятностная и зависит от качества линии связи. Время в которое сервер ПРИНЯЛ сигнал от клиента и есть то время Tserver
Пример когда Tserer < Tclient:
Tser[0] = 10
Tclient[0] = 20
K[0] = 10-20 = -10
Tser[1] = 16 +6
Tclient[1] = 25
K[1] = 16-25 = -11
Tser[2] = 21 +5
Tclient[2] = 30
K[2] = 21-30 = -9
Tser[3] = 27 +6
Tclient[3] = 35
K[3] = 27-35 = -8
Tser[4] = 29 +3
Tclient[4] = 40
K[4] = 29-40 = -11
Tser[5] = 32 +3
Tclient[4] = 45
K[5] = 32-45 = -13 /* это наилучший вариант */
Здесь запоминаем коэфициент = -13
Пример когда Tserer > Tclient:
Tser[0] = 30
Tclient[0] = 20
K[0] = 30-20 = 10
Tser[1] = 36
Tclient[1] = 25
K[1] = 36-25 = 11
Tser[2] = 39
Tclient[2] = 30
K[2] = 39-30 = 9
Tser[3] = 43
Tclient[3] = 35
K[3] = 43-35 = 8 /* наменьшее время, наилучший вариант */
Tser[4] = 53
Tclient[4] = 40
K[4] = 53-40 = 13 /* варп */
Здесь запоминаем коэфициент = 8
Анализ минимального коэффициента происходит 1 раз в секунду И минимальный коэффициент в лучшем случае держится 20 сек, в худшем 1 сек.
Далее после нахождения уравнивающего коэффициента для каждого клиента мы можем формировать пакеты положения клиентов в одном временном пространстве. Правда где то в связи с нетлагом будут сдвиги но в целом это позволит избежать нежелательного "подрагивания" самолетов на близком расстоянии. Данной системой синхронизации мы добиваемся исключения микроварпов.
=================== CUT ===================

[Chist]

А вот что придумал я.
Для простоты я рассмотрю вариант связи двух хостов. Связь большего количества происходит путем повторения этого алгоритма для каждой связывающейся пары.
Здесь делается допущение, что время путешествия пакета от одного хоста к другому равно путешествию в обратную сторону. Что, вообще говоря, может быть и не так, особенно при ассемитричном интернет-доступе.
Итак:
1. Пакеты объединяются в нити.
2. Пакеты, принадлежищие одной нити ходят поочередно туда-обратно между хостами.
3. Каждый хост для каждой нити записывает время отправки им последнего пакета.
4. Пакет в нити несет информацию о времени задержки нити на отправившем этот пакет хосте, а так же, помимо другой информации, угловые и пространственные координаты объектов с несколькими их производными (до 2-3й, чем больше тем лучше).
5. Время сетевой задержки опредеяется как (текущее время - время отправки последнего пакета нити - задержка нити на противоположном хосте) / 2
6. Текущие координаты объектов вычисляются исходя из полученных координат, производных и вычисленной сетевой задержки.
Я надеюсь, теперь все поняли зачем здесь нужны иллюстрации

Здесь:
красная, зеленая и синяя ломанные линии иллюстрируют нити. Наклонные участки - передача пакета в сети. Горизонтальные участки - обработка полученного пакета и формирование ответа. Время сетевой задержки T_з=(время возврата нити - время задержки нити) /2.
X=X₀ + V₀T_з + a₀T_з²/2
V=V₀+a₀T_з
и т.д.
Обозначения с индексом 0 - данные, полученные из пришедшего пакета.
Это теория. А теперь практика:
Хосты должны обменитьвася информацией регулярно, т.е. пакеты должны отправляться через определенные промежутки времени. Поэтому, необходимое количество нитей, которые будут связывать хосты заранее неизвестно и зависит как раз от той самой сетевой задержки, которую мы пытаемся измерить. Кроме того рассмотрите такую ситуацию:

Что здесь произошло:
Пакет крассной нити задержался и его обогнал зеленый. Синий пакет просто потерялся. Зеленый опять шустер и успел до отправки фиолетового.
Что делают хосты:
1. Недождавшись прихода крассного пакета хост А инициирует новую нить, фиолетовую.
2. По приходу зеленой нити он смотрит - ага, крассная нить еще не пришла, значит она либо потерялась, либо задержалась и уже не актуальна, т.к. есть более свежая информация. Крассная нить считается оборванной.
3. По приходу крассной нити из пакета извлекаются остатки полезной информации и эта нить обрывается.
4. Зеленый пакет пришел на хост Б до того, как был отправлен фиолетовый. Ну, да и Бог с ним, собственно, подольше полежит, прождет своего часа.
5. Синий пакет просто утерян и вместо него инициируется коричневая нить.
А теперь как это привести к общему знаменателю:
1. всем нитям присваиваются уникальные для данного сеанса связи идентификаторы.
2. По приходу, нить ставится в очередь на отправку.
3. Если на момент необходимости отправки нового пакета нет ожидающих отправки нитей, то создается новая нить.
4. В момент отправки пакета нить становится в очередь ожидаемых нитей.
5. Если получен пакет от нити, не стоящей первой в очереди ожидаемых, то все нити до нее считаются оборванными.
6. Если получен пакет от оборванной нити, то из этого пакета извлекаются остатки полезной информации и ответ на данный покет не посылается.
Уф... Вроде бы все, на первый взгляд. Если что еще вспомню - допишу.

[Danila-M]

Ну, в общем, обычная синхронизация часов по Эйнштейну... А остальное -- просто здравый смысл...

[Chist]

А я, собственно, ничего сверхестественного и не обещал
Собственно, синхронизация не нужна. Нужно определить сколько вреени назад эта информация соответствовала действительности.
По-моему, моя схема получилась лучше нежели WarBirth'овская. Она позволяет оценить задержку для каждого пакета и логично интегрируется в процесс обмена покетами. Хотя, с другой стороны, она несколько сложнее в реализации.