Sign in to follow this  
caymanbruce

Slow response in State interpolation when time gap is big between client and server

Recommended Posts

I implemented my first ever state interpolation in my game demo a few days ago. If client time and the server time has a time difference less than 10ms the player interpolates very smoothly. However if the time difference is bigger, such as 40ms or 90ms the player will suddenly stop and then after a while just flick to the target position like there is no interpolation at all.

My game demo is very simple. It only shows players moving around on the map. My current interpolation function is like this (written in Javascript):

interpolateState(previousState, currentState, renderTime) {
  if (renderTime <= currentState.timestamp && renderTime >= previousState.timestamp) {
      const total = currentState.timestamp - previousState.timestamp;
      const portion = renderTime - previousState.timestamp;
      const ratio = portion / total;
      // For every player do the following
      player.x = lerp(previousState.players[player.id].x, currentState.players[player.id].x, ratio);
      player.y = lerp(previousState.players[player.id].y, currentState.players[player.id].y, ratio);
      player.rotation = lerp(previousState.players[player.id].rotation, currentState.players[player.id].rotation, ratio);
  } else {
      sync(currentState);
  }
} 

sync(state) {
    player.x = findPlayerState(state).x;
    player.y = findPlayerState(state).y;
}

Here server runs at 60fps and send update every 50ms and the renderTime is the 200ms before the server time which I get from syncing the time with the server at client side.

On the client I put the states I received from the server into a queue which has 3 slots for storage temporary states so that on every network update the new state will be pushed into the queue and an existing state will be popped out for use. The queue will only pop a state when it's full, and to interpolate I need to have two states, that's why I choose 200ms before the present time.  This simple and naive approach seems to work but I think there are a lot to improve to make my game demo playable in real world situation. Is there anything I can work on to fix the lags due to server and client time difference?

Edited by caymanbruce

Share this post


Link to post
Share on other sites

Have you tried the things I mentioned in the other thread? I'll reword them to make it explicit:

1) You must not simply overwrite currentState and previousState whenever a new state comes in. Doing so will cause jerkiness. The states you want to interpolate between depend entirely on the render time, not on which states have arrived recently. You need to keep several states to make sure you have enough to work with.

You receive State x=1 at Time 500, then State x=2 at Time 1000. If rendertime is currently 750, then you treat x as 1.5. That's all good. Then you receive a new state, x=3 at Time 1500. But render time is still something like 900 (for example), and it's outside your 2 latest state timestamps, so you immediately snap it up to x=3, from the previous value of 1.5 or whatever. That's obviously wrong. Keep all your past states until the render time has become large enough that you know you'll never need it.

If you keep all past states for as long as they're needed, the only time interpolateState won't have valid data to work with is (a) right at the start, when 0 or 1 states have been received, or (b) if no state has been received for at least 200ms. In the first situation, you can skip rendering. In the second situation, extrapolating is probably fine (i.e. lerp, with a ratio > 1) until a new state comes in and you can snap the character back into place. This will be a rare occurrence if everything else works.

2) You mustn't just change renderTime or serverTime immediately based on data from the server. If you do, whenever there is a slow network packet, your rendering will not be smooth because time is no longer smooth. The time-sync algorithm you're using is not designed to give you smooth changes. To begin with, you should consider using it once at the start of play, to synchronise clocks, and then from that point onwards you use the local client time. This should work well enough for almost all situations. In future, you might consider performing clock adjustments during play, but by smoothing out those changes over time.

I'll add the following: you don't need 200ms of delay. Try 100ms, if lag is an issue.

Edited by Kylotan

Share this post


Link to post
Share on other sites

Typically, when you receive a new state from the server, you want to capture the current displayed position as the "checkpoint in time," (your "previous state") and then fill in the server state as the "future state to interpolate towards."

Typically, you'll set the server state to be the target a time T + 1 frame, where T is the time between server packets, giving you one extra frame of latency to allow for server jitter and such.

Very simplified:

State prevState;
State nextState;
State toRender;
onRender(Time t) {
  if (t < prevState.time) {
    toRender = prevState;
    warn("time too early");
  } else if (t > nextState.time) {
    toRender = nextState;
    warn("time too late");
  } else {
    toRender = lerp(prevState, nextState, (t - prevState.time)/(nextState.time - prevState.time));
  }
  renderState(toRender);
}

onReceive(State s) {
  if (s.time <= nextState.time) {
    warn("received bad time");
  } else {
    prevState = toRender;    // <--- IMPORTANT!
    nextState = s;
  }
}

Share this post


Link to post
Share on other sites

One key thing to note as a difference between the two answers above is that hplus0603 is advocating a 1 frame buffer - i.e. 50ms - rather than the original 200ms, which basically mandates holding on to a queue of the last 4 or 5 states.

Share this post


Link to post
Share on other sites

One key thing to note as a difference between the two answers above is that hplus0603 is advocating a 1 frame buffer - i.e. 50ms - rather than the original 200ms, which basically mandates holding on to a queue of the last 4 or 5 states.

Thanks so why do you suggest 100ms not 50ms or 200ms?

I am still digesting what you said in the previous post. The first problem I have is syncing the time. Now I try to sync the time only once at the beginning of the game instead of continuously syncing it. Say I sync the time for 5 times and get a mean offset, at an interval of 3 seconds. So that's a total 15 seconds before entering my game. That doesn't seem to be the case of other io games. I wonder if there is a better way syncing the time between server and clients.

Share this post


Link to post
Share on other sites

I suggested 100ms just as something that is less than 200ms. You could try lower than that. Ideally your time buffer is only as large as it needs to be to ensure that you always have some server data to render. In many games you don't really need to know or care what the server time is; when you get a new state, assume that is valid for exactly one frame from now and interpolate accordingly.

Even if you want to do server time sync, I don't see why you need to do it 5 times over 3 seconds. Once should suffice and it shouldn't even take a second.

I suspect trying to synchronise clocks and implement smooth rendering between past snapshots is overkill for the sort of game you're making. It's common for FPS games. You started out with the Valve and Quake 3 docs but you're (apparently) making some sort of Agar.io type game which clearly doesn't need that sort of approach. I would be willing to bet that typical games like that are just broadcasting out updates and interpolating towards the latest state, which is exactly what hplus0603 has recommended above. (So, ignore what I said about multiple snapshots, but ignore the server time, and treat updates received as being due at currentClientTime + 1 frame.)

Share this post


Link to post
Share on other sites

I suggested 100ms just as something that is less than 200ms. You could try lower than that. Ideally your time buffer is only as large as it needs to be to ensure that you always have some server data to render. In many games you don't really need to know or care what the server time is; when you get a new state, assume that is valid for exactly one frame from now and interpolate accordingly.

Even if you want to do server time sync, I don't see why you need to do it 5 times over 3 seconds. Once should suffice and it shouldn't even take a second.

I suspect trying to synchronise clocks and implement smooth rendering between past snapshots is overkill for the sort of game you're making. It's common for FPS games. You started out with the Valve and Quake 3 docs but you're (apparently) making some sort of Agar.io type game which clearly doesn't need that sort of approach. I would be willing to bet that typical games like that are just broadcasting out updates and interpolating towards the latest state, which is exactly what hplus0603 has recommended above. (So, ignore what I said about multiple snapshots, but ignore the server time, and treat updates received as being due at currentClientTime + 1 frame.)

 

Oh I am going back to the beginning now. But what makes the difference between these two approaches? Wouldn't using server time more accurate with positioning and collision detection? Even the io game has very bad latency sometimes. 

I do the syncing 5 times over 3 seconds because in this thread:

https://www.gamedev.net/topic/376680-time-synchronization-in-multiplayer/

someone said he does 10 syncing over an interval of several seconds. I can't tell how many times to sync the clock is best because it seems everyone here is more experienced than me.

Edited by caymanbruce

Share this post


Link to post
Share on other sites

The main difference between the 2 approaches is that the FPS approach is much more complex because it's trying much harder to keep everybody's perceived states equal.

In theory, respecting the server time-stamp on received state changes could make some movements appear smoother. Whether it's more accurate or not is a matter of opinion; the rendered value might more accurately represent where the object was at whatever the current 'rendertime' is, but the tradeoff is that you're rendering further in the past so it is a worse representation of where the object is now.

Compare that to the simpler approach where you start blending towards the new state immediately. The rendered positions may not be guaranteed to be exactly where the object was at some given point in the past, but they are moving towards the newly reported position right away. Rendered latency is actually lower in this situation because instead of waiting for a state to be 200ms or 100ms old (for example), you start factoring it in immediately.

Collision detection shouldn't matter because those decisions are handled by the server anyway (or at least they should be).

Regarding the time syncing: the anonymous poster in the other thread said "10 or so of these packets during your login process, over an interval of several seconds", by which he/she means all those packets are exchanged during those seconds - not one each time the period elapses. Note however that hplus0603 suggested doing timesyncs by measuring the round-trip time of regular game messages, which is a better approach if you need to keep clocks synced over time, but again, you can't just snap to the new value if you want smooth rendering.

Share this post


Link to post
Share on other sites

 

Typically, when you receive a new state from the server, you want to capture the current displayed position as the "checkpoint in time," (your "previous state") and then fill in the server state as the "future state to interpolate towards."

Typically, you'll set the server state to be the target a time T + 1 frame, where T is the time between server packets, giving you one extra frame of latency to allow for server jitter and such.

Very simplified:

State prevState;
State nextState;
State toRender;
onRender(Time t) {
  if (t < prevState.time) {
    toRender = prevState;
    warn("time too early");
  } else if (t > nextState.time) {
    toRender = nextState;
    warn("time too late");
  } else {
    toRender = lerp(prevState, nextState, (t - prevState.time)/(nextState.time - prevState.time));
  }
  renderState(toRender);
}

onReceive(State s) {
  if (s.time <= nextState.time) {
    warn("received bad time");
  } else {
    prevState = toRender;    // <--- IMPORTANT!
    nextState = s;
  }
}

 

 

The main difference between the 2 approaches is that the FPS approach is much more complex because it's trying much harder to keep everybody's perceived states equal.

In theory, respecting the server time-stamp on received state changes could make some movements appear smoother. Whether it's more accurate or not is a matter of opinion; the rendered value might more accurately represent where the object was at whatever the current 'rendertime' is, but the tradeoff is that you're rendering further in the past so it is a worse representation of where the object is now.

Compare that to the simpler approach where you start blending towards the new state immediately. The rendered positions may not be guaranteed to be exactly where the object was at some given point in the past, but they are moving towards the newly reported position right away. Rendered latency is actually lower in this situation because instead of waiting for a state to be 200ms or 100ms old (for example), you start factoring it in immediately.

Collision detection shouldn't matter because those decisions are handled by the server anyway (or at least they should be).

Regarding the time syncing: the anonymous poster in the other thread said "10 or so of these packets during your login process, over an interval of several seconds", by which he/she means all those packets are exchanged during those seconds - not one each time the period elapses. Note however that hplus0603 suggested doing timesyncs by measuring the round-trip time of regular game messages, which is a better approach if you need to keep clocks synced over time, but again, you can't just snap to the new value if you want smooth rendering.

 

Thanks so much. Since I have already implemented some kind of time syncing I decide to use the combination of these two approaches, or something in the middle. I follow the code structure of hplus0603's post above and still use a queue to store the incoming states from the server. Game render time is clientLocalTime + offset - 200. The offset comes from syncing time between the server and client for 5 times in 5 seconds. Now the movement of players are indeed very smooth with interpolation. However the positions are far from accurate. On Player A's screen maybe A is above B, but on Player B's screen A is underneath B. Also if I change 200 to 100 the render time won't fall in the range of the two states popped from the queue. This is so strange. I think I still have many bugs to fix but you guys really give me a lot of confidence.

Edited by caymanbruce

Share this post


Link to post
Share on other sites

On Player A's screen maybe A is above B, but on Player B's screen A is underneath B. - This is to be expected. If Player A and Player B start moving at the same time, they will see themselves move before news of the other player's motion reaches them. What each player sees is accurate, for them. If you can reduce latency, this effect will decrease.

Also if I change 200 to 100 the render time won't fall in the range of the two states popped from the queue - Then don't pop them from the queue. Look in the queue for the 2 relevant states either side of the time you want to render for and use them.

Share this post


Link to post
Share on other sites
The hard-coded "200" value probably needs to be actually determined by measuring round-trip time to the server.
Or start with 0, and when you find that you don't have the data yet, increase the value to the point where you do.

If you want players to seem "even" then you need to extrapolate. Extrapolation is like interpolation, except you go some time further out past the "end" sample.
A long time ago, I wrote a simple library called EPIC for doing such extrapolation, and a simple demo app (in C++, for Windows.)
You can check it out at http://www.mindcontrol.org/~hplus/epic/

Share this post


Link to post
Share on other sites

On Player A's screen maybe A is above B, but on Player B's screen A is underneath B. - This is to be expected. If Player A and Player B start moving at the same time, they will see themselves move before news of the other player's motion reaches them. What each player sees is accurate, for them. If you can reduce latency, this effect will decrease.

Also if I change 200 to 100 the render time won't fall in the range of the two states popped from the queue - Then don't pop them from the queue. Look in the queue for the 2 relevant states either side of the time you want to render for and use them.

 

This is tested on the same network in my room with two computers. If that latency makes a big difference in terms of player position I guess on the Internet it will only get worse.

Share this post


Link to post
Share on other sites

The hard-coded "200" value probably needs to be actually determined by measuring round-trip time to the server.
Or start with 0, and when you find that you don't have the data yet, increase the value to the point where you do.

If you want players to seem "even" then you need to extrapolate. Extrapolation is like interpolation, except you go some time further out past the "end" sample.
A long time ago, I wrote a simple library called EPIC for doing such extrapolation, and a simple demo app (in C++, for Windows.)
You can check it out at http://www.mindcontrol.org/~hplus/epic/

 

Sorry I am confused with the darken sentence in your post. I thought the hard-coded value is decided by how far behind I am from the server time. 

I choose 200ms because my queue is implemented like this:

  • It has 3 elements/states. 
  • It only pops a state out of the queue when it's full.
  • Network update rate is 20 times per second which gives 50ms interval.
  • When I pop the first state out of the queue I don't interpolate because there is no previous state to interpolate. I start interpolation when another state reaches the client and one more state pops out as the current state.

Now since the queue starts to fill states to the time I pop out the first current state to be used for interpolation, 200ms has passed. But I still want to start moving the player from the first state I received from the server, so I subtract 200ms from clientLocaltime + offset.

Edited by caymanbruce

Share this post


Link to post
Share on other sites

This is tested on the same network in my room with two computers. If that latency makes a big difference in terms of player position I guess on the Internet it will only get worse.

It will get worse, yes. But latency also depends on how quickly your software writes to the network and how quickly it reads from it. That code isn't shown above.

Share this post


Link to post
Share on other sites

I thought the hard-coded value is decided by how far behind I am from the server time.


You may be measuring something differently then. I don't know how far any player will be from the server. They may be 1 millisecond away. They may be 500 milliseconds away.
You are measuring something else here, probably "queue depth," which you have full control over, and should try to minimize as much as possible.
Once you have a new snapshot from the server, why would you use any older data other than as "come from" information?

Share this post


Link to post
Share on other sites

 

I thought the hard-coded value is decided by how far behind I am from the server time.


You may be measuring something differently then. I don't know how far any player will be from the server. They may be 1 millisecond away. They may be 500 milliseconds away.
You are measuring something else here, probably "queue depth," which you have full control over, and should try to minimize as much as possible.
Once you have a new snapshot from the server, why would you use any older data other than as "come from" information?

 

 

I think I understand now.  If I don't use a queue to store the states, I will only need two states for interpolation. One is the previous state, and the other is the future state or current state. Just need to swap the state buffer when a new state comes in. If I use a queue, I need to find a state in the queue that is just before the render time and a closet state that is behind the render time, this way the render time which is clientLocalTime + offset - 100 will be lying in the middle of the two states I find in the queue. The key value that matters most is the render time. Am I correct?

Edited by caymanbruce

Share this post


Link to post
Share on other sites

 

This is tested on the same network in my room with two computers. If that latency makes a big difference in terms of player position I guess on the Internet it will only get worse.

It will get worse, yes. But latency also depends on how quickly your software writes to the network and how quickly it reads from it. That code isn't shown above.

 

 

I think I know the reason. Before I was also running a physics simulation on the client. When the client receives updates from the server I excluded the player I am using on my client side and interpolated other players. That's why it will never look the same with the states position coming from the server. Now I have removed the simulation on the client and use only the states from the server (the server is totally authoritative now), the positions look just fine on all players' screens.  I may need to use other techniques such as client prediction/extrapolation for lag compensation though, otherwise on the Internet the latency will make it unplayable.

Edited by caymanbruce

Share this post


Link to post
Share on other sites
If I don't use a queue to store the states, I will only need two states for interpolation. One is the previous state, and the other is the future state or current state. Just need to swap the state buffer when a new state comes in. If I use a queue, I need to find a state in the queue that is just before the render time and a closet state that is behind the render time, this way the render time which is clientLocalTime + offset - 100 will be lying in the middle of the two states I find in the queue. The key value that matters most is the render time. Am I correct?

The last part is correct. But the question is not "whether you use a queue or not". Whether you use a queue or not depends on whether you want to use a queue or not, or whether you need a queue for what you want to do.

There are 2 strategies to choose from here:

1) Collect sufficient past states so that you can render at some arbitrary time in the past (e.g. 200ms), usually measured relative to a timer somewhat-synchronised with the server. A queue is a good way of storing these states, as you don't know exactly how many you're going to have when covering the necessary time period. It's possible to change the time buffer from 200ms to whatever you like, providing you do it smoothly, and that it always stays large enough that you have 2 states 'either side' of it, to interpolate between.

2) Keep 2 states, so that you can render between the last received position, and some position previous to that. Ideally that previous position is whatever you were rendering when the latest position came in, because that guarantees smooth rendering on the client. The render time here is not attempting to match any particular server time; it's just attempting to provide smooth rendering that closely follows what the server is sending.

What you can't do - but were doing, initially - is trying to use the 2nd strategy's data structure for the 1st strategy's algorithm, and that can never work because you couldn't guarantee that your stored positions spanned the time you wanted to render at.

Regarding client prediction, you will quickly realise that 'running a client simulation locally' and 'other techniques such as client prediction/extrapolation' are actually the same thing, with the same symptoms of showing different things on different screens. The best solution is to reduce latency so that the differences are minimised.

Edited by Kylotan

Share this post


Link to post
Share on other sites

 

If I don't use a queue to store the states, I will only need two states for interpolation. One is the previous state, and the other is the future state or current state. Just need to swap the state buffer when a new state comes in. If I use a queue, I need to find a state in the queue that is just before the render time and a closet state that is behind the render time, this way the render time which is clientLocalTime + offset - 100 will be lying in the middle of the two states I find in the queue. The key value that matters most is the render time. Am I correct?

The last part is correct. But the question is not "whether you use a queue or not". Whether you use a queue or not depends on whether you want to use a queue or not, or whether you need a queue for what you want to do.

There are 2 strategies to choose from here:

1) Collect sufficient past states so that you can render at some arbitrary time in the past (e.g. 200ms), usually measured relative to a timer somewhat-synchronised with the server. A queue is a good way of storing these states, as you don't know exactly how many you're going to have when covering the necessary time period. It's possible to change the time buffer from 200ms to whatever you like, providing you do it smoothly, and that it always stays large enough that you have 2 states 'either side' of it, to interpolate between.

2) Keep 2 states, so that you can render between the last received position, and some position previous to that. Ideally that previous position is whatever you were rendering when the latest position came in, because that guarantees smooth rendering on the client. The render time here is not attempting to match any particular server time; it's just attempting to provide smooth rendering that closely follows what the server is sending.

What you can't do - but were doing, initially - is trying to use the 2nd strategy's data structure for the 1st strategy's algorithm, and that can never work because you couldn't guarantee that your stored positions spanned the time you wanted to render at.

Regarding client prediction, you will quickly realise that 'running a client simulation locally' and 'other techniques such as client prediction/extrapolation' are actually the same thing, with the same symptoms of showing different things on different screens. The best solution is to reduce latency so that the differences are minimised.

 

 

Thanks for the detail explanation. I am using websocket I guess the client will always receive packets from server in order. And there would be no packet loss in transmission because it's TCP. So I think it might be enough to just use METHOD 2 -- just 2 states? 

Share this post


Link to post
Share on other sites
Which method you choose doesn't depend on packet loss or ordering; it depends on whether you want to always display a "correct" position (a position you know has happened in the past,) at the cost of additional latency, or if you want to display an "approximate" position (close to known correct possitions) with less latency.
Method 2 is fine, and will likely work well with websockets.
The main problem with TCP is the delivery jitter -- if there's any packet loss, there will be a significant delay before the TCP connection detects it and re-transmits, and then you'll suddenly get a whole bunch of packets all at once.

Share this post


Link to post
Share on other sites

Which method you choose doesn't depend on packet loss or ordering; it depends on whether you want to always display a "correct" position (a position you know has happened in the past,) at the cost of additional latency, or if you want to display an "approximate" position (close to known correct possitions) with less latency.Method 2 is fine, and will likely work well with websockets.The main problem with TCP is the delivery jitter -- if there's any packet loss, there will be a significant delay before the TCP connection detects it and re-transmits, and then you'll suddenly get a whole bunch of packets all at once.


Thanks I understand the drawback. But I need to get it working first. Now I am using method 2. Currently right after the time sync the player will move abruptly towards random positions which are far away from each other for about 2 seconds before it gets stable and renders at correct positions.
Suppose player receives input from the mouse, now even my mouse is not moving at the beginning the player still jumps for a while before it starts to interpolate. I am not sure if this is buggy or expected behavior of a networking environment.

Share this post


Link to post
Share on other sites

I am not sure if this is buggy or expected behavior of a networking environment.


That sounds buggy, if you're using interpolation. It could happen with extrapolation, but generally shouldn't unless the actual player movement is jumpy.

Think about it: If you use the previously-rendered position, and the next-received position, and interpolate linearly between the two, there's no way that a "large movement" should happen, unless you receive a very large position delta from the server.

To debug these kinds of things, I'd recommend recording each position/time received from the server to some kind of log file, and then perhaps also recording each position/time you get out of the interpolation code. If you then study these positions, you may be able to see patterns where you're not getting the result you want.
Once you have these log files, the next step is building a timeline display tool, that lets you "scrub" over time to render a frame based on the data, with a "ghost" for the last-received server position, as well as the player at the last-calculated interpolated position.

Visualizing data over time is crucial to a well-functioning distributed system. For straightforward code, you may be able to do it all in your head, but once multiple computers are involved, that each run on their own, getting concrete things you can study in freeze frame (be it logs, or timeline displays) is highly valuable!

Share this post


Link to post
Share on other sites

In addition to the above, a very simple graphical diagnostic would be to render a translucent circle onscreen at the positions of both states, and draw a line between them. If those circles aren't where you expect, the states aren't right. And if your player isn't somewhere along the line, your interpolation isn't right.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this