[Статья Armin Ronacher о принципах вычисления коллизий в сетевых шутерах. Носит скорее обзорный и исследовательский, нежели технический характер. Здесь и далее в квадратных скобках примечание переводчика]

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

Немного контекста

Должен признать, после того как вышла Bad Company 2 и, теперь уже, Battlefield 3, я спустил просто ужасающее количество времени на эту серию. А всякий раз, когда я понимаю, что трачу время на бесполезную ерунду, я пытаюсь получить от этой ерунды хоть что-нибудь, что можно было бы использовать в будущем.

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

Что касается Battlefield, мне стало интересно, как работает сетевая часть. В основном из-за того, что эта игра одну вещь делает совсем не так, как все из того, во что я играл раньше — каждая выстрелившая тут пуля имеет ускорение и вполне подвержена воздействию гравитации. Конечно концепция снарядов сама по себе не нова, но очень редкая игра пытается ввести для снарядов еще и компенсацию времени отклика. Вообще-то я не могу вспомнить ни одной игры кроме Bad Company 2 и Battlefield 3, которые делали бы это, но это, очень может быть, просто сказывается недостаток моих знаний в этой области.

Чертова физика.

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

Есть три способа выйти из этой ситуации. Первый – в вашу игру будут играть только по локальной (местной) сети, где задержки пренебрежительно малы, второй – вы можете попросту игнорировать эту проблему и позволить игрокам разбираться с их «лагами» самостоятельно. Третье решение – использовать для компенсации задержки какие-нибудь хитрые трюки.

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

Так что все, что делают игры – на самом деле просто фокусы, заставляющие игроков поверить в то, что нет никаких лагов. Для большинства игр вы даже не заметите задержку в 150 мс (это ведь совсем ничего по сравнению с общим временем, проводимым в игре). Быть может вы почувствуете как с увеличением времени отклика падает производительность, но привязать это падение производительности к сетевым задержкам сможете только если обладаете некоторым опытом.

Основы

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

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

Предположим, что сервер работает на 20 герцах и для каждого пересчета клиенту отсылается пакет. А клиенту надо на каждый пришедший пакет отрендерить три кадра. Вся штука с интерполяцией заключается в том, что она может оперировать только уже существующими данными. Значит предполагая на клиенте 60 герц, мы получаем примерно 16 миллисекунд на кадр, и если клиент интерполирует ситуацию между пересчетами сервера, то с каждым пакетом у нас будет 48 мсек уже прошедшего времени для интерполяции.

[я так понимаю имеется в виду, что при интерполяции происходит пост-обработка. Приходит пакет и на его основании строится уже прошедшие на самом деле три кадра, т.е. в приведенном примере ВСЕГДА будет отставание в те самые 48 мсек.]

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

Со всем вот этим у нас появляется отличный базис для моделирования повторяющихся движений других игроков. Но что делать с игроком локальным? Если локальный игрок захочет начать движение, затем отправит свои намерения на сервер и будет ждать, пока его команда на начало движения (подтвержденная) вернется обратно, прежде чем на самом деле начать двигаться, будет очень большой лаг. Решением этой является своеобразная «предсказательность» на клиентской части. В компьютерных играх к этой концепции часто относят термин Dead Reckoning (навигационное счисление). В статическом мире, где нет ничего, кроме изменений самого игрока, можно с уверенностью сказать, что клиент может просто игнорировать сервер для просчета собственных движений и имитировать начало движения в тот самый момент, когда была нажата клавиша.

А если моделирование на клиенте и сервере перестанет совпадать, вы получите артефакты, вроде коротких телепортаций игрока. Почему оно может перестать совпадать? Обычно такое случается, когда с игроком (на сервере) происходит что-то, чего клиент просто не мог предсказать. Например игрок может столкнуться с другим игроком. Или встать сверху на транспортное средство, которым управляет не он.

Машина времени.

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

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

Я попал?

С движениями все ясно, а вот со стрельбой пока совсем нет. В Quakeworld, например, задержки на движении игроков были замечательно скомпенсированы благодаря «предсказательности», но игроку приходилось стрелять на опережение, чтобы самостоятельно скомпенсировать задержку на стрельбе. Смотрите – если у стрелка возникает 100 миллисекундный лаг и он хочет выстрелить в другого игрока, движущегося со скоростью 100 условных единиц в секунду, игрок должен целиться в точку на земле за десять условных единиц до бегущего, для того, чтобы попасть в него. Раздражает.

Если же вы играете в современный шутер – это больше не проблема. Так как оно работает? В принципе – почти так же. Для того, чтобы определить, что игрок задел что-то выстрелом, клиент передает на сервер саму цель и намерение игрока выстрелить. Сервер считает разницу во времени, «возвращается в прошлое» на уже посчитанное время и проверяет – попал ли стрелок во что-нибудь. Если попал, то к цели «применяется» урон.

Однако, у этого метода есть два «но». Прежде всего, такой метод работает только с бесконечно быстрым оружием (hitscan), потому что в этом случае на самом деле не создается и не начинает бороздить время и пространство, собственно, пуля. Второе но – если у стрелка случился лаг в, скажем, 200 мсек, то человек, который должен был получить этот выстрел, вполне мог за эти 200 миллисекунд успеть забежать за укрытие. А благодаря тому, что стрелок, как бы, стреляет из будущего в прошлое, забежавший, уже было, за укрытие игрок вдруг умирает, потому что на момент выстрела был ясно виден стрелку.

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

Настоящие пули.

Первая проблема Battlefield в том, что он создает пули. В Quake и других играх в матче участвуют порядка 16 игроков. Каждый раз когда вы пытаетесь узнать, получил ли кто-нибудь пулю, сервер просто возвращает всех игроков на правильные (с точки зрения задержки клиента) позиции, интерполирует время и наблюдает – получил кто пулю, или нет. Даже с очень «многопулевым» оружием это не создает особых проблем, особенно если вы можете немного схитрить и запихать несколько пуль в один сетевой пакет. Конечно и раньше были игры, променявшие старый добрый hitscan на снаряды, но они не вводили никакой компенсации задержки и делали снаряды сравнительно медленными. И это вот сильно затрудняло игру при большом пинге. Попробуйте как-нибудь поиграть в Team Fortress 2 с медицинской пушкой, на далеком-далеком сервере с большим пингом. Посмотрим, как у вас будет получаться =).

Однако в Battlefield, стреляя, вы создаете настоящие пули. Время жизни каждой пули около 1,5 секунд, а для пули, выпущенной из снайперской винтовки, – целых пять секунд. Учитывая, что большая часть оружия – штурмовые винтовки, мы получаем что-то около 700 выстрелов в минуту с очень большим количеством вероятных промахов. Более того: карты здесь настолько огромные, что большая часть пуль будет лететь весь отведенный им срок (а это, как мы помним, 1,5 секунды) перед тем, как их удалят со сцены. А самое жуткое то, что при все при этом приходится иметь дело с максимумом в 64 игрока и кучей боевой техники.
Это огромное количество динамических объектов, каждый шаг каждого из которых должен быть проверен на столкновение с чем бы то ни было. И при каждой такой проверке игре нужно двигать все назад во времени к собственному времени каждой проверяемой пули, которое было записано как время выстрела. И это на каждом шагу моделирования. Не только при выстрелах.

Техника и разрушаемость.

Другая большая проблема баттлфилда – разрушаемое окружение – это часть игрового дизайна. Здания и техника здесь могут получать урон, так же как и игроки. И если, для того, чтобы проверить не было ли что-нибудь «застрелено», вам необходимо путешествие во времени, то вам нужно двигать назад не только игроков, но и всю технику и все строения с поля боя. Правда, я не думаю, что это же самое надо делать для разрушений [зданий], потому как разрушения не создают новых препятствий для пуль. Щебень может быть легко прострелен насквозь, а если новое препятствие, вдруг, и возникает в результате разрушения, оно, скорее всего, не будет замечено из-за дыма, этим разрушением вызванного.

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

Растягиваем протокол.

64 игрока на поле боя, десятки единиц техники, тонны разрушений, ракет, пуль, оружия, стреляющего в разные стороны и черт его знает чего еще – огромное количество данных для передачи. Однако если вы, вдруг, посмотрите на трафик, создаваемый Battlefield 3, вы увидите, что он не так уж и высок. Я полагаю, что тут используется что-то похожее на сетевую модель, применяемую в Halo, которая, в свою очередь, содана на основе модели из Tribes. Halo добавил в нее такую вещь как различные степени приоритетов для всех передаваемых по сети объектов. Объекты, находящиеся далеко от игрока обновляются (на клиенте) гораздо реже, чем объекты вблизи.

На моем компьютере при игре на сервере с 64 игроками игра передает около 16кб/сек в обоих направлениях. А это совсем немного.

Halo's Ragdoll Trick

На поле боя очень много физических объектов и я не думаю, что все они передаются по сети. К примеру рагдолл в большинстве случаев займет канал только на стадии начальной синхронизации физики между клиентами, а это мелочи. Вы в любом случае можете стрелять сквозь мертвые тела, так что самая большая проблема больше не проблема. Но есть другая беда – Battlefield позволяет вам оживлять павших товарищей.
Вот один пример. Некоторые люди не совсем честно используют механизм возрождения. По крайней мере если ниженаписанное правда.

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

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

Определение столкновений в Battlefield 3

Итак в Battlefield 3 есть настоящие пули и эти пули имеют корректно скомпенсированное время отклика. Если вы видите, что попадаете во что-нибудь – вы действительно попадаете в это. Что еще интереснее – попадание очень близко к «pixel perfect». Сложно точно сказать, потому что даже первый выстрел не дает 100% точности. Но, похоже, чертовски близко.

Все дело в том, что определением столкновений в Battlefield 3 занимается клиент, а не сервер. Почти как в моде ZeroPing для UT99. Если учесть сложности создаваемые всеми пушками в Battlefield 3, то все это обретает смысл. Преимущества определения столкновений на стороне клиента очевидны: дешево, 100%-верное определение, автоматическая компенсация задержки за ничего. Однако эти преимущества приходят с большим недостатком. Такой пересчет легко обмануть.

По словам Алана Кертза, DICE компенсирует последствия определения столкновений клиентом выполняя простую проверку на сервере, которая четко отвечает могло ли быть «доложенное» столкновение, или нет. Я полагаю, они и вправду что-то делают, так как видео с «убийствами через карту» перестали появятся сразу по окончании бета-тестирования. Да и главная проблема на PC – это эймботы и ESP хаки, так что я совсем не уверен, существует ли серьезный убыток безопасности на деле, а не на словах.

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

[видимо автор имел в виду – и проверить – попадает ли в этот конус цель]

Пишем собственную сетевую игру

Что вам нужно знать для того, чтобы написать свою сетевую игру? В интернете есть несколько полезных вещей, которые помогут вам с этим поиграться.
— Статьи по разработке игр от Glenn Fiedler на Networking for Game Programmers и Networked Game Physics
— На Gamasutra есть статья аж 1997 года о Dead Reckoning. Она – отличное введение в дело.
— Quake engine code review от Fabien Sanglard охватывает предсказательную и сетевую части. Вообще движок Quake – отличное место для старта.
— Valve's developer wiki – потрясающий информационный ресурс. Там есть статьи о компенсации задержек, предсказаниях, интерполяции и весьма полезная среди прочих статья от Yahn Bernier о сетевой части игрового движка.
— Презентация “I shot you first” в хранилище GDC
— Презентация о Robust Efficient Networking от Ben Garney.

Это все, что я успел посмотреть. И я уверен, что существует куча литературы по этой теме, но я пока не могу ничего порекомендовать.

Источник - http://habrahabr.ru/post/135306/