• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
greeniekin

quake 3's state based delta compression

13 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites
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.)
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.
0

Share this post


Link to post
Share on other sites

 

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
Restored post contents from history.
0

Share this post


Link to post
Share on other sites

 

 

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
0

Share this post


Link to post
Share on other sites

 

 

 

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
Restored post contents from history.
0

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  
Followers 0