How to Interpolate between two game states?

Question

What is the best pattern to create a system that all the objects positions to be interpolated between two update states?

The update will always run at the same frequency, but I want to be able to render at any FPS. So the rendering will be as smooth as possible no matter the frames per second, whether its lower, or higher than the update frequency.

I would want to update 1 frame into the future interpolate from the current frame to the future frame. This answer has a link that talks about doing this:

Semi-fixed or Fully-fixed timestep?

Edit: How could I also use the last and current speed in the interpolation? For example with just linear interpolation, it will move at the same speed between positions. I need a way to have it interpolate the position between the two points, but take into consideration the speed at each points for the interpolation. It would be helpful for low rate simulations like particle effects.

Answer 1

You want to separate update (logic tick) and draw (render tick) rates.

Your updates will produce the position of all objects in the world to be drawn.

I will cover two different possibilities here, the one you requested, extrapolation, and also another method, interpolation.

1.

Extrapolation is where we will compute the (predicted) position of the object at the next frame, and then interpolate between the current objects position, and the position that the object will be at next frame.

To do this, each object to be drawn must have an associated velocity and position. To find the position that the object will be at next frame, we simply add velocity * draw_timestep to the object's current position, to find the next frame's predicted position. draw_timestep is the amount of time that has passed since the previous render tick (aka the previous draw call).

If you leave it at this, you'll find that objects "flicker" when their predicted position didn't match the actual position at the next frame. To remove flickering, you can store the predicted position, and lerp between the previously predicted position and the new predicted position at each draw step, using the elapsed time since the previous update tick as the lerp factor. This will still result in poor behavior when fast moving objects suddenly change location, and you might want to handle that special case. Everything said in this paragraph are the reasons why you don't want to use extrapolation.

2.

Interpolation is where we store the state of the last two updates, and interpolate between them based on the current amount of time that has passed since the update before last. In this setup, each object must have an associated position and previous_position. In this case, our drawing will represent at worst one update tick behind the current gamestate, and at best, at the exact same state as the the current update tick.

---

In my opinion, you probably want interpolation as I've described it, as it's the easier of the two to implement, and drawing a tiny fraction of a second (e.g. 1/60 second) behind your current updated state is fine.

---

Edit:

In case the above isn't enough to allow you to perform an implementation, here is an example of how to do the interpolation method I've described. I won't cover extrapolation, because I can't think of any real-world scenario in which you should prefer it.

When you create a drawable object, it will store the properties needed to be drawn (i.e., the state information needed to draw it).

For this example, we will store position and rotation. You may also want to store other properties like color or texture coordinate position (i.e. if a texture scrolls).

To prevent data from being modified while the render thread is drawing it, (i.e. one object's location is changed while the render thread draws, but all others have not been updated yet), we need to implement some type of double buffering.

An object stores two copies of it's previous_state. I will put them in an array and refer to them as previous_state[0] and previous_state[1]. It similarly needs two copies of it's current_state.

To keep track of which copy of the double buffer is used we store a variable state_index, which is available to both the update and draw thread.

The update thread first computes all properties of an object using it's own data (any data structures you want). Then, it copies current_state[state_index] to previous_state[state_index], and copies the new data relevant for drawing, position and rotation into current_state[state_index]. Then it does state_index = 1 - state_index, to flip the currently used copy of the double buffer.

Everything in the above paragraph has to be done with a lock taken out on current_state. The update and draw threads both take out this lock. The lock is only taken out for the duration of the copying of state information, which is fast.

In the render thread, you then do a linear interpolation on position and rotation like so:

current_position = Lerp(previous_state[state_index].position, current_state[state_index].position, elapsed/update_tick_length)

Where elapsed is the amount of time that has passed in the render thread, since the last update tick, and update_tick_length is the amount of time that your fixed update rate takes per tick (e.g. at 20FPS updates, update_tick_length = 0.05).

If you don't know what the Lerp function above is, then checkout wikipedia's article on the subject: Linear Interpolation. However, if you dont know what lerping is, then you probably aren't ready to implement decoupled update/drawing with interpolated drawing.

Answer 2

This problem requires you to think about your definitions of start and finish a little differently. Beginning programmers often think of change in position per frame and that is a fine way to go in the beginning. For the sake of my response, let's consider a one dimensional answer.

Let's say you have a monkey at position x. Now you also have a "addX" to which you add to the monkey's position per frame based on the keyboard or some other control. This will work as long as you have a guaranteed frame rate. Let's say that your x is 100 and your addX is 10. After 10 frames, your x += addX should accumulate to 200.

Now, instead of addX, when you have a variable frame rate, you should think in terms of velocity and acceleration. I will walk you through all of this arithmetic but is is super simple. What we want to know is how far you want to travel per millisecond (1/1000th of a second)

If you are shooting for 30 FPS, then your velX should be 1/3rd of a second (10 frames from the last example at 30 FPS) and you know that you want to travel 100 'x' in that time so set your velX to 100 distance / 10 FPS or 10 distance per frame. In milliseconds, that works out to 1 distance x per 3.3 milliseconds or 0.3 'x' per millisecond.

Now, everytime you update, all you need to do is figure out the time elapsed. Whether 33 ms have passed (1/30th of a second) or whatever, you just multiply the distance 0.3 by the number of milliseconds passed. This means that you need a timer that gives you ms (millisecond) accuracy but most timers give you this. Simply do something like this:

var beginTime = getTimeInMillisecond()

... later ...

var time = getTimeInMillisecond()

var elapsedTime = time-beginTime

beginTime = time

... now use this elapsedTime to calculate all of your distances.