What every programmer needs to know about game networking

Introduction

You’re a programmer. Have you ever wondered how multiplayer games work?

From the outside it seems magical: two or more players sharing a consistent experience across the network like they actually exist together in the same virtual world. But as programmers we know the truth of what is actually going on underneath is quite different from what you see. It turns out that it’s all an illusion. A massive sleight-of-hand. What you perceive as a shared reality is only an approximation unique to your own point of view and place in time.

Peer-to-Peer Lockstep

In the beginning games were networked peer-to-peer, with each each computer exchanging information with each other in a fully connected mesh topology. You can still see this model alive today in RTS games, and interestingly for some reason, perhaps because it was the first way – it’s still how most people think that game networking works.

The basic idea is to abstract the game into a series of turns and a set of command messages when processed at the beginning of each turn direct the evolution of the game state. For example: move unit, attack unit, construct building. All that is needed to network this is to run exactly the same set of commands and turns on each player’s machine starting from a common initial state.

Of course this is an overly simplistic explanation and glosses over many subtle points, but it gets across the basic idea of how networking for RTS games work. You can read more about this networking model here: 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond.

It seems so simple and elegant, but unfortunately there are several limitations.

First, it’s exceptionally difficult to ensure that a game is completely deterministic; that each turn plays out identically on each machine. For example, one unit could take slightly a different path on two machines, arriving sooner to a battle and saving the day on one machine, while arriving later on the other and erm. not saving the day. Like a butterfly flapping it’s wings and causing a hurricane on the other side of the world, one tiny difference results in complete desynchronization over time.

The next limitation is that in order to ensure that the game plays out identically on all machines it is necessary to wait until all player’s commands for that turn are received before simulating that turn. This means that each player in the game has latency equal to the most lagged player. RTS games typically hide this by providing audio feedback immediately and/or playing cosmetic animation, but ultimately any truly game affecting action may occur only after this delay has passed.

The final limitation occurs because of the way the game synchronizes by sending just the command messages which change the state. In order for this to work it is necessary for all players to start from the same initial state. Typically this means that each player must join up in a lobby before commencing play, although it is technically possible to support late join, this is not common due to the difficulty of capturing and transmitting a completely deterministic starting point in the middle of a live game.

Despite these limitations this model naturally suits RTS games and it still lives on today in games like “Command and Conquer”, “Age of Empires” and “Starcraft”. The reason being that in RTS games the game state consists of many thousands of units and is simply too large to exchange between players. These games have no choice but to exchange the commands which drive the evolution of the game state.

But for other genres, the state of the art has moved on. So that’s it for the deterministic peer-to-peer lockstep networking model. Now lets look at the evolution of action games starting with Doom, Quake and Unreal.

Client/Server

In the era of action games, the limitations of peer-to-peer lockstep became apparent in Doom, which despite playing well over the LAN played terribly over the internet for typical users:

Although it is possible to connect two DOOM machines together across the Internet using a modem link, the resulting game will be slow, ranging from the unplayable (e.g. a 14.4Kbps PPP connection) to the marginally playable (e.g. a 28.8Kbps modem running a Compressed SLIP driver). Since these sorts of connections are of only marginal utility, this document will focus only on direct net connections. (faqs.org)

The problem of course was that Doom was designed for networking over LAN only, and used the peer-to-peer lockstep model described previously for RTS games. Each turn player inputs (key presses etc.) were exchanged with other peers, and before any player could simulate a frame all other player’s key presses needed to be received.

In other words, before you could turn, move or shoot you had to wait for the inputs from the most lagged modem player. Just imagine the wailing and gnashing of teeth that this would have resulted in for the sort of folks who wrote above that “these sorts of connections are of only marginal utility”. :)

In order to move beyond the LAN and the well connected elite at university networks and large companies, it was necessary to change the model. And in 1996, that’s exactly what John Carmack did when he released Quake using client/server instead of peer-to-peer.

Now instead of each player running the same game code and communicating directly with each other, each player was now a “client” and they all communicated with just one computer called the “server”. There was no longer any need for the game to be deterministic across all machines, because the game really only existed on the server. Each client effectively acted as a dumb terminal showing an approximation of the game as it played out on the server.

In a pure client/server model you run no game code locally, instead sending your inputs such as key presses, mouse movement, clicks to the server. In response the server updates the state of your character in the world and replies with a packet containing the state of your character and other players near you. All the client has to do is interpolate between these updates to provide the illusion of smooth movement and *BAM* you have a networked client/server game.

This was a great step forward. The quality of the game experience now depended on the connection between the client and the server instead of the most lagged peer in the game. It also became possible for players to come and go in the middle of the game, and the number of players increased as client/server reduced the bandwidth required on average per-player.

But there were still problems with the pure client/server model:

While I can remember and justify all of my decisions about networking from DOOM through Quake, the bottom line is that I was working with the wrong basic assumptions for doing a good internet game. My original design was targeted at < 200ms connection latencies. People that have a digital connection to the internet through a good provider get a pretty good game experience. Unfortunately, 99% of the world gets on with a slip or ppp connection over a modem, often through a crappy overcrowded ISP. This gives 300+ ms latencies, minimum. Client. User's modem. ISP's modem. Server. ISP's modem. User's modem. Client. God, that sucks.

Ok, I made a bad call. I have a T1 to my house, so I just wasn't familliar with PPP life. I'm addressing it now.

The problem was of course latency.

What John did next when he released QuakeWorld would change the industry forever.

Client-Side Prediction

In the original Quake you felt the latency between your computer and the server. Press forward and you’d wait however long it took for packets to travel to the server and back to you before you’d actually start moving. Press fire and you wait for that same delay before shooting.

If you’ve played any modern FPS like Call of Duty: Modern Warfare, you know this is no longer what happens. So how exactly do modern FPS games seem to remove the latency on your own actions in multiplayer?

This problem was historically solved in two parts. The first part was client-side prediction of movement developed by John Carmack for QuakeWorld, and later incorporated as part of Unreal’s networking model by Tim Sweeney. The second part was latency compensation developed by Yahn Bernier at Valve for Counterstrike. In this section we’ll focus on that first part – hiding the latency on player movement.

When writing about his plans for the soon to be released QuakeWorld, John Carmack said:

I am now allowing the client to guess at the results of the users movement until the authoritative response from the server comes through. This is a biiiig architectural change. The client now needs to know about solidity of objects, friction, gravity, etc. I am sad to see the elegant client-as-terminal setup go away, but I am practical above idealistic.

So now in order to remove the latency, the client runs more code than it previously did. It is no longer a dumb terminal sending inputs to the server and interpolating between state sent back. Instead it is able to predict the movement of your character locally and immediately in response to your input, running a subset of the game code for your player character on the client machine.

Now as soon as you press forward, there is no wait for a round trip between client and server – your character start moving forward right away.

The difficulty of this approach is not in the prediction, for the prediction works just as normal game code does – evolving the state of the game character forward in time according to the player’s input. The difficulty is in applying the correction back from the server to resolve cases when the client and server disagree about where the player character should be and what it is doing.

Now at this point you might wonder. Hey, if you are running code on the client – why not just make the client authoritative over their player character? The client could run the simulation code for their own character and simply tell the server where they are each time they send a packet. The problem with this is that if each player were able to simply tell the server “here is my current position” it would be trivially easy to hack the client such that a cheater could instantly dodge the RPG about to hit them, or teleport instantly behind you to shoot you in the back.

So in FPS games it is absolutely necessary that the server is the authoritative over the state of each player character, in-spite of the fact that each player is locally predicting the motion of their own character to hide latency. As Tim Sweeney writes in The Unreal Networking Architecture: “The Server Is The Man”.

Here is where it gets interesting. If the client and the server disagree, the client must accept the update for the position from the server, but due to latency between the client and server this correction is necessarily in the past. For example, if it takes 100ms from client to server and 100ms back, then any server correction for the player character position will appear to be 200ms in the past, relative to the time up to which the client has predicted their own movement.

If the client were to simply apply this server correction update verbatim, it would yank the client back in time such that the client would completely undo any client-side prediction. How then to solve this while still allowing the client to predict ahead?

The solution is to keep a circular buffer of past character state and input for the local player on the client, then when the client receives a correction from the server, it first discards any buffered state older than the corrected state from the server, and replays the state starting from the corrected state back to the present “predicted” time on the client using player inputs stored in the circular buffer. In effect the client invisibly “rewinds and replays” the last n frames of local player character movement while holding the rest of the world fixed.

This way the player appears to control their own character without any latency, and provided that the client and server character simulation code is deterministic – giving exactly the same result for the same inputs on the client and server – it is rarely corrected. It is as Tim Sweeney describes:

… the best of both worlds: In all cases, the server remains completely authoritative. Nearly all the time, the client movement simulation exactly mirrors the client movement carried out by the server, so the client’s position is seldom corrected. Only in the rare case, such as a player getting hit by a rocket, or bumping into an enemy, will the client’s location need to be corrected.

In other words, only when the player’s character is affected by something external to the local player’s input, which cannot possibly be predicted on the client, will the player’s position need to be corrected. That and of course, if that player is attempting to cheat :)


Next: Introduction To Virtual Go




If you enjoyed this article please donate.

Donations offset hosting costs and encourage me to write more articles!

149 thoughts on “What every programmer needs to know about game networking”

  1. Great post (as always), Glenn. :) Thanks for putting this up, definitely a resource I will be referring people to. I look forward to the rest of the updates in the series.

  2. I’m sure it was Dave ‘Zoid’ Kirsch that implemented the networking advancements in QuakeWorld and not Carmack.

  3. Actually, there was a time when Carmack was working on QW, and Zoid took that over, so I can’t say for sure who did the networking overhaul.

  4. Excellent article – I truly enjoyed reading it. I’d very much appreciate any clarification on how the client and server keeps track of “game time”, e.g. how do you know the difference between server and client time in order to properly record input and replay the authority updates. You have my donation from before and I’ll be sure to make another one when I’ve implemented a successful network code in my game :)

    1. Yeah this is actually quite a complex topic. The basic idea is that the server advances time forward independently for each player as packets are received, instead of advancing all players forward together. Obviously this relies on players generally not interacting directly with each other and moving around in a mostly static world (FPS style).

      Now instead of the server having a single current time, it actually has a different current time for each client player. When a packet is received from the client the server simulates that character forward and compares it’s result with the client’s. If the results are different the server responds with a correction. This is what triggers the rewind and replay on the client as described in this article.

      For more information the best thing to do would be to read about how this is done in QuakeWorld and in Valve games:

      http://fabiensanglard.net/quakeSource/quakeSourceNetWork.php
      http://fabiensanglard.net/quakeSource/Lag_Compensation.htm#Overview

      cheers

    2. Although this is an old comment, if like to post to ensure that there is some reference to this concept if others stumble across this post and have the same question.

      Firstly, Glenn’s linked article (one link is down but the links are traversable on the website) are very useful, read them!
      Instead of maintaining individual state for each client on the server, which requires separate physics worlds for each player for some physics engines like Bullet (which doesn’t nicely resolve single objects, unless you freeze other objects in place by suspending dynamics, and that isn’t fun, and doesn’t allow player – player collisions), you can run all the updates at the same time. To do this, you maintain a buffer of commands from each client that is designed to be used with around 100ms of commands. This means when packets arrive late, they are still usable. Then for each update tick, pop the command of the buffer and use it, and ack/reject the move based upon the command ID. It introsuces some additional latency, but it is only noticeable when performing non predicted events like projectile spawning (and collisions with networked objects)

  5. Pingback: Weekly links, january 31 | Jar Of Eyeballs
  6. btw afaik StarCraft don’t use peer-to-peer it uses client-server model with lockstep (at least warcraft 3 does so). It has the advantage what theoreticaly laggers will not affect gameplay/response latency at all (but to not let them fall behind server do timeouts so the lagger can catch up, also doing temporary local game speed increasing) and imo it’s the only and true way to do sync in RTS like games. (and for some reasons this technic isn’t good covered in the web)
    most articles are about FPS or peer-to-peer syncs

    1. You are correct. Also something cool is that in a C/S RTS model the server could also theoretically arbitrate to ignore turns from lagging players, and kick them if they don’t catch up – removing various exploits where you can time-shift your packets and lag out other players.

      1. Hello! I can’t find any good documentation about lock-step with client/server. The classic lock step model would need a very long delay in responsivness until the ack for a command goes all the way back. Also, because the server must initiate all ‘locks’ the delay gets even bigger. A way to reduce this delay would be to send a full snapshot of the world for resync each time a command did not arrive in time – but a full snapshot is a lot of data.

        Toadcop mentioned something about lagger’s don’t affect gameplay and local speed increasing technic is not covered in the web. Is there a way to find out more about it? :)

        Thank’s a lot!

  7. maybe it’s bit offtopic but i have a question about networking and floats…
    so for determenistic behavior (lock step based games) they are not suitable ? =|
    or is there some compiler feature which can enforce to calculate them in same way (on different machines) ?
    any information about this is very appreciated =)

    cause it seems what physics engines (for example) are not suited for determenistic behavior.
    but maybe i am wrong enlight me please ^_^

    1. My recommendation is that with a bit of work you can get floating point ops deterministic using the same compiler and the same machine architecture. If you attempt to get deterministic results across different compilers and/or architectures you are entering a world of pain.

      The IEEE 754 standard defines the set of standard operators: +,-,*,/,sqrt to give exactly the same binary results, assuming the same rounding mode set and same precision, floating point exceptions and so on.

      In order to get the same exact result across different architectures or different compilers your need to ensure that your *compiled* code executes the same set of standard operations in exactly the same order. This is harder than it seems. You put a lot of trust in your compiler’s “strict” IEEE 754 floating point mode when you do this. You also sacrifice a good deal of performance.

      Next consider trancendentals like sin/cos/tan. IEEE 754 does not specify the exact binary output of these functions. They are implemented as approximations which differ from platform to platform. Sure you’ll find that at single precision an AMD x87 sin matches Intel x87 output, but I’ve heard reports of the output being slightly different at double precision.

      Therefore if you want to get determinism for these routines across multiple ISAs you need to write your own approximations in software using the basic floating point operations. Look up Taylor’s series, McLaurin series etc.

      Alternatively, you could always consider dropping to fixed point and/or using a software emulated floating point library :)

  8. really enjoyed this – you’ve got me trying this out at home – very slowly :)

    any suggestions on security? udp seems pretty easy to pick up on . do you create your own authentication tokens to reverify after each event?

    is connected udp an kind of solution? it seems light enough to use for a game connection and i can see who is sending what.
    – does that present any issues – do you feel you have to home roll authentication too?

    1. game consoles usually have two levels of security. the closed platform itself (cannot modify the executable) and encrypted communications over UDP to avoid sniffing packets, modifying packets or injecting fake packets.

      if you are a PC you can encrypt your communications but remember, never trust the client.

      if you are on a PS3 you can trust that client slightly more

      cheers

  9. First, great articles. They are a breath of fresh air that actually explain some of these concepts and actually how to implement them.

    Are there still plans on doing further articles? It does not seem that any of the articles like this one had theif follow up’s.

    1. Yes, I intend to finish the article series, perhaps as an eBook but it’s a long term thing. Right now I’m focusing on my day job which is unannounced. Once that game is out, I hope I’ll have time to write articles about what I’ve been doing the past 2 years. (Obviously, network related!)

      1. Also, I’m doing another talk at the GDC2011 physics tutorial, so there will be a new presentation and probably some new demo stuff coming out then. I’ll be pretty busy preparing for that, taking up all of my spare time outside of work – so no time for any extra articles. cheers

        1. Understandable, i look forward to reading the new presentation.

          After reading your articles i came to the realization for my senior project game that probably saved me weeks or months of heartache heading the wrong direction.

          It was that my Online FPS game isnt really a game as much as its a networked physics simulation with a few rules. So i am lucky you wrote those in depth articles on that subject!

  10. Great stuff! But where is part 2 as in “Please return next week for part two”. The next article shown in the list is about floating point determinism.

  11. Hi Glenn,
    Great article and I would like to add some suggestions for the lock step.

    >It seems so simple and elegant, but unfortunately there are several limitations:
    >First, it’s exceptionally difficult to ensure that a game is completely deterministic;

    Yes, this is the main problem in this model. Several solutions based on my experience:
    – Do not use a float or double. The best solution is fixed point math.
    – Or same hardware on clients – like consoles
    – Separate rendering and logic. Do not use render data in logic.
    – Ideally, the logic module must be a separate library
    – Use automatic synchronization control system. In the code includes CRC check of current variables. This code should be executed simultaneously on different clients and the CRC should be the same. In the case of non-compliance with these conditions can be locate place in code where was a desync.

    > The next limitation is that in order to ensure that the game plays out identically on all machines it is necessary to wait until all player’s commands for that turn are received before simulating that turn.

    Use client – server lockstep. All clients send commands to the server. The server does not wait for the confirmation frame from the client – sends frames with a given frequency and add commands when recive it.

    >The final limitation occurs because of the way the game synchronizes by sending just the command messages which change the state.

    2 thread server:
    – on first thread – recive commands and send frame to clients
    – on second thread – logic.
    and powerful serialization system:
    – when client try to join game, on logic thread we serialize current state of game and send to client. At the same time on the first thread does not stop sending staff to clients ( for now and new client too ) – other clients do not feel lag.
    – After send serialized data logic thread server handles all the missed frames and return to the actual state.

    1. Yes this is great advice. The only point I have to add is that with the 2 thread server is that catching up on late join frames can sometimes be expensive, so you have to make sure you are not CPU bound. You want to be able to simulate n frames in less time than it would take to render those frames, otherwise the client won’t be able to catch up to present time.

  12. Hello, you help me a lot!
    However, I have an idea on “here is my position”thing…
    Say in counterstrike, there should be at least 8 people to form a good match, say one of them is a cheat, and it uses teleportion hack, why can’t I implement a client check in all 8 client, even the cheater closes it, the other 7 players will be able to calculate the position and the previous position, if it is larger than 15 or so, it sends a violation warning to the server, when the server receives more than say like 5 violation warnings, it start a vote ban thing, and that will be a client-server cooperated cheat detection system!
    Please direct me if I am wrong, I am new to networking. Thanks.

    1. many games actually do this, but consider — what if the cheater was smart and just moved a tiny bit faster over a few seconds, or if just dodged only at the right time to avoid a bullet, but this dodge was small enough that it seemed like a bit of lag?

      the trick with the client side prediction / rewind replay is that it makes the server completely authoritative so this sort of cheat can be detected, while heuristics + voting can only detect blatant cheating and must have some amount of tolerance, since the game is not perfectly synchronized

      also, consider what happens if you have a team full of cheaters? now you have one team all with hacked clients voting that the other team are cheaters. who do you believe? :)

      1. Hi Glenn,

        Thanks for the articles so far. Looking forward to more.

        If your game is not protected by Valve Anti-Cheat or something else that digs into your computer, people can still use aimbots. So sure, all this work due to not trusting the client means people will be able to teleport and do stuff like that, but they can still use an aimbot. Cheaters that edit packets more subtly could avoid heuristics and voting, but so can people that use aimbots more discreetly. My point is, this seems like a lot of work that could eliminate half the cheating techniques out there, but doesn’t do anything to prevent the other half of cheating techniques, like aimbotting or replacing wall textures with transparent walls (I don’t know what steps modern FPS games typically use to combat that).

        It just seems like immature people who want to cheat will still do it, if they can. To them, they’ll use an aimbot just as easily as they would some teleportation hack. Whatever’s available really. And they’ll be sneaky about it too, if the goal is to appear like a skilled player (really sad people). It seems like if you don’t have VAC to back you up, you are basically plugging half the hole in your boat.

        Now, if you plan to make an FPS and the studio plans to provide dedicated servers and stuff like that, then I think you’ll really need something like VAC and use authoritative-server models.

        But if someone just wants to make an indie FPS game, I think the better solution is to save yourself a lot of headaches and motivation-killing low-level work to just have a “trust the client” solution, and hope the people that host servers for your game have decent admins.

        Now an anecdote you don’t have to read:
        I mean, I’m just thinking about the game I love, Team Fortress 2. Now that it’s free to play, persistent cheaters can just make new Steam accounts after they get banned and keep aimbotting away. Maybe it’s because Valve is doing something behind the scenes, but I don’t think so, and yet, I barely ever see aimbotters. It just seems to me that most people get bored of cheating after awhile. If they don’t, well, they get banned (people that host/rent a server generally admin the servers themselves or appoint admins). They get banned from enough servers, then they quit. Only the truly deranged still keep trying by this point. I think that preventing cheating in some vague ways, is analogous to preventing piracy: Don’t spend too much effort on it.

        Of course AAA FPS titles spend considerable effort on both. I generally believe that you should not focus too much on DRM (people will almost always crack your game), but you don’t need to be all DRM-free and just make it too temptingly easily to illegally share your game. To bring the analogy back to cheating, that’s where I would put some heuristics and encourage the banning of cheaters, but not develop these super advanced techniques to prevent cheating.

          1. Well it’s a difficult problem. Even if you run everything on the server you always have the aimbots

          2. It’s a balance – not about spending ridiculous amounts of time on solving these problems.

            Take DRM – full-blown protection isn’t necessary, but a simple prevention of installing one CD (say) on multiple machines stops ‘unintentional’ (i.e., casual) piracy of sharing the game with friends. The proper pirates will pirate even with the most elaborate protection.

            Aimbots are part of a larger problem – computers replacing part of the human part. You can’t really protect against it. But allowing the Client to just say – “I hit that person – honestly!” is something that can be protected against.

            Even smaller games (in some ways – more so) can be susceptible to packet sniffing and injection; that can easily ruin a game for legitimate players. Again – a balance; fix the obvious stuff, fundamentally prevent as much as you can, but don’t dwell if it is destroying progress on a development.

          3. Modern games do have ways to protect against these kinds of cheats, but they aren’t perfect. The best they can do is use heuristics to decide whether or not an action by the client is actually possible. For instance, if the server flags a string of actions that could potentially be malicious (the mouse moving in a perfect line 5% of the time, when the user is “aimbotting”), then the player could potentially be banned. This was implemented in the Diablo 3 Auction House almost immediately, for example.

  13. Hi I have a question i hope you would be able to answer!

    If developing a multiplayer game where the main problem is network latency, would that suit a p2p architecture over client server as you are cutting out transmission to the “middle man”?
    Thanks!

    1. It’s clearly faster to go P2P, but much more complex than client/server – also, I need to know more about the type of game you are making to advise you on whether client/server or P2P is the way to go.

      cheers

      1. There are cheating considerations, network model considerations (eg. if P2P lockstep then you don’t gain anything… async, sure), also, bandwidth! There is much more data to upload and you’ll find yourself being able to support less players with P2P than c/s. I’d recommend P2P for 4 or maybe 8 player games max. cheers

  14. Hi its a FPS iphone game over 3G. It would likely only be for 2 players because its more like a prototype with the goal of measuring how effective prediction improve playability.

    I was thinking of using async p2p, though getting round the issues described in “I Shot You First! – Gameplay Networking in Halo: Reach” would be kinda difficult. I also read that p2p connections over 3G might be impossible on iphone due to NAT punchthrough issues and 3G, though i don’t know how accurate that might be -_-.
    Thanks, really appreciate the replies of someone so knowledgeable!

    1. Just code it the simplest way possible, get it working, look for problems then fix those. Don’t try complex network models first. Do the simplest thing you can think of! cheers

  15. How does a server and client synchronize gametime with latency in mind? Is it as simple as the the server gametime + the time taken for the request to send and return / 2?

      1. If the server receives a package from the client then it needs to know at what time the command was originated on the client in order to look back in time and make decisions etc.

        And similarly when the client receives an update from the server, should it not know when that update occurred?

        If this is not how time is tracked then how is it?

        1. Why not just evaluate the command at the point of it being received on the server? Why wind back? I guess, this is not something I normally do in my network models. I guess if in some case I want to look back, then I’d prefer to look back by some server estimated RTT/2 rather than trust any concept of client time being sent to the server — cheers

          1. I’d somewhat agree with both here… but alternative methods would be interesting.

            I currently have a server-time (that is actually just the milliseconds since the server started – quantised to only hundredths) which is sent with every Ping. The Client does simply determine a round-trip to estimate the Server Time. However – as Glenn – Client->Server commands are executed on the Server without any idea of what ‘time’ they were sent from the Client. However, Server->Client commands do, indeed, use this Timestamp in order that they are executed when they are ready (usually a few ‘ticks’ ahead of the current simulation).

            Assuming that a Client sends a command to the Server – a non-deterministic amount of time later the Server returns a message to the Client – how would the Client know at what point the updates are referring to (so the Client can rewind and interpolate what it thinks are true compared to what the Server thinks are true) without some form of Timestamp? Or is it just the concept of having a Client time that is sent back that you object to? (Rightly so, as this’ll likely be inaccurate).

  16. Pingback: networked multiplayer | nestheads WordPress
  17. > First, it’s exceptionally difficult to ensure that a game is completely deterministic; that each turn plays out identically on each machine.

    I would argue that its exceptionally easy to ensure that a game is deterministic on two machines. If both machines are running the same simulation (i.e. code) then if they both have the same inputs they will behave in identical ways. Only non-determinstic events need to be synchronized between the two machines which is generally the random seed and player input.

      1. Well you make it sound like in practice such techniques don’t actually work. If you google for ‘deterministic replay’ you will find many such implementations of capturing only the non-deterministic events and replaying them.

        In my own game engine I currently use this technique to do the lock-step network model. Of course it only works on a lan with very low latency but it works fine.

        If the problem is in capturing (or even figuring out) the non-deterministic events then I guess it could complicate things but I can’t think of situations where its not completely obvious.

        1. Jon I’m well well aware of how this technique works in theory.

          I also have experience earned implementing this technique in practice. Do you?

          1. Because your knowledge here sounds awfully theoretical. Yes, if your game is deterministic it’s easy. No shit. But how do you make sure your game is deterministic? What if you have 10 programmers working on it? What if the game streams in assets? What about random numbers? What about floating point calculations? What about SSE vs. FPU calculations? What about internal 80bit floating point precision on intel chips vs. AMD? What about cross-platform play between different architectures, one of which has FMADD and the other doesn’t? What about sin(x)? What if you call c runtime functions that have slightly different values depending on compiler (eg. GCC vs. Visual Studio)? What if you have bugs with uninitialized memory that cause desync at random points? What if this random point is 30 minutes into a play session with 7 other players? How do you detect and fix these desyncs? What about 3rd party libraries you integrated into your engine, are they deterministic as well? How can you be sure? How many players can you support? What about having to wait for the most lagged player? If it’s so easy why not just deterministic lockstep your MMO? What about cheating concerns and lag switches? What about desync hacks? How do you solve all this? What if one player cannot simulate fast enough to keep up? What about delta time? Do you need the same delta time on each machine or not? OK you do so how do you ensure that all players simulate at the same delta time rate, if one computer can render faster than the others? What about late joins? What if you want to hide latency (eg. GGPO)? And so on… and on… and on…

  18. “The Unreal Networking Architecture” link is down. I’ve had a look around unreal’s new site but I can’t find the article.

    If you can find it could you please let me know.

  19. I had a question, and this was the best place I could think to put it.

    I’m currently attempting to write a basic server for a small multiplayer game, with very few intended users. Despite having trouble understanding some of your articles ( I finally managed to understand your Flow and Reliability article after reading through it with a friend for two hours yesterday ), I finally got a sense of it, and started thinking about how I’d want to organize the structure around those concepts. I was talking about it with a friend, and we had an argument over clients and sockets. Primarily, how to farm out clients to sockets. My original interpretation was that all traffic was handled via one socket on the server side. He argued that the port could get overloaded with the packets received. Basically, what I’m looking for advice on is how to mete out clients to sockets. Should they all send packets to one socket on the server? Should the server have a socket that receives connections, and replies with information regarding which of a group of sockets to connect to, these other sockets serving up to N clients, or perhaps it should be done on a 1 socket per 1 client basis.

    Since neither of us actually have any real experience using this kind of a system, what is your advice on the matter?

    Additionally, thank you for these wonderful articles.

    1. with very few intended users there is no way a single socket will get overloaded. assuming that you are using UDP, you do indeed want to have only one socket. cheers

      1. Thanks for your reply! How does this change at larger user loads? At what number of users/amount of packets/etc. might I want to use multiple sockets? What can a single socket reasonably handle?

  20. Firstly great article…only understood it at a basic level.

    I hope you’ll forgive me ..But from a players POV (uninformed) and based only on playing experience,Quakes Cl/Serv setup has given the most desirable results..at least the perception .

    The move amongst AAA title industry to offer solely client-side prediction for FPS genre..has to the majority resulted in a less desirable game experience than a decade ago.Which, as we players are not informed on netcode, results in us thinking it’s crap because our experience is ‘poor hitreg’.

    COD and BF franchise have moved in recent times to p2p and client side prediction..away from Quakes server side prediction and our gaming has suffered.

    A recent example of such is Battlefield 3…the beta experience across the board was fantastic,many commenting on how great the netcode appeared.Even experiencing 128 player server hacks everyone was pleased with the performance.
    Unfortunately upon release it was rumoured that DICE had changed to client-side prediction and the subsequent experience was as bad as BFBC2 poor hitreg and rubber banding again.A move they didn’t deny or rather couldn’t as it was obvious and resulted in the introduction of a rather pathetic and stupid ‘interpolation slider’ (so that the user could randomly adjust).
    I say stupid because it was impossible to know what settings you were adjusting.Not only that but the reason given for not revealing information in the form of a user config -that would allow the player to optimize their net settings manually.Was so that the player couldn’t seek an advantage…ironic in that they provide the tool to do so .
    “here’s the tool to optimize your connection,but just to be fair we’ll allow you a 1 in 26 million chance of randomly finding it”.
    It used to be the way that the user config with universal settings was available to optimize and the community would share knowledge and optimisation was individual.

    My question to you is this…which model is theoretically superior ?

    PC players collective experience is that quakes client/server model was better…clientside prediction and p2p gaming experience has been poor.

  21. In addition …as my post isn’t relevant to what you all are discussing feel free to omit it.

    I would appreciate a reply though.

    There is a growing consensus of opinion amongst gamers that developers are taking a liberty.Loads of eye candy and profit..but poor netcode.

    A perfect example would be Infinity Wards MW2.The game used P2P and net settings were 30max pkts, 60fps, rate 5000..with a 60 horizontal FOV.
    Horrible experience for most players accept the host and totally at a loss to demonstrate in the world of fibre optics why a AAA title would think anything other than 56k dial up settings would break the game.

    To the other extreme 100max pkts..is also not desirable for a lot of systems because whilst my system can handle 76fps and a 2mbps BB connection…100max pkts quickly bottlenecks my system as my upload in UK is capped.

    So my preference and what works most games is 63max pkts…76fps…rate 25000.

    I realise I’m limited to what I’m trying to convey…some/all/none of my settings may be applicable depending on the netcode used.I can state IME..limiting my update packets to below 25kb works great.
    With user defined tweaking I can pretty much achieve a very good connection to a game server.Any inbuilt lagometer/latency graph demonstrates I’ve got it fine tuned…perhaps without understanding the technical details of what I am doing.
    But as you know all about netcode your thoughts would be most welcome.

  22. Pingback: Multiplayer JavaScript game built with Node.JS – Separating players | PHP Developer Resource
  23. Pingback: MMO的网络延迟处理相关参考资料
  24. Pingback: What every programmer needs to know about game networking « async I/O News
  25. Does anyone know of any good links that describe how, in a p2p gaming scenario, two computers are able to talk to each other through firewalls, home routers, etc? I’d also like to understand how things like port forwarding are done automatically without the players having to configure their home networks.

  26. Hey!
    I have a question related to general client-server online programming. Do server run at while(true) loop or for online games servers use some kind of fixed step loop? For example the server runs simulation and updating clients at 20 ticks per second? Could you explain it a bit or name some texts that explain it (I couldn’t find anything reliable about it). Thanks!

  27. Pingback: 【译】HTML5实现多人实时3D游戏 | Tencent AlloyTeam
  28. Pingback: List Processing in CoffeeScript
  29. So, who have the best connection with the server, will be the best in all FPS? Because server is authoritative over all clients…

  30. Thanks for the articles Glenn, they’ve been extremely enlightening. There are a couple of basic points that I’m still missing, hopefully you can help. Is recvfrom a blocking call (I assume it is). How can i keep my game responsive while I’m waiting for an update from the server? Do I run a background thread on the client? How do I notify the main thread? Do I simply trust that the server will respond quickly?

      1. Thanks that’s exactly what I was looking for! I somehow managed to skip right over that when I read that section :O

  31. Hi Man
    I Wonder that how to imitate the physic world in server? In my point ,we will create a physic world use a thirdparty tools like Havok physics, We may not create a physic world in the server ,When a player press W to move forward the client send a commod to server But right now in the client physic world there is a stone in front of player ,the server already recive the commond to move forward ,but in the client ,the player cann’t move because of the stone ,
    I wonder how to solve this comflict???? thanks a lot!

    1. In most games (HL2 engine for example) there exists both, clientside and serverside prediction. Whereby serverside prediction is always authoritative. In your rock scenario, the client would predict the collision with the rock and already stop before it receives the confirmation from the server. The server then corrects the client (if neccessary). Not simulating clientside prediction results in pretty unpleasant movement

  32. Awesome article! I have a question, though. In modern games, if everyone connects to a game server, what is the role of the “host” in games like call of duty?

    1. Many console games don’t use dedicated game servers. I this case the host is the player machine that is acting as the game server.

  33. Pingback: How to Create Realtime Multi-player Games in HTML5 | OSOS
  34. What do you suggest for a chess game at a server with a traffic of 700 to 900 users.
    Please leave me some reasons as well why I should choose that socket connection.
    Thanks for all your help :)

      1. Hi Glenn
        Would you please give a tutorial of TCP?
        I am also working on chess game project like Umair.
        Thanks
        BTW nice article

  35. I am a young programmer, and I’m curious, if client-side prediction only fixes the lag for the user’s character, how can you fix the a significant lag that occurs when the program reads the data for the other characters’ movements from the server?

    1. That’s a very good question.

      Firstly the remote players are different to the local player, so you cannot do the same technique as the local player — you don’t know their inputs ahead of time.

      The standard options is just to do nothing. The remote players will be slightly in to past due to lag. This is often acceptable. If fact, depending on how your game handles interactions between players, like shooting, you can often compensate for this effect giving the benefit to the shooter, so the shooter doesn’t need to “lead” by the amount of lag. Google for “latency compensation yahn bernier”

      Another option is to try to guess ahead where the remote player controlled objects are, to hide the lag. If you have a game like high speed cars which have very linear motion eg. F-zero, this may be a good option. But if you have buggy with physics based unpredictable motion, then the extrapolation will be inaccurate. Note that the error in position due to lag is proportional to speed. This is why buggy like physics objects have low speeds, while fast moving vehicles tend to have hover and more linear, hard to change direction type motion.

      Cheers

  36. I’d like to suggest one thing (note it would also help me better understand the concept): put a simple diagram showing how circular buffer would work between client and server, I’m getting the picture but failing to finish it and a cool image would help a lot!

    Thanks for this excellent article.

  37. First: Great article! I’m not a game programmer but got interested and found this through a StackOverflow-question.

    Now, I have one question regarding this bit:

    “[...] then when the client receives a correction from the server, it first discards any buffered state older than the corrected state from the server, and replays the state starting from the corrected state back to the present “predicted” time on the client using player inputs stored in the circular buffer. [...]”

    Would it not discard any buffered state _newer_ than the corrected state from the server, not older? Since those would be the “wrongly predicted” states that now needs to be “re-predicted” on the client, starting from the corrected state? Or am I misunderstanding?

    Thanks a lot for sharing your knowledge.

      1. Either I’m bad at understanding, or I’m bad at explaining what I mean. Either way, I suck :)

        But what I mean is: Say the client has buffered the following predicted states (s1 being the oldest and s4 the newest):

        s1 -> s2 -> s3 -> s4

        But then in comes a correction from the server saying: “beep! s3 is wrong, here, use this correct s5 instead”. Then, shouldn’t the client discard s3 and s4 (the newer ones) and re-play/predict from the corrected state (s5) into a new state s6? E.g:

        s1 -> s2 -> s5 -> s6

        I think I understand the sentence I quoted from above, I just find the “[...] it first discards any buffered state older than the corrected state from the server [...]” weird. Why should the states that are older be discarded? Isn’t it the newer ones, the ones that are based on the wrong prediction, that should be discarded?

        1. Once you have received corrected state for s3, this is the official state including everything from before (it supersedes s1 and s2).

          So if you have applied correction s3 and s2 or s1 (or a duplicate s3) arrive after this, they can be ignored.

          If you receive server correction s4 or greater, then you apply it because it has new information.

          Once you have applied s4 you ignore s1,s2,s3,s4 and only apply s5 or greater.

          And so on…

          1. Hi Glenn,
            the world is always on… new and new technologies and more powerful devices, servers, routers etc…
            How do you see the potential change in technologies used in FPS and other type of action games in the network and on mobile devices… Are we going into java or we still need to stick with C/C++? I see all the engines are still stick to C/C++. On the other hande Java is going more and more better in performance. Some devs just forgot about optimalization of code etc, and they stick to C/C++ just because the native character of the language…

          2. (And in triple A we embed scripting languages all the time already, eg: LUA, squirrel… It’s not all C++)

  38. Hi
    I am writing a 3rd person tank shooter game and ask this about networking:

    1/ I think P2P is fairer for player because the ping is about similar in each pair of players (the same distance) while client/ server will has lower ping for nearby player and higher ping for another, is it true?

    2/ The game is for fun, so I can trust clients, and if I can trust client, is there any technique for better lag compensation than traditional model where you can not trust clients?

  39. If I want to use the rewind and replay approach, then I must support state saving/restoring and input history, right?
    So if my game is a moddable one, unit has abilities provided by script/bytecode, how do I know what state to store for those script to rewind and replay correctly?

  40. Great article, I’ve enjoyed it.

    I’ve got one question, for when you can/want to answer it:

    I have in mind to make a multiplayer 1 vs 1 game, it is a shoot em up vertical scrolling game, you know, like the good old classic 1942, but with another player playing against.

    What networking model would you use?, a simple P2P would do?, if so, how are things going to keep in sync?.

    I’ve read an article explaining how networking works in fighting games but TBH I didn’t understand very well.

    (If you have a getting started link/tutorial/explanation much appreciated!).

    1. There are two major ways to go about doing this. Do you care about cheating? Then you should do client/server, otherwise you can do a distributed model where each player is authoritative over their position, and authoritative over whether they get hit by the other player.

      cheers

      1. No, I don’t really care about cheating. Anyway, I don’t know how things stay in sync.. I mean, I send a message, let say, I shoot a bullet, in my screen I see that the bullet is being shot instantly, the other player receives the message X time later and that produces a desync. Maybe I’m asking something extremely obvious here but.. I have no idea how it’s done.

        1. Things stay in sync because you are continually sending the state of your objects from one machine to another. State would include for example, the position of the ships and enemies in the level. You could send an event for bullet fire and simulate that bullet fire as a result of that event on both machines. You then need to decide which machine in the game decides whether or not the bullet hits. If you don’t care about cheating, do it peer-to-peer and evaluate bullet damage on a players ship on that players machine (peer).

          cheers

          1. Also a delayed shoot of a bullet on another machine due to lag doesn’t create a desync — because that machines view of that player is *also* delayed by lag. It will actually look fine. Pro-tip: You don’t want to do a deterministic lockstep model. Don’t think “if i do everything right it will be in sync”. No. Don’t do that, instead send everything across that needs to stay in sync, every damn frame. Then eventually, drop down to 10 or 20 times a second and interpolate between in the remote view, or snap the object in the remote view immediately and have a visual smoothing that eases towards the snapped object over time. Take a look at my Fiedler’s cubes demo for an example of this (it’s on google codes somewhere).

            cheers

          2. So, let me get this right, player A is the one who is authoritative/controlling everything, so player B is constantly playing a “delayed” version of what happens in play A screen, but, what happens when player B do something?, doesn’t that lag creates a problem?.

  41. Player A’s machine could be authoritative over player A’s ship, while player B’s machine is authoritative over player B’s ship. This is a distributed authority approach. Or, you could do client server, and have the server be authoritative over both A and B ships, treating A and B as separate clients connected to that server, but yes in this case you would have to implement latency compensation and client side prediction to handle delays. I do not recommend going down the path where one players machine is the server, but if you do keep the server logically separate (listen server) and make sure that player is a client of that server and goes through the same communication protocol as a remote client (and ideally, you’d add some fake lag here to make it fair).

  42. I see, do you know of any library/framework for C++ that takes care of P2P connectivity between 2 players (a strictly 1v1 game), the game cannot have any lag, I mean, it should act as a fighting game, where lag is out of the question.

      1. If the game cannot have any lag, you’re going to have to come up with some tricks to hide that lag, because that lag… exists.

  43. You have no idea how useful this article was – I searched far and wide for exactly this information and could find it no where… thank you!!!

Leave a Reply

Glenn Fiedler's Game Development Articles and Tutorials