Cтатья затрагивает тему сериализации данных, которые передаются по unreliable каналам.
В первую очередь это касается реалтайм игр, которые критичны к сетевым задержкам, имеют активное общение клиента и сервера, например, 10 - 60 раз в секунду и используют UDP протокол.
В статье вы узнаете, как с помощью дельта компрессии и квантизации можно уменьшить размер объектов и, тем самым, уменьшить размер сериализованных данных. Попутно мы познакомимся с библиотекой для битовой сериализации данных NetCode.
Особенностью реалтайм игр является то, что они требовательны ко времени, в течении которого получают актуальное состояние мира от сервера. Мало кому могут нравится большие временные задержки на отдельные действия пользователя во время игры. Тут очень важную роль играют: качество интернет соединения, расстояние между клиентом и сервером. Кроме того, немаловажную роль выполняет и сериализация данных, передаваемых по сети. Ведь именно способ сериализации определяет размер сетевых пакетов. В свою очередь размер пакетов, важен не только по причине ограничения серверного интернет-канала, но и потому, что большие пакеты подвергаются фрагментации, а потеря одного фрагмента приводит к потере всего пакета.
Проблема
В процессе работы у вас наверняка возникали вопросы:
-
как сжать передаваемые данные,
-
как сделать размер пакетов таким, чтобы они не подвергались фрагментации во время передачи,
-
как уменьшить серверный трафик?
Чтобы погрузиться в проблематику реалтайм игр и, в частности, разобраться с проблемой размера пакетов, рекомендую сначала ознакомиться со статьей Snapshot Compression из цикла статей Gaffer On Games. На основе информации и подходов из этой статьи мы будем работать над оптимизацией размера пакетов.
Представьте себе ситуацию: сервер тикает с определенной частотой и в каждом тике рассылает актуальное состояние мира всем игрокам. Для упрощения, рассмотрим рассылку информации только о положении игроков в пространстве.
Для этого, например, можно использовать следующую структуру:
public struct TransformComponent
{
public Vector3 Position;
public float Yaw;
public float Pitch;
}Размер указанной структуры - 20 байт. Position имеет тип Vector3, который содержит 3 float поля для каждой оси координат (X, Y и Z), Yaw и Pitch тоже имеют тип float. Что в итоге дает 5 float полей, каждый размером в 4 байта, при этом суммарный размер равен 20 байт (5 полей * 4 байта).
Убедиться в том, что размер структуры именно такой можно с помощью функции SizeOf:
Console.WriteLine(Unsafe.SizeOf<TransformComponent>()); // 20Тогда, если у нас шутер 5 на 5, то в результате получится 200 байт на пакет (20 байт * 10 игроков).
Вроде не страшно и не критично, но при этом рассмотрен только один компонент. А в состояние игры, которое мы отправляем по сети, входят и другие компоненты: скорость, здоровье, амуниция и т.д. При этом нам нужно уложиться в 1500 байт для отправляемого пакета по UDP согласно MTU, чтобы избежать фрагментации.
А если у нас шутер с режимом королевская битва на 100 человек, то в итоге получается 2 000 байт (20 байт * 100 игроков), которые показывают, что даже с 1 компонентом не укладываемся в параметры MTU.
Конечно, можно использовать зоны интереса, что позволит уменьшить количество передаваемых сущностей, но сути это не меняет.
Например, LiteNetLib по умолчанию использует MTU равный 1024 байт, пруф. И если вы отправляете по unreliable каналу пакет размером 1025 байт, то получите исключение.
Можно ли уменьшить размер? Согласно вышеупомянутой статье Snapshot Compression, можно. Предлагаю воспользоваться приемом квантизации, а именно, ограничить допустимые значения для полей компоненты.
Квантизация
Определение квантизации можно найти в Википедии. Если совсем коротко, то квантизация - процесс преобразования вещественных чисел в целые.
Рассмотрим на примере данный процесс.
Представим, что у нас есть игровое поле 100 на 100 и его координаты могут принимать дробное значение. Также предположим, что точности в 0.1 единицы нам будет достаточно. С такими исходными данными нам подходит тип float, его диапазон значений от ±1.5 x 10−45 до ±3.4 x 1038 и размер составляет 4 байта. Но дело в том, что весь диапозон нам не нужен, да и точность в 7 знаков после запятой для нас это перебор.
Можно ли оптимизировать хранение значений и сколько бит нам нужно для хранения? Достаточно хранить всего 1000 значений для каждой оси (100 * 10), т.е. 10 бит на ось или 20 бит для каждого объекта на нашем игровом поле. В случае использования переменных типа float без квантизации, у нас было бы 64 бита для каждого объекта (32 * 2).
Квантизировать можно не только типы с плавающей точкой float и double, но и целочисленные.
Например, в нашей игре нужно хранить угол поворота в градусах - от 0 и до 360. Для хранения потребуется 9 бит. Значит 8 битового типа byte нам не хватит, поэтому наиболее подходящий тип это ushort 16 бит, максимальное значение которого 65535. Но нам нужно только 9 бит. Квантизация как раз нам позволит использовать только 9 из 16 бит.
Самый маленький тип в C# это byte, как вы можете догадаться, его размер равен 1 байту. Поэтому для работы с отдельными битами надо использовать битовые операции. К самим битовым операциям претензий нет, но хотелось бы упростить нелегкую жизнь разработчиков и предложить более удобный инструмент: библиотеку NetCode.
Напомню, что тип bool в памяти тоже занимает 1 байт, поэтому можем забыть про массив из bool.
NetCode
NetCode это библиотека с открытым исходным кодом. Она предназначена для сериализации объектов, которые должны быть переданы по сети, и нацелена на уменьшение размера передаваемого массива. Высокая производительность и отсутствие аллокаций ключевые особенности этой библиотеки. Все то, что мы так любим и ценим в нашей работе.
Библиотека не предоставляет набор функций для работы с отдельными битами числа и не умеет находить количество установленных битов, зато позволяет записывать в массив байтов определенное количество бит из битового представления числа:
var bitWriter = new BitWriter();
bitWriter.WriteBits(bitCount: 3, value: 0b_101010); // 0b_010
bitWriter.WriteBits(bitCount: 3, value: 0b_1111); // 0b_111
Console.WriteLine(bitWriter.BitsCount); // 6
bitWriter.Flush();
Console.WriteLine(bitWriter.BitsCount); // 8
byte[] data = bitWriter.Array; // data[0] == 0b_111010
Console.WriteLine(Convert.ToString(value: data[0], toBase: 2)); // 111010В приведенном выше примере мы выполнили следующее:
-
2 раза записали по 3 бита (010 и 111), хотя сами исходные числа содержали больше значимых битов (101010 и 1111 соответственно),
-
вывели в консоль информацию о количестве записанных битов,
-
записали внутренний буфер в итоговый массив,
-
опять вывели в консоль информацию о количестве записанных битов,
-
и вывели на консоль представление итогового массива.
В результате, получен массив, первый байт которого содержит наши записанные биты 010 и 111.
Побитовая запись числа, конечно, хорошо, но мы сюда пришли не за этим.
Квантизация с помощью NetCode
Рассмотрим пример по квантизации значений:
var bitWriter = new BitWriter();
bitWriter.Write(value: 1f, min: 0f, max: 100f, precision: 0.1f);
Console.WriteLine(bitWriter.BitsCount); // 10
bitWriter.Flush();
Console.WriteLine(bitWriter.BitsCount); // 16
var data = bitWriter.Array;
var bitReader = new BitReader(data);
var value = bitReader.ReadFloat(min: 0f, max: 100f, precision: 0.1f);
Console.WriteLine(value); // 1В этом примере мы делаем следующее:
-
записываем float переменную со значением 1f, с ограничениями от 0 до 100 и точностью в 0.1 ,
-
выводим в консоль информацию о количестве записанных битов,
-
записываем внутренний буфер в итоговый массив,
-
опять выводим информацию о количестве записанных битов,
-
полученный массив передаем в конструктор класса BitReader,
-
читаем float значение с ограничениями от 0 до 100 и точностью в 0.1,
-
получаем исходное значение.
Как результат, мы записали дробное число с помощью 10 битов и успешно прочитали это число назад.
Таким образом, можно увидеть, что библиотека позволяет записать всего одну строку кода для записи одного значения в массив:
bitWriter.Write(value: 1f, min: 0f, max: 100f, precision: 0.1f);Давайте вернемся к нашему примеру с компонентой, которая отвечает за позиционирование игроков в пространстве, и посмотрим, как библиотека NetCode сможет нам помочь.
Напомню, что наша компонента имеет вид:
public struct TransformComponent
{
public Vector3 Position;
public float Yaw;
public float Pitch;
}и допустим, что наше игровое поле ограничено:
-
-100 < X < 100,
-
-10 < Y < 10,
-
-100 < Z < 100,
при этом пусть точность перемещения составляет 0.1 единицы (попугаев, метров или футов).
Также наложим ограничения на углы поворота:
-
0 < Yaw, Pitch < 360,
точность угла поворота пусть будет 0.1 градус.
Тогда сериализация примет вид:
var bitWriter = new BitWriter();
var positionXZLimit = new FloatLimit(min: -100f, max: 100f, precision: 0.1f);
var positionYLimit = new FloatLimit(min: -10f, max: 10f, precision: 0.1f);
var rotationLimit = new FloatLimit(min: 0f, max: 360f, precision: 0.1f);
var transformComponent = new TransformComponent { Position = new Vector3(10f, 5f, 10f), Pitch = 30f, Yaw = 60f };
bitWriter.Write(value: transformComponent.Position.X, limit: positionXZLimit);
bitWriter.Write(value: transformComponent.Position.Y, limit: positionYLimit);
bitWriter.Write(value: transformComponent.Position.Z, limit: positionXZLimit);
bitWriter.Write(value: transformComponent.Yaw, limit: rotationLimit);
bitWriter.Write(value: transformComponent.Pitch, limit: rotationLimit);
bitWriter.Flush();
Console.WriteLine(bitWriter.BytesCount); // 7Таким образом, мы:
-
создаем ограничения с помощью класса FloatLimit,
-
создаем объект нашей сериализуемой структуры,
-
записываем координаты и повороты,
-
записываем внутренний буфер в итоговый массив,
-
выводим в консоль количество байт итогового массива.
Размер сериализованных данных составляет 7 байт. Результат неплохой. Но можно еще лучше!
Дельта
Дельта значений, она же дифф значений, она же разность значений.
Мы можем пойти дальше и отправлять только те данные, которые изменились. Это и называется дельта компрессия.
Например, у игрока изменились только координаты, а наклон и поворот остались прежними:
var before = new TransformComponent
{
Position = new Vector3(10f, 5f, 10f),
Pitch = 30f,
Yaw = 60f
};
var after = new TransformComponent
{
Position = new Vector3(10.5f, 5.5f, 10.5f),
Pitch = 30f,
Yaw = 60f
};
var bitWriter = new BitWriter();
var positionXZLimit = new FloatLimit(min: -100f, max: 100f, precision: 0.1f);
var positionYLimit = new FloatLimit(min: -10f, max: 10f, precision: 0.1f);
var rotationLimit = new FloatLimit(min: 0f, max: 360f, precision: 0.1f);
bitWriter.WriteValueIfChanged(
baseline: before.Position.X,
updated: after.Position.X,
limit: positionXZLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Position.Y,
updated: after.Position.Y,
limit: positionYLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Position.Z,
updated: after.Position.Z,
limit: positionXZLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Yaw,
updated: after.Yaw,
limit: rotationLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Pitch,
updated: after.Pitch,
limit: rotationLimit);
bitWriter.Flush();
Console.WriteLine(bitWriter.BytesCount); // 5В данном примере мы делаем следующее:
-
создаем переменную before, которая содержит информацию до изменений,
-
создаем переменную after, которая содержит информацию после некоторых изменений,
-
создаем ограничения с помощью класса FloatLimit,
-
записываем координаты и повороты,
-
записываем внутренний буфер в итоговый массив,
-
выводим в консоль количество байт итогового массива.
Итоговый размер сериализованных данных будет зависеть от количества измененных полей. В нашем случае изменилась только позиция и размер массива данных составляет 5 байт.
Если поля структуры одинаковы, т.е. не было никаких изменений в данных, то будет записано столько бит, сколько полей. В нашем случае это 5 бит.
И это еще не все. Можно ввести ограничения на изменения значений, т.е. можно квантизировать дельту.
Квантизация дельты
Предположим, что игрок 90% времени перемещается пешком и изменения координат не превышает 1 (одного) юнита за 1 тик:
-
-1 < deltaX, deltaY, deltaZ < 1,
при этом точность перемещения, как и раньше, будет составлять 0.1 единицы.
Тогда наша сериализация примет вид:
var before = new TransformComponent
{
Position = new Vector3(10f, 5f, 10f),
Pitch = 30f,
Yaw = 60f
};
var after = new TransformComponent
{
Position = new Vector3(10.5f, 5.5f, 10.5f),
Pitch = 30f,
Yaw = 60f
};
var bitWriter = new BitWriter();
var positionXZLimit = new FloatLimit(min: -100f, max: 100f, precision: 0.1f);
var positionYLimit = new FloatLimit(min: -10f, max: 10f, precision: 0.1f);
var rotationLimit = new FloatLimit(min: 0f, max: 360f, precision: 0.1f);
var diffPositionLimit = new FloatLimit(min: -1f, max: 1f, precision: 0.1f);
bitWriter.WriteDiffIfChanged(
baseline: before.Position.X,
updated: after.Position.X,
limit: positionXZLimit,
diffLimit: diffPositionLimit);
bitWriter.WriteDiffIfChanged(
baseline: before.Position.Y,
updated: after.Position.Y,
limit: positionYLimit,
diffLimit: diffPositionLimit);
bitWriter.WriteDiffIfChanged(
baseline: before.Position.Z,
updated: after.Position.Z,
limit: positionXZLimit,
diffLimit: diffPositionLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Yaw,
updated: after.Yaw,
limit: rotationLimit);
bitWriter.WriteValueIfChanged(
baseline: before.Pitch,
updated: after.Pitch,
limit: rotationLimit);
bitWriter.Flush();
Console.WriteLine(bitWriter.BytesCount); // 3В данном примере мы делаем следующее:
-
создаем переменную before, которая содержит информацию до изменений,
-
создаем переменную after, которая содержит информацию после некоторых изменений,
-
создаем ограничения с помощью класса FloatLimit,
-
записываем координаты и повороты,
-
записываем внутренний буфер в итоговый массив,
-
выводим в консоль количество байт итогового массива.
Итоговый размер сериализованных данных будет зависеть не только от количества измененных полей, но и от того, насколько сильно изменились поля. Если наше предположение о том, что координаты игрока изменились в промежутке [-1, 1], окажется верным, то размер данных составит 3 байта. Если мы допускаем ошибку в оценке, т.е. координаты игрока по какой-то причине (например, он использовал телепорт) изменились сильнее, то размер составит 5 байт, как и в предыдущем примере.
Полный пример сериализатора и десериализатора
var serializer = new TransformComponentSerializer();
var deserializer = new TransformComponentDeserializer();
var before = new TransformComponent { Position = new Vector3(10f, 5f, 10f), Pitch = 30f, Yaw = 60f };
var after = new TransformComponent { Position = new Vector3(10.5f, 5.5f, 10.5f), Pitch = 30f, Yaw = 60f };
var serializedComponent = serializer.Serialize(before, after);
Console.WriteLine(serializedComponent.Length); // 3
var updated = deserializer.Deserialize(before, serializedComponent.Array);
serializedComponent.Dispose();
Console.WriteLine(updated); // Position: <10.5, 5.5, 10.5>, Yaw: 60, Pitch: 30
public record struct TransformComponent (Vector3 Position, float Yaw, float Pitch );
public struct SerializedComponent
{
private readonly ArrayPool<byte> _arrayPool;
public byte[] Array { get; }
public int Length { get; }
public SerializedComponent(ArrayPool<byte> arrayPool, byte[] array, int length)
{
_arrayPool = arrayPool;
Array = array;
Length = length;
}
public void Dispose()
{
_arrayPool.Return(Array);
}
}
public static class Limits
{
public static readonly FloatLimit Rotation = new FloatLimit(0, 360, 0.1f);
public static readonly Vector3Limit AbsolutePosition = new Vector3Limit(new FloatLimit(-100f, 100f, 0.1f), new FloatLimit(-10f, 10f, 0.1f), new FloatLimit(-100f, 100f, 0.1f));
public static readonly Vector3Limit DiffPosition = new Vector3Limit(new FloatLimit(-1f, 1f, 0.1f), new FloatLimit(-1f, 1f, 0.1f), new FloatLimit(-1f, 1f, 0.1f));
}
public class TransformComponentSerializer
{
private const int MTU = 1500;
private readonly BitWriter _bitWriter = new BitWriter();
private readonly ArrayPool<byte> _arrayPool = ArrayPool<byte>.Shared;
public SerializedComponent Serialize(TransformComponent baseline, TransformComponent updated)
{
var array = _arrayPool.Rent(MTU);
_bitWriter.SetArray(array);
_bitWriter.WriteDiffIfChanged(baseline.Position.X, updated.Position.X, Limits.AbsolutePosition.X, Limits.DiffPosition.X);
_bitWriter.WriteDiffIfChanged(baseline.Position.Y, updated.Position.Y, Limits.AbsolutePosition.Y, Limits.DiffPosition.Y);
_bitWriter.WriteDiffIfChanged(baseline.Position.Z, updated.Position.Z, Limits.AbsolutePosition.Z, Limits.DiffPosition.Z);
_bitWriter.WriteValueIfChanged(baseline.Yaw, updated.Yaw, Limits.Rotation);
_bitWriter.WriteValueIfChanged(baseline.Pitch, updated.Pitch, Limits.Rotation);
_bitWriter.Flush();
return new SerializedComponent(_arrayPool, _bitWriter.Array, _bitWriter.BytesCount);
}
}
public class TransformComponentDeserializer
{
private readonly BitReader _bitReader = new BitReader();
public TransformComponent Deserialize(TransformComponent before, byte[] array)
{
_bitReader.SetArray(array);
TransformComponent result = default;
result.Position = new Vector3(
_bitReader.ReadFloat(before.Position.X, Limits.AbsolutePosition.X, Limits.DiffPosition.X),
_bitReader.ReadFloat(before.Position.Y, Limits.AbsolutePosition.Y, Limits.DiffPosition.Y),
_bitReader.ReadFloat(before.Position.Z, Limits.AbsolutePosition.Z, Limits.DiffPosition.Z));
result.Yaw = _bitReader.ReadFloat(before.Yaw, Limits.Rotation);
result.Pitch = _bitReader.ReadFloat(before.Pitch, Limits.Rotation);
return result;
}
}
Заключение
За 3 простых шага (квантизация, дельта компрессия и квантизация дельты) и с помощью библиотеки NetCode, нам удалось сжать передаваемый компонент с 20 байт до 3 байт.
Материалы
https://gafferongames.com/post/snapshot_compression/
Автор:
Tidehunter
