Multiplayer Networking: How to deal with unordered packets?

Both of what you described are common.

It is typical to have several sub-channels communicated with packet headers. Some messages are mandatory and reliable, they will be repeated until acknowledged. Some are unreliable, you will probably get them but there's a chance you won't. Some Some you will require a strict ordering, others a weak ordering. You might implement more variety as well to implement idempotentcy so duplicates don't cause problems, and other features more typically associated with TCP and stream based protocols.

The replication you described sounds similar to what Unreal Engine does, it's not the only technique but it works well enough. The server tracks what is held on each client and updates it based on relevance and priority, which is based on several factors including staleness. Clients are not in perfect lockstep and occasionally get out of sync, rubber-banding when they get correct information. It tends to be a good mix of both performance and error tolerance for action games.

There are plenty of approaches, including running in lock step. What you use can be adjusted to fit your game. Board games like Go or Chess don't need unreliable messages nor dead reckoning, for example. You can implement transaction processing, up to and including the database guarantees if you want, dropping performance in exchange for reliability. Do what makes sense for your needs.

If you get messages out of order, then it's reasonable to keep track of the last received serial number, and ignore any message received that has a serial number lower than the last-received serial number.

You don't need to send the full serial number, btw, sending the lowest byte (8 bits) is plenty, as the remote end will know to increment the corresponding serial number appropriately to match. If you lose > 127 packets in a row, then this could go out of sync, but you probably should disconnect if you see more than that missing anyway. (Let's assume you schedule at least 20 packets a second; if you don't get packets for 5 seconds, that's 100 packets, and at that point, you're unlikely to be in sync with the game anymore.)

@frob probably should've been a little bit more clear in my original post that I'm trying to implement client side prediction for an FPS shooter. I'm tending towards the throw away any out of order packets, but I'm worried that this will cause a lot of rubberbanding. Is this what is done in practice for those kind of games?

overman1 said:
Is this what is done in practice for those kind of games?

What you described is part of many common approaches. There is no One True Path™ that will do it.

To dig deeper you might look at how Unreal works, or how GGPO works, as both have source code publicly available. I'll caution up front that each is many thousand lines of code.

For packet transmission, yes you'll want to have a data stream that includes player updates with the last known state. If you miss an update and get a newer update, you'll want to keep the latest state around. Prediction usually relies on knowing the player's action in addition to state. That is, it isn't enough to know the position and orientation, you also need to know the full physics plus the player's action; if the player is stopped presume they'll continue being stopped, if they're walking or jumping or flying or falling or swimming or driving, continue simulating as though they are walking, jumping, flying, swimming, driving, or whatever. You might decide you need to acknowledge these updates, or you might decide to bundle them in with other acknowledgement methods. All of that will be up to you.

It's been different on every game I've worked on. I've worked in Unreal, The Sims Engine, Frostbite, Slipspace, and several smaller games with custom networking, as well as using libraries from first-party systems like Nintendo's networking system that has the option to do that work. Every one of them does it differently.

Once the player changes action (like starting to walk, starting to run, turning, jumping, etc) you'll need to do something to handle the difference between the server and clients. Resolving that difference depends on the games. For Unreal, their replication system encodes some data and rubber-bands, plus if you're using Unreal's character motion component it's got about 13,000 lines of code on how to predict and handle differences in networked character motion. GGPO has something different yet still similar at trying to predict, rollback, and re-synchronize.

Since you're building your own game you'll need to figure out what it means in your own simulation.

@overman1 UDP is generally quite good. You will not get a lot of rubberbanding in the normal case.

The main case where UDP may start re-ordering, duplicating, or dropping packets, is when you're on a marginal Wifi connection. Those are actually about as bad as networking conditions get – one reason why FPS players generally don't like playing on Wifi.

More importantly: The alternative is worse! If you don't drop an out-of-order packet, then you instead have to wait for the out-of-order packet to be re-sent, which means you'll have to wait even longer to update the view of the player, than if you just went with the latest you've got.

@frob Thanks for the really insightful advice. I think I'll have to go back and re-examine how I'm handling those state changes, because right now I'm just keeping track of some pretty basic things. Fortunately, I'm using the Mirror library for Unity so I don't have to deal with the super low level stuff related to UDP!

frob said:
To dig deeper you might look at how Unreal works, or how GGPO works, as both have source code publicly available. I'll caution up front that each is many thousand lines of code.

Any tips on working through those lines of code? I get really confused pretty fast especially when the code bases are set up in such a way where there's a manager managing a manager managing a manager etc…

I always recommend this video, which covers many of the concepts above:

3 other things to consider:

1. Mirror isn't that great, Make sure it's not doing dumb stuff, make sure you're using the right transport, etc.
2. You don't need to throw away out of order messages, only those that arrive too late to be useful or those which are superceded by other messages.
3. You're always going to get some message loss, so on one hand you do need to actively mitigate against it with redundantly sent information and state interpolation to cover ‘gaps’, but on the other hand you want to be careful not to let these hide bugs.

you either collecting every communication in some buffer and manually memcpying things around… or you just go with tcp instead.

you either collecting every communication in some buffer and manually memcpying things around… or you just go with tcp instead.

Kylotan said:

I always recommend this video, which covers many of the concepts above:

3 other things to consider:

1. Mirror isn't that great, Make sure it's not doing dumb stuff, make sure you're using the right transport, etc.
2. You don't need to throw away out of order messages, only those that arrive too late to be useful or those which are superceded by other messages.
3. You're always going to get some message loss, so on one hand you do need to actively mitigate against it with redundantly sent information and state interpolation to cover ‘gaps’, but on the other hand you want to be careful not to let these hide bugs.

1. Damn…
2. I ended up throwing away commands that arrived too late and that helped significantly. The performance is way better now and there is not stuttering