How does delta compression reduce the amount of data sent over the network?

Question

Many games use the technique of delta compression in order to lower the data load sent. I fail to understand how this technique actually lowers the data load?

For example, let's say I want to send a position. Without delta compression I send a vector3 with the exact position of the entity, for instance (30, 2, 19). With delta compression I send a vector3 with smaller numbers (0.2, 0.1, 0.04).

I don't understand how it lowers the data load if both of the messages are vector3 - 32 bit for each float - 32 * 3 = 96 bits!

I know you can convert each float to a byte and then convert it back from a byte to float but it causes precision errors which are visible.

Answer 1

There are times when you cannot avoid sending the full game state - such as on load of a saved multiplayer game, or when a resync is needed. But sending full state is usually avoidable, and that's where delta encoding comes in. Generally, this is all that delta compression is about; your example doesn't really describe that situation. The reason delta compression is even mentioned is because naïve implementations will often send state rather than deltas because state is usually what any naive game implementation stores anyway. Deltas are then an optimisation.

With deltas, you'd never send the positions of units that did not move, at all. That's the spirit of it.

Imagine we were penpals for years, and I lost my memory (and had discarded all your letters after reading them). Instead of simply continuing with your series of letters as normal, you'd have to write me the entire history of your life in one massive letter, all over again, for me to catch up.

In your given case, it may (depending on your codebase) be possible use a lower number of bits to encode the deltas, as opposed to the large bit-ranges needed to send full state. Say the world is many kilometres across, you may need a 32-bit float to accurately encode positions down to say, a centimetre in a given axis. However, given the maximum velocity applicable to entities, which may only be a couple of metres per tick, it may be doable in just 8 bits (2^8=256 so sufficient to store max of 200cm). Of course, this assumes fixed rather than floating point usage... or some kind of half/quarter float as in OpenGL, if you don't want fixed point hassles.

Answer 2

You have the wrong delta. You're looking at the delta of the individual elements. You need to think of the delta of the entire scene.

Suppose you have 100 elements in your scene, but only 1 of them moved. If you send 100 element vectors, 99 of them are wasted. You really only need to send 1.

Now, let's say you have a JSON object that stores all your element vectors. This object is syncronized between your server and your client. Instead of deciding "did so and so move?" on your client, you can just generate your next game tick in a JSON object that contains only the elements that moved. On the client side, you apply the diff to your current tick's vector and you're all set.

Answer 3

Very often another compression mechanism will in combination with delta encoding like for example arithmetic compression.

Those compression schemes work much better when the possible values are grouped together predictably. Delta encoding will group the values around 0.

Answer 4

You are broadly correct, but missing one important point.

Entities in a game are described by many attributes, of which position is only one.

What kind of attributes? Without having to think too hard, in a networked game these might include:

• Position.
• Orientation.
• Current frame number.
• Colour/lighting info.
• Transparency.
• Model to use.
• Texture to use.
• Special effects.
• Etc.

If you pick each of these in isolation, you can certainly make the case that if in any given frame it needs to change, then it must be retransmitted in full.

However, not all of these attributes change at the same rate.

Model doesn't change? Without delta compression, it must be retransmitted anyway. With delta compresion it needn't be.

Position and orientation are two cases which are more interesting, commonly being composed of 3 floats each. Between any given two frames, there is a possibility that only 1 or 2 of each set of 3 floats may change. Moving in a straight line? Not rotating? No jumping? These are all cases where without delta compression you must retransmit in full, but with delta compression you need only retransmit that which changes.

Answer 5

You are right that a naïve delta calculation on its own, with the result stored in the same size data structure as the operands and transmitted without any further processing would not save any traffic.

However, there are two ways a well-designed system based on deltas can save traffic.

Firstly in many cases the delta will be zero. You can design your protocol such that if the delta is zero you don’t send it at all. Obviously, there is some overhead to this as you have to indicate what you are or are not sending, but overall it is likely to be a big win.

Secondly, the deltas will usually have a much smaller range of values than the original numbers. and that range will be centered on zero. This can be exploited either by using a smaller data type for most deltas or by passing the complete data stream through a general-purpose compression algorithm.

Answer 6

While most answers talk about how delta encoding is about only sending the changes to state as a whole, there is another thing called "delta encoding" that can be used as a filter for reducing the amount of data you need to compress in the full state update as well, which may be where the confusion comes from in the question as asked.

When encoding a vector of numbers, you can in some cases (e.g. integers, enums, etc.) use a variable-byte encoding for the individual elements, and in some of these cases you can further reduce the amount of data that each element needs if you store it as either running sums, or as the minimum value and the difference between each value and that minimum.

For example, if you want to encode the vector {68923, 69012, 69013, 69015} then you could delta-encode that as {68923, 89, 1, 2}. Using a trivial variable-byte encoding where you store 7 bits of data per byte and use one bit to indicate that there's another byte coming, each of the individual elements in the array would require 3 bytes to transmit it, but the delta-encoded version would only require 3 bytes for the first element and 1 byte for the remaining elements; depending on the sorts of data you're serializing this can lead to some pretty impressive savings.

However, this is more of a serialization optimization and is not what is generally meant when we talk about "delta encoding" when it comes to streaming arbitrary data as part of game state (or video or the like); other answers already do an adequate job of explaining that.

Answer 7

It's also worth noting that compression algorithms do their job better on the diff. As other answers mention either most of your elements stay the same between 2 states, or the values change by a small fraction. In both these cases applying a compression algorithm to the difference of your vector of numbers gives you significant savings. Even if you don't apply any extra logic to your vector like removing the 0 elements.

Here's an example in Python:

import numpy as np
import zlib
import json
import array


state1 = np.random.random(int(1e6))

diff12 = np.r_[np.random.random(int(0.1e6)), np.zeros(int(0.9e6))]
np.random.shuffle(diff12) # shuffle so we don't cheat by having all 0s one after another
state2 = state1 + diff12

state3 = state2 + np.random.random(int(1e6)) * 1e-6
diff23 = state3 - state2

def compressed_size(nrs):
    serialized = zlib.compress(array.array("d", nrs).tostring())
    return len(serialized)/(1024**2)


print("Only 10% of elements change for state2")
print("Compressed size of diff12: {:.2f}MB".format(compressed_size(diff12)))
print("Compressed size of state2: {:.2f}MB".format(compressed_size(state2)))

print("All elements change by a small value for state3")
print("Compressed size of diff23: {:.2f}MB".format(compressed_size(diff23)))
print("Compressed size of state3: {:.2f}MB".format(compressed_size(state3)))

Which gives me:

Only 10% of elements change for state2
Compressed size of diff12: 0.90MB
Compressed size of state2: 7.20MB
All elements change by a small value for state3
Compressed size of diff23: 5.28MB
Compressed size of state3: 7.20MB

Answer 8

Delta compression is a compression of delta encoded values. Delta encoding is a transformation that produces different statistical distribution of numbers. If the distribution is favourable to the compression algorithm chosen, it lowers the amount of data. It works very well in a system like a game where entities move only slightly between two updates.

Let's say you have 100 entities in 2D. On a large grid, 512 x 512. Considering only integers for the sake of example. That's two integer numbers per entity or 200 numbers.

Between two updates, all our positions change either by 0, 1, -1, 2 or -2. There have been 100 instances of 0, 33 instances of 1 and -1 and only 17 instances of 2 and -2. This is pretty common. We choose Huffman coding for compression.

The Huffman tree for this will be:

 0  0
-1  100
 1  101
 2  110
-2  1110

All your 0's will be encoded as a single bit. That's only 100 bits. 66 values will be encoded as 3 bits and only 34 values as 4 bits. That's 434 bits or 55 bytes. Plus some small overhead to save our mapping tree, as the tree is tiny. Note that to encode 5 numbers, you need 3 bits. We have traded here the ability to use 1 bit for '0' for the need to use 4 bits for '-2'.

Now compare this to sending 200 arbitrary numbers. If your entities can't be on the same tile, you are almost guaranteed that you get a bad statistical distribution. The best case would be 100 unique numbers (all on the same X with different Y). That's at least 7 bits per number (175 bytes) and very hard for any compression algorithm.

The delta compression works in the special case when your entities change only a little. If you have a lot of unique changes, delta encoding will not help.

---

Note that delta encoding and compression is used in other situations with other transformations as well.

MPEG splits picture in small squares and if part of the picture moves, only the movement and a change is brightness are saved. In a 25fps movie, a lot of changes between frames are very small. Again, delta encoding + compression. Works best for static scenes.

Answer 9

If your position are stored in vector3 but the actual entity can only move a few integer at a time. Then send it's delta in bytes would be better than sending it in integer.

Current position: 23009.0, 1.0, 2342.0 (3 float)
New position: 23010.0, 1.0, 2341.0 (3 float)
Delta: 1, 0, -1 (3 byte)

Instead of sending the exact position every time, we send the delta.