In a simple, casual online game like Slither/Agar, would more experienced network/multiplayer developers say I need a proper game server, which maintains an entire world state and prevents clients from doing things they shouldn't? I need to prevent different clients from diverging wildly but can I do that client-side only using rollbacks and so on? I don't know many technical terms for different multiplayer methodologies / design patterns so if there are standard names you can suggest I google that'd be helpful, as well as your own suggestion of how to design something like this?

Multiplayer seems an area I could get sucked into ever more complex designs if I'm not careful.

Let's say I need to support 100 clients - not thousands, but not 10 either.

You're misunderstanding the nature of cheating - you can only do a client rollback if that client accepts that it needs to rollback (which a cheater's client typically will not), or if you know that it's cheating (which a cheater's client typically will not broadcast). The client is in the hands of the enemy and it can be tampered with or modified to do whatever the user wants. Expecting a client to self-correct cheating is like expecting prisoners to lock themselves in their cells.

Practically, a game developer has 2 choices to prevent cheating:

• A central server maintains the authoritative state, and prevents cheating because all game state changes must be accepted by the server by definition. This is a typical client-server game.
• All players maintain an essentially identical state, and prevent cheating by ensuring that they all agree on what the state is, and reject players who disagree with the majority. This is sometimes called 'deterministic lockstep' or some variation.

Your game type will not scale to the second solution, so you need the first.

Yep, exactly as Kylotan says. Client-side anti-cheat is an example of "security through obscurity" at best. It's not a secure model at all.

Of course, the one caveat is that some games don't need anti-cheat at all. Namely, games where cheaters can just be banned on sight, or otherwise would be unable to ruin the game experience. AssaultCube opts to have no cheating prevention, for example; instead, the players can all vote to ban anyone they want out of the game.

Oh of course a client can't be trusted but non-tampered clients would reject the input from the dodgy one was my point... the results wouldn't tally. In this case every client effectively is a server+client. 

But I was more talking about the roll-back approach to defend against mistakes rather than deliberate cheating.

@Kylotan makes the valid point that scale requires a central server, even if all it does is post updates between all clients and do very minimal checks. However even here wouldn't clients typically have dual gamestates - the most recent server state and the current client state - to have smoother gameplay where we only roll-back if the server state mis-matches the client state. i.e. the client predicts what is going to happen, asa  way to reduce laggy artifacts?

Okay, there seem to be a few concepts being mixed together here. I'll try and unpick them.

If clients can broadcast the entire game state to each other, then sure, they can decide to reject any client whose game state doesn't match, based on some sort of majority system. Obviously broadcasting the whole state is impractical so you might have some sort of rolling checksum system. That at least guarantees that all connected clients have some representation of the correct game state in memory.

If clients are just transmitting inputs to each other and each client simulates locally via a deterministic simulation then that also works, except there are a bunch of practical issues such as ensuring every client has time to transmit, preventing some clients from gaining an advantage by deliberately transmitting last, etc. These are surmountable, but not necessarily trivial.

Some games - not all, probably not even most - might implement a rollback system under certain circumstances. This is usually only for the situation where you are allowing your local player to simulate ahead of the server AND the server occasionally makes a different decision regarding where the player actually is or about some other aspect of its state, and issues a correction accordingly. These conditions are not compatible with a peer-to-peer system - firstly, who would decide when a rollback needs to happen? And secondly, how can you keep 100 players in sync by ensuring they have the same game state, when you explicitly allow each client to have a different state for its own player entity?

Rollbacks in this context are not really about mistakes but about correcting for situations where 2 simulated game states diverge. It's not about lag (although increased or changing lag might increase the chance of divergence) but about the inherent problem of allowing clients to pretend that they're authoritative when they're not.

Keeping past states in order to implement interpolation is orthogonal to all these concerns. It's a client-side luxury which makes it look better when you're moving and rendering objects 30 or 60 times a second but only receiving updates about those objects 10 times a second (example numbers). It has nothing to do with rollbacks. You can (and probably would) use these states to implement smoothly rendering and moving entities even in a simulation where there is no possibility of or need for rollbacks.

In terms of scale you're on shaky ground anyway because you're talking about having no server but 100 players, which means each player presumably has 99 connections that have to work in a reliable and timely way. And if each client has to have the same game state, then that means each client has to have the whole game state, which can be expensive in terms of bandwidth.

Let's make this more concrete. Imagine you, as a player, hack your client so your can move at twice the speed, giving yourself an advantage. If you are just transmitting positions to other players, they have no obvious way of seeing that you're cheating and will presumably just simulate your character moving quickly through the world. If they all implement a system for checking your effective speed, you can decide to disconnect such a player, and that is an effective strategy, providing you have such a process for every relevant game system. You could switch to just accepting inputs instead of positions, and trust each client to simulate the speed correctly - but this is very likely to get out of sync quickly for games where entities move in continuous time and space, meaning you'll start seeing gamestates drifting apart - no-one can cheat, but the game can be inconsistent (e.g. 2 players both collecting the same item).

A server solves these problems, by forcing all the important logic to go through the server. It decides what really happens and tells everyone about it. It can't get out of sync with itself and no amount of client hacking can change the server logic (if implemented correctly).

Great post, thanks!

Is it normal/desirable that every client and server works in terms of frame number i.e. a fixed time-step, regardless of rendering? So a client says "at frame 1234 X happened"?

The last multiplayer game I worked on had this, and of course the issue is the server receives updates from clients not always in sync. You don't want to lock-step everything (I think) as one person's slow connection lags everyone. But the server is potentially getting frame 1236 from client B before it has got 1234 from A. What happened here was that the server did two things in parallel (as I remember it):

1. Apply the updates in the order they are received
2. Apply them in the order of their frames

And then check if the states match, and retrace its steps to the frame things diverged. This is what I'm calling rollback and I hadn't seen it before. So the server would have a state at frame 1236 which was malleable and another at 1234 which was locked in.

In the past I've heard advice that clients and server shouldn't try to be locked in sync but each should spit a constant stream of updates so things out of sync quickly get corrected. But you surely still need a way for the server to have a 100% accurate world-state... so for a fast-paced, relatively simple game is there an obvious design pattern to use? Maybe there's something I can read up on or a book you can recommend?

(and yes let's assume this is a client-server not P2P world now as that seems obviously the right direction)

1 hour ago, d000hg said:

Great post, thanks!

Is it normal/desirable that every client and server works in terms of frame number i.e. a fixed time-step, regardless of rendering? So a client says "at frame 1234 X happened"?

The last multiplayer game I worked on had this, and of course the issue is the server receives updates from clients not always in sync. You don't want to lock-step everything (I think) as one person's slow connection lags everyone. But the server is potentially getting frame 1236 from client B before it has got 1234 from A. What happened here was that the server did two things in parallel (as I remember it):

1. Apply the updates in the order they are received
2. Apply them in the order of their frames

And then check if the states match, and retrace its steps to the frame things diverged. This is what I'm calling rollback and I hadn't seen it before. So the server would have a state at frame 1236 which was malleable and another at 1234 which was locked in.

You're still confusing things.

In a lockstep environment, the server will receive client inputs and it must apply them in the order of their frames. Anything else will cause desync. This means the server can't simulate too far behind because it must wait for everyone's input. And this is why it doesn't scale to many users.

In a prediction-based, server-based network model (aka Quake's Multiplayer), client inputs can be applied in any order. But typically for responsiveness reasons you'll want to apply them in the order they're received (inputs aren't frame numbered, but packets still are sequenced) and discard inputs belonging to past packets.

For example if you receive packet 0, packet 2, and packet 1, in that order, then packet 1 should be ignored (unless you're receiving all those packets at the same time, in which case you sort them first, and apply them in order).

This potentially means if the user hit a button for one frame and its packet gets lost or reordered, then the server will never see that he pushed that button.

But that's rarely an issue because:

• In a UDP model, most packets actually arrive just fine for most of the time.
• The user isn't that fast to push a button for just 16.66ms
• Button presses that need to be hold down (like firing a weapon in a shooter, or moving forward) aren't a problem.
• Worst case scenario, you can send this "button pressed" message repeated in several packets, and the server gives it a small cooldown to prevent acting on this button push twice; or instead of a cooldown, this message is sent with a "I hit this important button 2 frames ago"; and the server keeps a record to see if that was done. If it wasn't, then we do it now.
• Alternatively, worst case scenario the user will push that button again.

To put it bluntly, a client-server Quake style model is like a mother and her child. The child has a toy gun, but the toy only makes a sound when the mother pushes a button in a remote control in her hand. The kid fires his toy gun but nothing happens, then suddenly 5 seconds later the toy gun begins making sound. The child says "Why mom!?!? I pressed this button 5 seconds ago! Why is it only reacting now!?" And the mother replies: BECAUSE I SAY SO.

Client/Server models are the same. The client says what it wants, but the server ends up doing what it wants. (have you ever played a shooter where you're clearly shooting at an enemy but he doesn't die? and suddenly you're dead???)

Now, the internet is unreliable, but it isn't that unreliable. It's not chaos. Normally most packets arrive and they arrive in order, and when they don't, it's hard to notice (either because nothing relevant was happening, or because the differences of what the client said it wanted and what the server ended up doing are hard to spot) and this is further masked via client side prediction (i.e. the weapon firing animation begins when the client pushed the button so it looks like it's immediate, but enemies won't be hit until server says so).

Errors only get really obvious when the ping is very high (> 400ms) or your internet connection goes really bad for a noticeable amount of time (e.g. lots of noise in the DSL line, overheated router/modem, overloaded ISP, overloaded Server, Wifi connectivity issues, etc) and thus lots of packets start getting dropped or reordered until the connection quality improves again.

For more information read Gaffer on Game's networking series, and read it several times (start from the bottom, then to the top articles)

52 minutes ago, d000hg said:

Is it normal/desirable that every client and server works in terms of frame number i.e. a fixed time-step, regardless of rendering?

It is common. It might even be the most common method. It's not essential. You can just do things based on real time instead.

I'm not going to dig into the meat of your other questions because I don't use frame-based systems or lock-step methods. There are a variety of ways to handle state synchronisation and they are all very dependent on the type of game you have. Slower games can require that every player responds within some arbitrary frame time. Perhaps more common is to have an asynchronous system where it's known that commands will take some time to arrive on a server and therefore the simulation can advance a small amount before needing to have heard back from the other side, perhaps covering this up with a sound effect so that it feels responsive even if the unit hasn't started moving yet. And yes, the most fast-paced games will have to advance the simulation significantly and since waiting for a response is too slow, they remember what they did in order to potentially rewind and replay the actions after a rollback of some sort.

For an Agar-like game, I'd just transmit positions from client to server, and have the server broadcast out those positions, after having verified that the distances are not implausible. The client can happily render the player's character assuming that the position changes will be accepted, and it can render changes to everything else whenever the server sends the data. This will lead to tiny visual inconsistencies when 2 moving entities approach each other but that is unavoidable if you want to do any prediction.

One theoretical point that I need to make - in a client/server game, yes, it is essential that the server has a 100% authoritative state but that actually places no requirements at all upon the clients. This is because the server state is authoritative by definition. The clients merely make requests to change that state, and sometimes they display things on the assumption that their request was accepted.

Thanks guys, that's most helpful. I'm already getting in too deep to the "make it perfect" trap rather than "the server decides, everyone does what the server says". A messy, imprecise system is clearly just fine - then you end up trying to make it look less messy ore on the client side rather than trying to make the underlying simulation perfect?