Hello.

I am programming a bomberman clone which is basically working, now I want it to have network functionality.

I think p2p would be great, but for now I am using a client/server model, where the server has the actual state of the game and the clients are dumb ( not trusted ) and a bit behind the actual state of the game.

I have read many articles about interpolation, lag compensation and client prediction.

I don't want to talk about the first two, but I have a question about client prediction.

I am implementing reliable UDP on my own.

I don't trust my clients, so they don't send absolute position, they send commands like move up, move right, move down, move left and plant bomb. The bomb always gets planted in the center of the current tile that the player is on ( which is depended on his position of course ).

I have not implemented a way to regard the order of the packets, which of course can lead to errors like:

Player sends move up and move right ( in that order ), the client predicts these commands and moves up and right, now let's say these packets are received in the wrong order, then the player is first moving right and then moving up. Now if things are going really bad then the player may have collided with a wall when going right first and basically his final position is different. I can of course correct this error when the player receives the position from the server ( a possibility is to just ignore packets that are older than the last received packet ) but when the player also send a plant bomb command afterwards and the different final positions lead to him standing on a different tile, then the client predicts the plant bomb on a different tile than the server. I can of course keep history of the last actions and also correct this and when the player receives the bomb planting by the server it gets corrected. But this correction will look pretty ugly, since it will remove the bomb from one tile and have it appear on another.

I know this is a very unusual scenario, but it would have such a deep impact, since the gameplayer will suffer immensely.

I talked about an uncorrect packet order, the same error could also appear when a packet is lost of course... I can resend packets, but to be sure a packet is lost the client checks if an ack hasn't been received in 1 second. The problem is, the bomb timer ( bombs explode after 4 seconds ) is already counting down every since it was planted, when the client predicted it.

And the server has to also send the bomb planting to all its clients and there of course packets might also get lost and becoming aware of that also takes another second.

It's kinda frustrating, a player can also pick up powerups, but I'm not there yet, at this point I just want everything to run great with the move commands and planting a bomb.

What is the best way to implement reliable udp and how do you know if a packet hasn't been received? Basically I am acking the packets with redundancy so you usually receive multiple acks for a packet and you will only not receive an ack if you don't receive any packet for about a second.

In short: What does reliable UDP do or how to make a good implementation of reliable UDP and what about client prediction/error correction?

I have read so many stuff and have a basic idea, but on my specific game I can think of many scenarios that I can't really find a good solution for. Is 1 second too long to make sure a packet wasn't received? Usually an ack should arrive in about 200ms, right? ( when sending a packet to server takes about 100ms and the server sending the ack takes another about 100ms. but that of course is depending on the connection between the client and the server ).

I really appreciate anyone taking the time to read and trying to answer my questions, you guys are the best!

One simple way simple way to solve this, would be to add the latest second of packages to the current package. For a game like this it wouldn't add much overhead.

Assuming the game is running at ten or twenty ticks per second and each message is one byte (none, up, down, left, right, place bomb, use ability ...) unless you are planning on adding more than 256 actions one byte should be enough. your total package size will still only be (player id) + (current tick) + (action) * 20 == 28 assuming you use int32 for both id and tick.

This means that missed packages wont matter as long as it doesn't happen too many times in a row. But in that case the client has probably left the game.

The server should just send the state every tick with every players position and velocity (for client side prediction) and all active/recently exploded bombs.

In short: What does reliable UDP do or how to make a good implementation of reliable UDP and what about client prediction/error correction?

The solution is quite simple, just add a sequence counter, increase it for each send message. The receiver remember the last processed sequence number and does the following:

0. The sequence number is <=last processed one: just ignore this message

1. The sequence number is +1 from the last processed one: process this message, send an acknowledgement for each X msg (ack contains only seq.number of last processed msg)

2. The sequence number is >+1 from the last processed one: dont process the msg now, put it into a list (or hashmap seq->msg)

3. The sequence number is +1 and there are already messages in the list: process like 1., then take the message from the list with sequence number+1 and start like receiving this msg now

4. If the missing msg, the one with seq+1, is not received within x milliseconds, send a request to the sender to resend the msg again.

The sender just need to save the last X outgoing msg to resend it. If it gets an ack-msg about a certain sequence number, it can clean up its outgoing buffer.

some pseudo code:

hashmap<int,Msg*> msgBuffer;
int lastSeq = -1;
long lastProcessTime = currentTime();

Msg* incomingMsg = blockingReceive();
while( incomingMsg!=NULL)
{
    int seq = incomingMsg->getSeq();
    if(seq==lastSeq+1) {
        processMsg(incomingMsg);
        lastSeq++;
        sendAck(lastSeq);
        lastProcessTime = currentTime();
    } else if(seq>(lastSeq+1)) {
        // add to msg buffer
        msgBuffer.put(seq,incomingMsg);
    } else {
        // just ignore this msg
    }

    // next msg
    if(msgBuffer.contains(seq+1)) {
        incomingMsg = msgBuffer.get(seq+1);
    } else {
        // timeout after 100 ms
        if((lastProcessTime+100)<currentTime()) {
            sendMissingMsg(lastSeq+1);
        }

        // get next
        incomingMsg = blockingReceive();
    }
    
    
}

If you want both reliability and in-order delivery, why don't you use TCP right away?

UDP is really only an advantage if you don't need in-order, and more so if you can ignore lost packets (and ignore them fast), since that greatly reduces the maximum latency when packets don't arrive as planned. Insofar, UDP can be "much faster" in presence of packet loss because it doesn't do the stuff that TCP must do to provide the above guarantees (otherwise it's exactly the same).

On the other hand, if you need the above guarantees, UDP must, on the application layer, do the exact same stuff that TCP is doing. Except you can probably not implement something in a few weeks or work that can compete with 40 years of development and stress testing. Plus, you kind of waste your time implementing something that already exists ready-to-use.

If you want both reliability and in-order delivery, why don't you use TCP right away?

UDP is really only an advantage if you don't need in-order, and more so if you can ignore lost packets (and ignore them fast), since that greatly reduces the maximum latency when packets don't arrive as planned. Insofar, UDP can be "much faster" in presence of packet loss because it doesn't do the stuff that TCP must do to provide the above guarantees (otherwise it's exactly the same).

On the other hand, if you need the above guarantees, UDP must, on the application layer, do the exact same stuff that TCP is doing. Except you can probably not implement something in a few weeks or work that can compete with 40 years of development and stress testing. Plus, you kind of waste your time implementing something that already exists ready-to-use.

There are still some advantages when using udp for game networking. As far as I know NAT-punch-through is much easier with UDP than with TCP (only important if you use P2P). You can handle multiple connections on a single port, you can skip messages if necessary (e.g. position msg), you can relax the reliability (only send ack every 5 msgs).

If you want both reliability and in-order delivery, why don't you use TCP right away?

UDP is really only an advantage if you don't need in-order, and more so if you can ignore lost packets (and ignore them fast), since that greatly reduces the maximum latency when packets don't arrive as planned. Insofar, UDP can be "much faster" in presence of packet loss because it doesn't do the stuff that TCP must do to provide the above guarantees (otherwise it's exactly the same).

On the other hand, if you need the above guarantees, UDP must, on the application layer, do the exact same stuff that TCP is doing. Except you can probably not implement something in a few weeks or work that can compete with 40 years of development and stress testing. Plus, you kind of waste your time implementing something that already exists ready-to-use.

There are still some advantages when using udp for game networking. As far as I know NAT-punch-through is much easier with UDP than with TCP (only important if you use P2P). You can handle multiple connections on a single port, you can skip messages if necessary (e.g. position msg), you can relax the reliability (only send ack every 5 msgs).

Probably those are not worth the trouble...

I would say use TCP instead. If you are set to use UDP, why don't you use enet?

Ashman72's approach is the right one to follow if you want the in-order + reliable layers added to UDP. But keep in mind that in the case of lost packages you either need to wait for an ack message from the server with a too low sequence number, or resend them often any ways.

First case will stall the connection in the same way as TCP does it and second case will send more data.

I recommend the second approach where you send unconfirmed messages just in case they should have gone missing.

There is a naive and simple way of doing this - the one I explained in my previous comment - If you couple that with Ashman72's approach you'll get relaiable and in-order. Further more you wont need to resend the latest second of messages, but rather just the last few, as you no longer need them as a safety net, but rather for decreasing the likeliness of package loss.

Another appoach for this is to append each package by its previous package XOR the package before that:

package n => id(n) + content(n) + (content(n - 1) XOR content(n - 2))

In that way you can append two packages for the price of one. Afterwards you can easily recreate lost packages, unless three is lost in a row.

Thanks for your answers, I think I voted up every one of them, since they're all useful/helpful.

So my basic understanding is that redundancy is the way, I have to either send packets multiple times or have larger packets, because they contain older packets.

That was also the idea of my current implementation, to make sure an ack arrives I had a bitfield ( 32bit ) and every packet had of course a sequence number. The bitfield contained the acks of the last packets ( starting from the sequence number of the current packet ).

My current implementation wasn't finished of course since I still had some questions.

My game runs with 60fps, since I only want to send about 20 packets per seconds they contain multiple commands.

The thing that really bothers me is that I don't want to have a scenario that maybe incredible unlikely but still would be possible.

So my idea is to use redundancy to make sure my packets arrive and if they don't then this would mean that many packets were loss ( in a row ), but that on the other hand would mean the client has connection issues ( high packet loss, high ping etc. ) and I tell him that ( he gets kicked, the game stops until things are fine again or things like that.... ).

I also don't really need correct order of packets, I think I will discard packets, that are older than something already received, though the problem with that is that I cannot reject planting a bomb, since the client has already predicted this and therefore a bomb is ticking on his screen. What I can do is discard move commands and correct the players position over time ( over time to make things look nicely ) , this however could lead to a client predicting a bomb on a wrong tile ( since the clients position is wrong ) and error correction would look stupid ( removing the bomb on one tile and have it appear on another ). But I can't find a good solution for this, other than that I don't predict bomb planting at all and wait for the server to answer with the planted bomb, this will of course look less smooth, since you don't instantaneously plant a bomb when pressing the key for it. Or I will predict planting a bomb and even though the error correcting will look shitty it will usually be corrected after roundtriptime and also it is very unusual that this will happen at all. ( hope you understood what I mean )

I will incorporate Ashaman's approach in my solution but maybe use a variable depending on the ping for the timeout ( instead of using a constant value of 100 ms ).

I'm really trying my best to have decent networking, because I think if the networking sucks, then players will stop playing your game. I even know some famous games that really made me stop playing them, because there were problems with the connection. Castle Crashers for example or Sonic & All-Stars Racing Transformed.

Another appoach for this is to append each package by its previous package XOR the package before that:
package n => id(n) + content(n) + (content(n - 1) XOR content(n - 2))

In that way you can append two packages for the price of one. Afterwards you can easily recreate lost packages, unless three is lost in a row.

This is basically a simple/primitive way for forward error correction.

Problem is that the "unless" case is not exceptional, but the rule. Except on wireless, packets are not randomly lost because of noise or such. Packets are usually lost when either an endpoint runs out of receive buffer or an intermediate router runs out of forward queue. And then, they're lost in dozens.

Which means: You don't lose 1 random packet out of 50. Instead, you receive 1000 packets fine without losing one, and then you lose 10-20 in a row.

Which means: You don't lose 1 random packet out of 50. Instead, you receive 1000 packets fine without losing one, and then you lose 10-20 in a row.

Didn't know that. I got that wrong in my bachelor project then. But to be fair my supervisor was a researcher on mobile communication :)