Дельта компрессия и квантизация объектов в C#

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