The solution we used for managing secret state, when the state is from a random source, is to delay generating the secret information for as long as possible (so, e.g., if a card is drawn, the drawn card is decided at that moment, as opposed to pre-shuffling the deck at the start of the game). We experimented with some designs in which the secret is revealed only to the player who owns it, and the rest only see a verifiable hash of the secret until the player performs an action which reveals the secret; however, it doesn't solve the general problem that any time the game must immediately (without network latency) make a random choice, the design must compromise between either allowing a hacked client to predict the result (when the RNG output is stable) or manipulate it (when the RNG output changes very often, e.g. every frame).
Sadly, the newer games went for a simpler synchronization algorithm, in which if a discrepancy is detected, the entire state is simply copied over from one player's game to another. This does allow blatant cheating; I'm guessing it was a concession due to the new engine lacking in robustness or portability.
Although the Worms games are turn-based, gameplay typically involves performing a lot of actions within one turn. Walking, jumping, using utilities (which don't end your turn), and finally firing a weapon. Many of these actions can trigger an event with a random outcome, which should ideally be unpredictable and un-manipulatable, such as which weapon will be found in a weapon crate, or how long the fuse of a mine with a random fuse will be.
In a peer-to-peer game, the server is just another player, and should not be considered intrinsically more trustworthy. Ignoring latency, it's possible to implement a scheme of securely generating random data, in which everyone produces a verifiable hash (commitment) of a random number, and after everyone announced their hash everyone announces their random number, which is then XORed together to produce the outcome (see e.g. Keybase's "Cryptographic coin flipping"). The problem with this approach is that the latency to obtain the result becomes the roundtrip to the player with the slowest connection and back.
For example let's say we're at frame 999 and have 2 players and 10 deterministic NPCs. And each player has 4 possible moves 2 of which have results depending on a random number being <= X or > X.
So each client calculates the next possible frame states knowing its user input (so it only has max 2 options depending on the random generator) * possible inputs from the other player (2 + 2*2 = 6 options), so there's 12 possible game states for frame 1000 from this client POV.
NPCs are deterministic so they can react to the player moves in each branch.
The other client does the same but has different variables missing and different state tree (with small overlap that only depends on random generator).
Then both clients send their player inputs to the server and wait for the missing variables to choose which branch of the state tree they both go. Depending on the game we may not wait just show the most likely branch and if we mispredicted we switch to the right branch after we get missing data.
This state tree could be several levels deep if there's enough computing power, and it could also be used by AI to choose best moves assuming what player can do (but then it gets complicated).
Advantages:
- server needs much less computing power than clients
- server can still verify the state
- clients don't have information they shouldn't have
- network latency is mostly hidden
Disadvantages:
- more computing power needed on the clients
- can get impractical quickly with more possible moves on each turn
I am curious in what scenario of online gaming does this assumption fail.
I remember that about a decade ago there was a mobile game called Chaos and Order (like dota/League of Legends but was played on apple device). In one game, I heavily outplayed my opponent. After winning the match we added friends and realized that we actually experienced two totally different games - he lost it in my game but won it on his side, and my in-game actions made nonsense in his one. We called it a "ghost".
It is just funny to see how crappy the outcome would be if the deterministic propagation fails. Also in context such as system theory where error inevitably happens, the design shall make sure the extent of failure will not go unbounded.
They attempted to make their recent engine deterministic, and failed miserably - at least on PC: https://www.reddit.com/r/halo/comments/r78moa/halo_infinite_...
Attempted deterministic engine, no desync detection or reconciliation, and support for the whole PC ecosystem - I couldn't believe it when I realized what they were doing... pure madness (not in the good way).
I suspect it actually works fairly well for players on console, who aren't playing cross-platform (since they're working with basically the same hardware everywhere).
It used to be the case not so long ago.
For example, if the client in a wargame says it would like to move a unit (by name) from place A to place B on the battlefield the possible moves are implicit (units and locations are known) and validation is nontrivial but easy (the unit is at A and it can move, it can reach B considering fog of war, etc.). Far cheaper than sending 50 different moves for each of 50 different units and validating all of them preemptively every turn.
Your example is one that it's not the best for and you could use a different approach or amend the approach to take a payload for some actions and have some client smarts for those actions.
Although even in your example of 50 units with 50 moves each, having 2500 moves is certainly not a disaster in a game where the server only does work in response to a player's move and players don't take multiple moves per second and more likely take seconds or even minutes between moves.
The point is just every bit of logic about when an action is enabled must be implemented on the backend for verification, so spelling that out to the client reduces duplication.
I do still like this system for some games with actions that aren't convenient to enumerate; it's safe and simple by default and you add validation only in exactly the places where you need a payload.
I'm curious to know how you achieve not to need a server at all. How do you create the initial connection between clients without a server to negotiate NATs and things like that?
Aren’t game servers just chat servers with extra constraints on the messages, e.g. physics, chess rules, etc?
Regarding cheating and bad network, you still need all the same client side stuff and to define the conflict resolution policies into the CRDT, but the rest of the needed features (e.g. consistency, rewind, replays, etc) are all part of CRDTs.
In a chat, information is simple, unordered, and public (to all parties).
Now imagine a turn-based strategy game where complex moves happen in random order and are known to all players regardless of unexplored territory.
For real-time games this analogy really breaks down.
If you are willing and able to make a very extreme sacrifice regarding client-server architecture, it is feasible to consolidate all state to 1 synchronous domain while serving an arbitrary number of participants.
The sacrifice is basically to build your game as a native take on the Google Stadia model. I.e. inputs are raw player events, output is a low latency A/V stream back to player.
Keep in mind you don't have to always serve an x264 stream to all clients. Depending on your objectives and type of game, you can serve an intermediate view model that instructs the client on how to draw its view using local assets and resources (textures, models, gpus, etc). This would be more like how Blazor server-side model operates.
Player client sends simple commands to the server. Server validates the command and updates game state.
The server then just simply listens for other clients to request the state of the world, at which point it sends a compete blob of data that includes everything that client can see!
The player can then interpret that data and send new commands as required.
My games are basically turn based so I don't need to poll the server constantly, just at the start of your turn and after every action.
For example, in an FPS you turn a corner, see an enemy and shoot them. But unbeknownst to the client a grenade exploded just beyond the corner killing the player before the shot got off.
Now we have to deal with the mess of the client thinking you just shot somebody while you were actually already dead. While it's true that this is "simply" a client-side issue, you'll hear endless complaints from players who, from their perspective, turned a corner and shot the enemy and then died to a grenade, but for some reason their shot didn't connect and to them it seems unfair.
Another scenario: An enemy client is approaching a corner. The server sends you their position because it estimates they'll continue moving beyond the corner. You see the enemy and shoot them. But then the enemy client's lagging input comes in and they actually stopped short of turning the corner! How do we reconcile the fact that you've seen and shot an enemy you shouldn't have been able to?
Have you ever written about the architecture of that and Blight anywhere?
AJAX long polling is a good way to send data while avoiding spurious requests and/or delays, albeit with a bit more load on the server.
The alternative is an infinite action soup, which opens opportunities for inspiration by lateral thinking. I'm doing it this way for a single player Lovecraftian text editor I'm working on. It's a terrible idea for multiplayer things.
I hope that was not a typo and would love to see what a Lovecraftian text editor looks like.
Deterministic lockstep is like trying to build a house with wet paper. You'll need to stack and compress millions of layers to make it solid.
Delta-update while not the best for bandwidth, is the cheapest for moving forward. I don't want to waste time fixing desync issues, when I can be creating more games and more features.
I'm still writing about my experience and showing exactly how I built my Delta-update networking model, but its working really well so far.
for turn in game:
for player in players:
action = await player.get_action()
engine.dispatch(action)
Multiplayer video game networking is a standalone discipline in its own right. It feels like most Computer Science departments are producing candidates to work for BigTech co that are focused primarily with large scale data access/processing. But video games gets so specialized that it takes on its on form. To be more concrete, A.I./M.L. for finance is going to be different than video game A.I. Occasionally something like A* can be applied to a "real world" problem, precluding video games, but almost every video game programmer knows A*.
I'm curious, did you acquire your video game experience from working at Big Budget game, indie game, video game development school, self taught from special interest forums (if so, is there an equivalent of HN or Reddit), or a traditional CS education?