Сетевой код для бедных +45



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

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

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

Проблема №1: ресурсы


Первый вопрос, который у меня возник: как сказать клиенту, что для рендеринга объекта нужно использовать такой-то меш?

Сериализировать весь меш? Не стоит, у клиента он уже есть на диске.

Передавать имя файла? Не-а, малоэффективно и небезопасно.

Ну ладно, может быть, просто строковый идентификатор?

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

Если я переименую текстуру, то не хочу получать от игроков отчеты об ошибках с такими скриншотами:


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

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

А тут я использую этих сложных чудовищ для идентификации объектов. Да я использовал строки даже для доступа к свойствам объектов. Какое безумие!

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

namespace Asset
{
	namespace Mesh
	{
		const int count = 3;
		const AssetID player = 0;
		const AssetID enemy = 1;
		const AssetID projectile = 2;
	}
}

Поэтому я могу ссылаться на меши следующим образом:

renderer->mesh = Asset::Mesh::player;

Если я переименую меш, то компилятор превратит это в мою проблему, а не в проблему какого-то несчастного игрока. И это хорошо!

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

Хорошие новости заключаются в том, что нас снова может спасти препроцессор.

const char* Asset::Mesh::filenames[] =
{
	"assets/player.msh",
	"assets/enemy.msh",
	"assets/projectile.msh",
	0,
};

Благодаря всему этому я смог запросто передавать ресурсы по сети.
Это просто числа! Я могу даже проверять их.

if (mesh < 0 || mesh >= Asset::Mesh::count)
	net_error(); // что ты пытаешься получить, парень?

Проблема №2: ссылки на объекты


Следующим у меня возник такой вопрос: как мне вежливо попросить клиента, чтобы он переместил/удалил/обработал «тот объект, что и раньше, ты знаешь, какой».

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

С самого начала я знал, что мне потребуется куча списков различных видов объектов, примерно вот таких:

Array<Turret> Turret::list;
Array<Projectile> Projectile::list;
Array<Avatar> Avatar::list;

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

Avatar* avatar;

avatar = &Avatar::list[0];

При этом появляется гора неочевидных проблем.

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

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

Ну ладно, хорошо. Буду использовать вместо указателя ID.

template<typename Type> struct Ref
{
	short id;
	inline Type* ref()
	{
		return &Type::list[id];
	}

	// перегруженный оператор "=" опускается
};

Ref<Avatar> avatar = &Avatar::list[0];

avatar.ref()->frobnicate();

Вторая проблема: если я удалю этот Avatar из списка, то на его место будет перемещён другой Avatar, а я ничего об этом не узнаю.

Программа продолжит выполнение, величественно и спокойно корёжа всё, пока какой-нибудь игрок не отправит мне отчёт об ошибке «игра ведёт себя странно».

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

Так, ладно. Вместо удаления аватара я буду приписывать ему номер версии:

struct Avatar
{
	short revision;
};

template<typename Type> struct Ref
{
	short id;
	short revision; 
	inline Type* ref()
	{
		Type* t = &Type::list[id];
		return t->revision == revision ? t : nullptr;
	}
};

Я не удаляю аватар полностью, а помечаю его как «мёртвый» и увеличиваю номер версии. Теперь всё, что попытается получить к нему доступ, будет получать null pointer exception. А сериализация ссылки по сети — это всего лишь вопрос передачи двух легко проверяемых чисел.

Проблема №3: дельта-компрессия


Если бы мне пришлось сократить свою статью до одной строчки, то это была бы просто ссылка на блог Гленна Фидлера.

Кстати, вот и она: gafferongames.com

Когда я решил реализовать собственную версию сетевого кода Гленна, я изучил эту статью,
в которой подробно рассматривается одна из самых серьёзных проблем многопользовательских игр. А именно следующая: если вы хотите передавать состояние всего мира по сети 60 раз в секунду, то забьёте 17 Мбит/с от ширины канала.

И это только на одного клиента.

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


Первая часть самая сложная: а знает ли вообще клиент, где находится объект? То, что я отправил позицию, не означает, что клиент её получил. Клиент может отправлять обратно подтверждения типа «я получил пакет 218, но это было 0,5 секунды назад и с тех пор ничего больше не принимал».

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

Кто-то задал на Reddit вопрос: «разве это не огромный объём памяти?»

Нет, не огромный.

Я храню в памяти 255 копий мира в едином огромном массиве. Но это ещё не всё —
в каждой из копий достаточно места для максимального количества объектов (2048) даже если активны только 2.

Если хранить состояние объекта как позицию и поворот, то нужно 7 чисел float: 3 на координаты XYZ и 4 на кватернион. Каждое число float занимает 4 байта. Игра поддерживает до 2048 объектов. 7 float * 4 байта * 2048 объектов * 255 копий =…

14 МБ. То есть примерно половина современной текстуры.

Могу представить, как писал бы эту систему пять лет назад на C#. Я бы сразу начал беспокоиться об используемой памяти, совсем как тот человек с Reddit, даже не задумавшись о действительном объёме задействованных данных. Я бы написал какую-нибудь ненужную, безумно изощрённую, переполненную багами систему компрессии. Когда вы уделяете секунду и задумываетесь над тем, какими будут настоящие данные, то это называется Data-Oriented Design. Когда я рассказываю людям о DOD, многие сразу начинают говорить: «Ого, это очень низкоуровневый подход. Похоже, ты хочешь выжать максимум производительности. У меня нет на это времени. Да и мой код работает нормально». Давайте разобьём эту фразу на утверждения.

Утверждение 1: «Это очень низкоуровневый подход».

Вы же видите — я всего лишь перемножил четыре числа, это не квантовая физика.

Утверждение 2: «Приходится жертвовать читаемостью и простотой ради скорости».

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

Вот решение, которое я только что описал. Всё статически размещено в сегменте .bss. Он никогда не перемещается, всегда одного размера и совершенно не использует указателей:


А вот характерное для C# решение. Всё случайным образом разбросано по динамической памяти. Элементы перераспределяются или перемещаются прямо посередине кадра, массив хаотичен, повсюду 64-битные указатели:


Что проще?

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

Но такова моя точка зрения. В моём решении я могу запросто сконструировать «достаточно хорошую» мысленную модель, чтобы понимать, что на самом деле происходит в машине. А в решении на C# я едва начал реализацию. Я понятия не имею, как оно поведёт себя в процессе выполнения.

Предположение 3: «Писать код таким образом стоит только ради производительности».

По моему мнению, скорость — это приятный побочный эффект Data Oriented Design. Главное преимущество — ясность мысли. Пять лет назад, если бы я приступил к решению задачи, то первым делом бы подумал не о самой задаче, а о том, как втиснуть её в классы и интерфейсы.

Недавно я собственными глазами наблюдал такой «паралич анализа» на геймджеме. Мой друг застопорился на создании сетки для игры в стиле 2048. Он не мог понять, должно ли каждое число быть объектом, или каждая ячейка сетки, или все они. Я сказал: «Сетка — это массив чисел. Каждая операция — это функция, изменяющая сетку». Внезапно ему всё стало кристально ясно.

Предположение 4: «Мой код работает нормально».

Повторюсь: скорость — не основная проблема, но она важна. Именно из-за неё весь мир переключился с Firefox на Chrome.

Попробуйте провести эксперимент: запустите calc.exe. Теперь скопируйте 100-мегабайтный файл из одной папки в другую.



Я не знаю, что делает calc.exe в течение этих бесконечных 300 мс, но вы можете сделать собственные выводы из двухминутного исследования: calc.exe запускает процесс Calculator.exe, и один из аргументов командной строки называется "-ServerName".

Скажите, calc.exe «работает нормально»? Упрощает ли всё добавление сервера, или только замедляет и усложняет?

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

Проблема №4: лаг


Теперь я вкратце расскажу о той части истории, в которой сетевой код хоть как-то работает.

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

Я решил повторно использовать эти 14 МБ копий мира. Когда сервер получает команду на выстрел снарядом, он перематывает мир назад на 150 мс к тому моменту, в котором находился игрок, когда нажимал кнопку стрельбы. Затем сервер симулирует снаряд и пошагово перематывает мир вперёд, пока он не будет совпадать с текущим состоянием. И здесь он создаёт снаряд.

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

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


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


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

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

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


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


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

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

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

Проблема №5: джиттер


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

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

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

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

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

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

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


Проблема №6: подключение к серверу посередине матча


Постойте, у меня уже есть способ сериализации всего игрового состояния. Так в чём же проблема?

Оказывается, для сериализации нового игрового состояния с нуля требуется не один, а несколько пакетов. А для передачи пакета клиенту может понадобиться несколько попыток. Чтобы получить полное состояние, может потребоваться несколько сотен миллисекунд, а как мы уже видели, это целая вечность. Если игра уже идёт, этого времени достаточно для передачи 20 пакетов с новыми сообщениями, которые клиент ещё не готов обработать, потому что он ещё не загрузился.

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

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

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

Проблема №7: вопросы разбиения


Эта часть будет самой противоречивой.

Помните житейскую мудрость разработчиков игр, упомянутую в начале статьи? «Никогда не добавляй сетевой многопользовательский режим в уже готовую игру».

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

Прежде чем распинать меня за это, подождите секунду. Что лучше: сгруппировать весь сетевой код в одном месте, или разбросать внутри каждого игрового объекта?

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

Но некоторые парадигмы проектирования (*кхм* ООП) не даёт мне принимать такие решения. Разумеется, нужно вставлять сетевой код внутрь объекта! Его данные приватны, поэтому для доступа к ним всё равно придётся писать интерфейс. Возможно, также придётся использовать всевозможные интеллектуальные преобразования.

Заключение


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

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

Благодарю за прочтение. Моя игра DECEIVER скоро появится в Kickstarter. Зарегистрируйтесь на сайте, чтобы скачать демо!

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (14):

  1. barbanel
    /#10684274

    Было интересно прочесть, особенно трюк с «машиной времени» на сервере, никогда не понимал как он работает.
    Спасибо за перевод, отличная статья!

  2. kalininmr
    /#10684592

    пинг 150 — както жестоко.
    ИМХО как не делай будет неиграбильно

    • Nikobraz
      /#10684654

      Вы видимо забыли как играется на 600+ по EDGE.
      У меня уже 3 месяца вообще общественная вафля со скачками пинга от 5 до 1500 и с периодическим падением инета до 10 секунд. Жизнь — боль. Но иногда играть в War Thunder даже не приносит боль, иногда.

    • Murimonai
      /#10684748

      Пинг 150 — это вполне норм еще. В зависимости от игры. В MechWarrior Online, помнится, это вообще норма была. Может и сейчас тоже. Там же в те времена был один товарищ, который ходил на тихоокеанские сервера и стримил бои с пингом в 1000. Весьма успешные бои, надо заметить. Комментировал он это обычно так: «It's not a ping. It's skill level»©

    • jewalky
      /#10684750

      От игры зависит. Я например в дум2 через Zandronum спокойно до 180мс могу (да и всякие южноамериканцы с 260 тоже норм себя чувствуют).
      Подход используется схожий с тем что здесь (положение игроков хранится за последние 70 тиков (1тик = 0.028с) и отматывается в соответствии с пингом того кто стрелял).

      По теме хочется сказать что вопрос с «какой клиент что знает» лично я решал bitfield'ом на предмет «объект уже известен игроку с id #» и в соответствии с этим битфиелдом либо посылал только то что изменилось либо полную инфу об объекте (и ставил «известно игроку» в 1 по получении). Плюс полная инфа об объекте посылается раз в N секунд чисто на всякий случай или по запросу клиента.

      Для игр с ограниченным количеством одновременно изменяющихся объектов (меньше 100-300) такой подход вполне сойдёт. Для 700+ уже придётся извращаться, ибо 60 раз в секунду обновлять инфу о 700 объектах уже 60*700 минимум. А ведь ещё данные есть :)

      • kalininmr
        /#10685438

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

        • jewalky
          /#10685518

          Ну во-первых, в начале подключения к серверу, клиенту скидывается дельта от изначального состояния уровня, называемая snapshot.
          А потом — открытие/закрытие двери это глобальное действие посылающееся всем клиентам. Учитывая что дверей на уровне не очень много, и открываются/закрываются они не все сразу одновременно 60 раз в секунду, это решается отправкой пакета по reliable каналу в момент изменения состояния. (а конкретно в названном порте Дума таким же образом посылаются все эффекты анимации секторов (статических частей геометрии уровня), и даже так траффик достаточно низкий).
          «Можно ли открыть» как правило предсказывается клиентом, т.к. у двери есть конкретный набор характеристик, прописанный в уровне. Есть конечно заскриптованные, но задержка 50-250мс не очень заметна пользователю, а если движок свой, то даже заскриптованные двери можно предсказывать в клиенте.

          • kalininmr
            /#10685976

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

  3. Nagh42
    /#10684788 / +2

    Вот и в этом описании сетевого кода пропущен один очень важный аспект — безопасность. Доверие сервера клиенту

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

    Или все-таки об этом подумали, но в статье описать забыли?

  4. Mingun
    /#10684830

    Мне одному кажется, что проблема то вовсе не в сетевом коде (хорошо, в основном, не в сетевом коде):


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

    ...


    Моя игра DECEIVER скоро появится в Kickstarter.

    Если с самого начала предполагалось делать игру сетевой, почему он раньше обо всём этом не подумал, ведь она ещё даже не вышла? Почему «так получилось, что бОльшая часть сетевого кода в буквальном смысле приклеена к этой игре скотчем»? Налицо полное отсутствие какого-либо проектирования, а с него и надо было начинать.

  5. luntik2012
    /#10685154

    Мне кажется, в первом примере и в представленом на github исходнике немного не хватает шаблонной магии и приколов времени компиляции (в частности, для (де)сериализации).

  6. PositiveAlex
    /#10685466

    Про 2048.


    Мне это напомнило MVC паттерн. Так и есть. Вью — игровая сетка. Ее источник — данные в массиве. Контроллер — процесс взаимодействия пользователя с экраном.

  7. Viknet
    /#10686272

    Часть про дельта-компрессию состояния мира напомнила реализацию хранения состояния уровня в Braid.

  8. buldo
    /#10686386

    Я понимаю плюсы хранения состояния в массивах — их можно очень быстро сравнить векторными инструкциями. Однако вот эта фраза заставила меня поднапрячься:

    Игра поддерживает до 2048 объектов.

    Для разработчика всякого бизнес-кода звучит, как какой-то жуткий хардкод. Я не вижу технической сложности сереализовать и сравнить дерево объектов(понятно, что это будет затратнее) и отослать клиенту дифф от предыдущего дерева.
    Да и вообще, почему нужно слать «слепки» состояния всего мира 60 раз в секунду? Почему не слать пачки изменений конкретных объектов с привязкой к меткам времени?

    Если здесь есть разработчики игр, может они ткнут меня носом в суровую реальность и расскажут почему автор всё сделал правильно?