Delta encoding to save bandwidth

on the server machine you need to maintain copies of position/velocity/angle for each object, and compare those to the real ones each update interval, if they are different, send them, then copy the real value over the old value for comparison at the next interval..

simple

in your example is the server holding the true game state and the clients only having a copy of that game state? or when you say the server machine need's to maintain copies of player value's do you mean maintain copies that it sends out to the client's?

Also you say compare them at each update interval? how exactly do you mean? because if i send the players current state to the server to be compared to the actual game state then that is defeating the purpose of delta encoding is it not? im trying to reduce the amount of packet's i send or reduce the size at least.

sorry i know it seems simple to you, i just need that extra kick to get it to click

cheers

Abstracting things a little.

Say you have a game state 'STATE', and you mark each game state you send to a client with a sequence number 'sqn'. On every server tick, the server computes a new game state : STATE[0], STATE[1], STATE[2], ....

Ignoring delta compression, the server would send STATE[0], STATE[1], STATE[2] to the client, and if a STATE[1] does not reach a client, another more up to date state (STATE[2] for example) will reach the client eventually.

If your client informs the server what state the client last received, instead of sending the full latest state, the server can send the difference between the latest state, and the state last aknowledged by the client.

So the server can send DELTA[sqn, ack] = STATE[sqn] - STATE[ack].

When the client receives DELTA[sqn, ack] from a packet, the client can reconstruct the latest state by doing...

STATE[sqn] = STATE[ack] + DELTA[sqn, ack].

But that requires two things. The server need to have in memory the state with the aknowledged sequence number, and so does the client. So the server needs to keep the states in a FIFO stack, and wait for an aknowledgement number from the client.

Once an acknowledgement number is received, the server can discard the states up to that number. Similarly, the client needs to keep a stack of states as well, to rebuild the latest state.

here's a little exmaple I cooked up.

EDIT : note that the delta compression I use is a RLE encoding system. It's barely optimised, I'll sort it out later.

[Edited by - oliii on February 21, 2010 5:12:05 PM]

oliii to the rescue again? im flattered.
okay so let me sum this up to see if i get it.

every server tick the server calculates the new positions of the clients saves the state updates it then sends it to the client and continues to keep doing updates. The client then gets a state from the server uses the data to update its player, and continues on it's merry way, and informs the server the latest packet it has recieved. Now if there is any lag between the client and server, which there inevitably is, you dont want the server to send the last few sequences the player has missed during the server tick due to latency, instead you find out the difference between the server's curent state for that client, and the clients current state and send that off, and then the client updates accordingly,so in essence gets one state instead of many? Then the server and client can discard all of the older states? and thats why you use a queue(FIFO).

also what is this ack youkeep reffering to in your code, i know sqn is the number of the state as an identifier and which order in the update stack it comes, but what on earth is ack?

cheers

Quote:

Original post by homojedi oliii to the rescue again? im flattered.

Just something I meant to do for a long time, got a couple hours to spare, seemed like a good idea [grin].

Quote:

also what is this ack youkeep reffering to in your code, i know sqn is the number of the state as an identifier and which order in the update stack it comes, but what on earth is ack?cheers

the ack number is basically the sequence number returned by the client to the host. It's the client 'acknowledging' reception of a particular state. It's the important part that tells the host what state he can use to base his delta compression from.

On the client, it is the number that the server used as a basis for delta compression. It's the "ack of a ack" so to speak. Since server / client code works kinda similar, I kept the name.

Quote:

every server tick the server calculates the new positions of the clients saves the state updates it then sends it to the client and continues to keep doing updates.

yes.

Quote:

The client then gets a state from the server uses the data to update its player, and continues on it's merry way, and informs the server the latest packet it has recieved.

yes.

Quote:

Now if there is any lag between the client and server, which there inevitably is, you dont want the server to send the last few sequences the player has missed during the server tick due to latency, instead you find out the difference between the server's curent state for that client, and the clients current state and send that off, and then the client updates accordingly.

yes.

Quote:

so in essence gets one state instead of many?

no, the client will keep on receiving the latest states, except the latest state is in compressed form, based on another state.

Quote:

Then the server and client can discard all of the older states? and thats why you use a queue(FIFO).

You don't want to keep the states forever in memory. Once the client acknowledge reception of a state, you know that his further aknowledgement should have a higher sequence number, because you keep sending him higher sequence numbers :).

So, once a client aknowledges a state, all the states with a lower sqn can be discarded, and the server can base his compression on that latest acknowledged state, as he 100% knows that the client has it stored in his memory, and that it is also the most up to date on the client.

For the client, it's the same thing. Once it receives a delta[sqn, ack], where ack is the reference state used as the basis, any old state stored in his memory that is lower than that ack can be discarded, as the host should never refer to them again (unless you have packets out of order, but then you just drop them).

it's a form of 'sliding window' protocol. the state numbers on the client and server piggy-back each other. That also allows you to use a rolling sequence number, a sequence number that wraps around. I use a single unsigned char, which gives a maximum window of 128 sequences (out of 256 possible numbers). I acually limit it to 64 sequences, which at 33 fps, will give you a two second window. If the latency reaches two seconds, the 'game' will stall updates, until the client sends acks once again.

That method protects you against most of the internet quirks reasonably well. Packet loss, packet duplication, packet out of order, latency (up to a point), and keeps the state transmission lossless (no data is lost during transmission of a particular state, what you send is what you receive), although you may loose state transitions in the process (missing some intermediate states through packet loss).