# How to organize messages queue in a fast-paced multiplayer game

I'm trying to develop a fast-paced multiplayer game. I decided to build my own protocol over UDP and now I'm stuck with the following question.

The idea of the protocol is very basic and it's similar to many others:

• Client does NOT do any game logic except of some predictions (like smooth walking). It just sends 'ping', 'connect', 'disconnect' and 'keypressed' / 'keyreleased' actions to the server.
• On contrary, the server does game logic based on the users inputs and sends diffs to each client every 30 ms

As I already mentioned, the client sends 'ping' messages (to notify server that we're still alive when there's no other messages in some period of time) as well as 'keypressed' / 'keyreleased' stuff.

I thought that the 'ping' messages can be unrelirable -- the client sends them at steady intervals anyway, so if one was lost, nothing bad will happen.

However, such messages like 'keypressed' and 'keyreleased' should be reliable. By this I mean that the client should resend them in case of any failure and they should appear on the server in the same order they were sent (otherwise 'keyreleased' message could arrive before 'keypressed' resulting in the incorrect game behavior).

So, the questions is -- how is it usually handled? I mean, what is the right way to implement such logic on the server? Should I queue all incoming reliable messages in some container and wait until messages with smaller sequence IDs also arrive? If so, what should I do with unrelirable messages then? Because I definitely shouldn't wait before 'ping' message arrived (and there's a chance that it won't arrive at all). Should I use a distinct sequence numbers for unrelirable messages or should I make 'ping' messages reliable as well?

You should implement your UDP reliable as TCP.

On http://gafferongames.com/ you can read about packing packets, resending them, correcting errors. There is some pseudo-code (or this is written in C, I don't remember now) - which explains everything well.

Let's say that you have a struct (or a class) with currently pressed keys:

class Input{
boolean left,right,down,up,space;
}


I assume that you did something like:

while(someCondition){
if(30ms passed){
client.sendPacket(new Input(player.getPressedKeys()));
}
}


This is not enought, because the server won't know which packed was sent first - it won't get the order. This could make a situation like this: On your device you jumped and then went to the right (space, right) The server gets these packets in a wrong order (right,space) and send them to your opponent in a new order - which is unacceptable of course.

In this case, you should add a field which is known as a SequenceNumber (also used in TCP networking).

class Input{
boolean l,r,u,d;
long sequenceNumber;
}


With each sent packet your should increase the sequence number so the server knows the order too.

But this is still not enough. What about lost packets? This is UDP, some packet's wont arrive. In this case you should make a superultranitroushypersystem called a 'List' - which will be a history list of your packets.

Let's make a list (in Java):

ArrayList<Input> packetHistory = new ArrayList<>();


And now we do two tricks: - we don't send a single packet, but the entire list - when adding a packet to the list, when it's size it higher than 32, we cut a packet from the top (the oldest one)

We send a packet:

while(condition)

if(30ms passed){
Input input = new Input(player.getPressedKeys());
input.sequenceNumber = sequenceNumber++;
if(packetHistory.size() > 32) packetHistory.remove(0) // i'm lazy
client.send(packetHistory);
}


Now, the server each 30 seconds receives a list of 32 previous positions and look what happens here.

Each packet in the list has a sequence number, for example after ~1second we would have a list with sequence numbers from 32 to 64 (64 is the most fresh).

Now let's assume that this list is LOST in the universe somewhere, so the server didn't get the list with the packet '64'. But wait, we don't have to make any corrections because the next list which is already going out has the range 33-65 - which of course has the 64 in it. We don't need to send any requests to the client like 'oh dear client, please, I didn't receive the 64'th packet'. We'll get it in ~30 seconds cause it will be in the next incoming list. We've fixed the packets loss.

Edit If we lose more than 32 lists in a row (which is of course possible) we could change our idea a little bit. We can keep a second list of packets on the client from which we don't substract the oldest packet when sending the entire list. This is a critical list, which is substracted only when the confirmation from the server comes.

What happens when we lose more than 32 packets? We send a response to the server, that none of received 32 packets matched the sequence number. We could name this packet 'CorrectionPacket'. On the server we pack to it a server's sequence number so the client knows where to substract the critical list and send these lost packets.

An example:

Some time has passed from the start of the game. We currently have a list with packets 65-97. Server is waiting for packet 97. We also have a critical list which has the same amount of packets (65-97). Now the crucial moment - there's a storm and 40 next packets are lost in the universe.

Normal history list: packets 105 - 137 (we sent 40 packets) Critical history list: packets 65 - 137

Server still didn't confirm a packet with a number 97, and the next range that it received after the storm was 105 - 137. He sends the CorrectionPacket() with his local sequence number (97) to the client and the client looks in the critical list, cuts it below 97 (not needed) and send the entire tail - 97-137 to the server which corrects everything.

I hope you get the idea :) - you have to keep two lists, one for normal packets - 32 all time - which is small with integers and one with the 'older' history to solve problems like this, when you lose more than 32 packets.

Of course - it should be improved - but this is on your own.

At the start, you create a number starting at 0:

long serverSeqNum = 0;


When a list arrives, you check all of the packets in it:

for(Input input : receivedList)
{
if(input.sequenceNumber.equals(serverSeqNum){ // perfect, this is the packet that we're waiting for
player.process(input);
serverSeqNum++; // and increment a number, we're waiting for a next packet
}

}

// and here one more trick
// we should send the confirmation to the client with the server's sequence number - so it won't send not needed packets anymore. For example if we received a packet with number 64 and processed it, we don't need it anymore so we send a packet to the client:
server.send(new ConfirmationPacket(64));


And when the client receives it - cuts the historyList below this packet, so we don't waste our network and don't send packet's which are not needed.

Messages like 'JoinedQueue', 'EndedMatch' should be TCP - always - they have to arrive and we don't care if it takes 100ms to show the player his stats or 300 ms.

Messages like 'Ping' should be implemented on your own. I send them via UDP (so it shows the real speed, how the game goes) and store every 3 of them. If I have 3, I add them and divide by 3 and get the average ping of 3 last packets. This is a newbie solution - but it works well. Most of the common networking libraries have their own pings to keep the connection alive - you can easly read from them their values when the arrive.

You don't have to re-send pings and ACK them. Ping is just for user's information, if he's lagging or not. Of course, you CAN re-send them, ACK etc, but it's that's not crucial. You know how the ping works in games - it only shows the average (it changes by couple of sends, it doesn't update each 30 ms and shows a new value).

Via TCP you send only crucial informations - things that HAVE TO be performed no matter what, for example inform player that his opponent was disconnected.

With UDP you send anything else (positions, spells, jumps, health changes) - but always with lists/confirmations, cause they have to arrive in order.

You can do this, of course, you can send everything, but be aware that if you store everything - positions, inputs, health changes and thousands of things, when you lose some packets you would need to resend a collection with 150 or even 54323 elements which will cause a lag. And what if the entire list is lost too? :D

If you receive informations on the server on one listener and check the packet type, if it's a 'InputPacket' or a 'AbilityPacket' you can store everything in one collection but you should apply the same sequence number to all packets.

When you want to split your things and send 'InputPackets' and 'AbilityPackets' separately, you should create two lists, two sequence numbers and two threads for sending them from the client. Then, you can send Inputs for example every 20 ms, and Abilities every 5 - or even only when they're 'used' by the user.

Your solution is of course correct. Do some tests, write some things and you'll know what's the best option for you. It really depends on the game type.

• "But wait, we don't have to make any corrections because the next list which is already going out has the range 33-65 - which of course has the 64 in it" -- but what if we lost 32+ packets that contain message with seq. number == 64 (for example, due to network errors)? – FrozenHeart Aug 1 '16 at 9:14
• And it doesn't answer my question directly. What should I do with 'ping' messages? Because they should (at least I think so) be unreliable, so I don't need to re-send them every 30 ms – FrozenHeart Aug 1 '16 at 9:16
• Writing an edit atm ;) – Jacob Aug 1 '16 at 9:37
• Nice explanation, just two questions. Why do you keep two lists, wouldnt one list with alle the unacked packets suffice? And for the ping, wouldnt you want to filter? ping 5 times, throw away highest and lowest, then take average? – Niels Aug 1 '16 at 14:03
• If we're talking about performance - yes, of course, we don't need two lists, but you know, if someone is beginning his programming journey, he just want's to make something working. I just pointed two lists cause it's easier to visualize the whole system :) Filtering the ping is a great idea. Of course we could make some other improvements, like checking the exact arrival time and using it for more complicated calculations :) Nice point :> – Jacob Aug 1 '16 at 15:13