Guys, I'm making a very simple first person shooter as my first 3D game. :cool:

As I started thinking about the multiplayer, I came to the conclusion that capping the frame rate is a really mediocre idea when dealing with lots of PCs.

That's why I decided to make a proper game loop where the game is updated at a fixed timestep but the rendering is done whenever the PC can( variable timestep, they call it).

The main idea is this:

double previous = getCurrentTime();
double lag = 0.0;
while (true)
{
  double current = getCurrentTime();
  double elapsed = current - previous;
  previous = current;
  lag += elapsed;

  processInput();

  while (lag >= MS_PER_UPDATE)
  {
    update();
    lag -= MS_PER_UPDATE;
  }
  render(lag / MS_PER_UPDATE);  
}

But there is a problem.

[attachment=33238:game-loop-timeline.png]

If I lock the game-update rate at 20 fps, then I render 3 to 4 times more than I update the game( talking about my laptop ). And imagine that I render just half a millisecond after an update and there is still time until the next update. Then I need to say: interpolatePosition( lastPos, nextPos, 10%( or 15 or 20%, it doesn't matter ) )

How to use the the next position in the function when I don't know what the next position is. I can predict the next position based on the current movement, but the user will always press a button and do something and then the extrapolation will be wrong, which is what will happen most of the time.

What to do then??

I'm talking just about position here, I won't worry about rotation because in order to interpolate quaternions I need to learn the maths, but I've left it for later.

This is really beyond me and I was wondering if I should leave it for some later time, but I wanted to figure out something really simple that will do for now, because there aren't easy problems with my game anymore, and I can't just leave everything for later.

Can you suggest something really easy to grasp? The easiest way, if there is one at all. <_<

( picture is from this article: http://gameprogrammingpatterns.com/game-loop.html )

"I can predict the next position based on the current movement" - yes, this is fine.

"but the user can press a button and do something and then the extrapolation will be wrong" - not really.

Firstly, let's assume you're right - it would be by such a tiny amount that it doesn't matter. Compared to the error of predicting the position of a remote networked player, this is infinitesimally small.

Secondly, the button press (or mouse movement, or any input event) isn't going to get handled until after the updates are done, right? The updates work on the current input state, as of whenever it was last updated. So there won't be any error where the rendering is in the wrong place - the 'error' is that the engine takes a little while to realise that the player has pressed the key. This input latency is something people do try and reduce but it's always non-zero.

First, thanks for the really quick answer.

And you are right. I haven't thought about that, but the only problem really is input latency, because sooner or later the next update will come and the position will be fixed to the proper one, so it's kind of temporary.

Compared to the error of predicting the position of a remote networked player, this is infinitesimally small.

So you say that the only thing I should do is to somehow extrapolate the current position based on the two previous positions and not worry about prediction errors?

Last paragraph on this page: http://gafferongames.com/game-physics/fix-your-timestep/ says:

"We can use this remainder value to get a blending factor between the previous and current physics state simply by dividing by dt. This gives an alpha value in the range [0,1] which is used to perform a linear interpolation between the two physics states to get the current state to render."

Ok I get the position from the last two game updates in order to get the position for the current render(). Isn't this called extrapolation, not interpolation?

In the Gaffer On Games case, it appears that he is indeed interpolating between the current state and the previous state, rather than extrapolating. This imposes additional latency. However, since he runs physics steps at a very high rate (100 times a second in that example) the latency is no more than 1ms.

Revising my earlier statement, I can imagine a hypothetical situation where an extrapolation becomes significantly wrong IF an input has a very significant effect on movement and IF updates are relatively infrequent compared to renders, and interpolation would fix that. In practice, with an update that is done frequently enough, it's going to make next to no difference. (Mathematically speaking, as your update frequency approaches infinity, the difference between interpolation and extrapolation approaches zero.)

In the Gaffer On Games case, it appears that he is indeed interpolating between the current state and the previous state, rather than extrapolating. This imposes additional latency. However, since he runs physics steps at a very high rate (100 times a second in that example) the latency is no more than 1ms.

Can you explain this a little bit more?

Ok, imagine you have a ball on one dimensional screen and you update the game at a fixed rate of 5 updates per second, forget about inputs.

Start of game: time since app start = 0.0 sec, the ball's position is at 0.0f;

1st game update: time = 0.2 sec( t0 ), the ball's position is at 3.0f;( x0 )

2nd game update: time = 0.4 sec( t1 ), the ball's position is at 6.0f( x1 );

Now I have a render() function which is executed at time == 0.5f;

How to find the ball's position at this time:

The only solution I can come up with: ( 3 steps )

1.Find the ball's velocity by doing this: ( x1 - x0 ) / ( t1 - t0 ) which is 3.0f/0.2f = 15.0f ( ball travels 15.0f per second )

2.Then find the elapsed time since the last update: 0.5f - 0.4f = 0.1f.

3.Now that we have the previous position( which is 6.0f ) and the speed ( 15.0f per sec ), we just multiply the speed with the elapsed time since the last update and add it to the previous position like this: 15.0f*0.1f + 6.0f = 1.5f + 6.0f = 7.5f

And we got the answer.

Is this the right way?

And how do you call this - interpolation or extrapolation?

"1.Find the ball's velocity" - normally you already have the velocity. Otherwise, how did you know how fast to move it in the last update?

"we just multiply the speed with the elapsed time since the last update and add it to the previous position"

That's fine, although you only want to add it to the position for rendering purposes, not as an extra update step. I'd suggest approaching this the other way around - the engine should be able to ask an object, "where are you now?" and the object can look at the current time, the last time it updated, and its current position and velocity, and return the interpolated value. (Or extrapolated - your choice.)

how do you call this - interpolation or extrapolation?" Since you are finding a value outside of your existing data points, that is extrapolation. When you look at a value inside or between existing data points, that is interpolation.

Guys, I'm making a very simple first person shooter as my first 3D game. :cool:

As I started thinking about the multiplayer, I came to the conclusion that capping the frame rate is a really mediocre idea when dealing with lots of PCs.

That's why I decided to make a proper game loop where the game is updated at a fixed timestep but the rendering is done whenever the PC can( variable timestep, they call it).

The main idea is this:

double previous = getCurrentTime();
double lag = 0.0;
while (true)
{
  double current = getCurrentTime();
  double elapsed = current - previous;
  previous = current;
  lag += elapsed;

  processInput();

  while (lag >= MS_PER_UPDATE)
  {
    update();
    lag -= MS_PER_UPDATE;
  }
  render(lag / MS_PER_UPDATE);  
}

But there is a problem.

game-loop-timeline.png

If I lock the game-update rate at 20 fps, then I render 3 to 4 times more than I update the game( talking about my laptop ). And imagine that I render just half a millisecond after an update and there is still time until the next update. Then I need to say: interpolatePosition( lastPos, nextPos, 10%( or 15 or 20%, it doesn't matter ) )

How to use the the next position in the function when I don't know what the next position is. I can predict the next position based on the current movement, but the user will always press a button and do something and then the extrapolation will be wrong, which is what will happen most of the time.

What to do then??

I'm talking just about position here, I won't worry about rotation because in order to interpolate quaternions I need to learn the maths, but I've left it for later.

This is really beyond me and I was wondering if I should leave it for some later time, but I wanted to figure out something really simple that will do for now, because there aren't easy problems with my game anymore, and I can't just leave everything for later.

Can you suggest something really easy to grasp? The easiest way, if there is one at all. <_<

( picture is from this article: http://gameprogrammingpatterns.com/game-loop.html )

Killzone Shadow Fall and Killzone 3 I think both uses an interpolation method. What the player see's is actually a very tiny delay of what is actually going on in the game.

Because you know what your previous state of motion was, and your current state of mation is... if you render as fast as possible then you'd just interpolate between those states while you wait on the next logical update.

Kylotan, I finally did it. Big thanks for the help, man. ^_^

That's fine, although you only want to add it to the position for rendering purposes, not as an extra update step

Of course. I just pass the extrapolation ratio in the render() function and I make a new variable so I don't have to update the actual variable that holds the position, this way I don't do an extra update step. I want to have the exact amount of floating point multiplications for every PC in order to preserve simulation predictability.

Tangletail, I do extrapolation, not interpolation. This way I have no delay at all. But extrapolation is not perfect, too, because I get small prediction errors when I suddenly stop or change direction.

I'm wondering which one is better - to interpolate and have a small delay, or to extrapolate and have prediction errors?

Do you know which one is the preferred way, the way most games do?

I want to have the exact amount of floating point multiplications for every PC in order to preserve simulation predictability

You shouldn't rely on this. You certainly shouldn't expect it to keep things consistent across different PCs.

You shouldn't rely on this. You certainly shouldn't expect it to keep things consistent across different PCs.

Maybe there still will be differences, but I don't see another way.