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.

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)

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?