Networked Physics

Introduction

Hi, I’m Glenn Fiedler and welcome to the final article in my series on Game Physics.

In the previous article we discussed how to use spring-like forces to model basic collision response, joints and motors.

Now we’re going to discuss how to network a physics simulation.

Networking a physics simulation is the holy grail of multiplayer gaming and the massive popularity of first person shooters on the PC is a testament to the just how immersive a networked physics simulation can be.

In this article I will show you how apply the key networking techniques from first person shooters to network your own physics simulation.

First person shooters

First person shooter physics are usually very simple. The world is static and players are limited to running around and jumping and shooting. Because of cheating, first person shooters typically operate on a client-server model where the server is authoritative over physics. This means that the true physics simulation runs on the server and the clients display an approximation of the server physics to the player.

The problem then is how to allow each client to control his own character while displaying a reasonable approximation of the motion of the other players.

In order to do this elegantly and simply, we structure the physics simulation as follows:

  1. Character physics are completely driven from input data
  2. Physics state is known and can be fully encapsulated in a state structure
  3. The physics simulation is reasonably deterministic given the same initial state and inputs

To do this we need to gather all the user input that drives the physics simulation into a single structure and the state representing each player character into another. Here is an example from a simple run and jump shooter:

    struct Input
    {
         bool left;
         bool right;
         bool forward;
         bool back;
         bool jump;
    };

    struct State
    {
         Vector position;
         Vector velocity;
    };

Next we need to make sure that the simulation gives the same result given the same initial state and inputs over time. Or at least, that the results are as close as possible. I’m not talking about determinism to the level of floating point accuracy and rounding modes, just a reasonable, 1-2 second prediction giving basically the same result.

Network fundamentals

I will briefly discuss actually networking issues in this section before moving on to the important information of what to send over the pipe. It is after all just a pipe after all, networking is nothing special right? Beware! Ignorance of how the pipe works will really bite you. Here are the two networking fundamentals that you absolutely need to know:

Number one. If your network programmer is any good at all he will use UDP, which is an unreliable data protocol, and build some sort of application specific networking layer on top of this. The important thing that you as the physics programmer need to know is that you absolutely must design your physics communication over the network so that you can receive the most recent input and state without waiting for lost packets to be resent. This is important because otherwise your physics simulation will stall out under bad networking conditions.

Two. You will be very limited in what can be sent across the network due to bandwidth limitations. Compression is a fact of life when sending data across the network. As physics programmer you need to be very careful what data is compressed and how it is done. For the sake of determinism, some data must not be compressed, while other data is safe. Any data that is compressed in a lossy fashion should have the same quantization applied locally where possible, so that the result is the same on both machines. Bottom line you’ll need to be involved in this compression in order to make it as efficient as possible without breaking your simulation.

For more details, see my new article series called Networking for Game Programmers.

Physics is run on the server according to a stream of input from clients

The fundamental primitive we will use when sending data between the client and the server is an unreliable data block, or if you prefer, an unreliable non-blocking remote procedure call (rpc). Non-blocking means that the client sends the rpc to the server then continues immediately executing other code, it does not wait for the rpc to execute on the server! Unreliable means that if you call the rpc is continuously on the the server from a client, some of these calls will not reach the server, and others will arrive in a different order than they were called. We design our communications around this primitive because it suits the transport layer (UDP).

The communication between the client and the server is then structured as what I call a “stream of input” sent via repeated rpc calls. The key to making this input stream tolerant of packet loss and out of order delivery is the inclusion of a floating point time in seconds value with every input rpc sent. The server keeps track of the current time on the server and ignores any input received with a time value less than the current time. This effectively drops any input that is received out of order. Lost packets are ignored.

Thinking in terms of our standard first person shooter, the input we send from client to server is the input structure that we defined earlier:

    struct Input
    {
         bool left;
         bool right;
         bool forward;
         bool back;
         bool jump;
    };

    class Character
    {
    public:

         void processInput( double time,
                            Input input );
    };

Thats the bare minimum data required for sending a simple ground based movement plus jumping across the network. If you are going to allow your clients to shoot you’ll need to add mouse input as part of the input structure as well because weapon firing needs to be done server side.

Notice how I define the rpc as a method inside an object? I assume your network programmer has a channel structure built on top of UDP, eg. some way to indicate that a certain rpc call is directed as a specific object instance on the remote machine.

So how does the server process these rpc calls? It basically sits in a loop waiting for input from each of the clients. Each character object has its physics advanced ahead in time individually as input rpcs are received from the client that owns it. This means that the physics state of different client characters are slightly out of phase on the server, some clients being a little bit ahead and others a little bit behind in time. Overall however, the different client characters advance ahead roughly in sync with each other.

Lets see how this rpc call is implemented in code on the server:

void processInput( double time, 
                   Input input )
{
    if ( time < currentTime )
        return;

    float deltaTime = currentTime - time;

    updatePhysics( currentTime, 
                   deltaTime, 
                   input );
}

The key to the code above is that by advancing the server physics simulation for the client character is performed only as we receive input from that client. This makes sure that the simulation is tolerant of random delays and jitter when sending the input rpc across the network.

Clients approximate server physics locally

Now for the communication from the server back to the clients. This is where the bulk of the server bandwidth kicks in because the information needs to be broadcast to all the clients.

What happens now is that after every physics update on the server that occurs in response to an input rpc from a client, the server broadcasts out the physics state at the end of that physics update and the current input just received from the rpc.

This is sent to all clients in the form of an unreliable rpc:

void clientUpdate( float time, 
                   Input input, 
                   State state )
{
    Vector difference = state.position - 
                        current.position;

    float distance = difference.length();

    if ( distance > 2.0f )
        current.position = state.position;
    else if ( distance > 0.1 )
        current.position += difference * 0.1f;

    current.velocity = velocity;

    current.input = input;
}

What is being done here is this: if the two positions are significantly different (>2m apart) just snap to the corrected position, otherwise if the distance between the server position and the current position on the client is more than 10cms, move 10% of the distance between the current position and the correct position. Otherwise do nothing.

Since server update rpcs are being broadcast continually from the server to the the clients, moving only a fraction towards the snap position has the effect of smoothing the correction out with what is called an exponentially smoothed moving average.

This trades a bit of extra latency for smoothness because only moving some percent towards the snapped position means that the position will be a bit behind where it should really be. You don’t get anything for free. I recommend that you perform this smoothing for immediate quantities such as position and orientation, while directly snapping derivative quantities such as velocity, angular velocity because the effect of abruptly changing derivative quantities is not as noticeable.

Of course, these are just rules of thumb. Make sure you experiment to find out what works best for your simulation.

Client side prediction

So far we have a developed a solution for driving the physics on the server from client input, then broadcasting the physics to each of the clients so they can maintain a local approximation of the physics on the server. This works perfectly however it has one major disadvantage. Latency!

When the user holds down the forward input it is only when that input makes a round trip to the server and back to the client that the client’s character starts moving forward locally. Those who remember the original Quake netcode would be familiar with this effect. The solution to this problem was discovered and first applied in the followup QuakeWorld and is called client side prediction. This technique completely eliminates movement lag for the client and has since become a standard technique used in first person shooter netcode.

Client side prediction works by predicting physics ahead locally using the player’s input, simulating ahead without waiting for the server round trip. The server periodically sends corrections to the client which are required to ensure that the client stays in sync with the server physics. At all times the server is authoritative over the physics of the character so even if the client attempts to cheat all they are doing is fooling themselves locally while the server physics remains unaffected. Seeing as all game logic runs on the server according to server physics state, client side movement cheating is basically eliminated.

The most complicated part of client side prediction is handling the correction from the server. This is difficult, because the corrections from the server arrive in the past due to client/server communication latency. We need to apply this correction in the past, then calculate the resulting corrected position at present time on the client.

The standard technique to do this is to store a circular buffer of saved moves on the client where each move in the buffer corresponds to an input rpc call sent from the client to the server:

struct Move
{
    double time;
    Input input;
    State state;
};

When the client receives a correction it looks through the saved move buffer to compare its physics state at that time with the corrected physics state sent from the server. If the two physics states differ above some threshold then the client rewinds to the corrected physics state and time and replays the stored moves starting from the corrected state in the past, the result of this re-simulation being the corrected physics state at the current time on the client.

Sometimes packet loss or out of order delivery occurs and the server input differs from that stored on the client. In this case the server snaps the client to the correct position automatically via rewind and replay. This snapping is quite noticeable to the player, so we reduce it with the same smoothing technique we used above for the other player characters. This smoothing is done after we recalculate the corrected position via rewind and replay.

Further Study

To accompany this article I have created a networked physics simulation where the FPS character is replaced by a cube. You can run and jump with the cube, and the cube will roll and tumble amount in response to your input. No shooting I’m afraid, sorry!

There are many visualizations included in the example program to help you understand the concepts of rewind and replay and smoothing, so download the example today and play around with it!

Conclusion

We can easily apply the client side prediction techniques used in first person shooters, but only if there is a clear ownership of objects by clients (eg. one player controlled object) and this object interacts mostly with a static world.

Once you have large stacks of objects, and players can interact with these stacks, or players can interact with objects controlled by each other it becomes much more complicated if you want such interactions to be latency free. Please refer to my GDC talks on networked physics describing alternative techniques to use in these situations.


Next: UDP vs. TCP




If you enjoyed this article please donate.

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

189 thoughts on “Networked Physics”

  1. There is another problem that you didn’t mention, that makes the simple “state-diff” method not work. Different numerical coprocessors generate slightly different values given identical inputs. I have confirmed this by adding a replay system to my game. When I run a replay file on another computer, errors start building up. You can read about this problem on Gamasutra.

    1. character physics are completely driven from input data
    2. physics state is known and can be fully encapsulated in a state structure
    3. the physics simulation is deterministic given the same initial state and input

    Therefore, #3 is not completely true. It is deterministic on any one machine, but not across machines. A partial stepped state update or full state update is required in order to overcome this problem.

  2. P.S. You are correct about client side prediction becoming useless in the future. I performed some tests to confirm what I’ve heard about human reaction time. You can safely add a local latency of 70ms to user input without the user even noticing. That 70ms is enough time to immediately send out the input over the wire to another client to be used at during the frame with the same timestamp on both machines. As broadband continues to get better, we may find that we get to remove a whole slew of dead reckoning tricks, and focus more on utilizing bandwidth.

  3. Actually, that’s not quite true. There are many floating point math functions that act deterministically across machines. Ones that generally don’t act deterministically include the transcendental functions. Use doubles but not sin, cos, sqrt, etc. and you should be fine in most cases.

  4. comment #1, i should clarify that for the techniques in this article, you dont require exact determinism, just that you need to get it as deterministic as possible. i should clarify this in the article — its confusing!

  5. Hey Glenn,

    As a hobbyist games programmer, I have really learnt a lot from your articles. I am interested in the actual structure you send across the network in your UDP packets. I had proper Structures, then a StructToByte() function that used the .NET serialization – but found there was far to much overhead in the resulting Byte array because it keeps information about the Packet Type, etc. It would make an interesting topic for an article, if you are keen! Keep up the great work, love your writing style.

    Cheers, Pinky.

  6. Ok, thanks for the info. I guess the answer I needed was that I should write my own (de)serialize methods which accepts PacketType as a parameter, and creates a Byte[] as appropriate. The first data in the packet could be an Enum for PacketType, or something like that. I will give it a shot. Cheers. – Pinky

  7. i dont limit my systems to structures, instead i provide a bitstream class and a serialize method, which both reads and writes the data — bit packing reduces bools to 1 bit, and integers can be written with n bits only

    once you have this bit packer to get your aggregate string of bytes, send that as your packet

  8. your use of un-escaped less than and greater than signs [in psuedocode] messes up this page badly in opera 9

    [came here from a link on a mailing list, that’s why I’m so late]

  9. Hi, you have a syntax error in your structure definition for struct Input. (If it was meant to be pseudo-code, then ignore this.)

    Since you are separating variables with a comma delimited list, you do not specify ‘bool’ each time. Else if you want to, substitute the commas (,) for semicolons (;).

  10. Hi,
    This seems like a very simple answer to the networking issue, however how does it stack up with larger simulation.
    The problem then is the need to keep a historic list for ALL objects in the simulation! With the kind of latency that can often be found, 1 second is a minumum. with each record taking just a few bytes, and a few hundred objects in the simulation, the memory requirements grow quickly!
    Are there any tricks you’ve found to reduce this limitation?

  11. stacks up just fine, the more interesting issue is how to handle time synchronization between server and multiple clients in order for this technique to work, taking into account latency and jitter in packet delivery, because larger simulations need to step the whole world at once, and cannot update each client independently

    and its not really the memory cost, its the simulation cost. rewinding and replaying a complex simulation (eg. havok) is expensive – and thats the main thing to overcome with this technique

  12. i would guess a good method to handle this would be to run two thread, one for the physics simulator, and one for the network listener.

    If a packet is recieved and requires a rewind to be performed, start the physics thread, rewound.

    If another packet is recieved with a timestamp previous to the current simulation time (possibly rewound) then kill the current simulation, rewind again and continue.

    If this new packet is timestamped later than the current sim time, just sort it into the input que at the end of the current step, and continue as normal.

    clients only need to be updated upon collision events. this is the only time the simulation becomes seriously discontiuous. client prediction should then keep us back in (roughly) the right place with the system already implemented handling any irregularities.

  13. I see your point on memory requirements, memory is cheap these days!

    although rewinding may be a costly exercise, rewinding could be sped up by also storing state information in the history que. the only time this state information would become invalid is after a collision event. once this is flagged for the object we can recalculate the new states for each frame, othewise it can be ignored.

    Collision detection would be the major bottleneck. In this case i would imagine using lower detail models for the physics, and a higher detail model for the renderer would be the simplest system (along with the usual hierarchal bounding volumes)

  14. Now i’m follow this article in my game that it is a racing game and now i try to use the technic that call ‘an exponentially smoothed moving average’ but in my game it is a 3d games that have not only position velocity but also rotation matrix I really want to know how to apply this technic with rotation matrix?? anybody can help ??

  15. In my game I use ODE as a physic engine and it use a rotation matrix, so by your suggestion I have to convert my rotation matrix to quatemions right? I already try to look in your code that load from zen of network,the box code with presentation, But I don’t know where to look .If you can point me to where to look, it would be a lot easier for me. Thank you.

  16. use quaternions, not matrices to represent your rotation – then its easy to implement exponentially smoothed moving average for orientation

    take a look at the zen of networked physics source code, there is in example in there of smoothing position and orientation of a cube

    cheers

  17. See Matrix.h and Quaternion.h for conversion routines, and Cube.h for the exponentially smoothed average.

    Its not hard at all, look!

            current.position = previous.position + (target.position-previous.position) * tightness;
            current.orientation = slerp(previous.orientation, target.orientation, tightness);
    

    Tightness is in the range [0,1]. If you set tightness to 1.0, then there is no smoothing, reducing tightness makes it follow more sloppy. Try values like 0.5, 0.25 and adjust to get the amount of smoothing you want — this technique for smoothing is framerate dependent, so you’ll want to have a fixed delta time

    cheers

  18. First of all thank you for your suggestion it’s help me a lot but I try to adapt it, and now I can work with smooth method but another problem for me is that I’m confuse with the time that we need to update, first I run physic on each client and server send position to update frequntly. when I receive the position from server I try to update it by use smooth method try to move car to its new position that come from server by call smooth method in the updatemethod that run by game loop, so if i’m right it should smooth it 1 time in 1 frame. And in that loop client also simulate physic so it’s position should be change. What if message come from server comes late or position is alreay absolete or client already pass that point. ???
    Oh and one more problem is that if 2 computer has different performance one can run at 60 frames per second and another can run at 30 frames per sec, so in my simulation(racing game) it’s performance of car doesn’t the same. So can this tricks work for this problem? or i have to implement anything else?

    Thank you…

  19. ok you are right – the article doesnt cover this problem

    in the networking biz we solve this with “input and state buffering” and “time synchronization”

    input and state buffering means that when a packet arrives early or is jittered a bit, we store it in a buffer. this makes sure that we get a reliable stream of input and state from the remote computer, even in real world conditions, where packets sent at 30fps clearly dont arrive at nice regular 30th of a second intervals (they are jittered, clumped together, out of order, duplicated etc. – welcome to the internets!)

    time synchronization is the way that we make sure that the client and server advance their concept of time together. in a nutshell, you send the current server time back to the client, and the client adjusts his own time to match the server’s time. if the client time is close to the server, it’ll smooth towards it (using you guessed it, an exponentially smoothed average), if its outside some threshold (say > 1second out), it’ll just snap.

    the client does this adjustment by speeding up and slowing down its concept of time progression. eg. you scale deltaTime on the client so it simulates a little bit faster, or a little bit slower, so it approaches server time and holds.

    bonus points if you realize that the client can speed up its local time ahead of the server by latency seconds, so that it delivers input packets ahead of the time they are required on the server.

    super secret bonus points if you measure the amount of jitter (uncertainty in packet delivery), and further make the client speed up such that it delivers packets so they arrive in time given the latency and jitter conditions.

    RADICAL bonus points if you realize that you can do fixed timestep updating on the client and server, but the client can adjust by subtly adjusting its concept of local time in a bresenham line drawing type concept – eg. to speed up it simulations 1,1,1,1,1,2,1,1,1,1,1,2 frames etc, to slow down it goes 1,1,1,1,1,0,1,1,1,1,1,0 etc.

    combine this with the “fix your timestep technique” and you can have both fixed timestep and perfectly smooth motion on the client, as well as a network time synchronization that delivers input packets on time to the server, even under latency and jittery packet delivery.

    cheers

  20. Hi

    I read your article several times but there is one thing I’m not sure to understand.

    Each client has its own physics simulation on the server. When the server receives an input packet (p1) from a client, its simulation steps.
    What happened when the server receive an other input packet (p2) from an other client, knowing that the date of p2 is earlier than p1 ? Does the server perform a rollback in the first client simulation to take into account p2 ?

    Thanks

  21. no, generally the server has one simulation, and the client has one simulation – we’re just relying on the fact that in typical FPS style physics, the player character is mostly moving around in a static world, so you can effectively rewind/replay the character physics in the simulation as input arrives, while leaving the rest alone — furthermore, you can keep different “time streams” for each client, so that they advance forward as input arrives for them, instead of necessarily together (because they dont interact)

    however, this breaks down when you have a modern physics simulation like havok, where the whole world needs to advance together, you cant just update object A independently of object B.

    my solution in this case is to adjust client time (by speeding them up), such that each client is ahead of server time exactly by the amount of latency and uncertainty (jitter), such that for any given frame n, the input for each client has arrived at the server.

    this is tricky, but possible, i have it working – its my fulltime job to work on this stuff!

    sure, if input arrives late you could consider replaying it, but in general this new technique works better with havok type simulations, — the cost of replaying a whole havok simulation even a few frames is prohibitive (as most games will have already maxxed out the CPU cost of havok to do just a single frame… how can you then go and replay 10-20 frames in one frame?)

    so. the new technique is this – speed up the clients so they deliver input and state to the server just before its needed, step the whole simulation forward on the server as normal. no special rewinding.

    on the client, give limited authority to the objects that the client controls, eg. his player, objects the player pushes, the vehicle the player drives. send updates for these to the server. the server accepts these positions and trusts the client. yes, this makes cheating possible, but frankly, we have no choice – we simply cannot afford the cost of rewinding on the client and replaying the whole havok simulation.

    cheers

  22. Thanks for your answer. It makes sense now.

    Indeed I am using a modern physics simulation (for a racing game), and I was wondering how you could afford the cost of rewinding. I have my answer for that question too.

    I think that I’ll have to choose between two solutions (considering using an havok type physics engine) :
    – Simulation by each client. Everybody trust everybody. The server just broadcast the state of the clients. Clients interpolate the other client’s states.
    – Simulation on the server. Prediction on the client. Speed up clients so that they deliver input in time to the server. Interpolate between prediction state and server state.

    Any advise? :)

  23. Hello Again, And long time no see.

    Glenn, Thank you for all advise you gave me. And now My Game network is a lot better and be able to sync. And for Nicolas I use the method that the same as your first method that is
    “- Simulation by each client. Everybody trust everybody. The server just broadcast the state of the clients. Clients interpolate the other client’s states.” and this was work well.

    Thank you. Glenn for this valuable article and your advice.

  24. First, thanks for such great information, your advice has helped me tremendously. I do have one question however, I’m curious about how the bresenham line drawing concept relates to speeding up time or slowing it down. I know it’s a line rasterization algorithm but how exactly does it help with time? Also, you mention “frames” in regard to that. Is this rendered frames or game “ticks”? Thanks!

  25. what i mean by bresenham line is that time is discrete (fixed dt) so its measured in simulation frames, n, n+1, n+2 etc.

    so how do you speed up and slow down time when its fixed rate time?

    i keep a floating point time values on the client and i increase it by the delta i calculate (somewhere between 0.75 and 1.25, depending on whether the client wants to speed up or slow down)

    then i look at the current and previous floating point time, and see how many integer frames it spans

    you can see with delta being in [0.75,1.0] that it must span either 0, 1 or 2 frames.

    so while running without any time adjustment looks like this (simulated frames per fixed real dt, eg: 30fps)

    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

    slowing down looks like this:

    1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0 …

    and speeding up looks like:

    1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,1,2 …

    (not that i dont actually simulate 2 frames, i just sim one frame with double the delta t, so it has the same cost)

    so this is where the bresenham line comes in, i just meant that its an aliased looking line as you adjust a floating point number and then alias it onto integer frames

    ps. if you dont want to see temporal aliasing (jitter) when it skips or doubles a frame when adjusting time, use the techniques in the “fix your timestep” article

    cheers

  26. Thank you so much for the clarification, manipulating time makes much more sense to me after your info. I must be misunderstanding one element though—you mentioned that by increasing a floating point time by a delta between .75 and 1.25 you would get a range that would span 0,1, or 2 frames respectively.

    I’m currently using your “fix your timestep” technique in my simulation(which works great). Let’s say I have a fixed timestep of 100hz, and I’m using a millisecond timer. Say I start at time 0, I keep rendering and accumulating time, then check my current time and I’m at 11 millseconds, just over a 100th and time for a simulation frame. If I multiply 11 milliseconds by 1.25 (I’m assuming you multiply when you say you increase?), I get 13.75 milliseconds, which is not 20, the amount needed for 2 simulation frames. Should I be multiplying after every render and not just after a 100th has passed?

    I think I see how multiplying by .75 would equal 0 frames (because it would reduce the time and mean you’re not quite at a 100th), but the 1.25 equals 2 frames I’m not sure about. Am I totally misunderstanding what you meant? Thanks!

  27. ok, i dont understand your example but i’ll explain my time adjustment again in detail:

    what you normally do, is you increase simulation time by 1.0, so its all very easy:

    time is 10.0, 11.0, 12.0, 13.0, 14.0, 15.0

    i call this time “normalized time”, because one time unit is a frame. you’ll find this very useful with this technique, instead of using seconds.

    ok, so when the client adjusts to meet a target, it is either going to speeding up or slowing down, during this period, it changes the delta time between 0.75 and 1.25 approximately. note that the client is still framelocking and actually simulating at exactly 30fps, its just that we apply a time scale on the client, in real time, so the client seems to be running faster/slower than usual. the goal being, catchup to the time value at which the server wants the client to be at.

    to the user, the time scale is at worst case 3/4 time when slowing down, or 5/4 time when speeding up

    note that my time adjustment technique doesnt actually multiply dt, it actually adds an offset to it clamped in the range of [-0.25f, +0.25f] towards the direction it needs to adjust, it does this by looking at the ‘target time’ sent from the server, and using an exponentially smoothed average and some filters to smoothly adjust towards this. calculating the target time is complex and requires lots of filters, i cant go into detail about how i do this yet, sorry.

    now, lets think in terms of fixed time again, ‘floating point’ time is really just frame number + some fractional number

    in terms of our fixed rate simulation, frame 10.26432 doesnt really have much meaning, but frame 10 does, and frame 11 does. fractional frames are meaningless to us – at frame n, we take state n, and input n, and apply the simulation to get state n + 1

    so how do we reconcile the two? let me show you how it works:

    lets say we’re speeding up so client delta time is 1.25:

    current frame time is 10.9 (almost 11), so we add our 1.25 to get frame 12.15

    how many integer frames have we crossed? we have crossed over frame 11, and frame 12. so 2 frames.

    so this simulation step, we do 2 frames instead of the normal one.

    next time through the simulation, delta time is still 1.25, and the frame time is 12.15, so we add 1.25 to this to get 13.4

    how many frames have we crossed? just 13. this time we do one simulation step.

    and so on.

    now consider the maximum slowdown case, client delta time will be 0.75, lets start at time 10.2:

    10.2 + 0.75 = 10.95

    how many frames have we crossed? zero. so this time around we do no simulation. this frame is skipped.

    next frame we have time = 10.95, and we add 0.75 to it, getting 11.7

    now we have cross one frame, so we simulate that.

    and so on, so you see when we are slowed down, the actual *effect* is to simulate 1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0

    and when we are speeding up 1,1,1,2,1,1,1,2,1,1,1,2 etc.

    get it?

    cheers

  28. i should also make it clear, that the technique i’m talking about now, is about how to do networking and time adjustment with a *fixed time step*, this is desirable for networking and for consoles

    when i say “use the fix your timestep” technique, i dont mean do the time accumulation and decouple render and simulation rate as per that article

    i mean, used fixed time step, and use the interpolation technique in that to handle the fact that on the client, you now have fractional frames, and interpolate between them

    hope that makes it clearer

    cheers

  29. Ok, I think I get it now, thanks for taking the time to explain it, I really appreciate it. (I also understand you can’t reveal everything you are doing, I’m just grateful for the snippets you can release :) When you say the server sends the correct time to the client, you meant it sends the correct integer simulation frame to the clients, and that’s what they catch up too, right? (looking at the source code for this article also seems to point to that conclusion) I had been assuming that the server sent an actual time value in seconds to the clients, that’s probably where I screwed up. Your sequence of 0,1, or 2 frames makes perfect sense under that conclusion.

    When you say the client is framelocked and simulating 30 frames to second, do you mean that the client just passes in 1/30 as dt to the physics function every rendered frame? Wouldn’t this cause the physics speed to fluctuate based on rendering rate, even with a fixed timestep?

    What I’ve been doing currently is using the time accumulation in the “fix your timestep” technique to regulate all sorts of time intervals—i.e. I only send updates to the server 30 times per second, as well as run all my game logic at that rate. I need this kind of exact game loop timing so I can save commands and play them back within my simulation engine, but it has caused me a nightmare in trying to network as each client accumulates time at a different rate, even though each is accumulating at 30 frames per second. The server just relays input as received, but sometimes a client will not get an update from another client in time to render it, thus causing stuttering. This is all just on a lan testing environment with no real latency.

    Perhaps I do need to work on combining the two methods as you mentioned, I wonder if there’s an easier way to get a fixed rate game loop and still synchronize timing?

  30. yes framelocking 30fps means the client passes in 1/30 dt each frame, but also that the client *waits* for 30fps to go past before simulating that frame, i do this by spinlock at the end of the frame (if 1/30th of a second has not been taken up, wait until it is), if you exceed 1/30th of a second, too bad you slow down

    the main reason i do this is that my network model advances all players and objects ahead together (unlike the article above, which advances them separately) – if you dont need this, then you dont have to framelock, so in that case do your client time adjustment some other way

    btw. the stuttering is called jitter, what you need to do is speed the client up so that he delivers his input ahead of time, both so latency is cancelled out, and jitter is accomodated for. if the client delivers packets +/- 2 frames spread, speed the client so he is 2 frames more ahead. solved.

    cheers

  31. I have a newbie question regarding how to build the networkedPhysics demo app. I downloaded and installed visual studio 2005 express. When I try to re-build the app I get an error saying windows.h not found. This .h is referenced by the project’s own windows.h file. Do you have any suggestions on what may be wrong?

    TIA,
    TB

  32. Hi Glenn,

    Hopefully you still get notifications about comments on this old post. I was wondering if you knew of any other resources regarding the very last section of your article on General networked physics. We want to do a multi-player physics simulation game. Where characters run around and all the players crash into piles of blocks, and or move the blocks. Are there any resources out there? Are you planning on writing the followup article any time soon?

    Thanks for any help,
    ~Curt

  33. Hi Glenn,

    I’m a little late but hopefully you’ll get to solve my dilemmas =).

    I’m implementing your techinques for networked physics and fixed timestep (so useful!!). I’ve got stuck though on how to deal with collisions. Collisions with the static world are handled quite smoothly but collisions between characters are giving me a headache. The server should be authorative on all clients but having the positions of the character out of sync cannot perform a global collision test accurately.

    I was thinking of waiting on the server for the input data to arrive from all clients before advancing to the next timestep, buffering any input arrived ahead of time. This way the server would have a synchronized world state an could make world collision calulations.

    Do you think it could work? Or do you have suggestions to solve the issue in another way?

    simone

  34. yep that works, using that technique on mercs2 right now

    only trick is you need to use time synchronization (speed up client / slow down) such that it delivers input and state for the frame *ahead* of server needing it

    that way, you advance through a buffer of input and state, and all input from the client has already arrived

    cheers

  35. Hi Glenn

    I have been reading both this article, and your other article, “fix your timestep!”, both articles have been a very enlightening read for me, being a game developing novice; thank you for your efforts in putting together these great articles.

    In post #31 on this page, you suggest that it may be possible to combine the two techniques, it also seems that Tim (#32) is trying to achieve the same goal; I just wondered if either of you might have any advice on how this might be achieved, or have either of you managed to achieve a working combination of the two techniques?

    I would be most grateful for any assistance you can give me, many thanks and best regards.

    Cyburg

  36. I’m a bit late to the game here…but I have a questions related to comment 22 where you suggest the client simulation could run ahead of the server.

    In this scenerio, how does the server update the client for objects the client does NOT control. Since the server will always be behind the client, any state updates it gives to the client would be out of date. It seems to cause the reverse problem of when the client has the input before the server.

    This article and the subsequent discussion have beeng great. I’m looking foward to your talk at GDC this year.
    Thanks for sharing!
    Todd

  37. you are right, you can solve it one of two ways:

    – extrapolate the predicted object ahead to current time on the client
    – ignore the time difference, and logically create two “time streams”, client time and lagged server time

    i go with #2 for mercs2, because we cant afford to extrapolate using the physics simulation and i dont want to do a dumb predictor (eg. dead reckoning) — as long as the objects from different time streams dont interact, it works awesome

  38. Great series of articles :)

    In the last post (42) what do you mean by two time streams? Do you mean that the server controlled objects will actually be n steps behind the client objects (i.e. when the server updates come in you just set that position in the client physics (or at least interpolate between the 2)). If n is small that it hopefully won’t matter too much?

    As a matter of interest why not do the dead reckoning?

    Presumably there must be also be some correction for the players object as well in case something hit them on the server? Possibly you could keep the last n frames on the client, then when the server comes back compare the history with the server to work out the differences – and then apply them to the current frame on the client?

  39. #39 (Cyburg), I’m sorry but at of yet our team hasn’t the time needed to implement the “adaptive framerate”, but I look forward to the GDC info as well.

  40. #43, I have the same questions as nigel. Glenn, in #42, you mentioned that as long as the objects in two time streams don’t interact, it works fine. However, what if they do? Eg. Client A gets a state update from the server k frames behind its current frame. That state is different from Client A’s state k frame behind. The difference is the position of an object that Client A will collide into. What can be done in this situation? Client A probably can’t afford to change the data and run k frames of simulations to fix the state different.

    Thanks for the article and the discussions. They are very helpful.

  41. read the slides from my GDC talk, when objects interact then the server authority wins, and the objects are pulled back into the latent time stream – this manifests as a pop on the client

  42. Hey Glenn,

    I’m trying to implement network physics from your articles, but I’m confused by a few things.

    In your article “Fix Your Timestep” you point out how important a fixed timestep is for deterministic physics,
    but in your Networked Physics article you appear to be using a variable timestep for physics on the server.
    Having fixed delta on the client, and variable delta on the server makes determinism impossible.
    1.
    void receiveInput(float time, Input input)
    {
    if ( time < currentTime )
    return;

    const float deltaTime = currentTime – time; //This varies greatly depending on how many inputs have been missed or delayed

    updatePhysics( currentTime, deltaTime, input );
    }

    Another thing that has me stumped is your NetworkedPhysics code. The article says to send a timestamp to the server, but your code just implements an Acknowledge number. Is the purpose of the timestamp just for rejecting out of order messages?

    Another question I had was regarding other clients. Do you use clientside prediction for all the other players also?

    Cheers.

  43. first question, you’ll note that “updatePhysics” internally assumes that deltaTime is a multiple of n frames at fixed framerate, so even though its updating a different amount of delta time, it does so in fixed delta time increments

    this is because the time values coming over the network are always multiples of fixed delta time (multiples of 1/60th second for example)

    eg. you have fixed delta time of 1/60, so to do deltaTime = 10/60 frames, you do 10 steps 1/60 each

  44. Thanks for the reply, Glenn. I still got a couple of questions. Please bare with me as I’m a newbie to this.

    1) As a follow up to #46 and #47, the client needs to be running ahead of the server for n-frames. If the client is pulled back into the latent time stream because of differences between server state and previous client state, the client will be in the same time stream as the server. How can the client be ahead of the server by n-frames again?

    2) Because a client is ahead of the server by n-frames, it runs its simulation based solely on his own input. It seems to me that the client will be always wrong on the states of other players because the client doesn’t have the input from them until the server update n-frames later. Won’t this cause constant snapping of things not controlled by the client disrupting game player and player to player interaction?

    Please bare with my poor English. I hope my questions are understandable. And thanks again for the great article and information.

  45. 1. the client is never pulled back into the latent time stream, we either rewind and replay to get the correction back to client time, or we dont apply corrections on the client (see my GDC 2008 talk on authority management)

    2. the client is wrong on the state of other players, you have a few options here, either just approximate them, extrapolated them to current time (i dont like this one), or to leave them in latent time (my preference)

    my recommended approach is the client running ahead of the server, and all objects sent from the server to client running in latent time – so client controlled objects are predicted ahead, but server owned objects are in latent time

    cheers

  46. also for #2 – if you dont want to be physically correct, research “interpolation and extrapolation” as used in networking, it is here (ghosts of remote objects on client), where this is normally used

    interpolation/extrapolation is not my normal strategy, but its something to look into for ghosts

    cheers

  47. Hey great info, thanks again for sharing!

    Two questions if you would be so kind…

    1.) You mention that with Havok (and with most physics engines if I am not mistaken) you can not ‘manually reposition’ individual objects. You have to update the ENTIRE simulation at once. Which begs the question, how are you correcting the position of out of sync bodies (for example when the server sends a ‘no you dont, that object is red’ message to the client).

    2.) I think the method you describe (giving the client authority for certain objects) is the ONLY way to achieve a truly dynamic multiplayer world. The only ‘good’ way at least :) . So it seems like we have no choice but to use this same model for non-coop games as well. Thus, what to do about cheating…

    It seems like some ‘outside the box’ thinking is required… Perhaps you could have the server randomly validate updates from the client, checking to see if something ‘fishy’ is going on (a teleport from one end of the map to the other, ect…). I feel you could build a fence high enough that, while not perfect, could deter the vast majority of cheaters. Any thoughts?

    Thanks in advance!

  48. you can of course apply individual updates to physics objects, but the point about not being able to rely on a static world and rewind and replay just the player controlled object – thats what i was talking about, you have to update the whole world together, and this implies that objects move and interact (not just player running around a static world)

    for #2, authority management is a good way to get the client feeling no latency (being able to client side predict), without needing to rewind and replay to apply corrections from the server to the physics world – anti-cheat could still be done, eg. running metrics on the server to check the client’s actions are valid, verifying hits and kills on the server are correct relative to the client’s perception of the world and so on — this is similar to what counterstrike does for locally predicted hits

  49. Sorry if i am so noob but why the client correction is important? why we dont just snap the new input and state without replaying the history’s moves?

    i dont understand the imporantece of replaying the history’s moves if they are not rendered during the game.

  50. remember that the client is predicting ahead, so if there is a 1 second round trip lag between client and server, the server will send corrections for time t back when the client is at t+1

    so unless you wish for the client to be pulled back by RTT each time the server applies a correction, then you must rewind and replay

    the alternative is not client side predicting at all, in which case the client feels the RTT latency in movement, but the server corrections can just be applied without replaying moves

    cheers

  51. Hey, hi there ! I trying to implement your article into a real app, but i see there is a problem with receiving timestamps. Sometimes when the server’s recieved the input from the server, cant handle well the synchronization because the JITTER.

    1:my question is: how do you handle the JITTER when recieving timestamps during the receive input of the server.

    Using the code below sometimes i get different delta times. very variable deltatimes. Your example source code works well because it has a fixed deltime times every tick, but in a real network the deltime time is variable because the jitter.

    2:How do you fix your deltatime so the simulation is stable?

    Thank for your time

  52. ok so in the context of this article, on the server you simulate ahead based on the delta time difference between the current time for the player, and the time in the packet for that player

    this stepping forward *should* always be some multiple of fixed delta time

    but it does mean that as packets arrive each player is slightly out of phase of each other

    the solution is to not render directly on the server, but instead to have clients running interpolation/extrapolation client for the remote view, so basically, always have a separate dedicated server running, so even if a computer is playing the game and acting as a server, the actual server is in another process

    this way, jitter is handled with traditional client side techniques such as interpolation/extrapolation

    more details here:

    http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

  53. Thanks for the great article!

    However I still can’t figure out the small question here. Let’s assume that a client has time t=100 and network latency=120ms.

    1) He sends to the server “START MOVEMENT FORWARD” command.
    2) Server will receive it after 100 + 120/GameStep (clientT + Latency/GameStep), react and start moving the object
    3) Server will reply to the client with current server time, position of the object and action “START MOVEMENT FORWARD”.
    4) Client will receive it after 100 + (120/GameStep * 2).

    According to your code from history.h old moves will be deleted since the received time is ahead from the current client time. User will notice kind of “JUMP”.

    while (moves.oldest().time<t && !moves.empty())
    moves.remove();

    Did I miss something?

    Thanks in advance!

  54. t is the lagged time, so it is RTT behind actual time – therefore the moves don’t get deleted until they are no longer needed

    for example if your lag is 100ms each way, then moves won’t be removed until 200ms at the earliest

    cheers

  55. Thanks for reply. So it means that server must trust the time of the client and use it for calculation?

    e.g. client sends “FORWARD COMMAND” with t=100, server receives it on t=110 and use the time of the client with t=100 to apply this command and resend it to other clients?

  56. yes, so some limit on the client advancing time +/- needs to be enforced so that obvious cheating cannot be performed

    for example you could calculate the approximate time offset between each player character and limit to some deviation around this, or you could track total amount of time advanced over a period of time and if its some % over/under real time advanced then it could be clamped

    alternatively you could just boot clients that have poor time advancing characteristics instead of trying to “fix” the time, and say its disconnecting because of poor network conditions ;)

  57. also one other point, note that the rewind and replay occurs on the client after the move goes client -> server, then server -> client again i got the feeling somehow (not sure if this is true) that you might think something is occurring on the server when it is actually on the client

    to clarify what goes on the server side, each time an update comes from the client, it advances ahead the time difference between the last update and the current one – meaning that each client player sim is slightly out of phase on the server

    this complicates weapon hit detection, because you have to account for all the client players being out of phase – but physics interactions between two players are “undefined” anyway given that you are client side predicting, so its no big deal

    see the valve article i linked to above for more details, its pretty good

    cheers

  58. Thank you so much for you explanation!

    But as I understood it won’t work with approach when the client sends only “commands” to the server. I mean, client presses “UP” button and sends it to the server. While he holds this button pressed you do not send any new commands until he holding it pressed?

    1. Client: T=100, UP button pressed

    2. Client: T=210, UP button unpressed

    Am I right here?

  59. the client sends the current input repeatedly, whether or not it changes – this is because we send input over an unreliable channel, so sending just commands as deltas is not a good idea

    cheers

  60. Of course floating point numbers are deterministic for a *given platform*. That’s how all RTS games work on the PC. Just make sure everyone is using the same version of SSE or even simpler: disable it.

  61. yes that technique works fine for synchronous games

    but first person shooters and action games can’t just sit around and wait for the input to arrive from all other players, so they run asynchronously

    in an asynchronous network game, just sending inputs is not enough to keep the simulation in sync – *even if* the simulation is entirely deterministic.

    so in this case, i recommend sending state as frequently as possible

    of course, the greater the amount of determinism you have, the lower frequency of object updates you can get away with

    and finally you can reduce the % of time spent waiting for other players inputs with time syncronization, time stamped packets and a jitter buffer

    but even with all of this, you still need to send state — because sometimes, no packets will get through at all for a second or two, and in a FPS you can’t just stop the game and wait!

    cheers

  62. Hi Glenn,
    Thanks for writing all of this! I have a few annoyingly long questions I was hoping you could answer about heavy physics simulations, if you don’t mind:
    1.) When does 1111211112-style time synchronization actually come into play? Does this have anything to do with rewind/replay, or do client/server times get out of sync simply because of framerate differences between client and server (one is running at 30 FPS and the other at 60 FPS) and/or nondeterministic simulation times (i.e. the server is briefly unable to sustain 60 FPS real-time)? Assuming the former, can/should time synchronization be used to amortize client-side rewind/replay costs while “catching back up” after a snap? Assuming the latter, if the client is running at 30 FPS and the server is running at 60 FPS, that would result in relatively consistent 1010101010 timing for the client, right? If the client is running at 120 FPS and the server is running at 60 FPS, that would result in a relatively consistent 2222222222 timing, right? Following in the same vein, would 1111211112 timing be consistently used if the client is running at 75 FPS and the server is running at 60 FPS?

    2.) In a physics-heavy simulation, you say that the client should have “limited authority” over objects under the players control, and the server trusts the client’s judgment (even if it enables cheating). Using the same trick, whenever the client collides with an object or stack of “connected” objects, the client could temporarily take control of those objects as well, perform authoritative collision detection locally, and update the results to the server (finally relinquishing control of the objects after they’ve eventually come to rest). What I don’t understand is, WHY?

    You say, “on the client, give limited authority to the objects that the client controls, eg. his player, objects the player pushes, the vehicle the player drives. send updates for these to the server. the server accepts these positions and trusts the client. yes, this makes cheating possible, but frankly, we have no choice – we simply cannot afford the cost of rewinding on the client and replaying the whole havok simulation.”

    You wrote the above paragraph after talking at length about cost-prohibitive *server*-side rewinds/replays (caused by late or out-of-order client input and largely alleviated by running clients ahead of the server in time). This paragraph confused me because you made a sudden shift from talking about cost-prohibitive server-side rewinds/replays to talking about [apparently] cost-prohibitive *client*-side rewinds/replays. I’m not sure which you actually meant to refer to, but in both cases, I’m confused:

    a.) If you really meant to say “we simply cannot afford the cost of rewinding on the server:” I understand that server-side rewinds/replays are entirely cost-prohibitive, and I understand how running clients ahead of the server in time mitigates the frequency of these rewinds (or eliminates them entirely if we simply ignore late input outright). That said, I do not understand how any kind of client authority over objects would help prevent cost-prohibitive server rewinding/replaying, because they seem completely unrelated. When server-side rewinds/replays depend on the timing of packet arrival, it doesn’t seem to matter whether clients are sending only player input info or if they’re sending position/orientation info for their player info and other “owned” objects. Regardless of their contents, late packets must either be discarded or reintegrated into the simulation in order, right? Sending position/orientation info does not magically fix this problem for the same reason that doing out-of-order, post-facto dead reckoning about player input does not magically fix it. In both cases, the input or object positions sent by different clients may result in unforeseen interactions/collisions, and the problem is integrating everything (to check for these interactions/collisions). Once we’ve dealt with late packets by running clients ahead and ignoring subsequent late packets, I’m not seeing how authoritative clients can help this issue at all.

    b.) On the other hand, maybe you really did mean to change the subject and talk about avoiding prohibitive client-side rewinds/replays. In this case, I can see how client authority over “owned” object positions would prevent routine discrepancies from floating point errors and spiraling nondeterminism from accumulating, which would save clients the trouble of rewinding and replaying the simulation MOST of the time. However, unless I’m missing something, doesn’t some level of client-side rewinding/replaying become completely inevitable whenever any interaction occurs between two players, a player and an object another client owns, or objects owned by different clients? After all, the server must run the authoritative simulation in those instances. For that matter, whenever two or more clients tell the server they want to take control of the same object at the same time, rewinding and replaying will need to occur on every client except for the one who “wins.” In any case, I can’t see how anyone but the server can handle interaction between two or more players…meaning rewinds and replays of client-side prediction are inevitably necessary whenever anything resembling actual online interaction occurs. Am I wrong here?

    Assuming I’m right, I have an idea: Clients are going to be doing a good deal of rewinding and replaying anyway, regardless of whether they’re considered authoritative over their movement and the movement of objects they control (when no real interaction is occurring). I suppose that if we rely on actual interaction occurring infrequently enough, making clients semi-authoritative reduces the frequency of rewinds. Still, wouldn’t the best solution be to somehow make client-side prediction cheaper, completely eliminating the need to make clients authoritative anyway (and saving ourselves the hassle of writing cheat-detection code)? After all, the very word “prediction” implies some level of uncertainty and doubt. Even if we run a full-blown replica of the server-side simulation, it’s always going to be subject to correction by the server (at the very least, whenever players interact). No matter what we do, our client-side prediction can be invalidated by unforeseen events generated by other players. Taking this into account, is it really necessary to run a full-blown physics simulation over the entire game world on the client side? Because the server is authoritative over game physics and collisions, it must incorporate every single object in the entire game world into its calculations, on the off-chance that certain interactions occur (even unlikely ones) that will affect the later state of the system. In contrast, client-side prediction has no real commitment to the long-term accuracy and stability of the system, because prediction is used only to give the player a smooth sense of movement and an instant, semi-reliable forecast of input results. When there are already a bunch of unavoidable *unknown* variables (caused by other players) that can break our client-side prediction, it seems kind of silly and wasteful to simulate every last known variable with meticulous accuracy (as if the validity of our prediction is likely to depend upon whether we incorporate the idle stack of crates a hundred yards away into our calculations). You say that dead reckoning doesn’t work with a stack of objects, and only the physics simulation can handle such situations…but what if we ran the “full” physics simulation on a *limited* subset of game world objects instead of all of them? The way I see it, we could significantly cut down on the client-side prediction time (and therefore rewind/replay time) if we ran a “full” physics simulation containing only a few objects:
    – The player
    – Interactive objects the player is touching or which the player is controlling – along with all objects attached to them. For uber-smoothness and minimal snapping, we could even throw in other nearby objects that our directly controlled objects are reasonably likely to collide with (determined by some heuristic).
    – Nearby level geometry (e.g. the ground, nearby walls, etc.). Regardless of whether we have static or entirely dynamic world geometry, our representation will hopefully make it relatively easy to incorporate important nearby data while cutting out superfluous data that’s unlikely to affect the client’s prediction this frame.

    In this way, we can make our client-side prediction much cheaper than a full-world simulation without significantly impairing its short-term forecasting accuracy or ability to handle connected objects (like stacks, etc.). Ideally, this would allow us to rewind/replay many frames of client-side prediction at a time. Of course, our prediction can occasionally fail if we aggressively cut objects from the simulation and leave out objects that would otherwise collide with the ones we’re controlling, but in that case, the server will notice the collision and snap the client back soon enough (just like when the server notices collisions due to other players’ actions). Does this sound viable to you, or is there some glaring hole I’m overlooking?

    3.) Finally, I’ve been trying to figure out if it’s possible to run huge, complex simulations with large numbers of interactive objects over a network. I can only think of a single game that has ever used large numbers of interactive objects, and that’s Cell Factor, which was basically created as a PhysX card demo. Needless to say, Ageia made it without online multiplayer, since the massive amounts of bandwidth required would have been prohibitive. Still, can you think of any techniques which might help alleviate this strain and make more physically complex games possible online? While UDP is clearly preferable for constantly-updated dynamic data (like player movement updates), would it be advisable to use TCP for less-frequently-updated objects, only sending updates on those whenever state actually changes? This still wouldn’t make it easy to model insane numbers of interactive objects (let alone something like interactive particle-based fluids in a completely dynamic, destructible world ;)), but I’m hoping it might allow for somewhat more interactive online worlds.

  63. Yeah, I agree with the essay comment. ;) So, errrm…if it’s too daunting, how about just starting with question 1? Admittedly, it includes a bunch of sub-questions all by itself, but it’s still not too bad compared to “question” 2. ;) Thanks!

    1. well i should preface this by saying that my newer synchronization techniques do not rely on 100% determinism or even fixed framerate (although it can’t hurt…), so i don’t do this technique anymore

      but yeah, basically the 11121112… thing comes in to play when client is trying to speed up time, it is doing this to ensure that it delivers it’s input and state for frame n to the server, some time *before* the server simulates frame n.

      at other points the client realizes it is further ahead in time, so the simulation steps would look something like this 11101110111 as it slows down.

      it does this because it desirable to have the client and server simulating at the same base rate, instead of simply scaling time (dt)

      note that while this is going on there is intra-frame interpolation going on (see “fix your timestep”), so everything remains smooth. also note that most of the time, the client is happy being where he is, so everything is 1111111 …

      again, please note that I no longer do this, because I now advocate a peer-to-peer approach for synchronizing physics, where no common timebase is required (or even, defined really…)

      so in other words, this whole discussion is about something i did around 2004, and it’s now 2009 and I do things totally different these days

      muahahah >B)

      cheers :)

  64. also, regarding all your points about rewinding – 5 years later, i no longer do any rewinding on the client or server side. instead, i use an authority scheme to solve all interactions

    cheers

    1. Hey,

      First of all, thank you very much for this!

      Can you explain a bit more about that authority scheme? I’m trying to do a plain combat game (not a plain simulator, more arcade thing), and I’m using Newton Game Dynamics, so I can’t rewind… I’ve checked your “Why you really should come to my GDC talk” page, but didn’t got much to my mind =|

      Could you help please?

      1. ok so the basic idea is that you run the physics simulation on all player machines, then give each player an id: 0,1,2,3 then you have a rule that the lowest player id wins

        first you assign all physically simulated objects default authority (maxPlayers+1 = 5), then whenever you interact with them locally (directly or indirectly), you set their authority to your local player id, if your local player id is lower than the current authority for the object

        so if you interact with an object, and nobody else is interacting with it – you get to interact with it latency free, effectively you become the server for that object

        but if you interact with an object with a lower player id, you cannot take authority, so you interact with it with lag

        if due to high latency, you and another player both take authority over the same object, then the lowest player id wins, and the higher player id will see a pop/warp on the first update received from the lower player

        all that is required to implement this is to add one bit per-object, which means “i think i have local authority” over this object, then send that along with the other rigid body data you send per-object, if the bit is set then the object is treated as having authority of the player id which sent it, otherwise the authority is 5

        cheers

  65. Thanks for the responses! Could you clarify what you mean by using the authority scheme to solve all interactions? Do you mean that you no longer do client-side prediction whatsoever, resulting in no need to rewind on the client side? (After all, it seems as though eliminating client-side prediction is the only way to eliminate rewinding all together. From my understanding of the terms, you were using the “authority scheme” all along to solve interactions; it’s just that clients never found out about the results of the server’s authoritative decision until several frames later, forcing them to rewind and replay their client-side prediction.)

  66. Hiya Glenn! God this is over my head as of now. I am a 15 year old who can write some BASIC and Java but nothing like this. So two questions:

    1. Is the written in Assembly or C++?

    2. Know any good starting program guides for Assembly/C++?

    Thank you for any response.

  67. Hi Glenn, thanks for your work!

    Maybe I have stupid but fundamental question :) : why to send client controls instead of its pos updates? Client does simulation in any case. So server can “trust” client most time but just sometimes check for cheating. This should release some server power.

    I’m more interesting in a MMORPG game. Is your architecture is applicable for this game type too? What should be changed?

    thanks

    1. you send out both client controls and position updates, the controls give you better extrapolation – for example if it was a car sim, you could send out the position of the car, torque of engine, wheel speeds, orientation, lin/ang velocity — you can predict OK with this, but you’d also want to know “steering wheel hard right”, and “brakes on”, you would get a much better prediction .25 secs from now with the control information as well as the states

      re. MMOs i haven’t coded an MMO so i’m not the right person to ask — i would assume that physics simulation + MMO is exceptionally difficult, since i don’t see any MMOs doing that right now. perhaps a client side physics following a simple server side motion is possible, but a true physics sim, no not yet.

  68. i wish to argue how peer-to-peer model is faster, much faster, than currently popular server-client model… and in fact, it has so many advantages over S/C that it is mindbogglingly unexplainable why in the world no online multiplayer game use it. why, why, why? but, if there are any games to use it after all, then please let me know about them. ok, here it goes…

    THE TRUTH ABOUT SERVER MODEL
    – central server collects all the input from all the clients, calculates movement/collision then sends to each client the new machine state, ie. new positions of each entity, velocities, orientation and such, which then each client renders, perhaps utilizing some extrapolation to fill in the gaps from, say network refresh rate of 20Hz to their screen refresh rate of 60 FPS.

    to put it simply, games on the internet today run only about 10-20FPS of real server-computed data and clients input samples, regardless of how many FPS your client renders, but those extra frames are only “smooth-candy”, and even worse, they may itself be the source of another set of visual artifacts since they can easily mismatch with server’s next update.

    that sucks, but it can be better and it’s rather simple actually,
    but this is not news, p2p is nothing new as we all know, tho most will be surprised that no game actually use this as a main network model for the game, only for chat, patches and some side-stuff. so, one thing is clear, p2p works… but does it work better than server-client model? can it host the whole game? you be the judge!

    1.) first let’s consider round-trip traversal with the best case scenario for S/C model, where server is in the middle and clients A,B,C,D describe a square around it. — shortest route should yield fastest path.

    AB=BC=CD=DA = 30km
    As=Bs=Cs=Ds = 20km

    *** P2P, one frame loop, per ONE client
    round-trip: ~33km (2x 30km, 1x 40km)
    packets sent: 3
    packets received: 3
    total packets per client: 6

    *** SERVER, one frame loop, per ONE client
    round-trip: 40km
    packets sent: 1
    packets received: 4
    total packets per client: 5

    2.) second, let’s consider bandwidth…

    packet overhead= 30 bytes
    packet client input= 10 bytes
    packet full entity state= 20 bytes
    ———————————-

    C/S, client upload per frame: 40 bytes
    C/S, client download per frame: 50 bytes * N_clients

    P2P, peer upload per frame: 50 bytes * N_peers
    P2P, peer download per frame: 50 bytes * N_peers

    *** 16 players, per one client, per second, 60Hz
    C/S: upload= 40*60 = 2400 bytes/s
    C/S: download= 50*16*60 = 48000 bytes/s

    P2P: upload= 50*16*60 = 48000 bytes/s
    P2P: download= 50*16*60 = 48000 bytes/s

    *** 32 players, per one client, per second, 60Hz
    C/S: upload= 40*60 = 2400 bytes/s
    C/S: download= 50*32*60 = 96000 bytes/s

    P2P: upload= 50*32*60 = 96000 bytes/s
    P2P: download= 50*32*60 = 96000 bytes/s

    3.) third, P2P updates are asynchronous, there is no FAST/SLOW here, no waiting – you only have FURTHER and CLOSER, and further is not SLOWER it is only more behind in the past, but the rate of update is NON INTERRUPTED, has CONSTANT streaming flow. theoretically working on FULL 60Hz and more, where frequency only depends on upload bandwidth, size of packets and number of peers. there is no lag, no glitches, no slowdowns, no waiting on server… only time dilation, depending only on DISTANCE.

    CONCLUSION:
    – P2P can not only allow for far better update frequency, but asynchronous, continuous updates will smooth many visual glitches automatically and the streaming nature of incoming data would even further make the whole experience more fluid.

    1.) does p2p have shorter traversal path than server-based model?

    2.) would parallel computing even further speed up latency by getting rid of serial computation server does?

    3.) can p2p run on much faster frequency (60HZ and more) due to the nature of uninterrupted, streamed, asynchronous updates?

    1. hi abaraba hows it going.

      lets have a nice discussion about peer-to-peer vs. client/server

      peer-to-peer has some disadvantages:

      bandwidth per-peer grows O(n) vs. constant bandwidth on the client and O(n) growth on the server. this is the primary disadvantage of using P2P, with high player counts it becomes prohibitively expensive. this is especially true considering that most internet connections have significantly less upload bandwidth than download bandwidth.

      secondly P2P has security issues. since there is no server, peers must be authoritative over some parts of the simulation – meaning that players can cheat. this is a serious issue for any sort of competitive game, and cannot really be solved on an open platform like the PC because the peers can be hacked to send out malicious packets.

      finally, it is significantly more difficult to code algorithms that work in a distributed fashion vs. algorithms where the server makes the decision which the clients must follow. a good example of this is acquiring a mutually exclusive lock on a resource. consider what you would have to do to implement this in a P2P fashion? consider that there is some prohibitive cost if you incorrectly acquire the resource and have to give it up? what if players can join or leave at any time? now consider how much easier this would be if the server just decides who owns the resource.

      of course P2P does have the advantage of lower latency since peers talk directly to each other instead of going through the server. this is obvious and well known. for certain applications such as networked physics, provided the player count is low, i believe that P2P offers some significant advantages over a traditional client/server model. for example, if you distribute server responsibilities and use an authority scheme you gain the advantage of latency free interations with a physically simulated world. however, this is just on single application where P2P wins and is in no way an endorsement that all games should be using P2P.

      in conclusion, the cheating problem and the O(n) per-peer bandwidth growth of P2P is enough to convince most game developers to make their games client/server – the extra-difficulty involved is just the icing on the cake. until you have actually coded one of these games abaraba you should probably respect their decision to do so, as it is most likely the correct one for their sort of game. there is significantly more to coding multiplayer games than just minimizing latency. P2P is not a panacea that solves all problems.

    2. abaraba, you seem to be confused. I’ll help you to fix your math and understanding.
      You have to treat the client and server as separate applications with their own upload and download rates.
      Before going onto my example we’ll analyze part of yours:

      abaraba :
      packet overhead= 30 bytes
      packet client input= 10 bytes
      packet full entity state= 20 bytes

      […]

      *** 32 players, per one client, per second, 60Hz
      C/S: upload= 40*60 = 2400 bytes/s
      C/S: download= 50*32*60 = 96000 bytes/s
      P2P: upload= 50*32*60 = 96000 bytes/s
      P2P: download= 50*32*60 = 96000 bytes/s

      Notice how you didn’t say what your numbers were for. The client and server applications are separate. This is probably why you are confused (well part of it). Using your own numbers let’s try this:

      Each packet the client sends to the server with it’s input looks like:
      PacketOverhead, ClientInput
      (30 + 10) * 60 = 2,400 bytes/sec

      So that 2400 number was for the client upload.
      What about it’s download? The server is sending the client a packet that looks like:
      PacketOverhead, EntityState * 32
      30 + (20 * 32) = 670 bytes * 60 = 40,200 bytes/sec
      You left that number out. Why? It’s important.

      So what is that 96,000 representing? Maybe you were trying to find out the server upload and download?
      Upload:
      (30 + (20 * 32)) * 32 players * 60 times a second = 1,286,400 bytes/sec (The reason you don’t use 60hz updates :P)
      Download:
      2400 bytes * 32 = 76,800 bytes/sec

      Okay nope. Looks like you just made up your data. Try not to do that. People frown upon it.

      What about your P2P math?
      Upload:
      (30 + 20) * 31 * 60 = 93000 bytes/sec
      Download:
      93000 bytes/sec

      Nope. Looks like you didn’t do that right either.

      Okay now onto my examples:

      I will point out no one updates a game at 60hz. That would be nearly pointless.

      Client-Server:
      Client upload never matters. To illustrate this if you send input from the client at a rate of 50 ms. (20 times a second). Using:

      PacketOverhead: 28 bytes
      ClientInput: 10 bytes
      ClientState: 20 bytes
      NumberOfClients: 32

      Lets say the game updates at 20 times a second. Also in a client-server sending out full state updates like what I’m about to assume is kind of wasteful. This would be like if every client could see every other client.

      So in the client-server model you have each client sending their input 20 times a second. So the upload cost per client is only:
      PacketOverhead, EventID, ClientInput per packet resulting in:
      ((28 bytes + 2 bytes + 10 bytes) * 20) bytes/sec
      = 800 bytes/sec
      You’ll notice this calculation is per client. So each client will require a 800 byte/sec upload speed.

      For the server to send out state you end up having per client packets that look like:
      PacketOverhead, EventID, NumberOfClients, ClientState * NumberOfClients
      28 bytes + 2 bytes + 1 byte + 20 bytes * 32 clients
      = 671 bytes
      And the server is sending out packets to each client at a rate of 20 packet/sec so:
      PacketSizePerClient * NumberOfClients * PacketRate
      = 671 bytes * 32 clients * 20
      = 429,440 bytes/sec

      Client-Server Cost:
      Client Upload: 800 bytes/sec = 0.006 mbps
      Client Download: 13,420 bytes/sec = 0.10 mbps
      Server Upload: 429,440 bytes/sec = 3.27 mbps
      Server Download: 16,000 bytes/sec = 0.12 mbps

      So pretty much any client can handle that. Except 56K users which have a 5734 bytes/sec download (or something close, I could be wrong though). The server must be hosted on a line with an upload rate of at least 3.5 mbps.

      However, this misses out on the idea that the server can do culling for clients and only send them the data for the other entities they can see. Also you’re dealing with 1 packet not 31 packets that the client has to process. The nice thing about that is that clients will get a full transaction of the state at one time. In P2P this isn’t the case where the client will be getting packets from other clients at different times. Like you get data for clients 1-3, 10-20 and then you do a physics update and now you get the packets for the other clients. This is especially true for when a client might lag for a few milliseconds.

      P2P:
      In this example each client is authoritative over it’s own game state. Again we’ll use these numbers:

      PacketOverhead: 28 bytes
      ClientState: 20 bytes
      NumberOfClients: 32

      So each client is sending a packet that looks like:
      PacketOverhead, EventID, ClientState

      28 bytes + 2 bytes + 20 bytes
      = 50 bytes
      Now it sends it to every client at a rate of 20 packets/sec
      PacketSize * (NumberOfClients – 1) * PacketRate
      = 50 bytes * 31 * 20
      = 31,000 bytes/sec

      Each client will be receiving these 31 packets so:
      Client Upload: 31,000 bytes/sec = 0.24 mbps
      Client Download: 31,000 bytes/sec = 0.24 mbps

      However, these are hypothetical numbers. Reliable packets can be fun.

      abaraba, if you want to understand more of this you’ll need to actually program both of these models and run some tests. Having used server-client myself with 100 clients (twitch-based, I use TCP with a throttled 1-10 packets/sec system) I really enjoy its flexibility. I like P2P and am currently using it for an application. You just jumped into this stuff. Take your time.

      (Hmm I hope I formatted this right. No preview… :( )

  69. >> hi abaraba hows it going.

    ughh, fantastic.. thanks, yourself?

    i can’t believe people went on to call me crazy without ever actually looking into code. and, i’m afraid to even look at your time-stepping page as i fear you still have not corrected the mistake where you have something like 0*1=1… uh, uh uh, zero times any number is zero! …not to mention other bugs that algorithm carries, which you kind of know about… if not, it’s still there, beautifully explained in my delightful e-book, which you kindly advertised on your website, thanks!

    did you see what i did to Intel and nVidia? kaaaa-booom! …hahaaaa! and… did you see i almost managed to simulate atomic bonding in real-time with that algorithm? i sure did manage to simulate all kinds of subatomic particles interaction, based on Lorentz formulas, it’s crazy… i should get nobel prize (while still alive), i’m not kidding! i mean, it’s the first in human history and it’s like my 5th discovery in the row. by the way, text-book physics is so wrong you’d go crazy too if you knew about it. http://www.youtube.com/watch?v=DUNP4z-Vaac

    anyhow, whenever you’re ready i can prove it all over again… you really only need to take a few minutes to compile two algorithms and compare, it’s so very obviously easy to see the difference you don’t even have to measure anything it’s that obvious… hoooo, hooo. — where do you work now, still Lucas Arts or something? tell your boss to let me do the networking, physics and animation for your next game and i guarantee it would outperform anything world has seen — 2x, at least – TWO TIMES FASTER, AT LEAST! …plus, it will be super visually smooth and absolutely deterministically correct. and i’ll do it for free so, how about it?

    ————————————-
    peer-to-peer has some disadvantages:
    ————————————-
    >>>bandwidth per-peer grows O(n) vs. constant bandwidth on the client and O(n) growth on the server. this is the primary disadvantage of using P2P, with high player counts it becomes prohibitively expensive. this is especially true considering that most internet connections have significantly less upload bandwidth than download bandwidth.

    i don’t think the difference is actually that big, as p2p could run on lower frequency while still achieving similar latency. but, if peers can’t support 32 player game, than they can still play 16 player game, or play 32 player on 30Hz instead of 60Hz.

    but of course, as a master as i am, i have some more wonderful solutions in my sleeves..
    – there is a very neat thing you can do with p2p. just like servers can send updates to client only about other visible clients or just of those that are nearby (in the game-world)… well, peers can do the similar thing much more elegantly – they can communicate on different frequencies depending on the distance of the peers in the game-world. so, if some peer is far away, in the game-world, you can send packets to that peer on much slower frequency, therefore drastically reduce bandwidth. you could send updates to peers that are out of visual range(in the game-world) on even 1 second intervals or slower, and increase the frequency dynamically as they close by to your field of view, therefore being able accommodate for different kind of of connections, as a simple change in frequency could allow to switch from ‘more players’ to ‘more frames’, as desired. — wanna make this together? actually, i kind of made it already, but don’t have anyone to help me test it.

    >>secondly P2P has security issues, since there is no server, peers must be authoritative over some parts of the simulation, meaning that players can cheat. this is serious issue for any sort of competitive game, and cannot really be solved on an open platform like the PC because the peers can be hacked to send out malicious packets.

    this is the best argument and for now let’s just say we’re developing military simulation or some kind of application where cheating is not in the interest of peers, say LAN game or some GPS, radar or bluetooth mapping/tracking mobile device, or something. on the other hand, what’s with all the consoles and all the other games that do not have central servers, but one of the clients must take the role. maybe consoles are secure enough so p2p on the consoles might by automatically “secure”, and then p2p would surely be much better option as consoles do not make for good servers, so distribution of bandwidth, no matter how high, would still be less per all the clients than per one server which would clog latency and the whole game for all the clients, and itself.

    >>finally, it is significantly more difficult to code algorithms that work in a distributed fashion vs. algorithms where the server makes the decision which the clients must follow.

    i don’t know, i’m not sure what kind game, what kind of resources you talking about. i’m not talking about massive multiplayer, just 16, 32, 64 or so peers with some average ADSL connection having more fluid experience than with central server, or worse, where one of the clients has to be the server… which can be terrible solution for consoles, such as Xbox, with large packet overhead and limited upload bandwidth.. as i have heard. actually, i find algorithm required would be extremely simple, just like all of my beautiful algorithms are ;-)

    server based model might be better when all the clients have dial up connection and you want to have 16 or more player in one game. but that does not make p2p unusable with dial up connection, only limits the maximum number of peers per game or broadcast frequency. — therefore, client/server model is simply byproduct of bandwidth constraints of the past.

  70. you seem to be somewhat missing the point abaraba

    assuming you require a certain bandwidth n kbps per-player to get a reasonable quality network sync, then by definition for a 32-player game you need 31 (n-1) times more bandwidth per-player in a P2P topology, than in a client/server topology to achieve the same level of quality.

    given this fact, why exactly is it that you think that P2P is so much better than client/server and everybody should use it?

    here let me quote you:

    “i wish to argue how peer-to-peer model is faster, much faster, than currently popular server-client model… and in fact, it has so many advantages over S/C that it is mindbogglingly unexplainable why in the world no online multiplayer game use it. why, why, why? but, if there are any games to use it after all, then please let me know about them.”

    any professional network programmer reading that statement just thinks you are a) completely ignorant and b) incredibly arrogant. you consider that everybody else in the world is wrong in using client/server over P2P, yet your reasoning behind this is completely incorrect, delusional even.

    have you in fact stopped to consider that perhaps it is *your idea* which is incorrect and not the rest of the world that is wrong. perhaps that all the professional programmers that use client/server out of necessity and who – i might add – have actually shipped multiplayer games, may actually have been correct in choosing client/server?

  71. and just in case you don’t get my point – IMO if you attempt to use a (fully connected) P2P topology for anything > 4 players, chances are you are probably a fucking idiot. a dunce. you didn’t take robert downey jr’s advice and you went full retard – have you even done the calculation for bandwidth taking the packet header overhead into consideration? I have (this is what I do professionally) and I can tell you > 4 players P2P it aint pretty – and I *like* P2P.

  72. “3.) third, P2P updates are asynchronous, there is no FAST/SLOW here, no waiting – you only have FURTHER and CLOSER, and further is not SLOWER it is only more behind in the past, but the rate of update is NON INTERRUPTED, has CONSTANT streaming flow. theoretically working on FULL 60Hz and more, where frequency only depends on upload bandwidth, size of packets and number of peers. there is no lag, no glitches, no slowdowns, no waiting on server… only time dilation, depending only on DISTANCE.”

    abaraba, what gibberish you write, it doesn’t even make sense

    you do realize you sound exactly like this guy don’t you?

    http://timecube.com/

    could it be true, abaraba is the timecube man?! suddenly it all makes sense!

    seriously dude, stop trying to code and start a religion or something – science, facts and logic have no place in that mind of yours.

  73. >>assuming you require a certain bandwidth n kbps per-player to get a reasonable quality network sync, then by definition for a 32-player game you need 31 (n-1) times more bandwidth in a P2P topology than in a client/server topology to achieve the same level of quality.

    go on, print some numbers, and then take some console for example where there is no central server but one of the home consoles has to be the server.. go on, compare and come back with numbers. i admit that this is far away from what is my job and experience, so i will trust your numbers. tho, are you forgetting about the bandwidth that flows from the server, and who is paying for it?

    >>given this fact, why exactly is it that you think that P2P is so much better than client/server and everybody should use it?

    as i said – SPEED and SMOOTH ANIMATION, don’t you realize the difference of continuous flow and latency caused by the distance speed of light has to travel, against the latency caused by server waiting on all the clients then loosing time to calculate and prepare info to only then return it back to clients? you loose the FLOW, you get interrupts, gaps, glitches… and you have to extrapolate and guess, and adjust… p2p has flow, flow, flow, like a river, one packet after another, you can miss a packet – no big deal! next one will adjust everything – no correction, smooth animation.

    >>any professional network programmer reading that statement just thinks you are a) completely ignorant and b) incredibly arrogant. you consider that everybody else in the world is wrong in using client/server over P2P, yet your reasoning behind this is completely incorrect, delusional even.

    >>have you in fact stopped to consider that perhaps it is *your idea* which is incorrect and not the rest of the world that is wrong. perhaps that all the professional programmers that use client/server out of necessity and who – i might add – have actually shipped multiplayer games, may actually have been correct in choosing client/server?

    stop insulting me before you print some real-world numbers. i, of course, considered it very carefully…

    1. no need for any calculations on my part abaraba: your own real world numbers in your first post proved beyond any doubt that a) you do not know what you are talking about, and b) client/server is in fact a better choice due to bandwidth growth in P2P, you do understand this don’t you?

  74. >>and just in case you don’t get my point – IMO if you attempt to use a (fully connected) P2P topology for anything > 4 players, chances are you are probably a fucking idiot. a dunce. you didn’t take robert downey jr’s advice and you went full retard – have you even done the calculation for bandwidth taking the packet header overhead into consideration? I have (this is what I do professionally) and I can tell you > 4 players P2P it aint pretty – and I *like* P2P.

    i’m sorry to upset you again. i did calculation and i posted it in my 1st message. would you now care to post your calculation since insults do not make any of your statements any more true.. in fact, according to my calculation, you’re very wrong.

    1. the calculation in your first message in fact shows that P2P has n-1 times more bandwidth usage per-player than a centrally hosted client/server model, yet you continue to argue that P2P is superior – how exactly is it superior abaraba?

  75. Glenn Fiedler :
    no need for any calculations on my part abaraba: your own real world numbers in your first post proved beyond any doubt that a) you do not know what you are talking about, and b) client/server is in fact a better choice due to bandwidth growth in P2P, you do understand this don’t you?

    what is the point on stating something without any proof or explanation? you are wrong. clearly, any average ADSL is very well suitable for 32 and more peers game. — do you understand what is the bandwidth requirements when there is no central server? did you compare latency and distributed bandwidth when say 16 or 32 Xbox clients play a game hosted on one Xbox? print some numbers and realize your mistake.

    Glenn Fiedler :
    the calculation in your first message in fact shows that P2P has n-1 times more bandwidth usage per-player than a centrally hosted client/server model, yet you continue to argue that P2P is superior – how exactly is it superior abaraba?

    more? more?! so? what is more? it is nothing!! even dial up connections should be able to support 4 or more peers on much better update rate than server based solution with in same conditions, especially if one of those clients had to be the server. you keep failing to explain how those games that are hosted on clients, like Xbox, can still manage their bandwidth. just like that can all the peers handle their distributed bandwidth, only easier, uninterrupted and faster.

    1. the explanation has already been made, you just failed to understand it.

      the proof is self evident: if you have a specific bandwidth X, and you chose to utililize this using a client/server model, then you have the entire bandwidth X available for the client to send and receive data. if instead you use P2P, then because you must send packets to the other peers in the game, you have only X/(n-1) bandwidth available per-player, where n is the number of players in the game.

      any reasonable person should be able to understand from this explanation why exactly it is that P2P uses more bandwidth than client/server, yet it seems that you do not – why is that abaraba?

  76. >>any reasonable person should be able to understand from this explanation why exactly it is that P2P uses more bandwidth than client/server, yet it seems that you do not – why is that abaraba?

    would you rather play a game on 20Hz or 60Hz network update rate?

    i told you, if you have ADSL you can play games on full, fluid 60Hz, instead of broken 20-30Hz. the bottom line: ADSL can easily manage games with 16, 32 and more players on much faster frequency over WWW than server-based model can achieve even over LAN. so, what is your concern? people with dial-up? well, they can still play on about 30Hz or even 15hz, and even that would still be faster, smoother and more fluid than any client-is-server model with the same hardware.

  77. but what if you could achieve the exact same quality with just 0.006mbps using client/server as you would using P2P with 0.24mbps — why chose to use more bandwidth than is necessary for exactly the same effect?

  78. abaraba :

    Glenn Fiedler :
    >>so what you are saying abaraba is that you would rather have 0.24mbps upload per-player than 0.006mbps? is this correct?

    yes, of course. you’re practically asking if i wanna play or not play at all. client-is-server model obviously can never support this game in this scenario, not even with 16 and barely with 8 players. so, yes i’d much rather be a peer and have 0.24mbps upload/download, than be the one client that has to be the server.
    so, would you rather have 3.27mbps upload and play the game on 5Hz, or 0.24mbps and have fluid 20Hz?

    Actually it was at 20 Hz not 5 Hz. Go back and read the math over again. You don’t even understand what the numbers mean. Do you have a reading comprehension problem? This is basic math and you’re failing at it. Sorry to be so blunt.

    abaraba :
    yes, of course. you’re practically asking if i wanna play or not play at all.

    Actually that’s not what he asked. If you look at the numbers instead of just making stuff up you’ll realize that he was talking about the client upload. The client upload is less in the server-client model by a lot.

    Your whole point has been based on the idea that P2P will help the clients with latency by sacrificing their bandwidth and security. Correct? Are you sure that latency is a problem and have you made sure P2P can solve that problem without causing other big problems? You haven’t yet. You need to test more. Oh fun example:

    Fun example to test latency. I’ve seen this run better than some people’s games. It’s just ajax going out to a PHP script which queries a database and giving it an x and y value and getting back a list of client positions. It’s possibly the most naive networking system ever, but even without extrapolation/interpolation it can help to clearly view the effects of latency. (Also it’s fun to run around with friends in).

  79. Hi Glen,

    This article has been very useful in my understanding of networked physics, and has helped me build a game engine that supports multiple entities that follow your principals of state synchronisation.

    However I am currently trying to fix a problem I am having with collision between 2 entities owned by different clients.

    My collision detection works fine, but I started running into problems when I simulate high latency.

    High latency is causing a client’s player collide in their “Replay” period in the client prediction when it should not have.

    As you only have 1 entitiy on your sample, and static collision planes you dont deal with this.

    I understand the problem arrises from one entity being rewinded back in time to receive a correction, while other entities stay at the latest time.

    If I rewinded everything in my scene when I do a client owned player state correction I could solve this problem, but this is going to get costly on the CPU time with any decent number of entities in my scene. Not to mention memory keeping a state history of all entities in my scene instead of the owned player.

    I have tried removing collision detection during replay, but as a player with any real latency will be replayed every frame for the last / frames of movement, collisions need to also happen in replay.

    Is there a simpler way to solve this than rewinding my entire scene by the latency amount for each client owned player update(ie every frame)?

    (just to clarify if its not clear, by “Replay” I mean when the server sends out a sync update to a client regarding the player it owns, it rewinds to update time, then replays the input to current time)

    1. yes this is a problem with client-side prediction – since each player predicts differently, and is effectively in a different “time stream” to each other. also, rewinding and replaying the whole simulation gets very expensive, it’s not really a practical option. even if you did do it, the results are *still* undefined when two players in different time streams interact with each other. not worth it!

      one option is to just accept the lag. the server runs the simulation only, and the clients are dumb, perhaps interpolating between position/orientation samples using a hermite spline. in this case because the simulation runs on the server only, the interactions between players are all well defined. but of course, the players movement is all lagged.

      if you cannot accept latency, another option is to use an authority scheme. you can find a quick overview of this technique here – http://developer.nvidia.com/object/physx_tips.html#Network. in an authority scheme, the collisions between players are still somewhat undefined, due to different time streams, but because you are not ever rewinding and replaying, it is cheaper to simulate and the result is much better.

      just be aware that the authority scheme prone to cheating so it’s best used for COOP games only.

      cheers

  80. Thanks for the quick reply!

    The authority scheme is no good as I am targeting competetive gaming.

    This also makes latency a problem.

    I have got collisions working fine where the server has the final say, but the client predicts them, using collision detection in the replay. My problem is that in the scenario (may not actually be a big issue in real situations):

    I simulate about 1 second of latency
    On the client simulation, the owned player runs through a section of empty space, a new entity is crosses paths anywhere the player passed through less than a second ago.

    As the client is receiving state from 1 second ago from the server. It saves the current time, loads the state from the update into the player.

    Making the player have a time of 1 second in the past, and having a position before the new entity that spawned.

    The correction then replays the input of the player for the last second, causing it to collide only on the client with the other entity.

    This causes the client to snap back for about half a second, then towards where the original position should have been. So in the end the server predicts correctly, and the client ends up in the correct state, but it suffers some nasty visual flicker.

    I Guess 1 second latency is not realistic anyway, but as you can see, its not a problem of clients being in different timestreams, but multiple entities on 1 client being in different timestreams.

    It might be nice to know that limitation of the client input replay method. That it creates a CLIENT SIDE only collision field of the movement in the last seconds. The only solution being that each entity exists in the same time stream in the whole scene which is not practical.

    Cheers,

    Speno

  81. *That it creates a CLIENT SIDE only collision field of the movement in the last “latency” seconds. The only solution being that each entity exists in the same time stream in the whole scene which is not practical.

  82. you are not correct.

    but i know the fact about floating points across multiple platforms, systems,… you name it. i had the problem with syncing server with the client’s web application. simple solution step up the precision on every individual calculation and round it down again; or you can tie multiple calculations together, as long as it dose not affect the initial precision. i have used it with floats and doubles; floats and 5 digit round numbers. the result was always the same.

    and there is always the way to use bit level calculations. after all a 1 is a 1 and a 0 is a 0. it might not be as fast though. but, any way, this is useless in networking with approximation and smoothing involved. but it is good for syncing sensitive data, like bank balance.

    1. You could totally consider using 64bit or 128bit fixed point instead of floats, but then you’d have to write all your own routines for sqrt, sin/cos/tan, etc. It would be totally portable and deterministic, but would be a lot of work. For example, Warcraft 3 did something like this, they could not get floating point deterministic so they emulated floating point in integer, about 5% of the frame time of their game was spent doing this.

  83. Hi Glenn,

    I’ve been playing around with your sample code, and I noticed that after changing cube’s mass (e.g. to 5.0), it started to look like gravitational acceleration has been reduced. Bug somewhere, perhaps?

    Thanks for this great article series.

    Alex.

    1. The simulation is very tuned for specific masses. If you change mass, you should change gravity and all the collision constraint forces, or vice versa. Not really the best way to do it, but quick & fast for me to code.

    1. actually, it’s probably that the gravity is being applied as a force but not scaled by mass — try adding that and it should fix it up. note that the collision will also seem more and more springy/spongy as you increase mass of the cube as well, you can compensate by adjusting the K and B for spring collision forces.

      but yeah, pretty good example of the reason why physics engines don’t use penalty methods for collision response these days (eg. spring forces) — it’s hard to tune and dependent on the mass of objects, amount of gravity etc.

      bottom line: use ODE or Bullet instead :)

  84. Yeah, that worked just fine, thanks.

    Probably, but this is a really good starting point in physics simulation.

    Many thanks,
    Alex

  85. A very useable game physics introduction. If you are further seriously interested in that topic, you should have a look in this one: Essential Mathematics for Games and Interactive Applications: A Programmer’s Guide. It covers a bunch of important topics about game physics in a clear manner. The part about linear- and rotational dynamics here could be from it. :)

  86. Hi Glenn,
    Awesome articles you got in your blog – really superb, especially considering the very few and low quality articles there are out there on multiplayer game programming and architecture.

    So I perfectly understand all the concepts, and I know this article was written around 4 years ago, and I was wondering – is there a good way to “player predict” dynamic players in a dynamic world without snapping? Or at least, player on player interactions – for example, a player controlled car smashing into another player controlled car that’s in motion.

    Great blog!
    – Ron

    1. It depends on what you are predicting, for example if you have a FPS game then prediction is usually just ballistic, eg. a simplified physics that knows how to apply gravity while falling and how to slide along surfaces (running some collision) when on the ground.

      However, as players can change direction almost instantly in FPS games (high jerk) prediction is of limited benefit. Most games assume you can get about 0.25secs of prediction in before it becomes potentially totally inaccurate, so if no packets are received after 0.25 secs the character stops extrapolating and stays still until the next packet arrives. This is rare, but avoids the players running fullspeed into walls when a player times out (it takes 10-15 secs to detect dirty disconnect via timeout… :)

      In racing games input has a less direct effect, being that your momentum is so high the input typically guides the momentum slightly left vs. right, but cannot make the vehicle turn on a dime. Consider networking say, F-Zero or Wipeout for example. Here you should easily be able to come up with physics equations that predict 0.25sec or more of motion from the initial conditions sent each packet, and this prediction should be reasonably accurate. The error that needs to be repaired if the input changes and the remote view does not receive this is much smaller.

      In some cases, especially physics simulation like with my “Fiedler’s Cubes” demo, the movement is slow and prediction is not necessarily important, except to fill the gaps between packets arriving — in this case, i just hold last inputs received and extrapolate with the physics simulation. You cannot do this for a racing game, because of the high speeds involved, the lag multiplied by the speed is quite a big difference in position, so you have to extrapolate forward to have two racing cars “next” to each other compensating for lag. But in my cube demo, speeds are slow, so I just have the other player cubes effectively running in the past.

      I hope this is useful.

      cheers

  87. Hi Glenn,

    Thanks for posting this gold mine of information on your site. It has been incredibly helpful for my own projects and I am only starting on working on my netcode now. Two or three years ago your fix-the-timestep article was instrumental in making my simulation engine run smoothly.

    I was reading some articles earlier about how FPS game netcode was done, and the concept of client-side prediction followed by rewinding and resimulating the buffered input clientside was a great revelation to me. Of course if I hadn’t stumbled back to your site today it would have taken me months to realize that the dynamic multiplayer world I envisioned would probably fall flat on its face when simulated using prediction and rewinding methods involving an authoritative server.

    I did come up with some ideas though.
    In any co-operative game type, hacking isn’t really a game-breaking issue. You mentioned at some point in the comments that a peer to peer protocol that allows objects to switch “ownership” between clients is probably a good way to go. At this point I am wondering about whether or not it would be better to introduce a server in order to reduce load on the clients. Is this something that even makes sense?

    I need to do more coding before I have any more good things to ask. I will be back, but not too soon.

    Also abaraba is a colossal asshat.

    1. The bottom line is that the authority scheme is very suited to physics heavy COOP games, for a good example look at “Ratchet and Clank: All 4 One”. It’s a COOP game using an authority scheme and it does very well. It would be difficult to see how to do all that they do with a rewind & replay scheme, that would be quite expensive.

      Another physics heavy sync approach can be seen in “Little Big Planet”. There is is networked deterministically by sending inputs, the cost being that you may only support a low player count (2-4) and the game network quality is proportional to the player with the worst network connection.

      Also, see my GDC2011 talk about networked physics. The part in there about how GGPO does it, is basically the same strategy that LBP uses.

      And yes. Yes he is :)

  88. Hi Glenn,

    I’m about to start playing with some of this for a personal project of mine which I hope to present to my bosses if all goes well. There’s a great deal of information in the replies, which I haven’t finished reading, but would I be right in saying the following:

    – The re-winding/re-simulation is just done on the client side, and on a per-player basis (if the physics engine permits)
    – The server does not rewind when it receives your inputs (which naturally occurred in the past) and instead the client is essentially tries to lean forward in time a certain amount proportional to their latency?

    Love these articles, very interesting =)
    Cheers
    J

    1. Yes. The server does not do any rewinding, however it is typical for projectile hit detection for the server to keep track of historical positions for each player such that it can check if projectiles hit, some time in the past. Google for “Valve Latency Compensation” to read more about this. cheers

  89. After reading the rest of the comments in my lunchbreak today, I’m more confused if anything =D

    So far all of the network programming I’ve done has been for MMOs, and now I’m branching out into an FPS for a personal project, it’s kind of blowing my mind!

    Anyway, do I understand correctly that there’s 2 main approaches here to consider:
    1) Client sends inputs, timestamping them with now+latency. Server applies these in its simulation and sends updates back to the client. Client rewinds and replays when necessary, or snaps when necessary. Optionally other players and objects can be predicted and rewound/replayed, but you said in a comment further up that this is a bad idea, and to just plough on being a little bit out of sync with everyone else?
    2) Authority system based on player ID, no rewinding for anyone (even the client?).

    I realise that this article was written a fair few years ago and techniques and technology may have changed. The game I’m attempting to create would be aimed more at coop, but there would be some competitive gameplay, so option (2) might not be possible.

    Any pointing of my newbie nose in the right direction would be v much appreciated =)

    Cheers
    J

    1. If you are shipping on the PC it is abundantly clear you want to do #1. Google for “Valve Client Side Prediction” and “Valve Latency Compensation” to understand how it is done server side including projectile hit detection.

      If you do #2, you really can only pull this off if you are COOP, or if you are on a console platform and have some way to detect these cheats. For example, Halo does this. Study the “Networking Halo Reach” talk by David Aldridge from GDC2011.

      Even then it’s a large risk and the cheat detection code is onerous. I only recommend #2 if you lots of physically simulated objects that must interact with each other that would be too expensive/complicated to rewind and replay.

      cheers

  90. It really depends on what you want to do. If you want to network an FPS and you can afford the rewind/replay then this is a good way to go. Valve does this technique. However, if you are massively CPU bound and/or in a large streaming world, or you are COOP not competitive, and authority scheme is a better way to go. See my GDC talk stuff from the last few years on the main page. cheers

  91. I gave the notes a read, very interesting stuff with the data packing, and the priority updating was especially cool.

    Yeah I’m thinking that (at this stage) option (1) may be better for me as cheating is a concern, and the world itself is going to be pretty damn static, just players, bullets, the odd grenade etc. I’m not sure how affordable rewinding other clients will be, I’m using Unity at the moment which doesn’t have the ability to rewind built in, so I’ll need to roll my own basic physics system (just position, velocity and acceleration) in order to achieve that.

    Cheers for your help, and for these articles. It’s extremely awesome to be able to read about the techniques being used by professionals =)
    J

    1. There are other techniques than just rewind and replay. Client side prediction is any action performed by the client which masks latency, for example you could play the grenade throwing animation before getting ack back from the server — the grenade itself comes out lagged, but the animation hides it enough for the user. I’m pretty sure Halo does something like this for grenade throws. Go watch the Halo Reach talk “I Shot You First” from GDC 2011 for details. cheers

  92. Me again (eek) =)

    I’ve been implementing rewind&replay for the players in my ongoing FPS project, and it’s been working beautifully for predicting/correcting the users own movement. However, it’s been falling flat when predicting other players, as they’re being predicted ahead using input data which is half their RTT old. But if I don’t predict other players then either the server will need to rewind players when doing hit testing for shooting etc (I read this is how valve do things?) or users will need to lead their shots? Am I right in thinking those are my options, or is there something fundamental that I’m missing?

    Cheers!
    Joe

    1. I don’t recommend predicting other players in an FPS. Instead, interpolate their motion and accept that it is “behind” relative to the client. Keep track of exactly how much, then you can compensate for this on the server when you check player projectiles hit another player — keep a historical buffer of positions for each player on the server, then look “back in time” the amount equal to latency + amount of interpolation (if you do valve like interpolation on client), then you’ll have the projectiles hitting without the player having to lead by the amount of lag

      For more information google for “Latency Compensation Valve”

      cheers

  93. Yes, try the valve way which is to just move the objects back in time on the server when detecting hits. This way the client does not need to lead. Read the “Latency compensation” paper by Yahn Bernier.

  94. Thought so, the amount of ballistic projectiles I want to have might be problematic, but I’ll give it a go!

    Cheers
    J

    1. It should be OK, the “move back in time” is easy to implement. Just remember historical positions for objects for a second or so, and have a function to move the state of the world back in time before you do projectile raycasts. This is pretty easy and cheap to do.

  95. Well the valve technique works best with instant hit projectiles, but at the cost of additional CPU and/or memory you can handle non-hitscan weapons as well. cheers

  96. Hey what to do if game Physics is not deterministic . Timestep of game not fixed.
    how to sync in this situation ?
    Cheers !!!!

  97. hi :)

    thanks for your great article.

    and i have an question about delta time.

    even if i use the rk4 integrater. another machine has different result (position)

    because of the delta time

    i think original machine use the delta time with const double dt = 0.01;

    but copy machine use the delta time from server like example

    const float deltaTime = moves[index].time – currentTime;

    updatePhysics(currentTime, deltaTime, currentInput);

    . it’s variable and so original and copy machine use different delta time

    and so i think it occur another result between original and copy machine

    how about that?

    Cheers !!!

    1. yes, you will get a different result on each machine. if you want the same result you need to step forward with the same timesteps on each machine.

  98. Hi Glenn,
    firstly I want to thank you for all the excellent articles you have written and also for the time you are spending for answering the questions regarding them – they help a lot in understanding the networked physics issues!

    I had a look at all your articles and your presentations from GDCs, and authority scheme looks really promising (at least for coop games). I do have a question about it though: Assuming there is an object that does NOT rest after interacting with it, but e.g. gets driven by a constant velocity, which player/client will take care of it and guarantee it is in sync with the other players?
    This covers the topic you mentioned at the summary of auth. scheme at GDC10: “this technique is good … where these objects typically return to being at rest after being interacted with”.

    What do you think is the best approach to solve this issue? Might assigning an activity region as large as the game world for the player with the highest id be an option? But this would lead to a high network & cpu load for that client, as he would be acting as the server for all objects not in the authority region of other players.

    Another approach that comes to my mind is that none of the players would take authority, when it is not in an authority region – so the moving object would be out of sync until it gets into the authority region of any player again. Though, this is not a real solution ;)

    cheers

    1. Typically I solve this by having one of the machines designated as the server, or perhaps having a dedicated server (you can still do this with distributed authority btw. google for “Insomniac Sync Host”)

      Then in the case where no player obviously has control, the server takes control by default. In the dedicated server case this would mean the whole simulation for the union of all player relevancy regions runs on the server, and for any active objects which are not under control of a player at one point are under authority of the dedicated server.

      cheers

  99. I’m just getting into programming my first networked 2d game and I’m coming across so many issues. I’m incredibly grateful for this article, it seems to have the most information about game networking in one place!

    I have one important question though. How do you synchronize the time on the client and server.

    I’m guessing that you have some float or int that you’re using to count the time on the client and the server every frame. When either sends a packet it stamps it with this time.

    My main issue is… how do i sync the actual time… when the server tells the client what time it is on the server, that new time was already out of date! I suppose you could attempt to adjust the packet by talking average round trip time/2?

    Can you advise me on how to do this?

    I’m starting to think that I want to rewrite my game a bit to handle doing this Bresenham Line time stepping thing… but I’m still having trouble wrapping my head around how I’d actually code it…

    Thank you for all the help you’ve already given and thank you in advance for any additional help you give me!

    1. Why do you need to synchronize time? Start with something simpler — for example, the client could just send it’s input the server and wait for the delay. Try that first. Walk before you run.

      1. Well, I started with just having users send control inputs to the server. The server sends Pos, Accel, and Vel back to the players (along with a few other things when necessary, such as adds and deletes).

        My problem is that using this seems to have a lot of jittery lag, even when I’m running the server and client on one machine. I could probably reduce their greatly if I attempted to implement a buffer for packets to reduce the processing of early/jittered packets. Also, using interpolation and a primitive lag compensation wouldn’t hurt.

        My difficulty is that it’s hard for me to do lag compensation well because when i just take the delay of a packet, or the average round trip time and I try to figure out how many frames that is, it’s always a bit in consistent. I’m having a hard time figuring out a good way to determine how many frames old a packet is.

        I thought that synching time might help me do this. Using the Bresenham line concept and synching time… and speeding up the client past the server so I don’t need to have the server store old world states to do control lag compensation as well.

        I don’t know if everything I’m trying to do is wrong. I have limited time though, I was being very ambitious. I want to develop games for a living… so I figured, why not make a networked game with basic physics for my “Senior Project”. I’ve already made a few physics engines… it can’t be THAT hard. Little did I know……

        Thank you again, for all your help!

        1. I think that I have a better understanding of how to do a few things here. My main concern now is how to figure out my target time.

          I know I want to try to sync with the server and I can do this by looking at the time stamps on packets and trying to figure out how old the time stamp is based on average round trip time….

          Do you think you could give me some idea about those “filters” you were talking about in one of your comments.

          It seems that the magic to this system is figuring out your target time well. If you can do that, it really makes this system do a lot of magic…… It removes the need to have world states stored on servers and taking packets and pushing them back in time and re-simulating…. right?.. I hope so :P

          1. Synchronizing time is overkill for what you need. Try to focus on unsynchronized time with smoothing, or loosly synced time via EPIC + smoothing

            cheers

          1. Thank you very much, I’ll definitely apply this. When I’m done with this assignment though, I do hope to make a real multiplayer game. When I get to that, I’m going to need to do something to reduce command lag, right?

  100. Hi Glenn,

    Thanks for the great articles which has really helped me out in my understanding of my first multi-player project (been coding for decades just not multi-player).

    I really would love some pointer/help/advice on how to achieve server/client time synchronization. I thought initially this is something that would be covered all over the net but actually…it’s pretty hard to come across. As with Eluem I have thought long and hard about using rtt/2 tests from server to client etc but it still seems that this would be at best a pretty wild guess (as I don’t know how much of the rtt is actually upstream or downstream).

    Any advice you can give me on this would be greatly appreciated as time synchronization is definitely the way I want to go with my project.

    Thanks again for all the great work

    1. Do you really need to make it cheat proof at this point? If so my advice is to google for “Valve Client Side Prediction” and “Valve Latency Compensation” and follow that network model, or download the Quake or Doom3 source code and follow how they do it there.

      And yes, time synchronization is complicated because it depends entirely on your network model, depending on your network technique you need very little of it, or a lot. I’ve shipped games with completely unsynchronized clocks, loosely synced clocks, and have done R&D projects with deterministic lockstep that requires complete synchronization.

      cheers

  101. Excellent guide Glenn,

    I would like to do a cooperative mario like, I would like to know what kind of technique should I use to smooth and eliminate latency.

    Regards,

    John

    1. Designate one machine as server. run all game logic there, except each machine runs the game code for their own controlled character locally and transmits positions and movement to the server. server accepts this movement. you’ll need to solve interactions between objects like opening doors, pickups, and damage in a client/server fashion with reliable network events. cheers

  102. “when that input makes a round trip to the server and back to the client that the client’s character starts moving forward locally”
    Does that mean these messages are being sent reliably (using a system simillar to acks you mentioned in your other article)

    And if not, are any of the msgs being sent reliable?? Thanks!

    1. Not necessarily. In this case I’m just trying to explain a network model where the client sends inputs to the server, and the game runs on the server and just broadcasts out game state to the clients for interpolation and rendering, eg. classic client/server without any client side code.

      The actual transport underneath could be unreliable, the delay does not come from reliability, but from the fact that the client cannot predict motion ahead because the game runs only on the server.

      cheers

  103. HI Glenn,
    I really enjoyed your series on game programming, especially this demo.

    I’m writing a networked FPS game in XNA (C#) and am using a physics engine that updates the whole world at once. (BEPU physics)

    The update method takes a Delta Time since the last update call, and I am a bit confused on how I could implement something similar to your demonstration using a physics system that updates all entities at once instead of just one entity.

    What would be the best possible method in this case to minimize cheating while still using some sort of authoritative networking with client side prediction?

    Thanks for your time and your great articles / demonstrations!

    1. This article is based around a server which updates the world one object at a time, eg. FPS. For example, if you have an FPS server it is typical to have each player in their own “time stream”, eg. slightly different time values, and to resolve this time difference when calculating projectile hits using code that rewinds back in time to the client’s POV at time of shooting (eg. read the valve “Latency compensation” white paper)

      This is totally different to what you would expect to do for a modern physics simulation where objects interact with each other and you have to update the whole scene at once. To do this, start with a pure client/server approach first, then if latency is a problem for you try distributing the physics using an authority scheme so that parts of the physics run on the machine that wants zero latency over that part, eg. the players character, the players vehicle, objects the player bumps into etc.

      cheers

      1. Also, to minimize cheating using some authoritative scheme, — well that is very difficult, you could inspect the motion of the physics and do basic checks, did they move too quickly, did they add too much energy to the system. You would need to accumulate this “divergence” over time, as small glitches would be expected to occur under packet loss. If you detect divergence, then put the player on the bench for 10secs, then respawn. If you detect multiple times then kick/ban the player.

        cheers

        1. Another option is deterministic lockstep, if you have a deterministic physics simulation and a low player count it’s actually very easy to detect cheating. Just have inputs go to a dedicated input server before being broadcast back out to the players — this way lag switches and time dilation hacks on packets can be detected and kicked.

          cheers

          1. Thanks for the fast reply!

            I have a small follow up question. You said that the server updates one object at a time, eg FPS games. How do games that use this model prevent players from colliding with other players(some games for example don’t let characters walk through other characters)? If the players are only being updated individually, how would the two different simulations (time streams) be able to synch together to know that player X is next to player Y and cannot move closer in that direction?

            Also, in this networking model, is the server side cube only being updated when an input packet is received, or is it continually being updated?

            Thanks again for your help, you’ve made the nightmare of networking physics much more bearable!

          2. Yes in this model the server is updating the physics for each player when a packet is received and immediately replying with corrected state for client side prediction rewind+replay — the collisions between players are approximate, you’ll notice that usually player vs. player collisions in these games are jittery. now you know why! :)

          3. also, while player vs. player direct collisions are approximate — projectile vs. player collisions are more accurate, since the projectile looks back into the past at the time of firing on the server to compensate for both lag *and* each player being in a slightly different time frame on the server (according to packets arriving). the first game to do this was counterstrike and it was able to do this because it had instant hit weapons, vs. the slow projectile weapons of quake. you’ll notice that in quake and even quakeworld post-client side prediction, you still had to lead your shots by the amount of lag to that player. same for unreal. then counterstrike solved this with latency compensation for projectile hits and became the most popular online game in the world ;)

          4. So I assume the server doesnt have to rewind and replay, it sort of literally just looks at the positions of the dudes according to saved histories using the time the shot happened at?

            Also sorry if these replies are formatted a bit odd, im not sure if this quotes the post im replying too lol.

          5. yes the server just stores a ringbuffer of positions per-player so it can look back in the past

          6. LOL IM AN IDIOT! I was doing the first part as you said, “Yes in this model the server is updating the physics for each player when a packet is received”, But transmitting the game state back to the user at a steady 15 FPS(server time). That makes no sense at all because then i would have to rewind back time significantly, (RTT/2) and also account for the time the server update finished!

            This is why i went from programming because i was curious to hating programming, and now pretty much loving it, can always learn something new, always do something better!

            I’m surprised at the results im getting so far runnign this over iphone and using 3G. Its working pretty decently so far.

  104. Ah ok, thats what I assumed but wasn’t 100 percent sure, I have currently implemented this, now to add client side prediction!
    Thanks very much!

  105. Hi Glenn, I just have a few final questions before I finish my implementation :) (Which is working well)

    If there is a prediction error, does the server recognize this somehow so it doesn’t continually spam out correction messages to the client (i.e. until the client has received the correction, updated, and sent back its new position)?

    (I’m having a problem where if there is a correction needed to be done, the server will cause the client to replay unnecessarily even after the correct state is received, from the the correction time until connection time + round trip time.)

    Also, I’m using a simple threshold (0.25F) on my server. If the client’s position is within the threshold of the server’s position after the server has updated to the current state, I simply snap the server to the client’s position. Is this a safe practice, since the server is still authoritative over movements above the threshold?

  106. I was wondering, receiving client states and sending server response could be very expensive, how many updates are usually sent by the server to clients ? Which is common server’s framerate ?

  107. when you replay your player’s action
    you used global-phy-update-function ” updatePhysics(currentTime, deltaTime, currentInput);”, but at that time, environment had been changed, (not like the environment when dirty prediction happen)。 could you tell how to deal with this ?

  108. Hi Glenn, great read, it’s still helping us newbies out all these years later. I’m starting out with networked vehicle physics and read the couple of comments above written back in 07 regarding it by Nicolas and Suchon. I was wondering if you knew of any new techniques for network vehicle simulations that have come about since those posts? Any papers that come to mind? Or would you stick with the two options of; clients tells everyone about their own vehicle or clients send inputs to server whiles simulating client side, corrections are made to the clients once we get the authoritative state back from the server?

    thanks

    /Laurence

    1. Your main options are:

      a) client authority over the vehicle
      b) rewind and replay client side prediction of the vehicle

      b is rather hard, and I think you would need a very strong reason to do that vs the easy approach

      Another thing to consider is the remote view of the vehicle, eg. a 3rd machine neither server nor controlling client

      In this case, you can choose between:

      a) running the sim on both sides
      b) interpolating/extrapolating motion in the remote view
      c) some mix of the two, depending on state

      If you have fast and mostly linear motion, I would recommend b. This is because if it is mostly linear and high speed (think a racing game like F-Zero) then the extrapolation of the car is easy, and *necessary* because for the typical delay when racing vs somebody else of 100ms, that is a lot of position difference when moving at high speed.

      If you have something slower, eg. like a buggy with suspension effects and lots of bouncing/tumbling motion go with a

      If you have different types of motion, eg. a crash where you can tumble, but most of the time it is fast linear motion, perhaps a mix of the two? Google for “Predictive contracts”

      cheers

      1. Great, much clearer now. I’ll have to find some tricks to minimise cheating as its PC based, but I think client authority is the way to go for me, along with a mix of running the sim on both clients and extrapolating. As far as running the sim on both sides goes, i’ll be sending updated states of the main chassis RB to each client along with player inputs so that steering, breaking etc can be mimicked and hopefully some predictive contracts can be made if the chassis’ angular velocities go over a threshold so we know if the player is in a state of rolling or spinning out.

        For anyone interested in the predictive contracts side, here’s a couple of articles that helped me understand it better:
        (dead reckoning, should know this before predictive contracts)
        http://www.gamedev.net/page/resources/_/technical/multiplayer-and-network-programming/targeting-a-variation-of-dead-reckoning-r1370
        (Bottom part of this introduces predictive contracts)
        http://www.gamasutra.com/view/feature/3230/dead_reckoning_latency_hiding_for_.php

        thanks Glenn

        /Laurence

        1. What’s usually done is that you do a client/server architecture, but the sim is not on the server — it is on the clients, then you try to come up with some empirical rules to detect cheating based on the stream of state coming from the client.

          You cannot have any false positives so you must have some slop. The idea is to detect movement that is too fast, over a period of time, warping, standard hacks like that — think of a cheat accumulator that decay over time, if weird stuff happens in a short amount of time the player hits a threshold and is flagged as a cheater.

          Typical response on the server is to kick or “delay” the player in a sin-bin for cheating in this way, this avoids rewind and replay for the server to correct the client btw.

          cheers

          1. The difficult thing btw. is detecting the difference between cheating and bad network conditions, they will often look the same!

          2. Sounds like quite a challenge. I can imagine just adding 10kph or so more to the cars velocity could be hard to detect, but would mean they’d have a great advantage.
            Can see this one taking a lot of trail and error.

            thanks again

            /Laurence

          3. Yes the problem is that because you cannot do tight checks there must be some slop, so this leaves an area in which it safe to cheat otherwise you would have too many false positives.

            Another solution is to record the games from the POV of all participants and store these with the game, then when a cheating report comes in you can take a look at each person’s view and compare.

  109. Hi Glenn, your article is great! But i have some issues with my code. Im writing flash based topdown 2D FPS with free movement on WASD. Due to Flash i can only use TCP connection but when i try to send 30 inputs per second my ping grows from 90 to 180-200. I desided to send only deltas of inputs. So client send only “forward button pressed” and start move. Server catch it and start move to, but store timestamp of input packet. When client send “forward button no more pressed” and stops, server still running forward for 100 ms, and it’s about 5-6 px more and then client need to smooth it position according to server. Is there any method to eliminate it? Or any other method to implement WASD movement? Thanks for advance.

  110. I am making a casual mobile soccer game with 5-a-side team, 2 clients play a match and each client can control 1 player character at a time while the remaining 4 in the team are controlled by AI. I am using Photon cloud for this – provided by ExitGames. Its a generic and extremely low cost service that provides the dumb matchmaking + message-relay server. Since its a casual mobile game and I am not worried about client cheating – I am not looking into a dedicated authoritative server approach where physics/gamestate is maintained. Since I do have a server in the middle, I have no worries about NAT/firewalls that come with traditional P2P. Also, only 2 players play a match, so I also don’t take the “bandwidth” hit associated with traditional P2P style. The time it takes for a message to go from one client to the other ranges between 100ms to 500ms (noticed average about 300ms)
    I have an option to make this P2P style where both clients run the simulation, each client is authoritative over their team. Each client sends over player velocities to the other as soon as velocity changes happen (within a threshold) but I do have to sync positions as well less frequently (4 times a second) to keep the game from diverging especially when players collide when one another etc. This leaves the matter of soccer ball not owned by anyone. Based on your guidance in these posts, one strategy that comes to mind is that the team that currently has possession of the ball (dribbling) temporarily becomes authoritative over the ball and even when the ball is during flight (passed or goal shoot) the source team can still stay authoritative until the opposing team intercepts. I am currently facing several issues with this approach. 1. I cant ensure that the “simulation” time is executing “in sync” across both clients. one phone can start/progress slower than the other. when client 1 moves a player, that player is moved immediately on client 1, the message takes X ms to reach client 2, so it starts moving slightly later on client 2 even though with position syncs , they ultimately end up in the same spot without much jitter. but client1 cannot steal the ball from client2 i.e. possession over ball has issues since client 1 sees the ball’s position “slightly in past” tries to steal it by colliding with it, client 1 simulation thinks “ball possession success”, move sent to client 2 which has progressed the ball position even further so player1 doesn’t end up colliding with the ball. Similarly the situation with goal shoot by client 1, keeper response on client 2 “goal saved” by the time that move gets back to client 1 goal has been scored.
    Option 2 would be to have one client as server and apply all the discussion in these threads related to lag compensation, server authority etc.. but I think that gives a lot of advantage to the host player. That’s why the P2P looked more balanced approach to me, but I don’t know how to handle these “conflicting” situations when both teams are interacting with ball etc. I also thought about putting physics/AI in a separate thread and having a fixed timestep e.g. 20MS counts as one physics timestep and running physics/AI about 10 timesteps (200MS) ahead of rendering thread on both clients essentially producing a buffer of gamestate that rendering thread consumes “later”, but I still cant figure how that can be helpful. I also thought about “scheduling” client 1’s actions 5 simulation steps in future kind of like the Age of Empires discussion hoping it would reach client 2 in time to be executed in the same timestep on both clients, but that may require “rewinding: simulation on client 2 if it already passed the target scheduled sim step. Also 5 timestep (100MS delay) on client 1 may be noticeable. Please provide some guidance and feel free to let me know I am being foolish :)

    1. Yeah so you are just describing lag.

      Perhaps photon is not the best choice if lag is a problem?

      Alternately why not design the lag into the game, be creative and come up with a design that works with 300-500ms lag.

      Hint: players may need to move slower

      1. photon also provides authoritative server based option, but that means hosting the servers myself and adding gameplay logic/physics code to server. the cloud service option is easier since they host in several regions of the world and its generic, I don’t push any code to any server.

    2. Also it seems in your head you are mixing deterministic lockstep approach and authority scheme.

      You should pick one, not try to do both.

      1. Yes, I am trying to mix them you are right… I thought maybe that could be useful for getting same results for the ball and especially goal score? I have the players moving slowly but the ball cant be as slow as the players :S.. even if do lockstep kind of approach, some one still needs to manage the ball and I am not doing strict lockstep I guess since I wont “stop” execution (which bring me to the question, is there a complete description of lock step method)…

        1. It seems you are trying to incorporate every technique from every article you’ve read into your project.

          This is not a good approach.

          First work out what you want to do, then do the simplest thing that will achieve that, find the next thing to improve and iterate.

    3. Also, needed to know if there are compelling reasons for running AI/Physics in a completely separate thread generating “game states” queue, which rendering thread can utilize? does that help in anyway with network syncing? especially if physics/AI runs ahead of rendering?

      1. It is an optimization. I would focus initially on getting everything working in the simplest way possible.

  111. Hey Glenn,

    Thank you for this article, I really enjoyed reading it!

    I have a question though: Should the server calculate all rigidbodies (objects like barrels and boxxes) and give their new position and rotation to the clients ?

  112. Hello, Glenn!
    Should I say that your articles are simply brilliant find for all those, trying themselfs at networking! Thank you very much for all that you’ve wrote and all those effort for answering all these comments with truly needed information!
    So, as far as I’m already here :DD can I have some sort of your advice on a specific aspect of our network model. We are planning to make a racing game, where main part of the show will be drifting. We have our physic model with lots of parameters, influencing on car behaviour, working okay offline (pretty much not deterministic, using Unity). As far as it will be fast-paced, dynamic game, where wining is based on player’s skills, we need to make sure that player have precise control of his car. So, we’ve chose to make physic simulation on both server and client. But the differenece in physics behaviour is pretty big, so we’re lerping rotation almost every time, and after certain threshold we just snap the rotation. After couple of day of brain melting, we’ve tried to use another approach, using physics only on server for full authority with 200ms fixed delay. It works fine in terms of behaviour, as it only runs on server, but those 0.2s is pretty much ruining that control over car. Not sure what to do: try to change physic to suit 0.2s delay or there is something we’ve missed in client and server sim?

  113. Hi Glenn,

    First of all, thank you for your articles, they help me so much to understand the network gaming.

    I’m currently developing a 2D space style MOBA (Multiplayer Online Battle Arena) game, like DotA or League of Legends. But, I’m including real 2D physics in my game. Basically the main concept is that every player has his spaceship, and moves it in a top-down 2D world, with every object (including spaceships) having its own position, velocity, etc… and can interact with each other (like hit and bounce off).
    So, what I’m currently doing is having the clients sending their input to the server and then the server simulates the world and sends the state back to the clients.
    Is client-side prediction good implementation in order to reduce the latency ? In my opinion it is, but after reading your article i have some doubts. I would like to hear your opinion as an expert!

  114. I don’t think I’m clear on how dropped packets are handled – what if the client sends a “Fire weapon” packet at time = t and this gets dropped and never reaches the server, how would things proceed? If there’s no reliability then the fire command may never reach the server, what happens in this case?

    1. If you are concerned about missing commands you could send the sliding window of unacked commands up to a second.

      Losing more than a seconds worth of data would be exceptionally low probability.

      You’d have bigger problems at that point

      Cheers

  115. Hi Glenn,

    first, the obligatory many thanks for a really informative article & comments – and I’ll throw in another thank you for the entertainment value of the arabara discussion ;)

    I’m currently trying to ‘network’ a fast-paced 2D multiplayer platform party game, where player character movement is driven by a physics simulation – box2D – by steering the player’s velocities based on input and letting the physics engine take care of movement & collisions. Core to the gameplay are concepts like players pushing each other. Now I’m trying to figure out the best approach to make this playable under laggy network conditions.

    My first approach was to have an authorative server, and implement client prediction + correction – although with a simplistic correction that only works with position deltas. This is where this approach failed, the resulting correction is unstable & often incorrect.

    A second approach was to give each client authority over its own player. Local player experience was immediately OK obviously, but I can’t figure out yet how to deal with playerplayer collisions in this case – when lag increases pushing other players becomes jerky, to the point where you can’t push the other player at all anymore. Whenever this subject is touched in literature it seems, it’s deemed “yeah that’s tough” without a real solution for it :)

    I am now considering going back to the classical first approach, throwing out the physics engine for player movement & doing the calculations myself, trying to turn the whole simulation into something deterministic and implementing proper rollback & replay. In my case the CPU cost *should* remain under control since we’re only talking max 4 players here and at most one extra physics object.

    However, since this would be a huge endeavour compared to the whole project, I’d love to hear your opinion on:

    1. whether this will be a solution at all to make playerplayer collisions look OK on average internet lag – or not really?
    2. whether there is another solution to this problem that does not require me to implement a full rollback & replay – (I’m considering scenarios where one player’s authority is handed over to another etc, but always seem to find cases where this would fail)

    Your view on this would be much appreciated!

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Glenn Fiedler's Game Development Articles and Tutorials