What application/game state "delta compression" techniques/algorithm do exist?

Question

I have interest in exploring real-time multiplayer client-server game development and related algorithms. A lot of famous multiplayer games such as Quake 3 or Half-Life 2 use delta compression techniques to save bandwidth.

The server has to constantly send the latest game state snapshot to all clients. It would be very expensive to always send the full snapshot, so the server just sends the differences between the last snapshot and the current one.

...easy, right? Well, the part that I find very difficult to think about is how to actually calculate the differences between two game states.

Game states can be very complex and have entities allocated on the heap referring to each other via pointers, can have numeric values whose representation varies from an architecture to another, and much more.

I find it hard to believe that every single game object type has an hand-written serialization/deserialization/diff-calculation function.

---

Let's go back to the basics. Let's say I have two states, represented by bits, and I want to calculate their difference:

state0:  00001000100    // state at time=0
state1:  10000000101    // state at time=1
         -----------
added:   10000000001    // bits that were 0 in state0 and are 1 in state1
removed: 00001000000    // bits that were 1 in state0 and are 1 in state1

Great, I now have the added and removed diff bitsets - but...

...the size of a diff is still exactly the same to the size of a state. And I actually have to send two diffs over the network!

Is a valid strategy actually building some sort of sparse data structure from those diff bitsets? Example:

// (bit index, added/removed)
// added = 0
// removed 1
(0,0)(4,1)(10,0)

// ^
// bit 0 was added, bit 4 was removed, bit 10 was added

Is this a possible valid approach?

---

Let's say that I managed to write serialization/deserialization functions for all my game object types from/to JSON.

Can I, somehow, having two JSON values, compute the difference between them automagically, in terms of bits?

Example:

// state0
{
    "hp": 10,
    "atk": 5
}

// state1
{
    "hp": 4,
    "atk": 5
}

// diff
{
    "hp": -6
}

// state0 as bits (example, random bits)
010001000110001

// state1 as bits (example, random bits)
000001011110000

// desired diff bits (example, random bits)
100101

If something like that was possible, then it would be reasonably easy to avoid architecture-dependent issues and handwriting difference calculation functions.

Given two strings A and B similar to each other, is it possible to calculate a string C which is smaller in size than A and B, that represents the difference between A and B and that can be applied to A to get B in result?

Answer 1

Since you've used Quake3 as an example, I'll focus on how things are done there. The first thing you need to understand is that "game state" in relation to client-server games doesn't refer to the entire internal state of an object, including the current state of AI, collision functions, timers, etc. The game's server is actually giving the client a LOT less. Just the objects position, orientation, model, frame within the model's animation, velocity, and physics type. The latter two are used to make movement smoother, by allowing the client to simulate ballistic movement, but that's about it.

Every in-game frame, which happens roughly 10 times per second, the server runs physics, logic, and timers for all objects in the game. Each object then calls an API function to update its new position, frame, etc, as well as update whether it was added or removed in this frame (e.g. A shot being deleted because it hit a wall). Actually, Quake 3 has an interesting bug in this regard - if a shot moves during the physics phase, and hits a wall, it becomes deleted, and the only update the client receives is being deleted, and not the prior flight towards the wall, so the client sees the shot disappearing in mid-air 1/10th of a second before actually hitting the wall.

With this little per-object information, it's pretty easy to diff new info vs old info. Additionally, only objects that actually change call the update API, so objects that remain the same (e.g. Walls, or inactive platforms) don't even need to perform such a diff. Additionally, the server can further save up on sent information by not sending to the client objects which are not visible to the client until they come into view. For example, in Quake2, a level is divided into view areas, and one area (and all objects inside of it) is considered "out of view" from another if all doors between them are closed.

Remember that the server doesn't need the client to have a full game state, only a scene graph, and that requires much simpler serialization, and absolutely no pointers (In Quake, it's actually held in a single statically-sized array, which also limits the maximal number of objects in the game).

Besides that, there's also UI data for things like player's health, ammo, etc. Again, each player only get their own health and ammo sent to them, not those of everyone on the server. There's no reason for the server to share that data.

Update: To make sure I'm getting the most accurate information, I double checked with the code. This is based on Quake3, not Quake Live, so some things may differ. The information sent to the client is essentially encapsulated in a single structure called snapshot_t. This contains a single playerState_t for the current player, and an array of 256 entityState_t for visible game entities, as well as a few extra integers, and a byte array representing a bitmask of "visible areas".

entityState_t, in turn, is made of 22 integers, 4 vectors, and 2 trajectories. A "trajectory" is a data structure used to represent an object's movement through space when nothing happens to it, e.g. ballistic movement, or straight-line flying. It is 2 integers, 2 vectors, and one enum, which can conceptually be stored as a small integer.

playerState_t is a bit larger, containing roughly 34 integers, roughly 8 integer arrays of sizes ranging from 2 to 16 each, and 4 vectors. This contains everything from the current animation frame of the weapon, through the player's inventory, to the sound the player is making.

Since the structures used have preset sizes and, well, structure, making a simple manual "diff" function, comparing each of the members, for each is fairly simple. However, as far as I can tell, entityState_t and playerState_t are only sent in their entirety, not in parts. The only thing that is "delta"ed is which entities are sent, as part of the entity array in snapshot_t.

While a snapshot can contain up to 256 entities, the game itself can contain up to 1024 entities. That means only 25% of the objects can be updated, from the client's perspective, in a single frame (Any more would cause the infamous "packet overflow" error). The server simply keeps track of which objects had meaningful movement, and sends those. It's a lot faster than performing an actual diff - simply sending any object that called "update" on itself, and is inside the player's visible area bitmask. But in theory, a hand-written per-structure diff wouldn't be that much harder to make.

For team health, while Quake3 doesn't appear to do this, so I can only speculate how it is done in Quake Live. There are two options: Either send all playerState_t structures, since there is a max of 64 of them, or add another array in playerState_t for keeping team HP, since it would only be 64 integers. The latter is a lot more likely.

To keep the objects array in-sync between the client and server, every entity has an entity index from 0 to 1023, and it is sent as part of the message from the server to the client. When the client receives an array of 256 entities, it goes through the array, reads the index field from each, and updates the entity at the read index in its locally stored array of entities.

Answer 2

I would suggest to step back for a second and look around in order to find potentially better solution.

As you've mentioned, game state can be really really complex and huge. So it is unlikely smart compression (diffs, compact serialized forms, etc) will help. Eventually, there will be a need to transfer really big diff, so game experience will suffer.

To keep the story short I would suggest to review two figures (link to the source will be provided).

You can translate user action into the function call, which will change game state:

Or you can create a corresponding command/action and let your command executor process it changing the state asynchronously:

It might look like the difference is pretty small, but second approach allows you:

• to avoid any race condition and update state safely by introducing a queue for user-actions
• to process actions from several sources (you just need to have them properly sorted)

I've just described Command Pattern which might be very helpful. It brings us to the idea of computed state. If commands behavior is deterministic (as it should be) in order to get a new state you just need a previous one and a command.

So, having initial state (same for every player, or transferred at the very beginning of the game) only other commands will be needed to do a state increment.

I will use write-ahead and command logging as an example (let's imagine your game state is in the database), because pretty much the same problem is being solved and I've already tried to provide detailed explanation:

Such approach also allows to simplify state recovery, etc, because action execution might be really faster comparing to generate new state, compare to the previous one, generate diff, compress diff, send diff, apply diff sequence.

Anyway, if you still think it is better to send diffs just try to have your state small enough (because you are going to have at least two snapshots) with small and easily readable memory footprint.

In that case diff procedure will generate sparsed data, so any stream compressing algorithm will easily produce good compression factor. BTW, make sure your compression algorithm will not require even more memory. It is better not to use any dictionary based solution.

Arithmetic coding, Radix tree will likely help. Here are and idea and implementation you can start with:

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

Final word: do not expose the state, do not transfer it, compute it instead. Such approach will be faster, easy to implement and debug.