Fixing the iterative damping interpolation in video games | Hacker News Reader

Fixing the iterative damping interpolation in video games

blog.pkh.me

127 pointsux53 comments

Unfortunately you cannot extend this approach much beyond this simple example if you are writing a physics simulation. There is no known closed form solution, for example, for the famous three body problem, so a some sort of numerical integration is absolutely required. At that point, you should just decouple the numerical integration timestep from the monitor refresh rate, or mandate a refresh rate that will be acceptable to the player.

You can do that, but it has serious drawbacks. You can:

* Run physics at such a high rate that sampling it at 30 or 60 or 144 or 260 hertz is fine, like running physics at 1kHz. This is appropriate for certain kinds of very realistic physics sim style games, but usually undesirable due to performance.

* Run physics at some fixed, sane rate (somewhere between 20 and 100 Hz probably), and then do rendering separately, interpolating between positions for refresh rates higher than the physics tick rate. This can be hard to make feel good on refresh rates which aren't clean multiples or divisors of the tick rate, but ensures that physics behaves identically independent of frame rate.

* Couple rendering and physics and run at a fixed frame rate (60 FPS). This will work okay for many players but a whole lot of people will be angry at you that your game is choppy on their fancy high refresh monitor, and if you don't change monitor mode to change the monitor's refresh rate, a 144Hz screen will sometimes refresh twice and sometimes thrice per game frame, meaning nothing will ever seem smooth even by 60 FPS standards.

* Couple physics and frame rate but allow the delta time to vary (maybe running physics 2 or 3 times per frame if the frame rate is really low). I'd say this produces the best results for any given refresh rate, and it's relatively simple to implement, but it causes physics to behave slightly differently with different frame rates, and it's prone to bugs like the one discussed in this article.

It's not an easy decision, there is no good rule of thumb. I tend to prefer the last option I listed for my games, but I'm aware that it has drawbacks. But "just decouple physics from rendering" is certainly not the straightforward rule of thumb you seem to suggest it is. (EDIT since this post seemed more negative than I meant: running at a fixed time step is a good solution and very appropriate for many games, I'm not saying your suggestion is bad)

In godot (compile main daily) I am running 120 tick rate but have found some interesting optimizations happen there and above (240) and am seriously temped to just make 240 my default (but I need to do more server load tests as I’m planning to scale)

240Hz has issues too though, it means that there's on average 1.66 physics ticks per screen refresh on a 144Hz screen. In practice that means that an object moving at, say, 0.1 meter per tick will have moved 0.1 meters in some frames and 0.2 meters in other frames, which leads to choppy animation. That's why I mentioned tick rates in the kilohertz; sometimes having 10 ticks between frames and sometimes 11 ticks isn't a big deal, but sometimes having 2 and sometimes 1 is noticeable (and obviously if some frames have 1 tick and some have 0 ticks between them, that's a disaster (unless you do interpolation which is a different can of worms)).

Now running physics at 240Hz or even 120Hz might still be the right choice for your game, especially when taking into account human factors and time constraints, it's just not a panacea

For 144 and 240 Hz, the LCM (least common multiple) would be 720 Hz. At 144 Hz that's 5 ticks per frame, and at 240 Hz it's 3 per frame.

https://www.calculatorsoup.com/calculators/math/lcm.php

> will have moved 0.1 meters in some frames and 0.2 meters in other frames

Not if you interpolate based on previous position. This means you accept up to 16ms display latency, but the trade off is smooth motion.

That's why I wrote this part:

> unless you do interpolation which is a different can of worms

Thanks for bringing up the intricacies involved. I shouldn’t have used the word “just” as it implies that the solution is easy.

> You can:

> * Run physics at such a high rate that sampling it at 30 or 60 or 144 or 260 hertz is fine, like running physics at 1kHz.

> (...)

> Couple rendering and physics and run at a fixed frame rate (60 FPS)

Both are sensible, but you can do better:

First you can detect the monitor framerate and do a benchmark to get which framerate the computer can comfortably run the game (at not too much CPU utilization), and take the minimum from those two values. That's a good way to gauge a baseline. The only problem is that the simulation will not be deterministic across two different computers (but there are many other sources of nondeterminism, and many games are okay with that)

Then another further issue is that if you run physics at exactly the same frame rate as the monitor, you might sometimes run two physics steps during a frame, or no physics step during a given frame, which causes staggering. To solve that, if your baseline ends up being your framerate, you then run the simulation at a few Hz higher than that (Bevy for example defaults to 64Hz [0], imagining that 60Hz monitors are still common)

[0] https://docs.rs/bevy/0.13.2/bevy/time/struct.Fixed.html

> The default timestep() is 64 hertz, or 15625 microseconds. This value was chosen because using 60 hertz has the potential for a pathological interaction with the monitor refresh rate where the game alternates between running two fixed timesteps and zero fixed timesteps per frame (for example when running two fixed timesteps takes longer than a frame). Additionally, the value is a power of two which losslessly converts into f32 and f64.

Wait but when you run physics at 64Hz for a 60Hz refresh rate, you'll still see some refreshes with 1 step and some with 2, which means you need some interpolation scheme if you wanna avoid a stuttering mess still. You should have some form of synchronisation which ensures that exactly one physics step happens between each frame that's displayed to the user

You always need such interpolation nonetheless, because the physics timestep is fixed but your FPS will not always be 60 (that is, you may have slowdowns that lower your FPS temporarily)

Running two physics steps in the same frame isn't a problem (besides consuming CPU pointlessly), the problem is when you run no physics step between one frame and another

Game dev here. Hardly any serious game developer uses lerp like that. I prefer a quadratic friction when I write custom friction, ie: a constant force away from velocity, and simply ensure it doesn't go past the zero point. More controllable. Box2Ds friction uses something like v = v * 1/(1+damping*delta_time), which is a good method as well.

Keep in mind it's best practice to run your game logic at a constant update rate and render an interpolated state between the current and previous game logic frame, meaning that if your game logic is frame rate dependent, you can still run it smoothly on any monitor.

> run your game logic at a constant update rate and render an interpolated state between the current and previous game logic frame

But if graphics frame rate is higher you won’t be able to interpolate until the next logic frame is ready, - wouldn’t that increase latency?

It will keep latency constant, at right the amount you tested the game with.

Technically, 'yes', but with huge caveats. You will still show player movement at the same 'latency', just _less than a full simulation frames worth_.

The benefits _far_ outweigh the costs of the other options. Games look _horrible_ if you render the physics at a different frame rate than the rest of the game. Like, horridly bad.

Constant update rate is a must, and can even be tweaked to minimize input latency if you are using a custom engine.

Using two frames to interpolate at render time is adding one frame of latency.

It is possible to do it on a single frame, extrapolating instead of interpolating, but you have to use a simple but uncommon trick to make it robust.

The latency gain is not a full frame but some sizeable fraction of a frame, I think it is worth it for some games.

What is the simple but uncommon trick?

Some sort of Kalman-esque algo?

https://en.wikipedia.org/wiki/Kalman_filter

> I think it is worth it for some games.

What types of games are you thinking?

Extrapolation isnt worth the chance of misprediction if it's a player movement based game.

The 'input latency' introduced by interpolating between frames is far different than typical 'input latency'. It's less than a single frame, and the game still renders movement at the same frame, just less movement. Most 'input latency' tests only test for _any_ movement, so those kinds of tests would detect 0 difference between 'interpolation', 'extrapolation' and 'render the exact game state'.

I'm a fast paced gamer, and I make fast paced games, I've never once 'felt' the input latency from interpolating the players position between simulation frames.

Alternatively, you could fix your timestep, decoupling your physics from your display refresh entirely.

https://gafferongames.com/post/fix_your_timestep/

Which is hard to do well and has its own set of drawbacks.

Hard disagree. It's not hard to do well. The draw back is less than 1 frame of input latency. If your game uses a physics engine or is networked you are forced to use a constant update rate, ie: 30 or 60hz. The draw backs to linking the physics update rate to the monitor refresh rate are enormous and untenable in a networked game.

I don't personally care much about a frame or two of latency (some do though, and for some genres that'll be a big deal); however I care about animation smoothness. If the monitor refresh rate is 144Hz and physics tick rate is 60Hz, you'll need some form of interpolation, which is hard to do well especially since the refresh rate isn't a multiple of tick rate.

> you'll need some form of interpolation, which is hard to do well

Due to non-constant accelerations?

Some games use a 120hz physics sim even if they're capped to 60hz display refresh.

An 'animation' tick can be (and should be) disconnected from the physics 'tick'. Physics/game logic 'ticks' should use a constant time so the simulation is more predictable and stable, a 'animation tick' can be exactly what the monitor refresh rate is and thus doesnt need 'interpolation between ticks'.

The position of objects is determined by the physics system though.

It's important to be precise. The position of a small subset of the "objects" are determined by the physics engine. You might have a character with 100s of thousands of vertices, but only a single capsule is in the physics engine. The movement of the characters fingers is not determined by the physics system.

This would still be needed for UI animations and lerpings that aren’t tied to the actual gameplay

All the frame rates in this post appears to refer to physics frame rates, but Godot makes the distinction between physics and display frame rates, and have separate callbacks for each:

https://docs.godotengine.org/en/stable/tutorials/best_practi...

Because physics frame rate is fixed (configured under project settings), I suspect developers would be able to get away with using the common lerp() formula and not having to worry about varying (display) frame rates.

While this is true for simpler games, the author mentions the possibility where we aren't able to hit the target of 60 FPS or whatever, and we get physics spikes on slower computers.

I think the real problem with the OP's straw-proposal interpolation method is that it's stateless and doesn't need to be. I would instead record the start position, then interpolate along a function F(t) to the end position. F(0)=0, F(1)=1, F'(0)=F'(1)=0 just so the ends aren't jerky. The curve can even overshoot 1 to give the animation some bounce.

I'm sure somewhere on the Internet somebody's written down some good choices of curve; hopefully someone else knows what to search for.

(I don't know what to do if another change interrupts the first but it's a rare case and can probably be handled imperfectly.)

> (I don't know what to do if another change interrupts the first but it's a rare case and can probably be handled imperfectly.)

This kind of lerp trick, while imperfect, is useful in exactly these sort of situations. It allows you to smooth movement even if the target point is changing at at arbitrary intervals (note too that it works okay generalised to multiple dimensions). And the statelessness is very useful too - I don't think the feel is great and it's not very controllable, but being able to just add some damping to the movement without having to track animation states or anything like that is super useful.

> I don't know what to do if another change interrupts the first but it's a rare case and can probably be handled imperfectly.

Extract the position (p0) and velocity (v0) vectors at the moment of interruption, and derive a new function F(t) that meets the constraints {F(0)=p0, F'(0)=v0, F(1)=p1, F'(1)=0}.

Don't most modern video games run a physics thread at fixed rate in addition to the rendering one?

I remember Quake 3 still having that issue, but that was in '99...

Wouldn't you just want to sample a normalized curve and apply that? What is the use case where you want to use this iterative call, care about frame accuracy, but can't afford curve data?

With the explicit curve you have more control in the exact damping, too.

Exponential decay has the special property that it can be calculated from the current state with no additional data needed. With other kinds of interpolation curves, you need to additionally store the time the animation started.

Sure, but when is that relevant?

When the end state changes over time, or there is no defined duration.

Stated dabbling with game dev very recently so I'm curious about this!

Couldn't we get the delta, or for some animations use modulo arithmetic? Maybe mix in some gradient noise into the animation to make it seem organic to break the looping.

It would be illuminating if you showed an example of what you mean by using modulo arithmetic, or getting the delta; otherwise we can't comment on your idea.

I was bit confused how a formula that depends on a constant frame rate works with variable refresh rate. Then the author commented that you don't need to calculate the quantity that depends on frame rate in code. https://news.ycombinator.com/item?id=40401211

I'm really lost, but alas have ~0 experience with 3D about 15 years into a career.

Ignoring variable frame rate: 1. Doesn't the frame rate depend on the display hardware?

2. Can you know the frame rate at runtime?

Variable frame rate: 3. What quantity do you use for frame rate for variable frame rates?

1. depends if you're in the physics main loop or not; in Godot for example the physics main loop is based on the project configuration, not correlated with the display (I could have expanded on that in the article)

2. You can know the targeted frame rate, you can also infer it by averaging the delta times at runtime (not reliable but maybe more accurate on a slow machine?)

3. In my graph, I did pick random delta between 15 and 120 fps IIRC; the point was to simulate what could roughly happen with random lag spikes

Proposed solution is too expensive with ln and exp calls.

Only the exp call happens in the processing loop. The ln is in the conversion function, it's not supposed to land in the code.

Nice, but ...

> So there we have it, the perfect formula, frame rate agnostic ,

... worth noting what happens on a frame time spike.

A frame time spike is covered by the overshooting point: it will basically land further down the curve, which means a point converging toward the B target.

In monoticity guaranteed even if the next frame is short?

As the delta time converges to 0, the lerp coefficient is going to converge to 0 as well, meaning it won't move. Said differently, if time stops the interpolation as well. You may enter into the realm of floating point accuracy issues at some point with low values, but I'm curious of what specific scenario you have in mind here?

OK, so that's confirmed Yes.

Thanks.

Now write the formula in terms of expm1 for numerical stability, and express the constant in terms of “half life” measured in seconds to make it intuitive instead of magical.

Seriously guys, don't write:

  a = lerp(a, B, 1.0 - exp(-delta * RATE2))

Write:

  a = lerp(a, B, -expm1(-delta * RATE2))

This is precisely the situation where you really want to use expm1: https://www.johndcook.com/blog/cpp_expm1/

And (as pointed in the above) if you're worried about the slowness of it, just Taylor expand it to x+x²/2.

Finally, unless division is too costly, do:

  a = lerp(a, B, -expm1(delta / -T))

Where T is the “time constant” (which you can intuitively express in time units, like seconds): https://en.wikipedia.org/wiki/Exponential_smoothing#Time_con...

It's not the half-life (sorry) but it's still a lot more intuitive as a parameter.

That's some very good recommendations you made here. I'm adding all 3 at the end, thank you.

Reply on news.ycombinator.com