Jump to content

  • Log In with Google      Sign In   
  • Create Account


quake 3's state based delta compression


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 greeniekin   Members   -  Reputation: 139

Like
0Likes
Like

Posted 09 March 2014 - 12:26 AM

So I have done plenty of reading about networking and made something that is similar to what I have read about with simple moving squares and thought I understood everything clearly.

 

Though as I decided to continue developing and wanted to do other things like say shooting I realised there are problems.

 

Now here is the hard part to explain

If I'm sending 20 packets per second and my frames per second is 60 and I am only sending the current state then I am missing 2 states(4 if 100 which some people insist in games like cs)

Which is fine for movement but not for shooting. Adding extra events start to ruin the simple state based system. 

 

The only way I can see this working if you delta compress the last 3 frames which will make the messages 3 times the size.

 

Is this what the quake 3 model does, because I have not seen any article mention this. Or maybe it I just can not remember any article mentioning this.


Edited by greeniekin, 09 March 2014 - 01:28 AM.


Sponsor:

#2 theflamingskunk   Members   -  Reputation: 254

Like
0Likes
Like

Posted 09 March 2014 - 07:27 AM

The Quake 3 model Delta Compresses Against the last known State. You can read more about it here: http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking

 

Unfortunately I most likely will not be able to help you further than that, but good luck!


Portfolio:

http://jel-massih.com/

 

Programmer - Commotion Games
http://recruitsgame.com/


#3 greeniekin   Members   -  Reputation: 139

Like
0Likes
Like

Posted 09 March 2014 - 09:33 AM

I seem to have confused everyone by saying delta compression. I understand the compression part.

What I do not know if multiple states for an entity are sent in the same packet.

 

when I said 3 frames are delta compressed I meant 3 frames are compressed and sent in same packet.

That article talks about the compression but does not actually say what was sent. Which is what I always hear.

 

Edit:

Just to further clarify

 

if i'm sending 20 packets per secound and I'm doing 60 game calculations(frames) per second then there are missing states.  which mean (60-20=)40 frames per second are not sent and things like a fire state may only last 1 frame then there is only a 1 in 3 chance that the shots will fire on the client.

So the only way I can think that it would be to pack extra previous states(the 2 missing) into the same packet. I was wondering if this is what the quake 3 model does.


Edited by greeniekin, 09 March 2014 - 09:40 AM.


#4 radioteeth   Prime Members   -  Reputation: 914

Like
0Likes
Like

Posted 09 March 2014 - 01:47 PM

the 'state' of the game is everything about everything at any given moment, regardless of frames, network updates, etc..

 

the network system in quake3 keeps track of the game states clients have acknowledged receiving thus far, so that it can cull older game state data from the delta compressed updates..

 

game ticks, frames, and packets aren't one and the same.. it's all about serializing and conveying the 'state' of the game.



#5 3TATUK2   Members   -  Reputation: 708

Like
0Likes
Like

Posted 09 March 2014 - 05:03 PM

Bullets need to be sent reliably. Ie, they must be guaranteed to be received. Send one original position shot. Then do all the physics simulation. Easy.



#6 hplus0603   Moderators   -  Reputation: 4970

Like
0Likes
Like

Posted 09 March 2014 - 09:50 PM

When you run simulation at 60 Hz, but send packets at 20 Hz, then you need to send three simulation/input packets per network packet. And, on the receiving end, you have to dequeue each of those three packets, and execute them at successive ticks! This means that received commands at the end of the packet are suitably delayed compared to received commands in the beginning of the packet. Basically, your send rate introduces another source of latency (in addition to transmission delay.)
enum Bool { True, False, FileNotFound };

#7 0BZEN   Crossbones+   -  Reputation: 2004

Like
0Likes
Like

Posted 10 March 2014 - 06:48 AM

As hplus says, you batch your inputs per packets. That should take care of the inputs, shots fired, ect... In any case, you need some determinism for client side prediction, so you have to play the same set of inputs on client and server, so you have no choice but to batch your inputs for sending. 

 

As for the state-state compression, it shouldn't matter if your game is running at 60 hz, or 100hz, and your network tick at 20hz, or 10hz. You take a snapshot of the game at an arbitrary time (A), you take another snapshot of the game at another arbitrary time (B), and you send the difference between the (A) and (B). Then what is guaranteed is that the client will have a matching state (B), provided the client has state (A) already.

 

If you want, you could do your shooting / reloading of guns using state-based updates, without sending 'I've fired a bullet' style messaging. Transmit the magazine capacity, and the total ammo capacity, and you should be able to replicate reloads and 'out of ammo' states. e.g. state (A) has clip_size(28/30). State (B) has clip_size(15/30). Player fired 13 bullets.

 

Another example,

State(A) has clip_size(2/30) ammo_size(115).

State (B) has clip_size(28/30), ammo_size(90).

Player has then fired 2 shots, reloaded a mag(30 bullets, now ammo_size(85)), fired another two shots, and picked up another 5 rounds (ammo_size(90)).

 

This technique is not very accurate. It's mainly for client-side updates, as an example, but you might get away with a lot that way, without the need for another type of event notification system. 

 

Consequently, the thing that might go missing are quick transitions and events not caught between snapshots. For example, imagine a flag being capped and returned within a couple of frames. Clients will miss the successive 'flag taken' + 'flag returned' messages, but would that really matter? 

 

You can always cache messages between frames if you really need to have the clients act on them, but that's kind of outside the purpose of state-based systems.


Edited by papalazaru, 10 March 2014 - 08:31 AM.

Everything is better with Metal.


#8 greeniekin   Members   -  Reputation: 139

Like
0Likes
Like

Posted 10 March 2014 - 06:50 AM

game ticks, frames, and packets aren't one and the same.. it's all about serializing and conveying the 'state' of the game.

I never said they were not the same. I said  that I have already implemented my first interpretation of quake 3 method which at the very least requires serialization and packets and game state as well as the compression. So I could not think they were the same. Also I explicitly said get the delta compression part out of your mind .

 

It is no doubt my fault as I am horrible at communicating. Why can't everyone just live in my brain.

 

 

Bullets need to be sent reliably. Ie, they must be guaranteed to be received. Send one original position shot. Then do all the physics simulation. Easy.

Why would bullets be guaranteed from the server to the client? if someone shot a bullet 1 second ago I'm not going to display it because it is out of date. If you think you need it to calculate someone's health that will be done by the players state on server.

 

hplus0603,

I am not sure if your talking about inputs from the client to the server or not. I understand from the client to the server of queuing commands.

 

I am more talking about getting entities sate that is on the server to clients so they can show the entities state. It is like the player input thing but in reverse. send 3 states taken at different times in a packet. not guaranteed though because we do not need old information.

It would have been nice to get a confirmation if that is what quake 3 uses or that this is the general idea of how this model should be implemented. I suppose no one really knows. 

 

Edit:
Missed papalazaru's message it was posted as I was writing.

 

Your idea about using state to communicate how many shots have been fired is interesting. I will give it some serious thought. Though things like flag caps I can represent with my broadcast event thing I have. 

 

 

I had a look around quake 3 source. Though it would take for ever to understand where everything is to figure out what to look out for.


 


Edited by greeniekin, 10 March 2014 - 07:12 AM.


#9 0BZEN   Crossbones+   -  Reputation: 2004

Like
0Likes
Like

Posted 10 March 2014 - 08:25 AM

Quake3 server->client state updates are not 'reliable' per-se. The client is merely a output device that displays whatever the latest server state is (with of course some client-side prediction added). For the client, you need some good accuracy on certain things (rockets, grenades), somewhat less accurate views (plasma streams, lighting stream), some where it barely matters (firing q3 machine guns, gatling gun in TF2). 

 

What you can miss are transcient events, which on the client side, should not matter greatly. It's all server authoritative, it only matters on the server where events need to be internally reliable for the game to transition from one state to the other. 

 

Another way of sending inputs, is to consider the inputs pretty much as you would with a normal reliable stream. You basically send all the inputs to the server that haven't been acknowledged by him. Then the server can replay client inputs he receives, sends back input sqn acknowledgements back to the clients. ect... Both replay the same stream of inputs.

 

The end result is that whatever your input catpure-rate and your network send-rate, the client will always send the missing inputs to the server, the client in the meantime can can run some client-side prediction, while the server will play the the input stream upon reception of input packets.

 

You can also add some safeguards client side, to stop him sending large input packets in case of catastrophic packet loss or latency. This can then trigger either a pause on the client side, waiting for the host to catch up, or some server corrections (due to missing inputs).

 

You can also send your inputs delta compressed as well (since the stream should be a reliable stream), to reduce your input packet size from the clients. 


Edited by papalazaru, 10 March 2014 - 08:29 AM.

Everything is better with Metal.


#10 0BZEN   Crossbones+   -  Reputation: 2004

Like
0Likes
Like

Posted 10 March 2014 - 09:21 AM

An example (completely untested), of what I would do for input transmission towards the host, and back.

// single set of inputs. 
struct Inputs
{
    float mousex;
    float mousey;
    float mousez;
    int mousebuttons;
    int keyboard;
};

typedef unsigned short Sqn;

Sqn sqnAdd(Sqn s1, Sqn s2)
{
    return Sqn(s1 + s2);
}

Sqn sqnDiff(Sqn s1, Sqn s2)
{
    return Sqn(s1 - s2);
}

bool sqnGreater(Sqn s1, Sqn s2)
{
    return  (s1 > s2) && (s1 - s2 <= 0x8000) ||
            (s2 > s1) && (s2 - s1 >  0x8000);
}

bool sqnGreaterEqual(Sqn s1, unsigned char s2)
{
    return (s1 == s2) || sqnGreater(s1, s2);
}

class InputStream
{
public:
    InputStream()
    : m_head(0)
    , m_tail(0) 
    {}

    // add inputs at the top.
    bool pushHead(const Inputs& inputs)
    {
        Sqn len = sqnDiff(m_head, m_tail);

        // to many inputs not acknowledged. 
        // Either pause the game, or carry on, but there will be a 
        // server correction later on when the server catches up.
        if(len >= MAX_INPUTS) 
            return false;

        m_inputs[m_head % MAX_INPUTS] = inputs;

        m_head = sqnAdd(m_head, 1);

        return true;
    }

    // read inputs from the tail.
    bool popTail(Inputs& inputs)
    {
        NEint len = sizeof(Inputs);

        // no more to read.
        if(len <= 0)
            return false;

        // get first input in the stream.
        inputs = m_inputs[m_tail & MAX_INPUTS];

        // push tail up.
        m_tail = sqnAdd(m_tail, 1);

        return true;
    }
        
private:
    // gives a 2 second window at 60 hz, before the server is stared of inputs.
    enum { MAX_INPUTS = 128 };
    Inputs m_inputs[MAX_INPUTS];
    Sqn m_head;
    Sqn m_tail;
};

class ClientInputStream: public InputStream
{
public:
    ClientInputStream() 
    : InputStream()
    , m_send(0)
    {}

    // acknowledge inputs from the tail.
    bool acknowledgeInputs(Sqn sqn)
    {
        // check sqn validity.
        if(sqnGreater(m_tail, sqn) || sqnGreater(sqn, m_head))
            return false;

        // re-align send sqn, if acknowledged past it.
        if(sqnGreater(sqn, m_send))
            m_send = sqn;
        
        // tail moved forward.
        m_tail = sqn;
        return true;
    }

    // add a set of inputs into a packet.
    int packInputs(const Inputs* inputs, char* packet, int packetLimit)
    {
        // send full state
        NEint len = sizeof(Inputs);

        // too much data.
        if(len > packetLimit)
            return 0;

        // crappy memcpy.
        memcpy(packet, inputs, len);            
        return len;
    }

    // add a set of inputs into a packet. Delta-compress if possible.
    int deltaCompressInputs(const Inputs* inputs, const Inputs* prevInputs, char* packet, int packetLimit)
    {
        // we have a reference state. 
        // do some delta compression between the two input blocks.
        if(prevInputs)
        {
            // meh... just send inputs uncompressed atm. work out some compression algo later.
            return packInputs(inputs, packet, packetLimit);
        }
        // no reference state. pack full-state.
        else
        {
            // send full state.
            return packInputs(inputs, packet, packetLimit);
        }
    }

    // build an input packet. 
    int buildPacket(char* packet, int packetLimit) const
    {
        // sanity check. Make sure we have room for packet header.
        // we pack in the first sqn, and the last sqn added to packet.
        if(packetLimit <= (sizeof(sqn) * 2))
            return 0;

        // iterators.
        int packetLen = 0;
        Sqn sqn = m_send; // Start from the send sqn.

        // pack sequence number of first inputs.
        memcpy(packet + packetLen, &sqn, sizeof(sqn));
        packetLen += sizeof(sqn);

        // pack sequence number of last inputs (placeholder value, until we know where we end up).
        int placeholderPtr = packetLen;
        memcpy(packet + packetLen, &sqn, sizeof(sqn));
        packetLen += sizeof(sqn);

        // write as many inputs as we can into the buffer.
        const Inputs* prevInputs = NULL;
        while((packetLen < packetLimit) && sqnGreater(m_head, sqn))
        {
            const Inputs* inputs = &(m_inputs[sqn % MAX_INPUTS]);

            // delta compress a single set of inputs, against the previous set of inputs (if available).
            int inputSize = deltaCompressInputs(inputs, prevInputs, (packet + packetLen), (packetLimit - packetLen));

            // fail to pack inputs, not enough room in packet.
            if(inputSize == 0)
            {
                // that was our first input, and we failed. 
                if(sqn == m_tail)
                {
                    // failed to pack any at all. Just bail. No need to send anything else.
                    return 0;
                }
                else
                {
                    // stop adding inputs and finish the packet.
                    break;
                }
            }

            // push packet pointer.
            packetLen += inputSize;

            // push the sequence number to the next input slot.
            sqn = sqnAdd(sqn, 1);

            // now is prev inputs, for delta compression.
            prevInputs = inputs;
        }

        // override the placeholder value for the last sqn added to packet.
        memcpy(packet + placeholderPtr, &sqn, sizeof(sqn));

        // update the sqn of the next send sqn.
        m_send = sqn;

        // we've reached the head. zip back to the tail, and start re-sending inputs.
        if(m_send == m_head)
            m_send = m_tail;

        // size of the data used by the inputs packet.
        return packetLen;
    }

    private:
        // sqn of the next inputs to send.
        Sqn m_send;
};

class ServerInputStream: public InputStream
{
public:
    ServerInputStream() 
    {}
    
    // read a set of inputs from a packet.
    int unpackInputs(Inputs* inputs, const char* packet, int packetLimit)
    {
        // send full state
        NEint len = sizeof(Inputs);

        // too much data.
        if(len > packetLimit)
            return 0;

        // crappy memcpy.
        memcpy(inputs, packet, len);            
        return len;
    }

    // read a set of inputs from a packet. Delta-decompress if possible.
    int deltaDecompressInputs(Inputs* inputs, const Inputs* prevInputs, const char* packet, int packetLimit)
    {
        // we have a reference state. 
        // do some delta compression between the two input blocks.
        if(prevInputs)
        {
            // meh... just send inputs uncompressed atm. work out some compression algo later.
            return unpackInputs(inputs, packet, packetLimit);
        }
        // no reference state. pack full-state.
        else
        {
            // send full state.
            return unpackInputs(inputs, packet, packetLimit);
        }
    }

    // get the Sqn to send back to the client for acknowledgement.
    Sqn getAcknowledgmentSqn() const
    {
        return m_head;
    }

    // [SERVER] parse an input packet. 
    int parsePacket(const char* packet, int packetLimit) const
    {
        // sanity check. Make sure we have room for packet header.
        // we pack in the first sqn, and the last sqn added to packet.
        if(packetLimit <= (sizeof(sqn) * 2))
            return 0;

        // iterators.
        int packetLen = 0;
        Sqn sqn;    // input packet iterator.
        Sqn last;   // end of iterator.

        // unpack sequence number of first inputs.
        memcpy(&sqn, packet + packetLen, sizeof(sqn));
        packetLen += sizeof(sqn);

        // unpack sequence number of last inputs.
        memcpy(&last, packet + packetLen, sizeof(last));
        packetLen += sizeof(last);

        // read as many inputs as we can from the buffer.
        const Inputs* prevInputs = NULL;
        while((packetLen < packetLimit) && sqnGreater(last, sqn))
        {
            // decompressed input from stream.
            Inputs inputs;

            // delta compress a single set of inputs, against the previous set of inputs (if available).
            int inputSize = deltaDecompressInputs(inputs, prevInputs, (packet + packetLen), (packetLimit - packetLen));

            // fail to unpack inputs, explode!
            if(inputSize == 0)
                break;

            // all right, we've got the next input to add at the end of the stream.
            if(sqn == m_head)
            {
                // add inputs to the head of the stream.
                // If we failed (because the stream is full), no matter.
                pushHead(inputs);
            }

            // push packet pointer.
            packetLen += inputSize;

            // push the sequence number to the next input slot.
            sqn = sqnAdd(sqn, 1);

            // now is prev inputs, for delta decompression.
            prevInputs = inputs;
        }

        // when reading inputs we should be reading up to the last sqn, no more, no less.
        SANITY_CHECK(sqn == last);

        // size of the input packet.
        return packetLen;
    }
};


Edited by papalazaru, 10 March 2014 - 11:29 AM.

Everything is better with Metal.


#11 hplus0603   Moderators   -  Reputation: 4970

Like
0Likes
Like

Posted 10 March 2014 - 10:15 AM

Why can't everyone just live in my brain


Be careful what you wish for... :-)

When it comes to server->client state communication, it's been so long, I forget exactly what Quake 3 does. Something that's generally done, is to baseline entity states every so often. For example, round-robin entities, with the "base" state of one entity per packet. Then, send the inputs for each entity to all the clients. Again, enqueued for the next X ticks of simulation. This lets each client simulate the game on its own. If there should be some divergence, then the occasional baselining will take care of that.

Another time to send entity state update is when you detect server-side interference; being shot, colliding between players, etc.

The state compression a la Quake 3 can still be transmitted the same way -- "state in this packet equals state in the last packet you acknowledged, with the following fields changed" and a bit mask for which fields changed.

Btw: Firing weapons happens so often and with such low latency in an FPS, that reliable messages for that doesn't seem like a good idea to me. The really important events that need reliable packets are mainly main entity creation/deletion -- player spawn, death, perhaps health pack pick-up, etc.
enum Bool { True, False, FileNotFound };

#12 zzzz....   Members   -  Reputation: 84

Like
0Likes
Like

Posted 10 March 2014 - 12:03 PM

 

Btw: Firing weapons happens so often and with such low latency in an FPS, that reliable messages for that doesn't seem like a good idea to me. The really important events that need reliable packets are mainly main entity creation/deletion -- player spawn, death, perhaps health pack pick-up, etc.

 

 

Agree -> UDP :-) Also didn't Quake3 use some kind of repetition of previous game states (in each packet transmitted) with unreliable sends? Kind of best of both worlds.


Edited by jbadams, 15 April 2014 - 02:18 AM.
Restored post contents from history.


#13 0BZEN   Crossbones+   -  Reputation: 2004

Like
0Likes
Like

Posted 10 March 2014 - 01:59 PM

 

 

Btw: Firing weapons happens so often and with such low latency in an FPS, that reliable messages for that doesn't seem like a good idea to me. The really important events that need reliable packets are mainly main entity creation/deletion -- player spawn, death, perhaps health pack pick-up, etc.

 

 

Agree -> UDP :-) Also didn't Quake3 use some kind of repetition of previous game states (in each packet transmitted) with unreliable sends? Kind of best of both worlds.

 

spinningcube

 

 

They used input duplication (cl_packetdup), but not state duplication, as it's unnecessary. 

 

You don't necessarily need reliable creation / deletion with reliable messages, it can also be part of the delta-compression protocol. (State (B) has entity E0, State (A) doesn't have entity E0 -> send entity E0 creation data + latest state). Maybe not as efficient as with a reliable stream, since you will send that creation data with every state until a state with that entity is acknowledged. 


Edited by papalazaru, 10 March 2014 - 02:04 PM.

Everything is better with Metal.


#14 zzzz....   Members   -  Reputation: 84

Like
0Likes
Like

Posted 10 March 2014 - 04:45 PM

 

 

 

Btw: Firing weapons happens so often and with such low latency in an FPS, that reliable messages for that doesn't seem like a good idea to me. The really important events that need reliable packets are mainly main entity creation/deletion -- player spawn, death, perhaps health pack pick-up, etc.

 

 

Agree -> UDP :-) Also didn't Quake3 use some kind of repetition of previous game states (in each packet transmitted) with unreliable sends? Kind of best of both worlds.

 

They used input duplication (cl_packetdup), but not state duplication, as it's unnecessary. 

 

 

Thanks, yes makes sense.


Edited by jbadams, 15 April 2014 - 02:18 AM.
Restored post contents from history.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS