Подтвердить что ты не робот

Многопользовательская игра - расчет интерполяции клиентов?

Я создаю многопользовательскую игру, используя сокет io в javascript. В настоящий момент игра отлично работает в стороне от клиентской интерполяции. Прямо сейчас, когда я получаю пакет с сервера, я просто устанавливаю позицию клиентов в позицию, отправленную сервером. Вот что я пытался сделать:

getServerInfo(packet) {
     var otherPlayer = players[packet.id]; // GET PLAYER
     otherPlayer.setTarget(packet.x, packet.y); // SET TARGET TO MOVE TO
     ...
}

Итак, я установил позицию Target. И затем в методе "Обновление игроков" я просто сделал это:

var update = function(delta) {
    if (x != target.x || y != target.y){
        var direction = Math.atan2((target.y - y), (target.x - x));
        x += (delta* speed) * Math.cos(direction);
        y += (delta* speed) * Math.sin(direction);
        var dist = Math.sqrt((x - target.x) * (x - target.x) + (y - target.y)
                * (y - target.y));
        if (dist < treshhold){
            x = target.x;
            y = target.y;
        }
    }   
}

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

Изменить: я только что прочитал Gabriel Bambettas Статья по этому вопросу, и он упоминает это:

Скажите, что вы получаете данные о местоположении при t = 1000. Вы уже получили данные при t = 900, поэтому вы знаете, где игрок находился при t = 900 и t = 1000. Таким образом, из t = 1000 и t = 1100, вы показываете, что сделал другой игрок от t = 900 до t = 1000. Таким образом, вы всегда показываете фактические данные перемещения пользователя, за исключением того, что вы показываете 100 мс "поздно".

Это снова предполагало, что он точно опоздал на 100 мс. Если ваш пинг сильно варьируется, это не сработает.

Вы могли бы предоставить некоторый псевдо-код, чтобы я мог получить Идею о том, как это сделать?

Я нашел этот вопрос в Интернете здесь. Но ни один из ответов не дает пример того, как это сделать, только предложения.

4b9b3361

Ответ 1

Я полностью свежусь к многопользовательской клиентской/серверной архитектуре и алгоритмам, однако при чтении этого вопроса первое, что пришло в голову, - это использовать фильтры Kalman второго порядка (или выше) для соответствующих переменных для каждого игрока.

В частности, шаги Кальманского предсказания, которые намного лучше, чем простые мертвые расчёты. Также тот факт, что шаги прогнозирования и обновления Kalman работают как взвешенные или оптимальные интерполяторы. И, кроме того, динамику игроков можно было бы закодировать напрямую, а не играть с абстрактными параметризациями, используемыми в других методах.

Между тем быстрый поиск привел меня к этому:

Улучшение алгоритма мертвых расчетов с использованием фильтра kalman для минимизации сетевого трафика 3D-онлайновых игр p >

Резюме:

Онлайн-игры 3D требуют эффективной и быстрой поддержки взаимодействия с пользователем по сети, а сетевая поддержка обычно реализуется с использованием сетевой игровой движок. Сетевой игровой движок должен минимизировать задержка сети и смягчение перегрузки сетевого трафика. Чтобы минимизировать сетевой трафик между игровыми пользователями, прогноз на основе клиента (алгоритм мертвого расчета). Каждый игровой объект использует алгоритм для оценки собственного движения (также других объектов) перемещение), а когда ошибка оценки превышает порог, объект отправляет пакет UPDATE (включая позицию, скорость и т.д.) в другой юридические лица. По мере увеличения точности оценки каждый объект может минимизировать передачу пакета UPDATE. Чтобы улучшить точность предсказания алгоритма мертвых расчётов, мы предлагаем Kalman основанный на фильтрах метод подсчета мертвой точки. Чтобы показать настоящую демонстрацию, мы используйте популярную сетевую игру (BZFlag) и улучшайте оптимизированную игру алгоритм мертвого расчета с использованием фильтра Калмана. Мы улучшаем точность прогнозирования и снижение сетевого трафика на 12 процентов.

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

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

Идея состоит в том, что вместо правильного измерения вы просто обновляете предсказания Кальмана. Тактика аналогична целевым приложениям отслеживания.

Я сам порекомендовал их на stackexchange - потребовалось около недели, чтобы выяснить, насколько они актуальны, но с тех пор я успешно их реализовал в работе по обработке изображений.

(... это заставляет меня хотеть экспериментировать с вашей проблемой сейчас!)

Поскольку мне нужно больше прямого контроля над фильтром, я скопировал кого-то другого, выполняющего собственную реализацию фильтра Kalman в matlab в openCV (на С++):

void Marker::kalmanPredict(){

    //Prediction for state vector 
    Xx = A * Xx;
    Xy = A * Xy;
    //and covariance
    Px = A * Px * A.t() + Q;
    Py = A * Py * A.t() + Q;
}

void Marker::kalmanUpdate(Point2d& measuredPosition){

    //Kalman gain K:
    Mat tempINVx = Mat(2, 2, CV_64F);
    Mat tempINVy = Mat(2, 2, CV_64F);
    tempINVx = C*Px*C.t() + R;
    tempINVy = C*Py*C.t() + R;
    Kx = Px*C.t() * tempINVx.inv(DECOMP_CHOLESKY);
    Ky = Py*C.t() * tempINVy.inv(DECOMP_CHOLESKY);

    //Estimate of velocity
    //units are pixels.s^-1
    Point2d measuredVelocity = Point2d(measuredPosition.x - Xx.at<double>(0), measuredPosition.y - Xy.at<double>(0));  
    Mat zx = (Mat_<double>(2,1) << measuredPosition.x, measuredVelocity.x);
    Mat zy = (Mat_<double>(2,1) << measuredPosition.y, measuredVelocity.y);

    //kalman correction based on position measurement and velocity estimate:
    Xx = Xx + Kx*(zx - C*Xx);
    Xy = Xy + Ky*(zy - C*Xy);
    //and covariance again
    Px = Px - Kx*C*Px;
    Py = Py - Ky*C*Py;
}

Я не ожидаю, что вы сможете использовать это прямо, но если кто-нибудь встретит это и поймет, что "A", "P", "Q" и "C" находятся в состоянии-пространстве (подсказка подсказки, понимание состояния пространства - это предварительный запрос здесь), они, вероятно, увидят, как соединить точки.

(и у matlab, и у openCV есть свои собственные реализации фильтра Калмана, включенные кстати...)

Ответ 2

Этот вопрос остается открытым с запросом более подробно, поэтому я стараюсь заполнить пробелы в ответе Патрика Клужа. Он предположительно предположил, что вы передаете как текущее положение, так и текущую скорость в каждый момент времени.

Поскольку два положения и два измерения скорости дают систему из четырех уравнений, она позволяет решить систему из четырех неизвестных, а именно кубический сплайн (который имеет четыре коэффициента: a, b, c и d). Для того чтобы этот сплайн был гладким, первая и вторая производные (скорость и ускорение) должны быть равны в конечных точках. Существует два стандартных эквивалентных способа расчета: сплайны Hermite (https://en.wikipedia.org/wiki/Cubic_Hermite_spline) и сплайны Безье (http://mathfaculty.fullerton.edu/mathews/n2003/BezierCurveMod.html). Для двумерной задачи, такой как это, я предложил выделить переменные и найти сплайны для x и y на основе касательных данных в обновлениях, который называется зажатым кусочно кубическим сплайтом Эрмита. Это имеет несколько преимуществ перед сплайнами в ссылке выше, например, кардинальные сплайны, которые не используют эту информацию. Точки и скорости в контрольных точках будут совпадать, вы можете интерполировать до последнего обновления, а не раньше, и вы можете применить этот метод так же легко к полярным координатам, если игровой мир по своей природе полярный, как космические войны. (Другой подход, иногда используемый для периодических данных, состоит в том, чтобы выполнять БПФ и выполнять тригонометрическую интерполяцию в частотной области, но это не применимо здесь.)

То, что изначально появилось здесь, было выводом сплайна Эрмита с использованием линейной алгебры несколько необычным способом, который (если бы я не допустил ошибку), сработал бы. Тем не менее, комментарии убедили меня, что было бы более полезно дать стандартные имена для того, о чем я говорил. Если вас интересуют математические детали того, как и почему это работает, это лучшее объяснение: https://math.stackexchange.com/questions/62360/natural-cubic-splines-vs-piecewise-hermite-splines

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

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

Если мой компьютер сейчас не работает, вот где я бы поместил графику, похожую на те, что я отправил в TeX.SX. К сожалению, сейчас я должен отказаться от них.

Является ли это лучше, чем прямая линейная интерполяция? Определенно: линейная интерполяция даст вам прямые пути, квадратичные сплайны не будут гладкими, а полиномы более высокого порядка, скорее всего, будут переоборудованы. Кубические сплайны являются стандартным способом решения этой проблемы.

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

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

Ответ 3

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

Что касается вашей обеспокоенности в отношении скорости движения, я бы предложил вам включить текущую скорость и направление игрока в дополнение к текущей позиции в вашем пакете. Это позволит вам более плавно прогнозировать, где игрок будет базироваться на вашем собственном времени фрейма/времени обновления.

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

Если разрыв между симулированным и известным становится слишком большим, просто добавьте больше внимания к известному местоположению, а другойPlayer быстрее догонит.

Ответ 4

Обновление 1

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

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


Оригинальный ответ



Предположения

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

Важность этого предположения будет видна по мере дальнейшего решения.



Определения

  • MessageQueue: Всякий раз, когда клиент получает пакет с сервера, это очередь, в которой клиенты хранят пакет.
  • SequenceQueue: Сервер также следует за каждым пакетом для клиента с другой информацией, называемой SequenceNumber. Это очередь, в которой клиент хранит их.
  • SequenceNumber: - это GUID, и он сопоставим, поэтому мы можем заказать SequenceNumbers.
  • Получение пакета: - это событие, когда клиент получает пакет с сервера.
  • Передача пакета: - это событие, когда клиент фактически считывает и обрабатывает пакет, полученный с сервера.


Проблема

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



Решения

Решение № 1

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

(Я не предлагаю метод реализации этого подхода, если вы не попросите его.)


Решение №2

Резюме

Клиенты могут получать два типа сообщений - пакетный или порядковый номер. Когда клиент получает пакет, он отправляет на сервер сообщение, сообщающее, что он получил пакет. Только когда сервер получает подтверждение, что все клиенты получили пакет, сервер отправляет сообщение SequenceNumber для этого пакета, уведомляющего клиентов об обработке этого конкретного пакета. Это позволяет синхронизировать игроков.

-

Псевдокод/​​Реализация решения 2

Клиент может получать два типа сообщений с сервера: пакет и SequenceNumber.

Случай: Получен пакет

  • Если GUID уже присутствует в SequenceQueue
    • Если GUID пакета является наименьшим из всех в SequenceQueue, мы доставляем (читаем приведенные выше определения) этот пакет и удаляем информацию о последовательности из SequenceQueue
  • Если идентификатор GUID отсутствует в SequenceQueue, тогда
    • Клиент помещает этот пакет в MessageQueue
    • Клиент также отправляет сообщение серверу, в котором сообщается, что он получил этот конкретный GUID

Случай: Получен A SequenceNumber

  • Если это число является наименьшим из всех полученных последовательностей SequenceNumbers, и если ни один из пакетов не имеет меньшего SequenceNumber
    • Отменить этот SequenceNumber
    • Поставьте пакет для этого SequenceNumber из MessageQueue
  • Иначе этот SequenceNumber не будет самым маленьким SequenceNumber
    • Просто добавьте его в SequenceQueue

Два случая, написанные выше, достаточны для синхронизации игроков.



Примечания к закрытию

Решение 2 представляет собой реализацию "Sequencer". Цель состоит в том, чтобы получить общий порядок событий. Это концепции распределенных систем. Так как ваша игра работает с несколькими клиентами вместе с сервером, это, по сути, распределенная система. Следующие ссылки могут прояснить для вас концепции: