Статья Сетевые игры — «Ты помнишь, как всё начиналось?...»

Под катом — перевод первой части статьи What every programmer needs to know about game networking, об истории становления и принципах устройства мультиплеерных сетевых игр. Автор Glenn Fiedler.

Введение


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

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

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

Жёсткая синхронизация по пиринговым сетям


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

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

Конечно, такое объяснение слишком просто звучит и не раскрывает множество тонких моментов, однако наглядно демонстрирует идею работы современных RTS. Более подробно об этом можно почитать тут: 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond.

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

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

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

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

Несмотря на все эти ограничения, такая модель работы хорошо подходит для RTS и применяется в таких играх как Command And Conqurer, Age Of Empires, Starcraft. Причина в том, что игровое состояние в этих играх обычно включает в себя информацию о большом количестве объектов (юнитов), которую затратно целиком передавать по сети. Вместо этого отсылаются управляющие команды, влияющие на эволюцию этого состояния.

Тем временем, в других игровых жанрах прогресс не стоит на месте. Рассмотрим эволюцию action-игр, начиная с Doom, Quake и Unreal.

Клиент/сервер


В эру динамичных action-игр ограничения предыдущего подхода стали очевидны в игре Doom, которая хорошо работала только по локальной сети, и ужасно — по интернету:

Хотя возможно соединить по интернету две машины с работающим Doom, используя модем, игра получится медленной, варьируясь от совершенно неиграбельной (например, при PPP соединении 14.4Kbps) до с трудом играбельной (например, при соединении 28.8Kbps по протоколу SLIP со сжатием). Поскольку такие виды соединений имеют минимум практического применения, этот документ будет рассматривать только прямые соединения (faqs.org).

Несомненно, проблема была в том, что Doom проектировался для работы только по локальным сетям и использовал описанный выше подход для организации сообщения между машинами. На каждом шаге ввод игрока (нажатия клавиш, и т.д.) передавался с его машины на другие игровые узлы сети, и перед симуляцией очередного шага на каждой машине требовалось, чтобы были получены события ввода от всех остальных игроков. Другими словами, прежде чем двигаться или стрелять, надо было дождаться, пока от самого лагающего игрока поступят события ввода. Только представьте, как бы скрипели зубами те ребята, которые написали выше, что «такие виды соединений имеют минимальное практическое применение» .

Чтобы выйти за рамки LAN и не ограничиваться лишь хорошо работающими локальными сетями университетов и крупных компаний, нужно было менять модель сетевого сообщения. Именно это и сделал в 1996 Джон Кармак (John Carmack), выпуская Quake с использованием модели клиент/сервер вместо однорангового подхода.

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

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

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

Но и тут возникли проблемы:

В то время как я могу вспомнить и оправдать все мои решения, использованные в сетевой модели, начиная с Doom и заканчивая Quake'ом, суть была всегда одна — основные предположения, из которых я исходил при разработке, никуда не годились для хорошей интернет-игры. Изначально я рассчитывал на задержки соединения менее 200ms. Люди, имеющие цифровое подключение через хорошего провайдера, не испытывали трудностей в игре. К сожалению, 99% пользователей подключены через модем, и, как правило, через хренового перегруженного провайдера. Из-за этого задержки становятся равными как минимум 300ms. Клиент. Пользовательский модем. Сервер. Модем провайдера. Пользовательский модем. Клиент. Это полный отстой.

Пожалуй, грубовато выразился. У меня дома стоит T1, так что я был плохо знаком с жизнью на PPP. Теперь я буду иметь это в виду.

Конечно, проблемой стали задержки передачи данных.
То, что сделал Джон, когда выпускал QuakeWorld, изменило индустрию игр навсегда.

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


В оригинальном Quake'е всегда ощущалась задержка соединения между клиентом и сервером. Нажмите «вперёд» и будете ждать сколько угодно долго, пока пакеты дойдут до сервера и обратно, и потом только начнёте двигаться. Нажмите «огонь», и будете ждать столько же, пока вылетит пуля.

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

Эта проблема исторически была решена в два захода. Сначала Джоном Кармаком была разработана система прогнозирования на стороне клиента для QuakeWorld, позже доработанная и использованная в игре Unreal Тимом Свини (Tim Sweeney). Вторым этапом явилась система компенсирования задержек, разработанная Яном Бернье (Yahn Bernier) из Valve для CounterStrike. Остановимся на первой из двух частей — как прятать задержку между поступлением ввода от игрока и откликом игры.

Джон Кармак так писал в своих планах по поводу готовящейся к выходу QuakeWorld:

Теперь я позволил клиенту самому догадываться о результате движения игрока ещё до того, как придёт ответ от сервера. Это очень большое изменение в архитектуре. Клиент теперь должен различать сплошные объекты, знать про физические характеристики, такие как масса, трение, гравитация, и т.д. Мне грустно осознавать, что элегантная модель клиент/сервер в чистом виде уходит в прошлое, но я скорее практик, нежели идеалист.

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

После нажатия клавиши «вперёд» движение будет происходить сразу, и не придётся ждать, пока пакеты пропутешествуют от клиента до сервера, и обратно.

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

Теперь вы, возможно, удивитесь. Эй, как же так? Если клиент управляет движением персонажа, почему бы не сделать его главным в этом процессе? Клиент мог бы просто вычислять движение и отсылать на сервер необходимую информацию. Проблема в том, что если бы каждый клиент мог говорить серверу «вот тут моя текущая позиция», не составило бы никакого труда хакнуть клиент так, чтобы, например, постоянно уклоняться от ударов, или телепортироваться за спины других игроков, чтобы подстрелить их сзади.

Таким образом, необходимо, чтобы в таких играх сервер имел высший приоритет при управлении персонажами, несмотря на тот факт, что каждый игрок локально может предугадывает своё движение, чтобы избежать задержек. Как пишет Тим Свини в The Unreal Networking Architecture, «Сервер — это начальник».

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

Если бы клиент вносил коррективы без всяких изменений, «как есть», ему пришлось бы откатить всё, что он вычислил после того момента, и фактически вернуться назад во времени. Как обойти это, в то же время позволяя клиенту продолжать прогнозирование далее?

Решением является использование циклического буфера, в котором хранится информация о предыдущих состояниях игрока и событиях ввода. Когда клиент получает коррективы от сервера, он отбрасывает всю информацию, которая старше корректируемого момента времени, после чего заново пересчитывает состояния игрока, начиная от только что скорректированного, заканчивая последним спрогнозированным, при этом используя имеющуюся в буфере информацию о произошедших в этот период событиях ввода. Фактически клиент незаметно «перематывает назад и заново проигрывает» последние n кадров анимации персонажа, при этом оставляя весь остальной игровой мир фиксированным.

При таком подходе игрок может управлять своим персонажем без задержек, кроме того симуляция становится полностью детерминированной — даёт один и тот же результат на клиенте и сервере, и необходимость вносить коррективы появляется редко. Тим Свини так говорит об этом:

… лучшее из обоих вариантов: в любом случае сервер остаётся главным в процессе управления. Практически всё время симуляция движения игрока на клиенте в точности отражает то, что происходит на сервере, поэтому состояние игрока редко корректируется. Только в некоторых случаях, например, когда в игрока попадает ракета, или он сталкивается с противником, его позиция изменяется сервером.

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