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?

Danielson

If you had a (multi-step) undo/redo mechanism, you could probably capitalise on that. – Catchings

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.

Fatherly

Very interesting information. I have some additional questions that I hope you can answer (or help me find an answer to): 1) It seems that health/ammunition and other state is not synchronized according to your answer - how does Quake 3 deal with this data? I am able to see my teammates' health in the HUD on Quake Live., 2) Is object #500 (stored in the static array) on the server synchronized with object #500 on the client?, 3) How is the diff actually calculated? Are there handwritten functions to calculate diffs for every object type? – Danielson

If there's anything extra you need from my answer, let me know – Fatherly

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.

Coates

Answer 3

When comparing bits, whether it is efficient to store the location of every changed bit depends on how many bits are changed. In 32-bit system, each location takes 32 bits, so it is efficient only when fewer than 1 in 32 bits are changed. However, since the changed bits are usually adjacent, it would be more efficient if you compare at larger units(e.g. bytes or words).

Note that your approach for comparing bits only works if the absolute locations of the bits don't change. If, however, some bits are inserted or removed in the middle, your algorithm will see almost every bit after the inserted/removed position as changed. To mitigate this, you would compute the longest common subsequence, so the bits only in A or B are those inserted/removed.

---

But comparing JSON objects don't have to happen bit-wise. (If you must, it's the same as comparing two bit strings.) The comparison can happen at higher level. One way to compute the difference of two abritrary JSON objects would be writing a function that takes A and B and:

• If the arguments are of different types, return "A is changed to B".
• If the arguments are of the same primitive type, return nothing if they're the same, else, return "A is changed to B".
• If both arguments are dictionaries, the elements whose keys are only in A are those removed, and whose keys are only in B are those added. For elements with the same key, compare recursively.
• If both arguments are arrays, compute the longest common subsequence of A and B(whether two elements are equal can also be checked by a recursive function), and find the elements only in A or B. So, elements only in A are those removed, elements only in B are those added. Or maybe the elements that are not equal can also be compared recursively, but the only efficient way I can think of requires having a way(such as recording IDs) to identify which element in A corresponds to which element in B, and compare an element with the corresponding element.

---

Difference between two strings can also be computed using the longest common subsequence.

Rung