Синхронизация состояний в многопользовательских играх

http://www.cakesolutions.net/teamblogs/how-does-multiplayer-game-sync-their-state-part-1
  • Перевод
image

Проблема многопользовательских игр


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

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

Обычно программа игры должна симулировать следующее:

изменения в окружении с учётом времени и вводимых игроками данных.

Игра — это программа, хранящая состояние, поэтому она зависит от времени (реального или логического). Например, PACMAN симулирует окружение, в котором постоянно перемещаются призраки.

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

Возьмём, например, классическую игру «Змейка»:

Предположим, что мы используем клиент-серверную архитектуру. Игровая логика работает следующим образом:

  1. Считывание вводимых игроком данных, изменяющих направление движения змейки. Они могут иметь одно из значений: [←, ↑, →, ↓].
  2. Применение вводимых данных в случае их наличия. Это изменяет направление движения змейки.
  3. Перемещение змейки на одну единицу измерения пространства.
  4. Проверка наличия столкновения каждой из змеек с врагом/стеной/своим телом, затем удаление их из игры.
  5. Повтор цикла.

Эта логика должна выполняться на сервере с постоянным интервалом. Как показано ниже, каждый цикл называется кадром (frame) или тактом (tick).

class Server {
  
  def main(): Unit = {
     while (true) {
        /**
        * 1. Считывание вводимых пользователем данных, имеющих одно из значений: [←, ↑, →, ↓].
        * 2. Применение данных при их наличии, при этом изменяется направление змейки.
        * 3. Перемещение змейки на одну единицу измерения пространства.
        * 4. Проверка столкновения с врагом/стеной/своим телом для каждой змейки, удаление их из игры.
        * 5. Передача нового состояния игры всем клиентам.
        */
        Thread.sleep(100)
     }
  }
}

Простейший клиент считывает обновления сервера и рендерит каждый полученный кадр для игрока.

class Client {
   def onServerUpdate(state: GameState) = {
      renderGameState(state)
   }
}



Обновление состояния с фиксированным шагом


Концепция


Для обеспечения синхронизации всех клиентов проще всего сделать так, чтобы клиент отправлял серверу обновления с фиксированным интервалом. Для примера возьмём интервал в 30 миллисекунд. Обновление содержит введённые пользователем данные, которые могут также содержать значение нет вводимых пользователем данных.

Получив вводимые данные от всех пользователей, сервер может перейти к следующему такту с учётом этих данных.


На рисунке выше показано взаимодействие одного клиента с сервером. Надеюсь, проблема для вас настолько же очевидна, как и для меня: клиент может простаивать на интервале от T0 до T1, ожидая для продолжения обновления с сервера. В зависимости от качества сети задержка может меняться в пределах от 50 до 500 мс, а современные игроки замечают задержки более 100 мс. Поэтому торможение интерфейса пользователя на 200 мс будет для некоторых игр огромной проблемой.

Это не единственная сложность подхода с фиксированным интервалом.



Рисунок выше немного более сложен, он демонстрирует взаимодействие с сервером нескольких клиентов. Видно, что у клиента B более медленное сетевое подключение, поэтому хотя A и B отправляют на сервер вводимые данные в T0, обновление от B достигает сервера в T2, а не в T1. Поэтому сервер продолжает расчёт только тогда, когда получит все обновления, то есть в T2.

Что это значит?
Задержка игры теперь равна задержке самого «лагающего» игрока.
Получается, что мы наказываем всех игроков потому, что у одного из них медленное соединение. Поэтому рано или поздно все игроки уйдут из вашей игры…

Не говоря уже о том, что есть вероятность отсоединения клиента B, которая заблокирует действия сервера до истечения таймаута соединения.

Обсуждение


Кроме двух вышеупомянутых проблем, есть ещё несколько:

  1. Клиент не будет отвечать, пока не получит обновление состояния от сервера (что ужасно с точки зрения пользователя).
  2. Отзывчивость игры зависит от самых «лагающих» игроков. Играете с другом по DSL? Удачи!
  3. Соединение будет очень «болтливым»: клиентам нужно регулярно отправлять бесполезные данные, чтобы сервер мог подтвердить, что у него есть вся необходимая для продолжения информация, и это неэффективно.

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

Для медленных игр небольшая задержка тоже приемлема. Хорошим примером может служить Farm Ville.

Ещё один хороший пример — шахматы, в которых два игрока ходят по очереди и каждый ход длится около 10 секунд.

  1. Пользователи должны ждать друг друга по 10 секунд. И они ждут.
  2. Два игрока делают ходы по очереди, поэтому задержка одного не влияет на другого.
  3. Каждый ход в среднем занимает 5 с (достаточно одного запроса каждые 5 секунд).

Но как насчёт быстрых игр? Например для всех FPS из-за таких проблем решение с фиксированными интервалами не подходит. В оставшейся части статьи мы узнаем, как решить эти проблемы.



Прогнозирование клиента


Давайте сначала решим проблему отклика игрока. Игра реагирует через 500 мс после того, как игрок нажал на кнопку, из-за чего игровой процесс рушится.

Как решить эту проблему?

Концепция


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

Предположим, для расчёта состояния игры в Tn нам нужно знать состояние в Tn-1 и введённые пользователем в Tn-1 данные.



Идея проста: давайте сделаем фиксированную скорость обновления, которая в нашем примере равна одной единице времени.

Клиент отправляет вводимые данные на сервер в T0 для эмуляции состояния игры в T1, поэтому клиент затем может рендерить игру, не ожидая обновления состояния от сервера, которое будет получено только в T3.

Такой подход работает только в следующих условиях:

  1. Обновления состояния игры детерминированы, т.е. нет никакой случайности или она прозрачна, и сервер с клиентом могут воспроизводить из одинаковых вводимых данных одинаковые игровые состояния.
  2. Клиент имеет всю информацию, необходимую для выполнения игровой логики.
  3. Примечание: 1 это не всегда верно, но мы можем попробовать сделать их как можно более похожими и игнорировать небольшие различия, например, вычисления с плавающей запятой на разных платформах, и использовать то же начальное число (seed) для псевдослучайного алгоритма.

Пункт 2 тоже не всегда верен. Я объясню:



На рисунке выше клиент A всё ещё пытается эмулировать состояние игры в T1 с помощью информации, полученной в T0, но клиент B в T0 уже отправил вводимые данные, о которых не знает клиент A.

Это значит, что прогноз клиента A о T1 будет ошибочным. К счастью, поскольку клиент A по-прежнему получает состояние T1 от сервера, он имеет возможность исправить свою ошибку в T3.

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

Разрешение конфликтов обычно называется согласованием (Reconcilation).

Реализация согласования зависит от конкретных условий использования. Я покажу простейший пример, в котором мы просто откажемся от прогнозирования и заменим его точным состоянием, получаемым от сервера.

  1. Клиенту нужно хранить два буфера: один для прогнозов, другой для вводимых данных. Его в дальнейшем можно использовать для вычисления прогнозов. Не забывайте, что состояние Tn вычисляется исходя из состояния Tn-1 и вводимых данных Tn-1, которые сначала будут пустыми.
  2. Когда игрок нажимает клавишу со стрелкой, вводимые данные сохраняются в InputBuffer, а клиент выполняет прогнозирование, которое затем используется для визуализации. Прогноз сохраняется в PredictionBuffer.


  3. В момент получения состояния State0 от сервера оно не совпадает с прогнозом Prediction0 клиента, поэтому мы можем заменить Prediction0 на State0 и пересчитать Prediction1с учётом Input0 и State0.
  4. После согласования мы можем безопасно удалить State0 и Input0 из буфера. Только после этого мы можем подтвердить, что всё правильно.

Примечание: согласование имеет недостаток. Если состояние сервера и прогноз клиента отличаются слишком сильно, то при рендеринге могут возникать визуальные ошибки. Например, если мы прогнозируем, что в T0 враг движется на юг, но в T3 мы понимаем, что он двинулся на север, то согласовываем данные простым использованием состояния с сервера. Враг скачком изменит своё направление, чтобы отобразить правильное положение.

Есть способы справиться с этой проблемой, но они не будут рассмотрены в этой статье.

Обсуждение


Техники прогнозирования на стороне клиента имеет огромное преимущество: клиент работате с собственной частотой обновления (независимой от частоты обновления сервера), поэтому когда сервер «тормозит», то это не влияет на частоту кадров на стороне клиента.

Но это неизбежно связано с определённой сложностью:

  1. Нам нужно обрабатывать больше состояний и логики на стороне клиента (буфер прогнозирования, буфер состояний, логика прогнозирования).
  2. Нам нужно определиться, как разрешать конфликты между прогнозом и реальным состоянием на сервере.

И у нас по-прежнему остаются старые проблемы!

  1. Ошибки визуализации из-за неверных прогнозов.
  2. Частый обмен бесполезными данными.

Заключение


В этой части мы рассмотрели всего два способа реализации сетевого соединения в многопользовательских играх:

  1. Обновление состояния с фиксированным шагом
  2. Прогнозирование на стороне клиента

Каждый из них имеет свой набор компромиссов, и мы всё ещё не рассмотрели подробнее то, что происходит на стороне сервера.

Интересные статьи по теме



Какова роль сервера?


Давайте начнём с определения действий сервера. Типичные задачи сервера:

а) Соединительная точка для игроков
В многопользовательской игре игрокам нужна общая конечная точка для связи друг с другом. Это одна из ролей серверной программы. Даже в модели связи P2P присутствует соединительная точка для обмена сетевой информацией для установки соединения P2P.
б) Обработка информации
Во многих случаях сервер выполняет код симуляции игры, обрабатывает все вводимые игроками данные и обновляет состояние игры. Стоит учесть, что так бывает не всегда: некоторые современные игры перекладывают большую часть обработки на сторону клиента. В этой статье я буду считать, что именно сервер несёт ответственность за обработку игры, т.е., например, за создание тактов игры.
в) Единый источник истинного состояния игры
Во многих многопользовательских играх серверная программа также имеет власть над состоянием игры. Основная причина этого — защита от читерства. Кроме того, гораздо легче ориентироваться, когда есть единственная точка для получения правильного состояния игры.

Наивная реализация сервера


Давайте начнём реализацию сервера самым прямолинейным способом, а затем усовершенствуем его.

Ядром игрового сервера является цикл, выполняющий обновление GameState на основании вводимых пользователями данных. Этот цикл обычно называется TICK (такт) и обозначается следующим образом:

(STATEn , INPUTn) => STATEn+1

Упрощённый сниппет кода сервера может выглядеть так:

def onReceivedInput(i: UserInput) = {
  storeInputToBuffer(i)
}

while(!gameEnded) {
  val allUserInputs = readInputFromBuffer()
  currentState      = step(currentState, allUserInputs)  // т.е. (STATEn , INPUTn) => STATEn+1
  sendStateToAllPlayers(currentState)
}

Обсуждение


Надеюсь, сниппет кода выглядит для вас интуитивно понятным и прямолинейным: сервер просто принимает вводимые данных из буфера и применяет их в следующей функции TICK для получения нового состояния GameState. Давайте назовём этот подход жадным игровым циклом, потому что он пытается обработать данные как можно быстрее. Это нормально, если не задумываться о нашей несовершенной Вселенной, в которой солнечный свет достигает Земли за восемь минут.

Здесь снова становится важной задержка.

Тот факт, что сервер обрабатывает вводимые данные из буфера каждый TICK означает, что GameState зависит от задержки сети. На схеме ниже показано, почему это становится проблемой.



На схеме показаны два клиента, отправляющие вводимые данные серверу. Мы видим два интересных факта.

  1. Запросы занимают разное время между разными клиентами и сервером: 1 единицу времени от клиента A до сервера, 1,5 единицы времени от клиента B до сервера.
  2. Запросы занимают разное время для одного клиента: первый запрос занял 1 единицу времени, второй — 2 единицы времени.

Если говорить вкратце, то задержка непостоянна, даже для одного и того же соединения.

Непостоянная задержка в сочетании с жадным игровым циклом приводят к нескольким проблемам. Мы рассмотрим их ниже.

Не работает прогнозирование на стороне клиента


Если мы не можем спрогнозировать время получения сервером вводимых данных (из-за задержки), мы не можем делать прогнозов с высокой точностью.

Игроки с низкой задержкой получают преимущество


Если вводимые данные быстрее попадают на сервер, то они будут обработаны быстрее, что создаёт нечестное преимущество для игроков с быстрыми сетями. Например, если два игрока одновременно выстрелят друг в друга, они должны будут убить друг друга тоже одновременно, но игрок B имеет меньшую задержку, поэтому убивает игрока A ещё до того, как команда игрока A будет обработана.
Для сглаживания непостоянной задержки существует простое решение — рассмотренное выше обновление с фиксированным шагом. Сервер не продолжает вычисления, пока не получит вводимые данные от всех игроков. У такого подхода есть два преимущества:

  1. Не требуется прогнозирование на стороне клиента
  2. У всех игроков будет та же задержка, что и у самого медленного игрока, что устраняет вышеупомянутое преимущество.

Однако этот подход не работает в быстрых активных играх из-за низкой отзывчивости.

В следующем разделе мы поговорим о том, как заставить сторону сервера работать в быстрых играх.

Согласование на сервере


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

Один возможный способ реализации этого — позволить клиенту предлагать, когда необходимо применить вводимые данные. Таким образом, сторона клиента сможет точно предсказывать время их применения. Термин «предлагать» использован, потому что сервер может отклонить это предложение, если оно неверно, например, игрок пытается произнести заклинание, хотя у него закончилась мана.

Вводимые данные должны применяться почти сразу после ввода данных игроком, например, Tinput+ X, где X — задержка. Точное значение зависит от игры, для отзывчивости обычно необходима задержка менее 100 мс. Заметьте, что X может быть и нулём. В таком случае данные применяются сразу же после ввода пользователем.

Давайте примем X = 30 мс, что примерно равняется одному кадру при 30 кадрах в секунду. Для передачи на сервер данным требуется 150 мс, тогда существует большая вероятность того, что когда вводимые данные достигнут сервера, кадр для ввода уже будет пропущен.



Посмотрите на схему: пользователь A нажал клавишу в T. Эти данные должны обработаться в T + 30 мс, но вводимые данные из-за задержки получены сервером в T + 150 мс, что уже находится за пределами T + 30 мс. Решением этой проблемы мы займёмся в данном разделе.

Как сервер применяет вводимые данные, которые должны были случиться в прошлом?

Концепция


Вы наверно помните, что прогнозирование на стороне клиента имело ту же проблему с неточными прогнозами из-за недостатка информации о противниках. Неверные прогнозы позже корректировались обновлениями состояния с сервера с помощью согласования. Ту же технику можно использовать здесь. Единственная разница в том, что мы исправляем GameState на сервере на основе данных, вводимых клиентами.

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


Примечание: на первой пунктирной линии Time X на стороне клиента, но Time Y на стороне сервера. Это интересная особенность многопользовательских игр (и многих других распределённых систем): поскольку клиент и сервер работают независимо, время на клиенте и на сервере обычно отличается. Наш алгоритм позволяет справиться с этой разницей.

На схеме выше показано взаимодействие между одним клиентом и сервером.

  1. Клиент отправляет вводимые данные с меткой времени, сообщая серверу, что эти данные клиента A должны произойти в Time X.
  2. Сервер получает запрос в Time Y. Положим, что Time X раньше, чем Time Y. При разработке алгоритма надо принять, что Time Y больше или меньше Time X, это обеспечит нам большую гибкость.
  3. Красное поле — это момент выполнения согласования. Сервер должен применить Input X к последнему состоянию игры, чтобы казалось, что ввод Input X произошёл в Time X.
  4. Передаваемое сервером GameState тоже содержит метку времени, которая необходима для согласования и стороны сервера, и стороны клиента.

Подробности согласования (красное поле)


  1. Сервер должен хранить

    • GameStateHistory — историю состояний GameState в течение кадра времени P, например, все GameState за последнюю секунду.
    • ProcessedUserInput — историю вводимых данных UserInput, обработанных за кадр времени P, например, то же значение, что и кадр времени GameStateHistory
    • UnprocessedUserInput — полученные, но ещё не обработанные UserInput, тоже в кадре времени P

  2. Когда сервер получает от пользователя вводимые данные, они должны вставляться в UnprocessedUserInput.
  3. Затем, в следующем кадре сервера

    1. Выполняется проверка на наличие вводимых данных в UnprocessedUserInput, которые старше текущего кадра
    2. Если их нет, то всё в порядке, просто выполняется игровая логика с последним GameState и соответствующими вводимыми данными (при их наличии), и трансляция клиентам.
    3. Если они есть, то это значит, что часть ранее сгенерированных игровых состояний ошибочна из-за отсутствующей информации, и нам нужно это исправить.
    4. Сначала нам надо найти самые старые необработанные вводимые данные, допустим во время Time N, (подсказка: эта операция выполняется быстро, если UnprocessedUserInput  отсортирован).
    5. Затем нам нужно получить соответствующее состояние GameState в Time N из GameStateHistory и обработанные вводимые данные в Time N из ProcessedUserInput
    6. С помощью этих трёх фрагментов данных мы можем создать новое, более точное GameState.
    7. Затем перемещаем необработанные вводимые данные Unprocessed Input N в ProcessedUserInput, чтобы можно было использовать их в будущем для согласования.
    8. Обновляем GameState N в GameStateHistory
    9. Повторяем шаги с 4 по 7 для N+1, N+2 ..., пока не получим последнее GameState.
    10. Сервер отправляет свой последний кадр всем игрокам.

Обсуждение


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

Кроме того, неверные GameState иногда приводят к ужасным скачкам UI. На схеме ниже показано, как это происходит.



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

Возможно, я преувеличиваю это влияние, иногда объект двигается не так далеко и скачок менее заметен, но во многих случаях он всё равно очевиден. Мы можем контролировать скачки, меняя размер GameStateHistory, UnprocessedUserInput и ProcessedUserInput. Чем меньше размер буфера, тем меньше будут скачки, потому что мы будем менее терпимы к сильно запаздывающим вводимым данным. Например, если вводимые данные запаздывают более чем на 100 мс, то они игнорируются, а игрок с пингом > 200 мс не сможет играть в игру.

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

Есть одна популярная техника для борьбы с проблемой неточных Game State — это интерполяция объектов (Entity Interpolation). Идея заключается в сглаживании скачков растягиванием их на короткие промежутки времени.


В этой статье я не буду описывать подробности реализации интерполяции объектов, однако приведу полезные ссылки в конце.

Подводим итог


Мы обсудили способы работы клиентов и сервера в многопользовательских играх.


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

Заключение


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

Спасибо за чтение, удачного хакинга!

Ссылки и дополнительное чтение


Метки:
Поделиться публикацией
Похожие публикации
Комментарии 38
  • 0
    В игре Teeworlds именно так все и сделано. Есть некое «ядро» игры, в котором ведутся все основные расчеты физики мира. Это ядро используется одновременно на сервере и на клиенте (для предсказаний). Вдобавок файлы с его кодом используются при расчете специального хеша. При подключении клиента к серверу эти хеши сверяются, и если они не совпадают, значит на клиенте и на сервере используются разные, скорее всего несовместимые версии игры.
    Правда, последний момент не слишком удобен для игр без автообновления. В некоторых версиях разработчики сами костыль ставили, чтобы передавался старый хеш.
    • 0
      Лучше у Варгейминга статью на эту тему напишите.
      Насколько помню серваков у них только для одних танков 10 штук.
      • 0
        Танки это скушно :)
        Во-первых скорость по меркам FPS/MMORPG низкая, во-вторых количество игроков в сессии жестко лимитировано.
        • –4
          С технической точки зрения, было бы интересно узнать!
          Только в росийском регионе одновременно онлайн у них там несколько сот тысяч игроков.
          Это Вам не Рыбалка с 60-70 игроками онлайн)))
          • +4

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

      • +4
        Ну есть ещё чисто «игромеханические» трюки, позволяющие сглаживать скачки. В первую очередь анимации действий, тех же скиллов, выстрелов, резких поворотов и т.д. Ну, вы же не можете в реальности бежать влево и внезапно, тут же, побежать вправо. У вас будет вполне себе задержка на торможение, разворот и разгон. Вот это время можно и нужно закладывать в анимации. У игроков с быстрым пингом анимации отработают как надо, у лагающих — будут дёргаться, но сами позиции объектов не будут слишком сильно скакать.
        • 0
          В качестве классического примера решения задачи предсказания действий игрока интересующимся можно посоветовать взглянуть на механику многопользовательской игры первого Quake. Вот обзор его исходного кода, смотреть часть «Прогнозирование». Насколько мне известно, это было одно из первых решений такого рода в игровой индустрии.
          • +1
            Перечитывал этот абзац много раз, что-то трудно воспринимается:
            Это значит, что мы не можем применить необратимые последствия, например, убийство игроков. Такие необратимые последствия можно применять только когда они поступают из GameStateHistory, т.е. когда их больше нельзя перезаписывать.
            This means we cannot apply irreversible outcomes, i.e, killing a players, such irreversible outcomes will only be applied when it goes out of the GameStateHistory, ie. when it cannot be rewriten anymore.
            Кто в теме, объясните пожалуйста подробней, а то чувствую от меня ускользает полное понимание этой идеи.

            Логично выглядит так, что если в серверном буфере GameStateHistory например в GameState N записано что определённого игрока уже замочили, а затем происходит согласование на сервере (появились данные в UnprocessedUserInput которые старше текущего кадра) и будут обновлены GameState N+1, N+2,… — то этот игрок уже никак не может «ожить», это необратимое последствие, перезаписывать в этой ситуации нельзя.

            А если наоборот, например в GameState N записано что определённый игрок жив, но затем после согласования (появились данные в UnprocessedUserInput которые старше текущего кадра, скажем от клиента с медленным соединением) оказывается что в следующем GameState N+1 его замочили, то перезаписывается, нельзя же ему оставаться бессмертным :) Это будет выглядеть «как смерть из-за угла», у Valve доках это следствие применения Lag Compensation: For instance, if a highly lagged player shoots at a less lagged player and scores a hit, it can appear to the less lagged player that the lagged player has somehow «shot around a corner».

            Правильно ли, что описанная тут методика согласования, является попыткой обобщить Lag Compensation, который специфичен именно для шутеров?
            • 0
              Отличная статья, давно было интересно как происходит работа игрового сервера.

              Очень хочется видеть продолжение с более сложными алгоритмами, которые применяются в более быстрых играх (шутеры, ММОРПГ)
              • +2

                FYI: Я переводил статьи Gabriel Gambetta(которые вы рекомендовали к прочтению):
                https://habrahabr.ru/post/302394/

                • 0
                  Это не я рекомендовал, а автор статьи. Спасибо за ссылку, попозже добавлю в перевод.
                • 0
                  А все эти сложности точно нужны? Здесь есть одна компания, которая как раз продаёт тупые клиенты «передай клавиши по сети, получили видео обратно», и вроде бы у неё хватает клиентов. Значит это не принципиально?
                  • 0
                    Если лаги в вашей игре не портят игровой процесс, то можно не заморачиваться. Но в играх где нужно стрелять и быстро реагировать на действия других игроков, без этого будет просто ад.
                    • 0
                      Насколько я понял, это решение рекламируется для всех игр. Правда игроки к рекламе относятся скептически.
                      • 0

                        Я играл, мне не понравилось. Хотя я в Питере, а сервера в Москве, ощущение лага не проходило ни на секунду(пинг около 50).

                  • 0
                    Было дело, ради фпс резал графику. ММОшником был.
                    • 0

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


                      Как наиболее надежно сообщить серверу, в какой именно момент на клиенте произошли действия?

                      • 0

                        В IV части вы найдете все ответы( https://habrahabr.ru/post/302394/ ), но возможно стоит просмотреть так же предыдущие части чтобы убедиться что вы все правильно понимаете.

                        • 0
                          Текущий алгоритм работы мультиплеера
                          • Сервер получает команды с клиентов и времена их отправления
                          • Сервер обновляет состояние мира
                          • ...

                          Да, читал всё части, но как раз-таки остаётся вопрос: как передать время отправления команд на клиенте таким образом, чтоб его невозможно было подделать?
                          То есть каким образом сервер может удостоверится, что команда на клиенте действительно была выполнена в заявленный момент.
                          Просто напрашивается батальный чит: получаем от сервера актуальное состояние S(t), а команды шлем как будто мы видели состояние S(t-1). И всё, мы всегда на один шаг впереди остальных.

                          • 0
                            Для надёжности можно читить вдвоём. Один читер живёт в будущем, другой эмулирует большую задержку и живёт в прошлом. Тогда читер из будущего может открывать данные для читера из прошлого.
                            • 0

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

                              • 0
                                Так никто не мешает получить эту информацию на другой клиент.
                                • 0

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

                                  • 0

                                    Вами описанный сценарий — это сервер без согласования ("наивная реализация" из данной статьи). То есть как только команда пришла от клиента, она сразу выполняется "окончательно".
                                    И тогда игроки с меньшим пингом имеют преимущество над остальными, что не всегда приемлемо.
                                    Согласование подразумевает, что сервер может "переиграть" историю если более медленный клиент выполнял команды в то время.
                                    Например, это заметно в некоторых ММО: жизни персонажа падают до 0, но умирает персонаж несколько позже, видимо когда сервер дождался всех медленных клиентов.

                                    • 0

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


                                      А вот компенсация лага — другое дело (см. https://habrahabr.ru/post/303006/). Но в моей статье как раз и написано, что выстрел происходит так: сервер откатывает состояние мира назад, проверяет попал ли выстрел, возвращается обратно к текущему состоянию(не переприменяет команды, а просто возвращается), а затем применяет эффект от попадания или промаха, в зависимости от того, попал выстрел. Таким образом бессмертия не достичь, так как:
                                      1) если игрок умер, такой методой его уже не воскресить.
                                      2) применяется компенсация лага только для темпорально критичных действий(таких как выстрел).

                                      • 0

                                        Я собственно ссылался на текущую статью, где есть отдельная глава "Согласование на сервере". И на сколько я понимаю это несколько отличается от "компенсации лага".


                                        Но это не меняет сути моего вопроса. Что при согласование на сервере, что при компенсации лага клиент должен как-то сообщить серверу "что он видел" в момент выполнения команды.
                                        Так вот как это сделать наиболее надежно от подделок?

                                        • 0

                                          Я знаю что такое согласование. Нет, клиент не должен сообщать серверу что он видел, клиент только отправляет команды. Перечитайте еще раз, возможно посмотрите на мои статьи(https://habrahabr.ru/post/302834/)

                                    • 0
                                      > Если информация о выстреле дошла на какой-либо клиент, он уже произошел на сервере

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

                                        Нет, не будут. Команды не сбрасываются из-за изменения мира(нигде такого не было написано).


                                        Например, при выстреле произойдут следующие проверки:
                                        1) Жив ли персонаж сейчас?
                                        2.1) откатить время назад
                                        2.2) может ли персонаж стрелять?
                                        2.3) попал ли персонаж при выстреле во врага?
                                        2.4) вернуть время назад
                                        3) если все проверки прошли, наносим урон врагу


                                        При передвижении произойдет следующее(предположим, что игрок контролирует персонажа только на земле)
                                        1) На земле ли персонаж? (в настоящем времени)
                                        2) Если на земле, изменить скорость в соответствии с пользовательским вводом


                                        Итог: сервер никогда не меняет прошлое. Сервер иногда заглядывает в него, чтобы синхронизировать моменты, требующие особой точности.

                                        • 0
                                          1) Жив ли персонаж сейчас?

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

                                          2) Игрок повернул влево. Но он уже по инерции вошёл в стену и поворачивать не может.

                                          и т.д.

                                          Хотелось бы математически строго описания переключения состояний онлайн игры. Как народ любит заморачиваться для распределённых систем.
                                          • 0

                                            1) Ну вот так вот обычно делают. Если хотите, можете проверку смерти сделать в прошлом, а значит применить выстрел. Все равно выстрел применится в настоящем. Да, враг умрет, но и вы тоже умрете.
                                            А вот у игроков будет ощущение того, что что-то пошло не так, т.к. обоюдные убийства в игре с hitscan оружием поспринимаются как признак забагованности.


                                            2) Вы не правы. Если клиентское согласование работает корректно, персонаж двигается по одинаковым траекториям что на сервере, что на клиенте. При этом персонаж мгновенно реагирует на ввод игрока.


                                            Хотелось бы математически строго описания переключения состояний онлайн игры.
                                            Если сделаете — будете первым, на сколько я знаю. Только учтите, что стоит формально описывать существующий механизм, а не тот, который вы придумали, ну либо сначала проверить, что ваша идея действительно лучше.
                                            • 0
                                              > Да, враг умрет, но и вы тоже умрете.

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

                                              Тут важно понимать, что реальности разошлись, и что склеивать их надо согласно какому-то компромиссу. Например, убивая обоих игроков ради справедливости.

                                              2) Это пока состояние клиента_1 не наблюдает клиент_2. А если, например, клиент_1 заморгал на радаре клиента_2, то обратно ему пути нет, если он хочет соблюсти непротиворечивость. Хотя, конечно, лучше оставить противоречие, как неизбежную цену за многопользовательский режим.

                                              > Только учтите, что стоит формально описывать существующий механизм,

                                              Математика так не работает. Сначала делается понятная и удобная абстракция, а потом уже ищется как применить её к реальности. Наоборот можно, только когда у тебя уже есть десяток абстракций, и ты подбираешь сочетание инструментов наиболее подходящих для твоей задачи.
                                              • 0
                                                Можно, конечно, понизить в правах лагающего, тогда страдать будет только он, но лучше так не делать.

                                                Повторюсь, обычно так и делают — понижают лагающего в правах.


                                                Dota в данном контексте лучше не вспоминать, там нет ни client side prediction, ни lag compensation. А смерть после телепорта видимо происходит если они прямо в одном кадре произошли.


                                                Математика так не работает. Сначала делается понятная и удобная абстракция, а потом уже ищется как применить её к реальности.

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

                                                • 0
                                                  > Dota в данном контексте лучше не вспоминать, там нет ни client side prediction, ни lag compensation.

                                                  Я удивлён. Прям в этой же статье дана ссылка на статью валве про client-side preditction.

                                                  На всякий случай продублирую:

                                                  https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking
                                                  http://www.dota2.com/reborn/part3

                                                  > Математика прекрасно так работает.

                                                  Ни разу не встречал. Обычно математика описывает что-то не слишком рабочее. А потом уже программист натягивает это на реальность.

                                                  Кстати, я тут подумал ещё об одном виде игр — гоночках. Если в шутерах у тебя есть три подзадачи:
                                                  а) стратегическая — выбрать подходящий инструмент и огневой рубеж
                                                  б) мышкокликерство — попасть прицелом точно в противника. Может быть усложнена, если игра включает баллистику.
                                                  в) игра на реакцию, как в вестернах, где три ковбоя одновременно наставили друг на друга по пистолету.

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

                                                  Далеко не все конфликты временных линий неразрешимы. Смерть — как раз такой пример. А обычные виражи при движении считаются не такими важными и их допустимо менять в прошлом.

                                                  А вот как быть в гоночках? Там же каждый момент важен. Если вы стартуете одновременно с противником и видите себя в настоящем, противника — в прошлом, то он ещё стоит на месте. И у вас возникает искушение подрезать его. Он поступает зеркально. В результате — крушение.
                                                  • 0

                                                    У Valve конечно же есть технология клиентского согласования. Но в доте она почти не используется, только вызывается отработка анимации.
                                                    Например, передвижение персонажа не предсказывается(как минимум, не предсказывалось в 2015 году, после выхода reborn)
                                                    https://www.youtube.com/watch?v=fWaVcWNh3Ro&t=729s


                                                    Ни разу не встречал. Обычно математика описывает что-то не слишком рабочее.

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


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

                                                    Да, так и стараются делать.


                                                    А вот как быть в гоночках? Там же каждый момент важен.

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

                                          • 0

                                            Как-то не очень конструктивна получается дискуссия. Попробую объяснить своё видение.


                                            Возьмём абстрактную игру и события во времени:


                                            • t(0) — есть некий игрок (И), у которого 10 из 100 ед. жизней ("чуть живой");
                                            • t(1) — другой игрок лекарь (Л) жмет кнопку "вылечить И на 10 ед";
                                            • t(2) — третий игрок убийца (У) жмет кнопку "ударить И на 10 ед";
                                            • t(3) — у У быстрый интернет и его команда прилетает на сервер первой;
                                            • t(4) — у Л медленный интернет, его команда пришла второй;

                                            Вопрос: что произойдёт с И?
                                            По вашему получается, что И будет мертв, а Л получит отказ (пытался лечить мертвого).
                                            В итоге игрок с быстрым интернетом получает преимущество.


                                            Я же считаю, что И должен остаться при 10 ед. жизней (10 начальных + 10 вылеченных — 10 ударенных), так как лекарь отправил команду раньше.
                                            Даже если в момент t(3) сервер разослал всем клиентам что у И 0 жизней, он должен иметь некий "grace period" и если позже пришла запоздалая команда, то переиграть историю.


                                            От сервера, я соответственно ожидаю состояния:


                                            • t(0) — у И 10 ед. жизней;
                                            • t(1) — у И 10 ед. жизней;
                                            • t(2) — у И 10 ед. жизней;
                                            • t(3) — у И 0 ед. жизней, но он всё ещё жив (ждем немного, авось кто-то опаздывает с лечением);
                                            • t(4) — у И 10 ед. жизней;

                                            А если лечение не прилетело, то где-нибудь в t(5) отправляем клиентам что И мертв окончательно.


                                            Или я мыслю слишком утопично? По аналоги можно смоделировать ситуации с движением, выстрелами в дверной проём и прочим.


                                            Так вот что, собственно, меня будоражит: как достоверно сообщить серверу, в какой именно момент произошла отправка команды с клиента?
                                            Как серверу проверить, что Л действительно отправил команду в t(1), а не в t(3) и прикинулся медленным?

                                            • 0

                                              Да, игрок с более быстрым пингом получает преимущество.
                                              В вашей схеме с ожиданием основные проблемы:
                                              1) Стреляющий игрок гораздо хуже чувствует время, которое ему нужно потратить на убийство(это очень важная метрика, пруф: https://www.youtube.com/watch?v=EtLHLfNpu84). Что увеличивает чувство лага.
                                              2) Игрок дольше чувствует себя живым, хотя на самом деле он мертв(и чаще он действительно умирает, а не оказывается чудесным образом спасен), что тоже увеличивает чувство лага.


                                              Или я мыслю слишком утопично?
                                              100% справедливости вы никогда не достигните, ведь игроки живут рассинхронизированных, немного отличающихся мирах.
                                              Самое важное в мультиплеере — это иллюзия одновременности, а не сама одновременность. И поэтому выбор обычно делают в сторону уменьшения самых заметных проблем.

                                              И да, сервер не может проверить что Л действительно отправил команду в t(1). Нет достоверного способа отличить пакет, который шел дольше обычного, от позже отправленного пакета. Так что стоит разрабатывать геймдизайн, который уменьшает профит от такого мухлежа.

                            • 0
                              Из текста не очевиден момент:

                              Как определить в какой момент пользователь сделал какое-либо действие, если у нас нет его времени (отправки сообщения), а есть только серверное, то есть время, когда его запрос пришел на сервер?

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.