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⁻⁴⁵ до ±3.4 x 10³⁸ и размер составляет 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/

https://ru.wikipedia.org/wiki/Maximum_transmission_unit

https://github.com/Levchenkov/NetCode