Sign in to follow this  
sufficientreason

State Snapshot Delta Compression and "Slippy Floats"

Recommended Posts

I'm using a traditional Quake-style delta compression system for my state snapshots. The general process is this:

  • Server keeps track of the past N world snapshots.
  • Server keeps track of the tick-stamp of the last snapshot the client received (sent by the client).
  • When the server wants to send a snapshot to a client, it...
    • Retrieves the snapshot at the tick last acked by the client (if we can, otherwise send a full snapshot)
    • Compares the latest snapshot to that retrieved snapshot
    • Sends a delta

This is pretty straightforward, and it's nice because all the client has to send back is the tick of the last snapshot it received. It works because we can assume that, even though we're only sending deltas, that the client has the latest data for all values at the tick it has acknowledged.

...Except with floats. After months of successfully using this system, I've now run into a problem with floats that only change very slightly tick to tick, such as with damping velocities. Because I can't use strict equality with floats, I'm running into the following problem on low-latency connections:

  • Client acked at 48, Server send 49. abs(floatValue@48 - floatValue@49) < epsilon, don't send
  • Client acked at 49, Server send 50. abs(floatValue@49 - floatValue@50) < epsilon, don't send
  • Client acked at 50, Server send 51. abs(floatValue@50 - floatValue@51) < epsilon, don't send

And so on. Because the float changes so little between ticks, the value is never sent, even though after a while of this it can get very out of date due to this kind of epsilon-slipping. At high latency this is much rarer because instead of comparing ticks 49 and 50, I'm comparing something like ticks 32 and 50, and the difference is big enough to overcome the approximation epsilon and be sent.

Anyone have any ideas for how I fix this problem? I'd like to keep it so the client is only sending an ack tick. I've thought about periodically forcing a "keyframe" snapshot with full data, but that could be expensive for many players. Wondering if any of you have encountered this problem before with delta compression.

Thanks!

Share this post


Link to post
Share on other sites

Instead of comparing the floating-point values logically, you could try a bitwise comparison of the two values. If their bit representations are the same, you know the values must be identical as well. Otherwise, they could be different and you send the update. This won't tell you how they changed, or whether the change is logically significant, but false-positives are preferable to false-negatives.

Share this post


Link to post
Share on other sites

Of course there is the straightforward solution of storing and comparing to the latest sent value instead of the latest calculated value.

Share this post


Link to post
Share on other sites

Instead of comparing the floating-point values logically, you could try a bitwise comparison of the two values. If their bit representations are the same, you know the values must be identical as well. Otherwise, they could be different and you send the update. This won't tell you how they changed, or whether the change is logically significant, but false-positives are preferable to false-negatives.

 

Yeah, this is probably closest to the solution I'll probably end up with. If I pre-discretize the floats before storing them in the server-side snapshots (say by converting them to a 24/8 fixed point) then I can do explicit comparisons from that point onward and I won't have this problem. It does remove the dead reckoning type benefits of only sending values when they've changed beyond a certain point, though.

 

Of course there is the straightforward solution of storing and comparing to the latest sent value instead of the latest calculated value.

 

I'm not sure it's quite that easy in this case. Comparing against the last sent doesn't give me information about what the client actually has. I could do both, where if the auth value is different enough from the client's last acked or our last sent then we send the new one. This is still susceptible to packet loss though. Also, I was trying to avoid having to store an extra snapshot per client if I could.

Edited by sufficientreason

Share this post


Link to post
Share on other sites
Note that the "delta" in the Quake compression is applied to the mask bits of "what things am I sending," not to "sending delta-X instead of X."

If you send delta-X as a float, you might as well send X as a float, as they have the same size (32 bits.)

If you send quantized values, then you can send a smaller value as a delta instead of the full value. But then, the values you deal with will be inherently quantized.

Share this post


Link to post
Share on other sites

Note that the "delta" in the Quake compression is applied to the mask bits of "what things am I sending," not to "sending delta-X instead of X."

If you send delta-X as a float, you might as well send X as a float, as they have the same size (32 bits.)

If you send quantized values, then you can send a smaller value as a delta instead of the full value. But then, the values you deal with will be inherently quantized.

 

Right, that's what I'm doing. I'm sending full values, not offsets. The problem stems from determining equality between snapshots using epsilons for floats.

Share this post


Link to post
Share on other sites

The problem stems from determining equality between snapshots using epsilons for floats.


If you know what you sent in the packet that is last-acknowledged from the client, then just use regular "!=" to the current value.
If your simulation is doing something to the position (sliding along a wall, slightly slipping down a slope, or whatever,) then you should probably send that update.

Share this post


Link to post
Share on other sites

 

The problem stems from determining equality between snapshots using epsilons for floats.


If you know what you sent in the packet that is last-acknowledged from the client, then just use regular "!=" to the current value.
If your simulation is doing something to the position (sliding along a wall, slightly slipping down a slope, or whatever,) then you should probably send that update.

 

 

Yeah, you and Zipster are right. I'm overthinking it. Going ahead with bitwise float comparison which should fix the problem.

 

Thanks everyone!

Share this post


Link to post
Share on other sites
Because I can't use strict equality with floats

You get taught that == on floats is dangerous for good reason, as there's plenty of mathematical cases where you want to cope with the fact that they are imprecise, but in this case where you're trying to synchronize some pattern bits over a network, then == is perfectly fine.

If you send delta-X as a float, you might as well send X as a float, as they have the same size (32 bits.) If you send quantized values, then you can send a smaller value as a delta instead of the full value. But then, the values you deal with will be inherently quantized.

This is pretty common to these quake-esque schemes, isn't it? Your data definition often specifies the ranges and precision required of all your float values, and the system can then quantize them appropriately to as few bits as possible. The delta generation step would then compare two sets of quantized values together to determine the difference. Then as you mention, actual delta values (as in just the difference to be added to an old snapshot) will often be close to zero, which lets you compress your packets to even fewer bits by using variable length encodings. I imagine that this would typically result in your packets being somewhere around a quarter of the size compared to actually sending floats?

Edited by Hodgman

Share this post


Link to post
Share on other sites

The range and precision are important.  In one case a 0.01% difference may be negligable, in another it may make a critical difference.

Although it would be more work, it may make more sense to have a sliding level based on traffic levels.  If there is plenty of bandwidth available and the connection is otherwise idle, you might as well start fixing up the tiny errors. If traffic is busy, leave them out.

Share this post


Link to post
Share on other sites
On 56k modems, that sliding level of compression/precision would totally make sense!
On modern broadband, perhaps not as much ;-)

People with limited data plans and wireless action games may still perhaps benefit from that kind of optimization, and if you have a very crowded game and want to push as many updates as possible into a 1280 byte un-fragmented IPv6 datagram, perhaps that will help, too!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this