Deterministic Lockstep with UDP.

Discussion in 'Programming' started by flyingsaucerinvasion, Feb 17, 2018.

  1. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,240
    Does anyone here have experience with doing networking in this way? Can you offer some advice on the sucbject before I jump into it?

    Did you encounter any tricky gotchas you'd like to warn me about?

    What kinds of games would or would not work well with this networking strategy?

    How many frames behind does your simulation run? Does that number vary over time? What happens during a network interruption or lag spike?

    Are there any non-deterministic things in GML that I should be aware of, other than player input, randomize(), delta timing, and box_2d stuff? Also, I am under the impression that randomness should be deterministic across different computers on the same platform, given that all machines use the same seed of course. Is that impression absolutely correct?

    EDIT: Also, if you have any general experience building relaiabilty systems out of udp, I would appreciate any advice.
     
    Last edited: Feb 18, 2018
  2. PNelly

    PNelly Member

    Joined:
    Jun 20, 2016
    Posts:
    256
    Lockstep:

    Age of Empires II actually used this kind of design in its multiplayer to great advantage. This Gamasutra article - https://www.gamasutra.com/view/feature/131503/1500_archers_on_a_288_network_.php?page=1gives a great overview of the scheme and some of the problems the development team had to tackle. A design choice of theirs I thought was particularly interesting is that a delay was built into the game so that each machine could maintain a queue of commands to execute, which helped smooth out the impact of latency swings during a session.

    As you're probably aware since you're asking a question like this, network design for multiplayer game generally falls on a spectrum that runs from total lockstep to maximum client side prediction. AOE is an example of the former, Halo 2 would be an example of the latter. The two biggest advantages of lockstep are (1) packet size will be much smaller, since you need only describe the inputs to the system, instead of having to describe the state of the system, and (2), development will generally be much easier because lockstep reduces (or in the extreme eliminates) opportunities for desynchronization.

    Lockstep's big drawback is responsiveness. Each client machine has to wait until it has all of the inputs of the current frame before it can advance to the next frame. So in the best case the fastest the result of a player issued command can be seen is the round trip latency. Additionally, the inputs of every player have to collated before an update can be issued, so the game can only advance at the pace of the slowest player connection in the session. The slower responsiveness of lockstep ends up determining what game types it's suitable for. Namely, those where instantaneous feedback isn't an important part of the player experience. This makes lockstep a great choice for games like Age of Empires, where the nature of the interface makes the delay unnoticeable, but a very poor choice for fast-twitch games like Halo 2, where the foundation of the player experience is the tight feeling of the controls.

    Determinism:

    Your biggest enemy with determinism is different floating point behavior on different machines. This Gaffer on Games article gives a good description of the problem: https://gafferongames.com/post/floating_point_determinism/. It is fairly monstrous. In short, it is not easily achievable to make the same code produce the same floating point results on different platforms. The amount this matters varies with the nature of your project. Inputs into a physics simulation with calculations being performed on multiple machines is basically a no-go (certainly with GM), but if you don't have much interdependence between calculations (unlike a physics simulation) then it might not be such a big deal.

    Alternatively, you can ditch floating point numbers all together. Integer-based math can easily be deterministic across platforms. Banks for instance, perform financial calculations on integer values of cents rather than on fractional values of dollars, because it allows complete precision and will give the same results regardless of platform. In the world of games, you can do things like describe player positions using integer values, and as long as your base unit is small enough you have all the precision you need.

    Issues with randomness can actually be circumvented fairly easily. Most pseudo random number generators are of a type called a linear congruential generator, which you can read about here: https://en.wikipedia.org/wiki/Linear_congruential_generator. It turns out they're actually really simple. You could easily build one in GM that produces consistent cross-platform results (as long as you stick with integers).

    Reliable UDP:

    This also isn't so bad, there are only a few components. To have reliable messaging, the receiver of the message has to respond to the sender with a confirmation that the message was received. If the roundtrip ping time elapses and the original sender hasn't received a confirmation, the sender begins reissuing the same message until that confirmation comes back. To achieve that effect, you need unique identifiers for your messages, a way to store messages that have not yet been confirmed as received, and a way to associate them (easy enough with buffer copies and a ds_map). The recipient also needs to store the id's of messages it's previously received, so that if it receives the same messages multiple times it only acts on it once.

    Hope this helps.

    Also, this other Gaffer article describes a lot of stuff related to your question. He's even gone as far as using lockstep to produce a cross-network physics simulation: https://gafferongames.com/post/deterministic_lockstep/ The entire website is a great resource on network multiplayer design.
     
    Last edited: Feb 20, 2018
    Binsk, Ampersand and kevins_office like this.
  3. flyingsaucerinvasion

    flyingsaucerinvasion Member

    Joined:
    Jun 20, 2016
    Posts:
    2,240
    Thanks for your reply.

    I was under the impression, according to things I've read posted by yoyo staff, that you can expect floating point calculations to be the same on different machines as long as the platform is the same. Are you saying this is not correct?
     
  4. PNelly

    PNelly Member

    Joined:
    Jun 20, 2016
    Posts:
    256
    No problem at all.

    From what I've read yoyo staff ought to be correct on that point. Two computers of the same architecture running the same executable should produce the same floating point results, which should apply to floating point calculations within GM along with its implementation of Box2D.

    When it comes to different platforms, it appears floating point consistency can be achieved if you're very strict about enforcing IEEE754 compliance in your builds (it is often discarded in exchange for a floating point performance boost), but we don't have that level of control using GM. Would be way cool if they decided to include such an option down the road, though I imagine it could represent an impractical amount of work. You can read more about it in the Gaffer article I linked in my first post.
     
    Last edited: Feb 19, 2018
    Ampersand likes this.
  5. Ampersand

    Ampersand Guest

    One major thing to remember regarding any type of AI (and really many aspects of your engine) is that anything regarding gameplay must be deterministic. Lockstep will not work well with anything that is using RNG. Between builds for the same target platform, you should have no problem with floating point errors. You will have a lot of issues with mechanical determinism though.
     
  6. meseta

    meseta Member

    Joined:
    Feb 26, 2018
    Posts:
    30
    I've been writing a blog series on netcode, including deterministic lockstep with input delay and rollback: https://medium.com/@meseta/netcode-concepts-part-3-lockstep-and-rollback-f70e9297271

    Lockstep is best for games where it's important for both players to see exactly the same thing, and to stay absolutely in sync: a fighting game is a good example of where this is important: you don't want to see one character lag out and be an easy target; an RTS is another good example: you don't want unit A to kill unit B on one machine, but unit B to kill unit A on the other due to some lag. However, as I mention in the blog - this advantage is also its disadvantage - the only way to make sure everything is in-sync is to lock each game client in step with each other. If one player lags, everyone lags. This becomes a problem when there are a lot of players connected to a game session. This makes it a bad choice for large-scale multiplayer games like FPS shooters or MMOs.

    The demo implementation I produced in GMS2: https://meseta.itch.io/lockstep runs the simulation at 60fps with a 15pps input/netcode rate, a 3-frame input delay, and a maximum of 5-frames prediction/rollback. This is actually quite slow, and will feel quite laggy. Exactly what kind of rates and delays you set really depends on the pacing of the game, and the geographical spread of your players.

    Network interruption or lag spikes do affect lockstep, this is where the prediction/rollback mechanism comes in. With deterministic lockstep, when network issues causes the network packets to not arrive on time, instead of just lagging out waiting for that data, you can implement a mechanism where the game saves its state, and continues to simulate forward using predictions for what the other player's inputs would be. When the data eventually arrives, the game state is "rolled back" to the earlier point, and re-simulated forward with what the actual inputs were, and then the game state updated with that new state. This whole roll-back and re-simulation ideally happens instantaneously - the player won't see the game state rolling back, they'll just see stuff on their screen snap to a new position.

    This is not an ideal solution - it results in rubber-banding or teleportation, as can be seen in some fighting games when players have high ping. But it's a slightly better experience than lags and freezes if the lag spikes don't happen too much.

    GML determinism is quite good. I can't speak for the physics engine. Do not use delta timing with lockstep.

    As for udp reliability, the demo I linked above implements a rolling window buffer for inputs. Each client periodically announces to other clients what frame they are currently on; this means each client knows where each other client is in terms of the data they have received; and so will simply continuously attempt to re-send any old frames. This is a fairly simple implementation of re-transmission, you can do more to reduce the amount of data that needs to be transmitted.

    All in all, deterministic lockstep in GM is very doable, but is somewhat fiddly. Good luck.
     
    JAG and flyingsaucerinvasion like this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice