Quakemonkey: an implementation of the Quake 3 snapshot model on top of the existing network code

Because I’ve got some spare time this holiday, I decided to implement the Quake 3 network model. In short, this UDP-only protocol sends partial messages to each client in order to save bandwidth. These partials are created from the difference at byte level of the current message and the message that was last received by the client. It is built on top of the existing framework, so only two or three lines extra in the client and the server, and you’re good to go.



Some benefits:


  • UDP-only: fast connections

  • Delta messages: smaller packages

  • Byte-level deltas: invisible to user

  • No need to split up master gamestate

  • Built on top of existing framework

  • Easy way connection to client is lagging



Hopefully quakemonkey will provide an easy way for both beginners and advanced users to quickly set up an efficient server-client connection without having to worry about speed, UDP packet loss and managing lots of small update messages.

I am still polishing the code, adding some comments, and the following days I'll try to make the code adhere to the jMonkeyEngine style guide. The version online should be working.

Visit the project page to read the full overview, and of course, to download the code :)
7 Likes

Curious, how do you track which message was already received by the client?



In a test application, I had the full state update for 80 objects (including position and orientation) down to around 1180 byte UDP messages… trying to maximize MTU throughput. Byte level delta compression would be even better but I wonder if the back channel necessary to know what the client has already received complicates it too much.



I’ll have to try that.

I think with the message sent to the client you also have to send which message it is a delta from. After all, depending on how fast the messages are streaming in you could receive many messages between the time that the client sent the ACK and the server actually received it. The client would have to know the difference between messages sent before and after the ACK was received.



This shouldn’t be too bad, though. The message could include a general sequence number that is the current delta baseline. A byte or smaller could then be used as the delta sequence number… so adding these two together gives the actual message ID.

Messages sent from the server are packed in a LabeledMessage, which simply gives the message a label. This label is linked to the position in the snapshots array. When the client receives a LabeledMesssage it sends back an ACK containing the ID. When the server receives the ACK, it knows which message has been received and this message will be used to diff against in the future.



There could be one small problem with this setup, which I also marked as a TODO in the code. Imagine that the client receives a message and uses its contents, and sends an ACK back, but the ACK does not arrive. Then the server assumes that the message is not used. In most cases this is not a problem, but in the following case it is:


  • Master gamestate: 0 1 1 0
  • Sends to client, client ACKS
  • Master gamestate: 0 2 1 0
  • Sends to client, client ACKS but ACKS does not arrive
  • Master gamestate: 0 1 3 0
  • Now it diffs 0 1 3 0 with 0 1 1 0, and sends only the 3
  • The client nows receives the diff and creates the gamestate 0 2 3 0



    So the 2 is erroneous. This same behaviour also happens in Quake 3, I suppose. It could lead to some short glitches - probably very short - if the connection is bad.

awesome, good luck with it :slight_smile:

@pspeed said:
I think with the message sent to the client you also have to send which message it is a delta from.

Good idea. This also solves the issue I described above and the issue of packages arriving in different order. I just need to add a hashmap or cyclic array like structure to the client that keeps track of the received messages.

edit: quake seems to be doing something like this in the client (reference code, CL_ParseSnapshot).

I’ve implemented the changes. I still need to do some testing, but it seems to be working.

I like this library… Do you see a chance we add it to the contributions update center as a library people can add to their projects?

https://wiki.jmonkeyengine.org/legacy/doku.php/sdk:development:extension_library

Sure, I’ll see if I can turn it into a module next week.

I have created the module and made it Java 1.5 compliant, so I guess I am good to go to post the first version. My google code username is benruyl@gmail.com.

Okay, I added you https://code.google.com/p/jmonkeyplatform-contributions

Mind to use the https protocol for svn so you can commit :slight_smile:

After struggling a while with this error, I have pushed the first commit :slight_smile:

Sorry to gravedig a 2 year old thread, but…
What if you wanted 1 message to be instanced? E.g player state.
There’s no system for allowing a key to be set on a message, it assumes 1 instance of all messages only, and that’s a pretty poor system.

@fabsterpal said: Sorry to gravedig a 2 year old thread, but... What if you wanted 1 message to be instanced? E.g player state. There's no system for allowing a key to be set on a message, it assumes 1 instance of all messages only, and that's a pretty poor system.

I think you are supposed to send the entire game state at the same time

@ankangronto said: I think you are supposed to send the entire game state at the same time

Doing that is REALLY not scalable at all.

@fabsterpal said: Doing that is REALLY not scalable at all.

It was designed to have low latency and minimize bandwidth for the Quake 3 use case. So maybe it isn’t suited to your use case.

http://fabiensanglard.net/quake3/network.php

This is one of the things that makes networking had and what makes creating any “standard network state sync” library pretty much impossible.

Every game will have different requirements and the solution changes greatly depending on those requirements. Any approach to “real time” network sync that requires scalability will be 100 to 1000x more complicated.

Hi Ben,
great quake networking plug-in alternative, works well and quite stable, love it, however found a little bug in the client difference handler and the current position cyclic array using a short variable identifier, when current position hits the maximum short positive value, the current position identifier is then reset to zero, the bug I found was in the client handler side not handling the reset.

       [java]boolean isNew = curPos < lm.getLabel()
                || lm.getLabel() - curPos > Short.MAX_VALUE / 2;

        // message is too old
        if (curPos - lm.getLabel() > numSnapshots
                || (lm.getLabel() - curPos > Short.MAX_VALUE / 2 && Short.MAX_VALUE
                - lm.getLabel() + curPos > numSnapshots)) {
            log.log(Level.INFO, "Discarding too old message: {0} vs. cur {1}", new Object[]{lm.getLabel(), curPos});
            return;
        }[/java]

Was able to fix it using the following code, and posting this fix to notify you about the bug.

       [java]boolean isNew = lm.getLabel() == 0 || curPos < lm.getLabel()
                || lm.getLabel() - curPos > Short.MAX_VALUE / 2;

        if (lm.getLabel() > 0) {
            // message is too old
            if (curPos - lm.getLabel() > numSnapshots
                    || (lm.getLabel() - curPos > Short.MAX_VALUE / 2 && Short.MAX_VALUE
                    - lm.getLabel() + curPos > numSnapshots)) {
                log.log(Level.INFO, "Discarding too old message: {0} vs. cur {1}", new Object[]{lm.getLabel(), curPos});
                return;
            }
        }[/java]