Delta compression and object quantization in C#
The article touches upon the topic of serialization of data that is transmitted over unreliable channels.
First of all, this applies to real-time games that are critical to network delays, have active communication between the client and the server, for example, 10 – 60 times per second and use the UDP protocol.
In this article, you will learn how you can use delta compression and quantization to reduce the size of objects and thus reduce the size of serialized data. Along the way, we will get acquainted with the library for bit serialization of data. net code.
A feature of real-time games is that they are demanding on the time during which they receive the current state of the world from the server. Few people can like large time delays for individual user actions during the game. Here a very important role is played by: the quality of the Internet connection, the distance between the client and the server. In addition, an important role is played by the serialization of data transmitted over the network. After all, it is the serialization method that determines the size of network packets. In turn, the size of the packets is important not only because of the limitation of the server Internet channel, but also because large packets are fragmented, and the loss of one fragment leads to the loss of the entire packet.
Problem
In the course of work, you probably had questions:
how to compress transmitted data,
how to size packets so that they are not fragmented during transmission,
how to reduce server traffic?
To immerse yourself in the problems of real-time games and, in particular, deal with the problem of packet size, I recommend that you first read the article Snapshot Compression from the Gaffer On Games article series. Based on the information and approaches in this article, we will work on optimizing the packet size.
Imagine the situation: the server ticks with a certain frequency and in each tick sends the current state of the world to all players. For simplicity, let us consider the distribution of information only about the position of the players in space.
To do this, for example, you can use the following structure:
public struct TransformComponent
{
public Vector3 Position;
public float Yaw;
public float Pitch;
}The size of the specified structure is 20 bytes. Position is of type Vector3 which contains 3 float fields for each coordinate axis (X, Y and Z), Yaw and Pitch are also of type float. Which in the end gives 5 float fields, each 4 bytes in size, while the total size is 20 bytes (5 fields * 4 bytes).
You can make sure that the size of the structure is exactly this using the SizeOf function:
Console.WriteLine(Unsafe.SizeOf<TransformComponent>()); // 20Then, if we have a 5v5 shooter, then the result will be 200 bytes per packet (20 bytes * 10 players).
It seems not scary and not critical, but only one component is considered. And the game state that we send over the network also includes other components: speed, health, ammunition, etc. At the same time, we need to keep within 1500 bytes for the sent packet via UDP according to MTUto avoid fragmentation.
And if we have a shooter with a royal battle mode for 100 people, then the result is 2,000 bytes (20 bytes * 100 players), which show that even with 1 component we do not fit into the MTU parameters.
Of course, you can use zones of interest, which will reduce the number of transferred entities, but this does not change the essence.
For example, LiteNetLib by default uses an MTU of 1024 bytes, proof. And if you send a packet of 1025 bytes over an unreliable channel, you will get exception.
Can the size be reduced? According to the above article Snapshot Compression, can. I propose to use the quantization technique, namely, to limit the allowable values for the component fields.
Quantization
The definition of quantization can be found in Wikipedia. In short, quantization is the process of converting real numbers into integers.
Let’s take this process as an example.
Let’s imagine that we have a playing field 100 by 100 and its coordinates can take a fractional value. Let’s also assume that a precision of 0.1 units will be enough for us. With such initial data, the float type suits us, its value range is from ±1.5 x 10−45 up to ±3.4 x 1038 and the size is 4 bytes. But the fact is that we do not need the entire range, and the accuracy of 7 decimal places is too much for us.
Is it possible to optimize the storage of values and how many bits do we need to store? It is enough to store only 1000 values for each axis (100 * 10), i.e. 10 bits per axis, or 20 bits for each object on our playing field. In the case of using float variables without quantization, we would have 64 bits for each object (32 * 2).
It is possible to quantize not only floating-point types float and double, but also integer ones.
For example, in our game we need to store the angle of rotation in degrees – from 0 to 360. 9 bits are required for storage. So the 8 bit byte type is not enough for us, so the most suitable type is ushort 16 bits, the maximum value of which is 65535. But we only need 9 bits. Quantization just allows us to use only 9 of the 16 bits.
The smallest type in C# is byte, which, as you can guess, is 1 byte. Therefore, to work with individual bits, you must use bitwise operations. There are no complaints about the bit operations themselves, but I would like to simplify the hard life of developers and offer a more convenient tool: the library net code.
Let me remind you that the bool type also takes 1 byte in memory, so we can forget about the bool array.
net code
net code it is an open source library. It is designed to serialize objects that must be transferred over the network, and is aimed at reducing the size of the transferred array. High performance and no allocations are the key features of this library. Everything that we love and appreciate so much in our work.
The library does not provide a set of functions for working with individual bits of a number and does not know how to find the number of set bits, but it allows you to write a certain number of bits from the bit representation of a number into a byte array:
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)); // 111010In the above example, we have done the following:
3 bits were written 2 times (010 and 111), although the original numbers themselves contained more significant bits (101010 and 1111, respectively),
output to the console information about the number of recorded bits,
written the internal buffer to the final array,
again brought to the console information about the number of recorded bits,
and output to the console a representation of the resulting array.
As a result, an array is obtained, the first byte of which contains our recorded bits 010 and 111.
Bitwise notation of a number is, of course, good, but we did not come here for this.
Quantization with NetCode
Consider an example of value quantization:
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); // 1In this example, we are doing the following:
write a float variable with a value of 1f, with limits from 0 to 100 and a precision of 0.1 ,
output to the console information about the number of recorded bits,
write the internal buffer to the final array,
again we display information about the number of recorded bits,
the resulting array is passed to the constructor of the BitReader class,
read a float value with limits from 0 to 100 and a precision of 0.1,
get the original value.
As a result, we wrote a fractional number using 10 bits and successfully read this number back.
Thus, you can see that the library allows you to write just one line of code to write one value to an array:
bitWriter.Write(value: 1f, min: 0f, max: 100f, precision: 0.1f);Let’s go back to our example with the player positioning component and see how the NetCode library can help us.
Let me remind you that our component looks like:
public struct TransformComponent
{
public Vector3 Position;
public float Yaw;
public float Pitch;
}and let’s say that our playing field is limited:
-100 < X < 100,
-10 < Y < 10,
-100 < Z < 100,
at the same time, let the accuracy of movement be 0.1 units (parrots, meters or feet).
We will also impose restrictions on the rotation angles:
let the rotation angle accuracy be 0.1 degree.
Then the serialization will look like:
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); // 7Thus, we:
create limits using the FloatLimit class,
create an object of our serializable structure,
write coordinates and rotations,
write the internal buffer to the final array,
output to the console the number of bytes of the final array.
The size of the serialized data is 7 bytes. The result is good. But it can be even better!
Delta
Delta of values, it is diff of values, it is the difference of values.
We can go further and send only the data that has changed. This is called delta compression.
For example, only the coordinates of the player have changed, but the tilt and rotation remain the same:
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); // 5In this example, we do the following:
create a before variable that contains information before the changes,
create an after variable that contains information after some changes,
create limits using the FloatLimit class,
write coordinates and rotations,
write the internal buffer to the final array,
output to the console the number of bytes of the resulting array.
The resulting size of the serialized data will depend on the number of fields changed. In our case, only the position has changed and the size of the data array is 5 bytes.
If the fields of the structure are the same, i.e. there were no changes in the data, then so much will be written bithow many fields. In our case it is 5 bits.
And that’s not all. You can introduce restrictions on changes in values, i.e. delta can be quantized.
Delta quantization
Let’s assume that the player moves 90% of the time on foot and the change in coordinates does not exceed 1 (one) unit per 1 tick:
-1 < deltaX, deltaY, deltaZ < 1,
in this case, the displacement accuracy, as before, will be 0.1 units.
Then our serialization will take the form:
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); // 3In this example, we do the following:
create a before variable that contains information before the changes,
create an after variable that contains information after some changes,
create limits using the FloatLimit class,
write coordinates and rotations,
write the internal buffer to the final array,
output to the console the number of bytes of the final array.
The final size of the serialized data will depend not only on the number of fields changed, but also on how much the fields have changed. If our assumption that the player’s coordinates have changed in the interval [-1, 1]is true, the data size will be 3 bytes. If we make an error in the assessment, i.e. the player’s coordinates for some reason (for example, he used a teleport) have changed more, then the size will be 5 bytes, as in the previous example.
Full Serializer and Deserializer Example
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;
}
}
Conclusion
In 3 easy steps (quantization, delta compression and delta quantization) and with the help of the library net codewe managed to compress the transmitted component from 20 bytes to 3 bytes.
materials
https://gafferongames.com/post/snapshot_compression/
