Delta Compression: how much compression?

how can the client identify which properties have actually changed when rebuilding the information from binary data

That's pretty much automatic.

The function on the server is:

- get state from last client-acked tick
- calculate diff to current state to send
- send bitmap of which properties changed, and the value of those properties

The function on the client is:

- receive update packet
- decode and apply the properties that are updated according to the bitmask
- update the acked-tick-to-send to be the tick number of this update

This will automatically only send the properties that change, and automatically only apply the properties that change (by virtue of the bitmask of changed-properties.)

Oh ok, I think this is the part I was missing, using bitmask to describe what is set or not.

So I suppose in the message to the client you would have a set of bits that describes what has been set, followed by the actual values for each of these properties set. On the client you would read explicitly each bit from the bitmask (has x been set? yes? get the value, has y been set?...), and then assign its values to the network entity.

Am I understanding this correctly?

Yup

In my implementation I write the deltas to a bitstream. When writing a property (except bool, which are 1 bit) I either write a 1 followed by the delta, or a 0 indicating that there's no change.

For arrays, I either write an array of bits (1 bit for each array element), followed by just the elements that have changed, OR, write an array containing the indices of changed elements. These two strategies are selected depending on which would be smaller. The array is preceded by a single bit indicating which strategy is in use.

When writing a delta for a property, you can either write out just the new value, or you can write "oldValue XOR newValue". In the first case, the client simply copies the values from the delta packets over its own values, and in the second case, the client XORs the delta packets values with their own to recover the new value.

This second method is much more complex / slow / fragile, but, if you apply generic compression to your packets before sending them, this XOR process is likely to produce long strings of zeros, which compress quite well. Doom 3 didn't use a general purpose compressor like zlib, but instead wrote a simple RLE compressor that only looked for repeated 0's in the bitstream and replaced them with a single zero followed by a 3bit repetition count.

in the second case, the client XORs the delta packets values with their own to recover the new value

Note that the client then needs to know which previous server state this is in reference to, so the server needs to include which last acked client tick it based its compression on. The client then needs to also have as long a queue of old client states as the server has, to be able to reconstruct the correct value. As you said, a lot more complex, not to mention uses more memory.

I'd love to see some numbers on the actual size uses of the different approaches, on the wire and in RAM, if you have them!

Thank you both for such great insights, there's a lot of ideas to explore for sure!

16 hours ago, Hodgman said:

This second method is much more complex / slow / fragile, but, if you apply generic compression to your packets before sending them, this XOR process is likely to produce long strings of zeros, which compress quite well. Doom 3 didn't use a general purpose compressor like zlib, but instead wrote a simple RLE compressor that only looked for repeated 0's in the bitstream and replaced them with a single zero followed by a 3bit repetition count.

That ultimate quest for compression, fascinating topic!

I had to wrap my head around it to completely understand why it would creates long strings of zeros, it's when oldVal and newVal are the same, right?

So that means that on the second method, whether the property has changed or not, it's still part of the packet sent over? Would it not make the packet bigger in the end even after stripping the zeros out?

If something hasn't changed at all, you still shouldn't send it.

What XOR does is cancel out bits that don't change. If you have a triplet of Xpos, Ypos, Zpos, stored as three 32-bit integers, and you move 1000 units along X, 20 units along Y, and nothing at all along Z, then most likely, the two top bytes of X won't change (and will turn into 0,) the three top bytes of Y won't change (and will turn into 0,) and all four bytes of Z won't change, and it will be all zero.

If you have a single bit for "the position changed," then compressing the delta you send for position will save you some extra space. The draw-back is that you need a copy of the exact old data that the XOR was based on, to recover the intended update.

Oh I see that makes a lot of sense now! Very interesting!

For now I'm going with the first method, which is replacing the old value by the new value, because as you said there's a need to keep track of previous states at the level of the client in order to reconstitute the new value.

And right now, as I'm still building everything up, I would like to see how the pieces fit together before even considering that XOR optimization.

But it's great to see different options there in the future. Thanks a lot!

On 6/20/2018 at 2:04 PM, hplus0603 said:

Note that the client then needs to know which previous server state this is in reference to, so the server needs to include which last acked client tick it based its compression on. The client then needs to also have as long a queue of old client states as the server has, to be able to reconstruct the correct value.

22 hours ago, tromtrom said:

For now I'm going with the first method, which is replacing the old value by the new value, because as you said there's a need to keep track of previous states at the level of the client in order to reconstitute the new value.

In Quake 3, they use this method (copy, not XOR), but they still do need to keep track of a history of old states on the client and server. This is because Quake 3 sends the deltas via UDP, which means they can be lost or arrive out of order -- and if simply naively apply deltas that arrive to the client's current state in this situation (where some don't arrive, or arrive in the wrong order), then the client won't correctly reconstruct the server's state.

To get rid of the history-buffer concept, you need to use a reliable protocol like TCP, to ensure no deltas are lost and the order of changes is preserved. This is the same regardless of whether you do straight copies, or the XOR trick
The history buffer idea is really the key innovation of Quake 3, which allows them to use both UDP and delta encoding reliably.

Another alternative to the XOR method is to store differences. e.g. if health was 100 and now it's 80, then you send a delta value of -20 across the network, and the client ADDs this onto their value. This can also help when you've got an extra compression step, as if the changes are small, then the high bits of the detlas will probably contain a long string of zeros too.
Google's protobuf system for reading/writing bitstreams is also optimized for situations like this -- IIRC, when writing an integer, the process is something like the following:
* if it's smaller than 128, they write a 0 followed by the 7bit value
* else they write a 1, and then:
** if it's smaller than 16384, they write a 0, followed by the 14bit value
** else they write a 1, and then (...repeat the pattern...)
This causes small values to take up less space in the bit-stream, while large values pay an overhead of a few extra bits. If most of your values are small, then this can add up to a massive space saving.

Another trick I've heard of is, when sending deltas that are against some previously known state (like in Quake 3), you use the previous state as the "dictionary" in LZ-style compression. The kinds of compressors build up a list of bit patterns that they reference ("the dictionary"), so if there's a lot of common patterns in the previous state and the new one, then they will be able to compress the data really well. It's a kind of automatic delta encoding.
Normally this wouldn't be that great, because the "dictionary" has to normally be stored alongside the compressed file -- but in this situation, both parties already have the dictionary, so it doesn't need to be sent!

You don't need a history buffer on the client when you apply the state in the incoming packets. There are some interpolation mechanisms that will work better if you do, but that's not for communications purposes. You just need to know the packet number that you get. Discard packets that are out of order. Applying the state when you receive it (assuming it's not out-of-order) is sufficient to get the object to a state that you know it has had on the server.

If you miss a packet, the server will just re-send the deltas that were in that packet (or, more accurately, deltas for objects that were in that packet, but with later state) in the next update, because you're not going to acknowledge that packet. And if you discard a packet that arrives out-of-order, that's the same as that packet being dropped.

This assumes that you send ALL the objects that have outstanding changes in each packet. If you want to schedule updates across different packets, it gets a lot more complicated, and you do need at least a "last packet per object" counter, if not the full state, to make it work. So, this delta compression works best for systems with fewer moving objects (dozens, not hundreds or thousands.)

14 hours ago, Hodgman said:

To get rid of the history-buffer concept, you need to use a reliable protocol like TCP, to ensure no deltas are lost and the order of changes is preserved.

Well I'm trying this out in the context of a web browser game, so TCP it is anyway.

Thank you for all the good suggestions