Networking Series#

This is the first post in a series about the architecture and details of the code that powers our new multiplayer game, Veil of the Soulstones.

I thought I'd start by discussing the simplest possible parts of the system, then move on to the more complicated ones in future posts. With that in mind, the bit-packer is probably the best place to start, as its responsibility is quite limited and it may be used for purposes other than networking, such as save files. It is also self-contained, making it perfect to explain in a simple blog post.

I should also say that a lot of what I'll discuss in this series is nothing groundbreaking. It's not like we are doing R&D and pushing the boundary on what's possible with multiplayer video games or network programming.

This series is more about sharing how we are solving these problems, such that if you are thinking about starting a multiplayer video game and want to do your netcode, this series should give you some pointers and, in some cases, implementation details to help you out.

Serializing#

The concept of bitpacking is a subset of serialization. Serialization is a simple concept: you have some data in memory and you want to have it in a format that you can easily transport -- be it over the network or "transport" into a file on disk -- in such a way that you can deserialize it later to get the same data back.

Generally speaking, there are two main ways to serialize data: text-based and binary-based. Binary-based serialization is more efficient in terms of space and computation, while text-based serialization allows users to read and possibly edit the serialized data at rest (e.g. a save file).

I won't go into too much detail here about serialization as I'm sure most game developers have run into it one way or another, save files being the most likely scenario.

Bitpacking is just a way to serialize data, which provides some interesting benefits which I'll discuss shortly.

Bitpacking#

Concept#

The main difference between bitpacking and "normal" serialization is that data is packed more tightly than in its source representation. As an example, let's take a player's health. In the vast majority of games, a player's health will be less than 1000. While it would be more than enough to use a 16-bit short to represent the health, most games will use a 32-bit int for convenience. However, when it comes to saving that health to a file or transmitting it over the network, it would be very wasteful to serialize the full 32-bit range when we know we need no more than 10 bits. In fact, even using a 16-bit short would be wasteful. That's where bitpacking comes in.

When you know the range a particular piece of data may take, you can "pack" that data into a bit stream using only the number of bits required to represent it. In the case of a player's health, we would want something like Serialize(health, min: 0, max: 1000), such that Serialize() encodes health into the save file or network packet using only the bits required to represent values from 0...1000 -- in this case, 10 bits.

Saving 6 bits may not seem like much, but when you consider a game with dozens of entities, each with many fields, saving 2, 5, 10 bits per field quickly adds up.

As a concrete example, in Veil of the Soulstones we often synchronize a dozen enemies, each of them with a health field -- in reality we synchronize the damage it has taken and subtract that from health to get the current health value, but the result is the same -- we can save as much as 150 bytes / second / player on health alone:

Without bitpacking:

bits per health: 16
tick rate: 20
enemies per tick: 10
total bits: 10 * 20 * 16 = 3200 / second

With bitpacking:

bits per health: 10
tick rate: 20
enemies per tick: 10
total bits: 10 * 20 * 10 = 2000 / second

That's a ~37% bandwidth reduction, with no loss of data. And that's the least we'd save. As I mentioned, most games (including ours) use a 32-bit integer to represent health, in which case a naive serialization would use 6400 bits / second, or over 3x more data than using bitpacking.

API#

Our implementation of a bitpacker is pretty standard and it was based on Glenn Fiedler's¹ serialization article. The API is pretty symmetrical for reading and writing, so you only need to write one serialization function to serialize/deserialize the object. Here's what a typical serialization function looks like:

struct Player
{
    public Vector3 Position;
    public int Health;

    public bool Serialize(ref BitPackSerializer serializer, ref Player player)
    {
        var ok = true;
        ok = ok && serializer.SerializePosition(ref Position);
        ok = ok && serializer.Serialize(ref Health, min: 0, max: 1000);
        return ok;
    )
}

BitPackSerializer is a struct that's constructed as:

var serializer = BitPackSerializer.CreateWrite(buffer);

or

var serializer = BitPackSerializer.CreateRead(buffer);

A few details about BitPackSerializer:

• It's a struct, so we pass it by ref through the codebase. That's slightly more efficient than if it was a class.²
• It has a ReadMode field where you can check if it's reading or writing data. Just to give you an idea: we have over 800 calls to the various Serialize() functions and only 25 use cases of ReadMode, so we only care whether we are reading or writing in about 3% of all serialization cases. So the symmetrical serialization/deserialization really pays off.
• Our BitPackSerializer makes heavy use of method overloading, allowing us to just write serializer.Serialize(ref data); for nearly all types of data -- although struct and enums have special functions because overload resolution in C# is not capable of distinguishing between them. The main benefit of this is ergonomics.
• It is capable of serializing all unmanaged types, including unmanaged structs, as well as string, Span<byte>, enums and arrays thereof. It can also quantize float numbers to a specified number of decimal places -- it just converts the float number into a fixed-point number according to how much precision and range you need.³
• All Serialize() functions have a min and a max (or a max length for strings and arrays). These define how many bits will be used to serialize the data. This has an important implication: two different game instances must use the same min/max values when writing and reading. If an update changes one of these min/max values, that's a breaking change and the two versions will be incompatible for network play.
• We also have C# extension methods for special types of data that we serialize often, such as position, rotation, time variables, etc. The extension methods are useful because we can keep the same call signature, serializer.Serialize(), while passing in a type that's not natively supported by the bitpacker.
  • SerializePosition(), for example, will serialize the (X, Y, Z) coordinates of the Vector3 using the maximum world size as the range. We also have an optimized quaternion serialization that uses the smallest three approach⁴.

Implementation#

Implementing something like this can feel a bit daunting at first because there are just so many different types to support, but if you start from the very core, everything becomes easier:

1. In C#, ideally you'd use a Span<byte> or void* as the backing storage for the bitstream. That will allow you to use the highest number of different storage sources: stackalloc memory, byte[], heap-allocated pointers, native pointers from an underlying networking library (e.g.: SteamNetworkingSockets, etc.)
2. bool WriteBits(uint data, int numBits) & bool ReadBits(out uint data, int numBits).
3. int RequiredBits(long min, long max)

Once you have these 3 components, everything else falls into place.

For example:

 bool WriteGenericInteger(long value, long minValue, long maxValue)
 {
     var bits = BitPackUtils.BitsRequired(minValue, maxValue);
     var normalized = (uint)(value - minValue);
     return WriteBits(normalized, bits);
 }

Note that despite the long parameters, this function writes up to 32 bits of data -- having long parameters just makes it easier to handle int/uint. If this function received int or uint, you'd have a hard time passing one or the other into the function, whereas with long you can pass either an int or uint value and know that it can be represented in value.

This WriteGenericInteger() alone is responsible for writing bool, byte, sbyte, ushort, short, uint, and int. ulong and long are serialized as 2 int instances.

Here's an implementation of BitsRequired:

public static int BitsRequired(long min, long max)
{
    if (Assert(max >= min))
    {
        NetUtil.LogError($"Max must be greater than or equal to min. Max: {max}, min: {min}", logStackTrace: true);
        return int.MaxValue;
    }

    return BitsRequired(0ul, unchecked((ulong)max - (ulong)min));
}

public static int BitsRequired(ulong min, ulong max)
{
    if (Assert(max >= min))
    {
        NetUtil.LogError($"Max must be greater than or equal to min. Max: {max}, min: {min}", logStackTrace: true);
        return int.MaxValue;
    }

    if (max == min)
    {
        return 0;
    }

    var range = max - min;
    if (range == ulong.MaxValue)
    {
        return 64;
    }

    if (range == 0)
    {
        return 0;
    }

    // The highest normalized value is max - min.
    var value = range;
    var bits = 0;
    while (value > 0)
    {
        value >>= 1; // Shift right by 1 bit
        bits++;
    }
    return bits;
}

The unchecked((ulong)max - (ulong)min) is a way to get the absolute distance between max and min without having to check which is positive, which is negative, etc.

This is by no means a super-optimized function. We could, for instance, use intrinsics to get the number of bits (instead of the while loop at the bottom). In Unity, we have the math class which provides such intrinsics to us, but our bit packer is compiled into a .NET Standard 2.1 DLL outside Unity (along with other networking-related classes), so we don't have access to math.

And the WriteBits() function can be implemented as:

public struct BitState
{
    public ulong Scratch;
    public int BitsUsed;
    public int ScratchBits;
    public int BytePointer;
}

public bool WriteBits(uint source, int bits)
{
    State.Scratch |= ((ulong)source) << State.ScratchBits;
    State.ScratchBits += bits;

    while (State.ScratchBits >= 8)
    {
        Data[State.BytePointer++] = (byte)(State.Scratch & 0xFF);
        State.ScratchBits -= 8;
        State.Scratch >>= 8;
    }

    State.BitsUsed += bits;
}

ReadBits() is just the reverse of the WriteBits() function.

It accumulates X bits in a variable big enough not to overflow (i.e. a ulong) and, as soon as it holds at least 8 bits, flushes them out into the backing buffer. There are also more efficient ways of doing this, as mentioned in Glenn's article¹, but it has worked fine for now.

All of the other types are derived from these simple functions: they calculate how many bits they need to write, and call WriteBits(). The string serialization, for example, serializes a bit for is-null, a length for the number of bytes it uses, and the UTF-8 encoded byte[].

In reality, all of these functions are a little more complicated than I made them look because they need to handle errors such as overflowing the available backing storage, invalid input, logging and so on.

Change groups#

All you've seen up to this point was run-of-the-mill stuff. These are all standard bit-packing techniques used by pretty much all bit-packers out there.

We do, however, have something extra in our bit-packer which allows us to detect whether or not a particular piece of data has changed. We use this information to determine if we need to synchronize the data or not.

This is how they look:

[Serializable]
public struct LobbyPlayerSyncSnapshot
{
    public ChangeGroup Ready;
    public ChangeGroup Position;
    public ChangeGroup Gameplay;
}

public struct LobbyPlayerSync
{
    public bool Ready;
    public int Gold;

    public bool Serialize(ref BitPackSerializer serializer, in LobbyPlayerSyncSnapshot confirmedSnapshot, ref LobbyPlayerSyncSnapshot latestSnapshot)
    {
        var ok = true;

        if (serializer.PushChangeGroup())
        {
            ok = ok && serializer.Serialize(ref Ready);
        }
        serializer.PopChangeGroup(confirmedSnapshot.Ready, ref latestSnapshot.Ready);

        if (serializer.PushChangeGroup())
        {
            ok = ok && serializer.Serialize(ref Gold, min: 0, max: 10_000);
        }
        serializer.PopChangeGroup(confirmedSnapshot.Gameplay, ref latestSnapshot.Gameplay);

        return ok;
    }
}

• On write:
  • PushChangeGroup() always returns true.
  • PopChangeGroup() returns true only if the data within the group has changed when compared to confirmedSnapshot and latestSnapshot.
• On read:
  • PushChangeGroup() returns true only if the sender actually wrote something for that group when it wrote the message.
  • PopChangeGroup() returns true if PushChangeGroup() returned true.

The system uses these two "snapshot" instances to detect if the data you've just serialized needs to be sent to the remote player. If not, the system doesn't serialize the data and instead places a single bit to be used by the reader to determine if PushChangeGroup() should return true on their end.

confirmedSnapshot and latestSnapshot are tracked elsewhere in the game (we'll talk about that in a later post), but they represent:

• confirmedSnapshot: The version of the data that is known to have been received and processed by the remote player.
• latestSnapshot: The version of the data that was last serialized, which may or may not have been received by the remote player.

To determine if we need to send the data, the system will:

1. Serialize all the data within PushChangeGroup() ... PopChangeGroup()
2. Hash the contents of the serialized data
3. Compare the hashes, as well as ChangeGroup.Version, between confirmed and latest
4. If it's different, increment the ChangeGroup.Version of latest and leave the serialized data in the buffer, along with a one-bit true flag at the start of the data -- this means the data has either changed compare to what the remote player has, or has changed since we last serialized (in which case we must serialize because the remote player might not have received the last thing we've serialized); either way, we must send the data as it has changed.
5. If it's the same, roll back the serialized data (this just rolls back the BitState) and instead write 1 bit as false. This essentially undoes the serialization of the group because the remote player already has the data, so there's no point in sending it again.

On the reader side, PushChangeGroup() reads the 1 bit that was placed by the writer's PopChangeGroup(), which will determine if data should be read or not. If not, it returns false and none of the calls to .Serialize() will happen.

This technique has its trade-offs:

On the positives:

• We can check whether or not we need to send data to the remote player without keeping copies of the old data, potentially reducing memory usage.
• We can group multiple variables together in one group, in effect using 1 bit to detect change across N variables. If variables are known to change together, you can put them into 1 group and save N-1 bits, where N is the number of variables.
• Because we have a struct to hold the change groups for each serialized data type, we can store other data in there, effectively tracking the data as received (if it's in the confirmed snapshot) or last serialized (if it's in the latest snapshot).
  • For example, here's the snapshot struct for the enemy:

[Serializable]
public struct EnemyBasicSyncSnapshot
{
	public ChangeGroup Data;
	public ChangeGroup HealthData;
	public ChangeGroup CombatData;
	public ChangeGroup ConstantData;
	public ChangeGroup Position;
	public ChangeGroup Target;
	public EnemyJumperSyncSnapshot Jumper;
	public EnemyAggroJumperSyncSnapshot AggroJumper;
	public EnemyChaserSyncSnapshot Chaser;
	public EnemyChargerSyncSnapshot Charger;
	public EnemyOpportunisticSyncSnapshot Opportunistic;
	public EnemyMasterChaserFlyingSyncSnapshot MasterChaserFlying;
	public EnemySuicideExplosiveSyncSnapshot SuicideExplosive;
	public EnemyChaserExplosiveSyncSnapshot ChaserExplosive;
	public EnemyChargerExplosiveSyncSnapshot ChargerExplosive;
	public EnemyPhasedSyncSnapshot Phased;
	public CombatDataSyncSnapshot CombatDataGroups;
	public ChangeGroup Group;

	// We use this value to cache what the position was when this snapshot was taken
	// We use this to calculate distance-based syncing.
	public Vector3 PositionCache;
}

• You can see PositionCache in there. Because we have access to the confirmed and latest snapshot, we can know for certain what enemy position the remote player has received and processed, as well as the position that we sent last. We use that information to detect when we need to synchronize the enemy (i.e. if the player already has the latest position and the enemy is not on screen, we don't need to send the enemy snapshot).
• We get this "tracking" for free without needing to hold the entire serialized data set.

On the negative side:

• It needs to hash the data, which can be expensive.
  • We do have a small-data-optimization where any data smaller than Vector<byte> (it's fixed at 16 bytes for a .NET Standard 2.1 DLL) will get its serialized contents cached and compared instead of hashed.
  • I've profiled the hashing function. On a tick frame on the host (of which we have 20 a second), with 1 player connected, on a debug build, we spend about 0.1ms on hashing. So... not very cheap, but not prohibitively expensive either, especially considering the alternative wouldn't be free -- we would need to compare the contents of the data.
• The system supports nested groups, but when the child group changes, the parent is necessarily detected as changed as well, even if its data doesn't change. This isn't too bad because we can always avoid nesting if we need to, but nesting is very ergonomic when serialized structs have members which are themselves serialized structs and so forth.
• It's not the most ergonomic system. You have to pass in 2 variables to serialize a snapshot.

I've never seen this approach used for change detection / delta-compression⁵. That may very well be for a good reason: this might end up biting us in the ass. So far it has worked okay, though. If you have knowledge to indicate that this is a bad idea, or if you've seen this approach somewhere else before, please let me know as I'd love to hear more about it.

The alternative way of doing something like this (that I know of) would be to keep N past instances of the data, and do a comparison on each field to see which changed, then send a bitmask with 1s and 0s for changed/not-changed for each field, followed by the data. That would obviously work fine, but I wanted to try something different that fit directly into the serialization process, gave us control over how many variables are detected as a group, and was more immediate-mode-like⁶.

Beyond bits#

Bitpacking is very effective, but the most "compression" you'll get out of it is still in "bit units", meaning that if you are encoding a value that takes 10 bits to represent, the best you'll ever get is 10 bits. However, there are other ways to squeeze some more bandwidth out of the process.

One thing we do is compress the packet before sending. We use ZstdSharp⁷, which reduced bandwidth by ~25%. This is just standard compression, think of zipping a file.

However, if you really want some savings and are willing to do the extra engineering work, you can use Arithmetic coding. We don't use it in our project as it seemed overkill, but if you have servers that are supposed to handle tens of thousands of players, then it's probably a good idea to look into it. It handles compression by using fewer bits to serialize common values, and more bits to serialize less common values.

Arithmetic coding compression rates approach the theoretical limit of how much you can losslessly compress the source data. I first came across the concept by reading some Game Developer Magazine articles; Jonathan Blow (of Braid and The Witness fame) wrote about it way back in the early 00s. You can read the article in the October 2003 issue of GDM here (page 9 of the PDF file, 16 of the magazine). This is a series of articles, so there's another entry in September 2003, and an even earlier one. All of the GDM issues are freely available in the GDC vault.

Conclusion#

This is our approach to bitpacking in our network code. We'll also be using the bit-packer in our save system.

Hopefully this was informative. And again, if you see anything in here which you think is a terrible idea, please send me an email or DM me on X.

This is the first in a series of articles on our networking code. I'll be detailing more sophisticated parts of the system over time, in the hopes that eventually it will all come together into a cohesive architecture.

As always, check out our projects and feel free to join our Discord or mailing list.

Have a good one.