This covers dead-reckoning which is super interesting and tends to lead to designs where you "predict" things since that's easier to design for than reaction based game models with latency.
The other really common one is "lock step" where a common rng seed is shared and all player inputs are replicated. The game state then moves forward deterministically in "lock step" with all the players inputs. This is pretty common for RTS style games where a few inputs can drive thousands of units. Most also hash the game state and "resync" if a client is found to have diverged.
The article isn't about dead reckoning. The "prediction" here is the client predicting its own movement based on its (stale) state of the world and its inputs; no dead reckoning here. For other entities, you get authoritative updates from the server at low frequencies, so you interpolate to get smooth movement, and you see them "in the past" in some sense; no dead reckoning here either.
I you really want to split semantics dead reckoning term[1] comes from predicting your self position(which the article talks about).
Back when I was in games any sort of predictive interpolation was usually under the header of dead-reckoning. The big divergence for me was always prediction vs deterministic state at a fixed rate.
Predicting your self position based on known inputs, not on extrapolating your current position based on velocity and acceleration. With FPS-like controls with no inertia, you can absolutely do CSP without a trace of dead reckoning.
At some point I need to write a blog post about how VRChat works. We don't have dedicated servers and work primarily through rebroadcasting. It's tolerable from an airplane, tolerable, and we regularly have users in Russia, Canada, Japan and Thailand playing together. Some of our users regularly connect via satellite phones!
It's not perfect by any means, but the results are pretty good:
If it is we do something similar for https://dotbigbang.com although it still requires careful game design and engineering to work with worst case latency.
You can see this in action with our swarm game Straits of Danger where random viewers from chat and Day[9] streaming are hooked together through our regular infrastructure.
Tangentially related: I once read that EVE Online, the massive multiplayer space game, uses a technique to "slow down" the passage of time when network congestion or server CPU usage reaches a certain point, so that the game remains playable, but the infrastructure can temporarily take a sigh of relief.
I worked on EVE at the time this was done, although not on Time Dilation itself. It’s really even more interesting because EVE is written with Stackless Python. The team also outs out a lot of technical blogs about the features including TiDi so rather than explain it I can let the guy who wrote it do so from the past.
Well EVE is written in C++ with Stackless Python embedded so as you might expect parts like the renderer were already written in C++ but plenty of core systems have been rewritten over the years from Python to C++ although that those have been pretty herculean efforts of some very smart people.
This is true, but although the devs made a great effort to keep the game playable with time dilation (colloquially known as "TiDi" by the players), in practice the game will never slow down below 10% of "realtime", even in situations where the players create fights so complex that it would require slowing to 5% or even 1% of realtime in order for the servers to process every command correctly. This means that in the biggest fleet battles, many commands pilots issue are ignored by the server since it runs out of time to process every interaction before the next server tick. So those mega-battles that make headlines are typically dreaded by players due to the pain of playing when the game becomes unresponsive. Large alliance leaders typically tip off the devs before big battles so that the solar system the battle takes place in is simulated on the best servers that the developers have access to, which helps a little.
One other fascinating thing about EVE is that it has extremely slow server ticks - one full second, which would be unthinkable in any other online game I've played. Partly because it's very old (2003), partly because it's unsharded and every player on the globe from Australia to Germany is playing in the same persistent universe, in the same servers in London, and having high ping to the server isn't as noticeable.
> Unlagged uses a technique called “backward reconciliation” for hitscan weapons' hit tests. For the duration of a hit test, it moves players to where you saw them when you fired. (It knows because it sent you the player origins in the first place, it saves that information up in a history queue, and your fire command contains a timestamp.) After the hit test, it moves them back.
Moving player entities around like that is perfectly fine, as long as the entities' states are restored exactly, and as long as no code runs which requires players in their correct state while the server is in a backward-reconciled state. Unlagged is very careful about such things, so it doesn't present any problems.
The joy of writing and designing multiplayer games is the constant tension between cleverly hiding latency and trying to keep the view of the game somewhat coherent between players.
Probably the most relatable example is “peekers advantage”. A static player looking at a corner will always be at a disadvantage to someone coming round it if there is client side simulation of the local player. This is caused by the moving player getting round the corner and seeing the static player before the server is even aware of it (as they are locally ‘ahead’), the static player won’t see them until the movement makes it through the server to them. As such the advantage gets bigger as the round trip time between the players increases.
For the static player this manifests as seeing someone coming round the corner and having them dead to rights. Clicking the fire button, seeing the shot hit (in their local ‘ahead’ view) and then getting shot and killed by the moving player. Fast FPS games with short time-to-kill weapons are particularly affected by this which is why competitive games try to reduce the time the server spends sitting on updates by running at high tick rates.
If both players have a fast connection to the server (20-40ms) and the server is running at 60Hz (~16ms tick) peekers advantage still exists but is much less exploitable (~56ms best case). Versus the bad case where both players have a slow connection to the server (100-150ms) and the server is running at 10Hz (100ms tick) so best case becomes 300ms and the moving player enjoys an enormous advantage.
Yup which is one of the reasons competitive games host physical events and companies like Network Next exist to try to improve the packet routing situation. But at some point you can't beat the physics involved.
I haven't done any experiments but at those low figures it's likely imperceptible to people but I think it's important from a perception of fairness to have each participant with the same low latency. Like if one team averaged 10ms and another averaged 20ms that might not be a compelling competitive difference but just from a perception of fairness not having it is important.
> A static player looking at a corner will always be at a disadvantage to [a moving one]. ... The static player won’t see them until the movement makes it through the server to them.
Do you mean that an accelerating player has an advantage? If all the remote players are being simulated locally, I’d expect that to be just as good at predicting straight-line motion as for stationary players— The hard part is predicting player input, not kinematics.
I'm skipping out local simulation of remote players as a potential mitigation strategy to illustrate the core concept which is caused purely by latency and local client simulation of the controlled player.
Naive extrapolation can cause issues, for example players appearing briefly from behind corners on other peoples machines that they actually stopped behind.
How you might locally simulate depends a lot on the game simulation. Is it deterministic or not? Are more complex things happening like rigidbodies being simulated in a distributed manner that still need to collide reasonably and so on.
One of the more interesting techniques in my opinion is deterministic lockstep (DL). DL is achieved with fixed point numbers (or standard floating point but this is very very brittle) and an incredibly high level of attention paid to all sources of randomness, lest your clients become desynced.
DL allows your clients and servers to run the same simulation at the same time. Not “in the future” or “in the past”... at exactly the same time, frame for frame exactly equal. This means the server doesn’t have to dictate the transform results for any objects, they are entirely computed on the client.
My understanding is that while this sounds like the holy grail in theory, in practice it doesn’t work with a large number (read: greater than 2) of clients because “lockstep” means lowest common denominator latency. I am very interested in hearing ways to beat this limitation though, as it seems like an ideal model for network performance.
> in practice it doesn’t work with a large number (read: greater than 2) of clients
I'm not sure I agree with that. Pretty much all real-time strategy games use this sort of lockstep simulation, and many are perfectly playable with 8-12 players.
There are various techniques for hiding some of the latency (making it less obvious). For example, for an RTS game if you issue a move command to a unit, you might locally play an acknowledgement sound immediately and animate the unit starting to turn towards the destination even before it actually starts moving.
It's true that one player with particularly bad latency can ruin the latency for everyone. But the same is true even with just 2 players.
It's also worth noting that a lockstep simulation is probably not suitable for games where immediate feedback on player actions is required/desirable (e.g. a fast-paced FPS), due to the inherent extra latency of having to synchronise player actions to all clients before actually simulating them.
IIRC, the original DOOM netplay (and serial/modem) used deterministic lockstep. If you have a low enough latency and a solid guarantee against packet loss it works fine for FPS. Problem is, of course, that neither of those things are true outside of a LAN (and sometimes even within them).
Networked games touch on a number of general challenges with distributed computation:
1 Logical clocks used for synchronization. The clocks aren't literally synchronized, but the events taking place across multiple clocks(at least one per connection, and maybe more if concurrency within the client is accounted for) are all logged to an eventually-consistent timeline. How that consistency is enforced is where the trade-offs come in.
2. The closer the featureset resembles shared memory, the worse the experience is. Item duplication bugs were a common occurrence for so long because they express shared memory ownership in a fairly direct manifestation, and it takes a few roundtrips to verify ownership. Saying "I shot you", in contrast, is just sending a message, and can usually coexist with other messages.
3. Consensus algorithms that are governed by nominally human inputs and perceptions. Input manipulation and ESP tools are typical entry points for cheating. When we say "you cheated at this game", we're talking about an attack on consensus.
The thing that I think more could be done of is to ignore the notion of really playing "simultaneously", since we're already using logical clocks, and to focus instead on performance capture and reproduction with AI. The thing that we want out of the experience, generally, is better signal-to-noise, and that isn't had just by lowering the ping times and exhaustively tracking all the data, but by distilling player behavior into pertinent factors and then recreating them in approximation. We're already doing it, but our expectations force the reconstruction to stay close to real-time, which means consensus is constantly being disrupted by anomalous behaviors.
If we looked instead towards trying to create a bot that can accurately match each player's observed unique playstyle, it becomes easier to make "dream matches" that provide a rich signal for players of all types and skill levels. But current bots never throw that much effort into quality, hence their poor reputation as computer opponents persists.
This seems like a good opportunity to share this semi-technical article which talks about rollback-based network code: https://ki.infil.net/w02-netcode.html
I found this article very interesting and took away a lot of different ideas around how state can be modeled efficiently for networked games.
37 comments
[ 3.8 ms ] story [ 84.7 ms ] threadThe other really common one is "lock step" where a common rng seed is shared and all player inputs are replicated. The game state then moves forward deterministically in "lock step" with all the players inputs. This is pretty common for RTS style games where a few inputs can drive thousands of units. Most also hash the game state and "resync" if a client is found to have diverged.
I've wrote about all this in extensive detail, including a live demo, here: https://gabrielgambetta.com/client-server-game-architecture.... (it is in fact the third "further reading" in the article).
I you really want to split semantics dead reckoning term[1] comes from predicting your self position(which the article talks about).
Back when I was in games any sort of predictive interpolation was usually under the header of dead-reckoning. The big divergence for me was always prediction vs deterministic state at a fixed rate.
[1] https://en.wikipedia.org/wiki/Dead_reckoning
It's not perfect by any means, but the results are pretty good:
https://www.youtube.com/watch?v=jDZ0ThMma-A
From where to where rebroadcasting is done ?
If it is we do something similar for https://dotbigbang.com although it still requires careful game design and engineering to work with worst case latency.
You can see this in action with our swarm game Straits of Danger where random viewers from chat and Day[9] streaming are hooked together through our regular infrastructure.
https://youtu.be/bs1p22oI_V4
https://www.eveonline.com/article/introducing-time-dilation-...
One other fascinating thing about EVE is that it has extremely slow server ticks - one full second, which would be unthinkable in any other online game I've played. Partly because it's very old (2003), partly because it's unsharded and every player on the globe from Australia to Germany is playing in the same persistent universe, in the same servers in London, and having high ping to the server isn't as noticeable.
Moving player entities around like that is perfectly fine, as long as the entities' states are restored exactly, and as long as no code runs which requires players in their correct state while the server is in a backward-reconciled state. Unlagged is very careful about such things, so it doesn't present any problems.
https://www.ra.is/unlagged/faq.html
Probably the most relatable example is “peekers advantage”. A static player looking at a corner will always be at a disadvantage to someone coming round it if there is client side simulation of the local player. This is caused by the moving player getting round the corner and seeing the static player before the server is even aware of it (as they are locally ‘ahead’), the static player won’t see them until the movement makes it through the server to them. As such the advantage gets bigger as the round trip time between the players increases.
For the static player this manifests as seeing someone coming round the corner and having them dead to rights. Clicking the fire button, seeing the shot hit (in their local ‘ahead’ view) and then getting shot and killed by the moving player. Fast FPS games with short time-to-kill weapons are particularly affected by this which is why competitive games try to reduce the time the server spends sitting on updates by running at high tick rates.
If both players have a fast connection to the server (20-40ms) and the server is running at 60Hz (~16ms tick) peekers advantage still exists but is much less exploitable (~56ms best case). Versus the bad case where both players have a slow connection to the server (100-150ms) and the server is running at 10Hz (100ms tick) so best case becomes 300ms and the moving player enjoys an enormous advantage.
Do you mean that an accelerating player has an advantage? If all the remote players are being simulated locally, I’d expect that to be just as good at predicting straight-line motion as for stationary players— The hard part is predicting player input, not kinematics.
Naive extrapolation can cause issues, for example players appearing briefly from behind corners on other peoples machines that they actually stopped behind.
How you might locally simulate depends a lot on the game simulation. Is it deterministic or not? Are more complex things happening like rigidbodies being simulated in a distributed manner that still need to collide reasonably and so on.
DL allows your clients and servers to run the same simulation at the same time. Not “in the future” or “in the past”... at exactly the same time, frame for frame exactly equal. This means the server doesn’t have to dictate the transform results for any objects, they are entirely computed on the client.
My understanding is that while this sounds like the holy grail in theory, in practice it doesn’t work with a large number (read: greater than 2) of clients because “lockstep” means lowest common denominator latency. I am very interested in hearing ways to beat this limitation though, as it seems like an ideal model for network performance.
I'm not sure I agree with that. Pretty much all real-time strategy games use this sort of lockstep simulation, and many are perfectly playable with 8-12 players.
There are various techniques for hiding some of the latency (making it less obvious). For example, for an RTS game if you issue a move command to a unit, you might locally play an acknowledgement sound immediately and animate the unit starting to turn towards the destination even before it actually starts moving.
It's true that one player with particularly bad latency can ruin the latency for everyone. But the same is true even with just 2 players.
It's also worth noting that a lockstep simulation is probably not suitable for games where immediate feedback on player actions is required/desirable (e.g. a fast-paced FPS), due to the inherent extra latency of having to synchronise player actions to all clients before actually simulating them.
1 Logical clocks used for synchronization. The clocks aren't literally synchronized, but the events taking place across multiple clocks(at least one per connection, and maybe more if concurrency within the client is accounted for) are all logged to an eventually-consistent timeline. How that consistency is enforced is where the trade-offs come in.
2. The closer the featureset resembles shared memory, the worse the experience is. Item duplication bugs were a common occurrence for so long because they express shared memory ownership in a fairly direct manifestation, and it takes a few roundtrips to verify ownership. Saying "I shot you", in contrast, is just sending a message, and can usually coexist with other messages.
3. Consensus algorithms that are governed by nominally human inputs and perceptions. Input manipulation and ESP tools are typical entry points for cheating. When we say "you cheated at this game", we're talking about an attack on consensus.
The thing that I think more could be done of is to ignore the notion of really playing "simultaneously", since we're already using logical clocks, and to focus instead on performance capture and reproduction with AI. The thing that we want out of the experience, generally, is better signal-to-noise, and that isn't had just by lowering the ping times and exhaustively tracking all the data, but by distilling player behavior into pertinent factors and then recreating them in approximation. We're already doing it, but our expectations force the reconstruction to stay close to real-time, which means consensus is constantly being disrupted by anomalous behaviors.
If we looked instead towards trying to create a bot that can accurately match each player's observed unique playstyle, it becomes easier to make "dream matches" that provide a rich signal for players of all types and skill levels. But current bots never throw that much effort into quality, hence their poor reputation as computer opponents persists.
I found this article very interesting and took away a lot of different ideas around how state can be modeled efficiently for networked games.