How to implement accurate frame-rate-independent physics?

Question

So, I have been working on a project for a while now and recently stumbled across a problem:

The common approach to frame-rate independent physics is to either use a fixed update interval (ie. Unity) or just multiply each physical change with delta. So it would look something like this:

update(int delta)
{
   ...
   positionX += velocityX * delta;
   ...
} 

And when acceleration is added, the velocity change is treated similar:

update(int delta)
{
   ...
   velocityX += accelerationX * delta;
   ...
}

This works fine for most use cases. In fact so fine, that I haven't noticed anything was off for months. But there is a problem with this logic, namely that the position will be slightly off for entirely different frame-rates. This problem is negligible when working with small frame-rate changes, but is entirely noticeable once the delta time is changing by bigger amounts. Say, FPS rate from 30 to 600. Now, in a normal game the FPS are just locked and even if the positions are off for a few frames by like 5% it doesn't matter because one doesn't notice it. But I manually multiply the delta with a factor to accomplish a certain effect, and the error is somewhat noticeable and game breaking.

A small example to clarify what I mean:

There is a game object with start position posX = 0 and a x-Velocity of 10 and an horizontal acceleration of 0.1.

After two frames, for 50FPS this would lead to (with an average delta)

velocityX += acceleration * delta; 
posX += velocityX * delta;

velocityX += 0.1 * 20; //velocityX = 12
posX += 12 * 20 //posX = 240

//next frame

velocityX += 0.1 * 20; //velocityX = 14
posX += 14 * 20 //posX = 520 (240 + 280)

After one frame with 25FPS, which equals the same time interval like two frames with 50FPS, this would get us:

velocityX += 0.1 * 40; //velocityX = 14
posX += 14 * 40; //posX = 560

So two situations with the same time interval elapsed we get different results (520 for 50FPS and 560 for 25FPS).

Now, the problem obviously is that there is one extra frame (in this example, it could be any number of frames but the results still differ for the same interval) in which the acceleration is applied and therefore you get further with less FPS.

Stabilizing the delta is not an option as I need different deltas for said effect, so I need to physics to be entirely independent there. Has anyone ever come across a similar situation and are there any solutions for it?

Answer 1

You can fix this problem by averaging the initial and final velocity:

velocityOld = velocityX
velocityX += acceleration * delta; 
posX += (velocityX + velocityOld)/2 * delta;

In this particular example it will completely remove dependancy on delta. In general this solution will reduce the effect of delta.

Answer 2

Stabilizing the delta is not an option as I need different deltas for said effect, so I need to physics to be entirely independent there.

Stabilising the delta time is your only option. If we could change the time step of a numerical integration and were guaranteed to get the same results, we could exploit this to get really accurate calculations with barely any computational effort. Unfortunately, there are no free lunches today. If you change the accuracy of your simulation, the result could change.

If you're okay with the results changing slightly, you could opt for a different integration method. Verlet integration performs a lot better than Euler in your example: the position after 40 ms will be estimated at 480 with Δt = 40 ms and at 480 with Δt = 20 ms, but they too will vary if you introduce a non-constant acceleration.

I am not completely sure what the effect is that you want to pursue by changing the time step, but if you're looking to create a slow-motion effect that only affects playback, you need to decouple the simulation from the framerate. An example: your simulation normally works with a Δt of 10 ms. Every ten milliseconds, you advance the physics by one tick. The game runs at 25 fps; you redraw the screen every fourth tick. If you want to slow down to half the normal speed, you advance the physics by one tick every 20 milliseconds instead, but you keep Δt at 10 ms (because that's the time that has elapsed in-game). To keep a constant framerate, you now have to redraw the screen every two ticks.

Regardless of playback rate, the results will be the same, but this method has other disadvantages. You can't draw a new frame until at least Δt has elapsed in-game and because that value is fixed, there is a limit to how slow you can go without the framerate dropping. You can push this lower limit by selecting a smaller value for Δt, but you'll be wasting resources for accuracy you don't need at normal speed. Eventually, your game might not be able to run at normal speed at all, if one tick is still being calculated when the next one is scheduled to begin.

Answer 3

Welcome to the wonderful world of integral calculus.

Speed = distance / time
Acceleration = distance / (time * time)

So to get the correct answer you need to calculate the integral of your speed, and then the integral of your location. The math can be quite daunting, and in most cases it will be overkill and just make things more complicated. You can use this to calculate the positions, but detecting collisions means calculating the time an object reaches a certain position and for two moving objects the arrival times of their paths. Well, it's even more calculus to calculate, and for very little gain (if any at all since Float might not be accurate enough for it).

This is why you normally use fixed timestep for the physics calculations, even if you have a variable framerate, simply keep track of time elapsed and then run your physics calculation in a fixed timestep:

for (timeElapsed += delta; timeElapsed > timeStep; timeElapsed -= timeStep) {
  velocityX += acceleration * timeStep; 
  posX += velocityX * timeStep;
}

This can be put in your update loop to keep the physics running at a fixed timestep regardless of what timestep your update loop runs at, timeElapsed's value would have to be kept over time of course. Whenever you want to use fixed timesteps there are some things to pay in mind, Shawn Hargraeves has a very interesting blog post about this, it mentions XNA specifics but the concepts apply to any fixed timesteps.

Answer 4

Calculating physics with a delta is generally not a good idea, not only because of the reasons you gave, but also because you get slightly different results every time you run the app even with similar frame rates, which already might be game breaking. Or, if the frame rate drops too low, fast moving objects can completely clip through each other. (Assuming you aren't using continuous collision detection.) So the usual workaround (or, mine at least) is to have two different "tick events" for your world: A fixed tick and a frame tick. The fixed tick is where you do all the physics stuff and everything that needs to always work exactly the same. That function just advances the simulation state by a fixed amount, every time you call it. You just measure how much time passed and call the function the appropriate amount of times. Of course you should remember how much time passed over multiple frames, so that you don't "lose" time. In the frame tick function/event you do things that have to be time perfect, but where it doesn't matter if the results are reproducible, like the camera. (If you'd move the camera in the fixed tick function/event, you'd be getting slight but noticeable jittering, because it's position wouldn't always be perfectly aligned with how much time actually passed.)

One problem of this is that if you are so CPU-bound that you can't run enough fixed-tick iterations, the game is just gonna completely lag itself out, because every frame takes longer and longer and you have to run more and more iterations each frame. But you can't really get around that, you just have to perform a certain number of simulation steps to get accurate results.