Jump to content
  • Advertisement
Sign in to follow this  
LonelyStar

Why does delta compression of game states make sense in Q3?

This topic is 2946 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

this article: http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking
says, in Q3, game states are delta compressed before being send over the network.

Why does that make sense? What information is sent? For every player:
- position
- velocity
- looking direction
- "shooting state"

All of this variable (maybe not "shooting state", but the rest) change constantly in a FPS. So what is gained by delta compression?

Thanks!
nathan

Share this post


Link to post
Share on other sites
Advertisement
As far as I remember a game state in Q3 is much larger. It contains all game related attributes, including weapons,ammo, health, position,velocity,skinname, modelname etc which sums up to a few kbytes. q3 transfers always the whole (compressed) gamestate, but many attribute doesn't change frequently (ammo of unused weapons etc.). The whole game state is just a large memory block (no objects,lists, refrences etc) from which you can easily calculate a delta image of the current memory block and the last send memory block (set bit to one when a bit toggled,else keep 0). This way you have mostly 0 bits, a simple RLE compression of this delta image is enough to crunch a few kbytes to a few (hundred) bytes.

Share this post


Link to post
Share on other sites
Your position will have a huge range on a regular map, but it will change by comparatively little each frame. Same for velocity, etc. It takes less bits to represent a small number compared to a large number. Even for floats, if you can weather a loss of precision on your numbers, you can send a fixed point number that takes fewer than 32bits for your delta. And that is likely fine, since a position might be in the range XXXXX.YY but your deltas are only ever going to be in the range X.YY (rounding off the number after the decimal reduces precision, but who's going to notice things moving at 2m/s that are off by .005m?)

There are other compressions you can do too. Like in a direction, you can send 2 components of a normalized vector, and extrapolate the third component on the other end as sqrt(x2+y2). etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran
Your position will have a huge range on a regular map, but it will change by comparatively little each frame. Same for velocity, etc. It takes less bits to represent a small number compared to a large number.


Are you suggesting that the difference to the last game state is send, as in:

newPos = oldPos + sendDifference

? I do not think that is done in Q3, because for that the client would need to know which state the server is relating the difference to.

Share this post


Link to post
Share on other sites
Quote:
Original post by LonelyStar
Quote:
Original post by KulSeran
Your position will have a huge range on a regular map, but it will change by comparatively little each frame. Same for velocity, etc. It takes less bits to represent a small number compared to a large number.
Are you suggesting that the difference to the last game state is send, as in:
newPos = oldPos + sendDifference

? I do not think that is done in Q3, because for that the client would need to know which state the server is relating the difference to.
I don't know if send the difference in position like that, however, the client does know which state the server is relating the difference to -- that's the key to the whole Q3 algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
I don't know if send the difference in position like that, however, the client does know which state the server is relating the difference to -- that's the key to the whole Q3 algorithm.


Is that really the case? I thought the client uncompresses against the last state it received from the server, which does not necessarily have to be the same as the last state, the server knows the client has received.

Share this post


Link to post
Share on other sites
Quote:
Original post by LonelyStar
Quote:
Original post by Hodgman
I don't know if send the difference in position like that, however, the client does know which state the server is relating the difference to -- that's the key to the whole Q3 algorithm.


Is that really the case? I thought the client uncompresses against the last state it received from the server, which does not necessarily have to be the same as the last state, the server knows the client has received.

The whole algorithm is based on a binary(bitwise) delta, which will be compressed, it does not handle position, names, ammo or velocity in any special way.

Some pseudo code about the basic idea

struct gamestate
{
float x;
float y;
float z;
int ammo;
.. rest
} last_send_gamestate,current_gamestate;

byte* delta = new byte[size_of(gamestate )];
byte* source= (byte*)last_send_gamestate;
byte* target= (byte*)current_gamestate;
for(int i=0;i<size_of(gamestate );i++)
{
delta=source ^ target;
}

// now delta contains high percentage of 0 and only some 1 for changed states
byte* compressed_delta = rle_compression(delta);

// put into some message and send delta
sendDeltaMessage( delta);





On the client side you need to hold the last valid state, then the decompression works like this:

struct gamestate
{
float x;
float y;
float z;
int ammo;
.. rest
} last_send_gamestate,current_gamestate;



byte* delta = rle_decompress( getDeltaFromIncomingMsg);
byte* source= (byte*)current_valid_gamestate;
byte* target= (byte*)current_gamestate;
for(int i=0;i<size_of(gamestate );i++)
{
target = source ^ delta;
}



It is very simple and independent of the gamestate attributes ! Though you have to handle alignment and cross-plattform issues.

Share this post


Link to post
Share on other sites
I haven't looked at the code, but the delta-uncompression doesn't make sense otherwise.

Both ends have to have a history-buffer that extends into the past as far back as the last received ack from the other end.

If the server is up to state #105, and it knows the client has ack'ed state #100, then it's got to buffer all states between #100 and #105.

Likewise on the client - let's say the server sends them a delta that updates them from #100 to #105, and the client acks #105.
Now, if the client receives an update which is delta-compressed against state #105, then the age-limit on it's buffer becomes #105 (states before this will no longer be required).
Even if the client sends out an ack saying that it's received #107, it's still got to keep state #105 around, because the server might not receive the ack, and might still be basing it's deltas off of #105. If the next delta comes through and is based on #107, then all states before #107 can be purged from the clients state buffer.

Share this post


Link to post
Share on other sites
1. The server knows the last state the client received, so it can delta-compress against that.
2. We're not just talking position/velocity/view angles, but also what weapons and powerups you have, what model/skin, etc.

Check out Quake3Networking.

Share this post


Link to post
Share on other sites
"Delta Compression," as used by Quake, is not a byte-by-byte delta. It's just a way of basing the entity update information (from server to client) on what data we know that the client already has.

Instead, state is broken into separate pieces/fields, and a bitmask is sent up front for which state pieces changed or not since the last acknowledged state. The packet also contains a packet number to which it is relative.

So, suppose I have "user inputs," "position," "velocity," "orientation" and "hitpoints."

When the server needs to send "moving forward," it will first send a change to user inputs, position and velocity.
It will keep sending that for each new packet, until it gets back an ack for a packet that has the appropriate "user input" and "velocity" values. After that, further updates will be relative to the last acked packet, and will only contain the "position" field, which presumably changes every tick.

When the user turns, assuming user is authoritative of orientation (so we don't send commands for that), the packet going out will contain a new "velocity" and "orientation" field, until the new data is acked, at which point the packet stream will only contain position fields again.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!