26
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Any time you're doing networking with a game that uses any form of delta compression, you need to be perfectly deterministic (fail, and you get desyncs). Whether "converting from byte to float" (or whatever) causes precision errors isn't important - the necessary condition is to have everything exactly the same in all the synchronized machines/games. If there are "precision errors" (unavoidable, even if you used full floats - your CPU doesn't use the same floats as my CPU), they need to be the same on all machines - and therefore aren't visible. You chose the types to avoid visible effects. \$\endgroup\$ – Luaan May 15 '17 at 12:50
  • 2
    \$\begingroup\$ @Luaan or you can add a partial absolute state every so often, for example you can every so often select a few entities and pass the absolute position, prefer selecting entities close to the player. \$\endgroup\$ – ratchet freak May 15 '17 at 15:20
  • \$\begingroup\$ Somehow, I was expecting this question to be about some relative of rsync... \$\endgroup\$ – SamB May 16 '17 at 13:39
  • \$\begingroup\$ Huffman Coding. \$\endgroup\$ – Ben Voigt May 17 '17 at 3:10
  • \$\begingroup\$ Just use middle out man \$\endgroup\$ – John Demetriou May 17 '17 at 17:51
42
\$\begingroup\$

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.

\$\endgroup\$
  • 7
    \$\begingroup\$ Your answer isn't clear to me. I feel like not sending the information of a not moving object is just a side effect of delta encoding and not "The spirit of it". The real reason to use delta encoding seems to be highlighted in ratchet freak 's answer better. \$\endgroup\$ – Etsitpab Nioliv May 15 '17 at 16:23
  • 14
    \$\begingroup\$ @EtsitpabNioliv "The Spirit" is simply "don't send what you don't have to". This can be taken down to the bit level - "use only as much bandwidth as you need to get the required message over the wire". This answer evidently seems clear enough to everyone else. Thanks. \$\endgroup\$ – Engineer May 15 '17 at 16:29
  • 4
    \$\begingroup\$ @EtsitpabNioliv Ever learned about how SVN stores files server side? It doesn't store the whole file each commit. It stores deltas, the changes each commit contains. The term "delta" is often used in math and programming to refer to the difference between two values. I'm not a game programmer, but I'd be surprised if the usage is that much different in gaming. The idea then makes sense: you "compress" the amount of data you must send by sending only the differences, instead of everything. (If any part of it is confusing to me, it's the word "compress.") \$\endgroup\$ – jpmc26 May 16 '17 at 0:14
  • 1
    \$\begingroup\$ Also, small numbers have a higher number of zero bits, and using the proper compression algorithm to encode/decode information sent can lead to even smaller payload to be sent over the network. \$\endgroup\$ – liggiorgio May 16 '17 at 17:16
22
\$\begingroup\$

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?" you can just generate your next game tick in a JSON object, make a diff tick100.json tick101.json and send that diff. On the client side, you apply the diff to your current tick's vector and you're all set.

Doing this you leverage the decades of expertise in detecting differences in text (or binary!) and don't have to worry about missing anything yourself. Now ideally you also use a library that does this behind the scenes for you to make it even easier on you as a developer.

\$\endgroup\$
  • 2
    \$\begingroup\$ Using diff sounds like an inefficient hack. Keeping JSON string on the receiving end, patching and deserializing it every single time is unnecessary. Calculating difference of two key-value dictionaries isn't a complicated task, basically you just loop over all keys and check if values are equal. If not, you add them to resulting key-value dict and finally you send the dict serialized to JSON. Simple, no years of expertise needed. Unlike diffs, this method: 1) won't include old (replaced) data; 2) plays more nicely with UDP; 3) doesn't rely on newlines \$\endgroup\$ – gronostaj May 15 '17 at 21:54
  • 8
    \$\begingroup\$ @gronostaj This was an example to get the point across. I don't actually advocate using diff for JSON - that's why say "suppose." \$\endgroup\$ – corsiKa May 15 '17 at 22:30
  • 2
    \$\begingroup\$ "Doing this you leverage the decades of expertise in detecting differences in text (or binary!) and don't have to worry about missing anything yourself. Now ideally you also use a library that does this behind the scenes for you to make it even easier on you as a developer." That part definitely makes it sound like you're suggesting using a diff or using a library that uses a diff when no one would reasonably do such a thing. I wouldn't call delta compression "diffing", it's just delta compression, the similarities are superficial \$\endgroup\$ – Selali Adobor May 16 '17 at 21:53
  • \$\begingroup\$ An optimal diff and an optimal delta compression are the same. While the diff utility on the command line is geared for text files and would likely not provide you an optimal result, I would recommend researching libraries that do the delta compression for you. There's nothing fancy about the word delta - delta and diff, in this sense, mean literally the same thing. That seems to have been lost over the years. \$\endgroup\$ – corsiKa May 17 '17 at 0:39
9
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Another example: if you have 100 spaceships each with their own position but travelling at the same velocity vector, you only need to send the velocity once (or at least have it compress really well); otherwise, you'd need to send 100 positions instead. Let others do the adding. If you consider shared-state lock-step simulations an aggressive form of delta-compression, you don't even send the speeds - only the commands coming from the player. Again, let everyone do their own adding. \$\endgroup\$ – Luaan May 15 '17 at 12:55
  • \$\begingroup\$ I agree. Compression is relevant in the answer. \$\endgroup\$ – Leopoldo Sanczyk 22 hours ago
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice example. Compression plays a role here. \$\endgroup\$ – Leopoldo Sanczyk 22 hours ago
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

protected by Josh May 15 '17 at 16:27

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.