4 ms·

Hey wheybags, this is not deterministic lockstep. That is an algorithm for peer-to-peer games, where each peer waits for the input from all other players befor

Hey wheybags, this is not deterministic lockstep. That is an algorithm for peer-to-peer games, where each peer waits for the input from all other players before advancing the game simulation. The deterministic part is because players share inputs (not simulation results) AND the simulation is deterministic for the same inputs. The lockstep part is because all clients advance at a coordinated pace. The Age of Empires series use this approach, and that’s why units don’t move immediately when you click. Starcraft uses this too, but it has some tricks to smooth the gameplay experience. Both are peer-to-peer with no single “server”. In the case of Reflect, we have a server-authorative simulation (not peer-to-peer). Clients send their inputs to the server, but they do not wait for the result, they instead predict the result locally without confirmation from the server. The server also rolls back time and then replays inputs to compensate for individual client latency. And the client corrects/reconciles their local simulation once the server sends a simulation result that included one of their inputs. The keywords for this algorithm are: - Server-authoritative - Predicted - Lag compensated (simulation rollback / server rewind / input replay) - Prediction reconciliation (local simulation rollback / local input replay / misprediction smoothing) I’m not sure if Reflect has it, but client-side interpolation is also a common feature in FPS games, where upon receiving a world update, the client will tween entities to their new positions/rotations over a fixed interval (such as 0.1s). This allows you to send updates to clients at only 10Hz but have entities move smoothly (without needing the client to locally simulate the physics of every entity). There is only one authority, the server, so determinism isn’t super important. However, it is nice to have for client predictions to reduce the occurrences of mispredictions. Mispredictions occur when the server state did not advance the way the client predicted. These can happen when: (1) Another client’s input changed the world state in an important way, (2) The simulation is not deterministic (e.g. the random number generation is not synced). In FPS games, (1) is impossible to eliminate. These mispredictions are often smoothed using interpolation. (2) should be minimised, but may actually be desirable. For example, Counter Strike does not sync the RNG for bullet spread randomness, to prevent “nospread” cheat programs from predicting where each bullet will go and instantly adjusting the player’s aim so the bullet lines up perfectly. https://www.gabrielgambetta.com/client-side-prediction-live-demo.html https://www.gabrielgambetta.com/client-side-prediction-live-... https://developer.valvesoftware.com/wiki/Latency_Compensating_Methods_in_Client/Server_In-game_Protocol_Design_and_Optimization https://developer.valvesoftware.com/wiki/Latency_Compensatin... https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking https://developer.valvesoftware.com/wiki/Source_Multiplayer_...

wheybags 3y ago
Yes, I know there's some differences in what you're doing here from classic deterministic lockstep, but the fundamental concept of syncing a queue of inputs from which the game state can be derived, instead of syncing the game state itself is the same, which is why I mentioned it. Also, while deterministic lockstep can be used peer to peer, it is not fundamentally a peer to peer model. Factorio for example, uses server authoritative deterministic lockstep, and has lag compensation (but only for certain actions like movement).
- meheleventyone 3y ago
  All multiplayer games sync a queue of messages to derive game state, that’s inherent in networking. Deterministic lockstep means that the speed of the simulation is dependent on the slowest member as everyone waits to get all the inputs before advancing a frame. You’ll get literally pauses and jank if someone is on a poor connection. That’s not the case here. The difference with this model of networking is what is synced in the lockstep case the simulation being deterministic means you only need to send inputs to keep the game in sync so you vastly reduce network traffic. In this case it’s not necessarily deterministic and the server sends back the new state to the clients after determining what it is as it’s the authority on what that state is. Clients can predict ahead by making the change locally but must correct mispredictions. In the deterministic case there can be no mispredictions and it’s a pain in the butt to ensure that your game is actually deterministic and resolving sync issues is a real pain. Factorio sounds like it uses a deterministic model that doesn’t wait to run in lockstep and instead reconciles errors that causes. The typical way of doing that is to rollback to a prior state where the simulation diverged due to missing inputs and redo the following ticks. That’s probably prohibitively expensive given the scale of Factorio versus something simpler like a fighting game so I assume there is a hybrid model and some extra info is sent by an authoritative source that can be checked locally.
- aboodman 3y ago
  FWIW, I don't think this is deterministic lockstep for the key reason that Reflect is not deterministic: https://i.imgur.com/q9FnN4R.png https://i.imgur.com/q9FnN4R.png The whole idea of DL as I understand it is to take advantage of determinism to reduce bandwidth. But Reflect doesn't do this. I think this is a feature for developers. It's nice to be able to have the server just do whatever it wants for whatever reason it wants. It also means you can use normal JS, and don't need to try and enforce determinism somehow. There are a lot of different names for these protocols floating around. Server Reconciliation is the one I found that best describes what Reflect does: https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html https://www.gabrielgambetta.com/client-side-prediction-serve... But in the end I felt like since we're going to continue to evolve this and have made specific choices, it made sense to give our version its own name so that we can refer to it.

wheybags 3y ago

Yes, I know there's some differences in what you're doing here from classic deterministic lockstep, but the fundamental concept of syncing a queue of inputs from which the game state can be derived, instead of syncing the game state itself is the same, which is why I mentioned it. Also, while deterministic lockstep can be used peer to peer, it is not fundamentally a peer to peer model. Factorio for example, uses server authoritative deterministic lockstep, and has lag compensation (but only for certain actions like movement).

meheleventyone 3y ago
All multiplayer games sync a queue of messages to derive game state, that’s inherent in networking. Deterministic lockstep means that the speed of the simulation is dependent on the slowest member as everyone waits to get all the inputs before advancing a frame. You’ll get literally pauses and jank if someone is on a poor connection. That’s not the case here. The difference with this model of networking is what is synced in the lockstep case the simulation being deterministic means you only need to send inputs to keep the game in sync so you vastly reduce network traffic. In this case it’s not necessarily deterministic and the server sends back the new state to the clients after determining what it is as it’s the authority on what that state is. Clients can predict ahead by making the change locally but must correct mispredictions. In the deterministic case there can be no mispredictions and it’s a pain in the butt to ensure that your game is actually deterministic and resolving sync issues is a real pain. Factorio sounds like it uses a deterministic model that doesn’t wait to run in lockstep and instead reconciles errors that causes. The typical way of doing that is to rollback to a prior state where the simulation diverged due to missing inputs and redo the following ticks. That’s probably prohibitively expensive given the scale of Factorio versus something simpler like a fighting game so I assume there is a hybrid model and some extra info is sent by an authoritative source that can be checked locally.
aboodman 3y ago
FWIW, I don't think this is deterministic lockstep for the key reason that Reflect is not deterministic: https://i.imgur.com/q9FnN4R.png https://i.imgur.com/q9FnN4R.png The whole idea of DL as I understand it is to take advantage of determinism to reduce bandwidth. But Reflect doesn't do this. I think this is a feature for developers. It's nice to be able to have the server just do whatever it wants for whatever reason it wants. It also means you can use normal JS, and don't need to try and enforce determinism somehow. There are a lot of different names for these protocols floating around. Server Reconciliation is the one I found that best describes what Reflect does: https://www.gabrielgambetta.com/client-side-prediction-server-reconciliation.html https://www.gabrielgambetta.com/client-side-prediction-serve... But in the end I felt like since we're going to continue to evolve this and have made specific choices, it made sense to give our version its own name so that we can refer to it.