Fix Your Timestep!
NEWSFLASH: Did you click on a link from a forum? Some crazy guy spouting nonsense about integration timesteps? Read the full story here!
Introduction
Hello, I’m Glenn Fiedler and welcome to the second article in my series on Game Physics.
In the previous article we discussed how to implement an RK4 integrator to integrate the equations of motion.
Now we want to display our physics simulation on the screen. To do this, we step our physics simulation forward by small amounts of time, and after each step we draw the simulation on the screen.
This may sound easy, but there are many pitfalls for new programmers when time-stepping a simulation.
So read on for all the details on how to do it right!
Stepping forward in time
First thing we need to do is choose the timestep to advance the simulation ahead each time we draw the object. The easiest way to do this is to step your physics ahead by a fixed amount of time each step.
For example you could step ahead 1/100th of a second each frame:
float t = 0.0f;
float dt = 0.01f;
while (!quit)
{
integrate(state, t, dt);
render(state);
t += dt;
}
The problem is that you can never really be sure exactly what framerate the simulation is running at. Slower computers may only be able to render at lower framerates, while faster computers may simulated at very high rates, if VSYNC is turned off. If VSYNC is turned on, you may find your simulation locked to rates like 60hz, 75hz or 85hz depending on the display and the user settings.
This means that if you step your simulation forward with a constant delta time each frame, your simulation will seem to run faster or slower, depending on how fast the computer is rendering your scene.
One way to fix this is to use a high resolution timer to get the current time value each time you update the physics. Then you can work out the time in seconds between the current physics integrate call and the previous one, and pass that time in as the dt for the next simulation update:
float t = 0.0f;
float currentTime = time();
while (!quit)
{
float newTime = time();
float dt = newTime - currentTime;
currentTime = newTime;
integrate(state, t, dt);
t += dt;
render(state);
}
This last method looks pretty good. If the game is running at 60fps then each dt will be passed in as 1/60th of a second to the simulation, and if the game is running on a slower computer it will pass in 1/30th of a second for 30fps. No matter how fast or slow the computer is, your simulation will always run at the correct speed.
But there is a huge problem with doing it this way which I will now explain!
Fix your timestep or explode
The problem is this. We are using numerical integration so the results of the integration depend on the size of the timestep. This is even true for advanced integrators like RK4. The larger the timestep the less accurate the results. So if you develop your simulation running at 60fps then at some point during your game the framerate drops to 10fps then all bets are off.
This may not seem like a big deal, but consider that in physics simulation, a small change in timestep can cause huge differences in behavior. If you have a series of really stiff spring constraints for shock absorbers in a car simulation then tiny changes in dt can actually make the simulation explode.
What we want is the best of both techniques. We want to choose a single dt so that every time the simulation runs it is stable and behaves exactly the way it was intended. At the same time we want the simulation to run at the same perceived speed irrespective of the display framerate. These two requirements seem completely at odds, and they are, unless we can decouple the physics and display framerates.
Free the physics
What needs to be done is to advance the physics simulation ahead using a fixed dt but make sure that it keeps up with the display framerate so that the simulation appears to run at the same speed. For example, if the display framerate is 50fps and the simulation is designed to run at 100fps then we need to take two physics steps every display update to keep the physics in sync.
What if the display framerate is 200fps? In this it would seem that we need to take half a physics step each display update, or alternatively one physics step every two display updates. Even trickier, what if the display framerate is 60fps, but we want our simulation to run at 100fps. There is no easy multiple here. What if VSYNC is disabled and the display framerate fluctuates from frame to frame?
If you think about exactly what is required to keep the physics update in sync with the display update while only ever taking discrete timesteps of size dt you will see that its not trivial. But now I will share with you a trick that makes it very easy to implement correctly.
The trick is to use a time accumulator. Each update you add the display deltaTime from your high resolution timer into this accumulator. Then, while there are whole increments of your dt available you run a physics step and subtract the physics step dt from the accumulator. Effectively the timer produces time and the physics update consumes it in discrete dt sized chunks.
float t = 0.0f;
const float dt = 0.01f;
float currentTime = time();
float accumulator = 0.0f;
while (!quit)
{
float newTime = time();
float deltaTime = newTime - currentTime;
currentTime = newTime;
accumulator += deltaTime;
while (accumulator>=dt)
{
integrate(state, t, dt);
t += dt;
accumulator -= dt;
}
render(state);
}
This code handles both undersampling and oversampling correctly which very is important. Undersampling is where the display framerate is lower that the physics framerate, eg. 50fps when physics runs at 100fps. Oversampling is where you have an insanely high framerate (or you are viewing physics in slow motion) where one physics frame accumulates over several display updates.
There is one final thing that you need to be careful of when using this technique. Now that our physics simulator is smart enough to step any large deltaTime passed to it in small dt increments, make sure that you clamp the deltaTime passed in from the timer to some maximum value like 0.25 seconds. Why? Well if you alt-tab away from your physics simulation in windows then come back to it 10 minutes later, you'll be waiting a long time for it to catch up the last 10 minutes of physics in 1/100th of a second increments...
The final touch
So it seems that all is well. Our simulation is stable and framerate independent but there is still one last thing to do before it is perfect. Consider what will happen if the display framerate is 55fps and the physics is running at 60fps. Basically the time accumulator will have to alternate between taking one and two physics steps each display update to make sure that it keeps up. This irregular amount of physics steps taken per update causes a subtle but visually unpleasant stuttering of the physics simulation on the screen known as temporal aliasing.
Even worse, if you setup a slow motion mode (1/10th speed) your effective display framerate would be 600fps if your display is actually updating at 60fps. Assuming the physics is also running at 60fps the accumulator would only do one physics step every 10 display updates. Objects would animate in discrete jarring steps every 1/6th of a second. This looks pretty dodgy but the good news is that there is a way to make sure that everything runs smoothly all of the time.
The solution is to interpolate between the previous physics state and the current state based on how much time is left in the accumulator. This will add a latency of up to dt to your physics simulation, but the visual results are definitely worth it. Here is how to implement it:
float t = 0.0f;
const float dt = 0.01f;
float currentTime = time();
float accumulator = 0.0f;
State previous;
State current;
while (!quit)
{
float newTime = time();
float deltaTime = newTime - currentTime;
currentTime = newTime;
accumulator += deltaTime;
while (accumulator>=dt)
{
previousState = currentState;
integrate(currentState, t, dt);
t += dt;
accumulator -= dt;
}
const float alpha = accumulator / dt;
State state = currentState*alpha + previousState*(1.0f-alpha);
render(state);
}
This looks pretty complicated but here is a simple way to think about it. After the deltaTime has been added to the accumulator and the physics steps of size dt have been performed, if the physics and display fps are not integer multiples of each other, then some time will remain in the accumulator. This remainder is effectively a measure of just how much more time is required before another whole physics step can be taken. For example, a remainder of dt/2 means that we are currently halfway between the current physics step and the next one. A remainder of dt*0.1 means that the update is 1/10th of the way between the previous and current states.
We can use this remainder value to get a blending factor between the current physics state and the previous 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. This interpolation is easy to do for single values and for vector state values. You can even use it with full 3D rigid body dynamics if you store your orientation as a quaternion and use a spherical linear interpolation (slerp) to blend between the previous and current orientations.
If you implement this interpolation technique you ensure that there will not be any visual stuttering when your display and physics framerates are out of sync. It will also perfectly handle the undersampling case so your objects will move smoothly when you view your simulation in slow motion or ten years from now on a really fast computer.
Conclusion
Time stepping seems so simple, yet it contains many subtleties you must understand to implement it perfectly.
If you use the techniques presented here you can decouple your display and physics framerates for determinism and stability, and at the same time make sure your simulation animates smoothly on the screen.
Click here to download the source code for this article.
Now that you understand the important of a fixed time step, lets continue on to the next article where we discuss how to take our physics simulation into the third dimension!
Great article! Best article I’ve read on this important subject. Very nice and clean implementation too.
Do not worry about your difficulties in Mathematics. I can assure you mine are still greater
-Albert Einstein
Excellent articles on game physics. I’m starting to do some research on network-based state machines/physics and they were quite helpful.
Thanks so much for posting this! After trying to figure this out after many hours, I was able to quickly
come up to speed thanks to this article. Excellent work!
Also, fixed internal framerates help when you do networked games.
Given the last interpolation trick with ‘alpha’ blending between states, you’d think that for physics-intensive programs it may be important to really catch up with realtime. I.e. after the while(accumulator>=dt) loop finishes, do a new deltaTime calculation with a new time() call and re-enter the while loop if deltaTime is bigger than some threshold.
I’ve noticed with my car simulator that the physics can take up quite a bit of CPU time, making the last alpha blending call a bit useless if you’re already straying away from the actual time.
Excellent article and very helpful to my current situation. Thanks for taking the time to explain this in terms that non-mathematician games programmers can have a half chance of understanding.
Thank you very much!
(really!)
This solves all my problems
Very nice article. I’m curious about a possible optimization though. Rather than doing the physics in a While loop, why not calculate how many physics updates you have time for and run them in a For loop? Obviously if the framerate is fluctuating this is less accurate, but this way – because you know when you’re going to end – you need only capture the state on the last run through. Since you only do multiple physics updates when the system is struggling to keep up, knocking out the requirement to capture the state before and after each update might save you time and help you keep up, no?
well, i’m not sure if that will work – there are certainly other strategies for doing updates, but if you want to use this one, you need to be very careful to follow the accumulator/while loop logic very closely
its quite intricate and is doing a lot more than it looks like it is…
yes, it is possible to get into a “spiral of death” with physics when using this technique, when you are heavily CPU bound
so in general this technique is great when you are renderbound and simulation is cheap and reasonably predictable.
to take it even further, you can run the main physics loop entirely on a separate thread which actually runs (in real time) at the number of frames per second the physics should run (say 100hz) and the render thread just reads latest physics state and interpolates, completely independent of physics
this way you are never doing two or more physics updates per-update, so processing is more evenly distributed
in addition, if you gather the input for you simulation on the physics thread, you sample the joystick or keyboard at regular 100hz intervals, which leads to better behavior of your physics
consider this, “fix your timestep version 2.0″
cheers
ps. another option i should mention is just plain framelocking, just pass in delta time as 1/60th of a second every frame, no matter what the real time value is. yes, your simulation will slow down in real time, but you’ll get the stability benenfits of fixed delta time updates — this is a good technique when you are mostly simulation bound, but it breaks down when you want synchronize with display refresh to get everything perfectly smooth
I thought I could get by without fixed timestep, however some testers were having issues with the game I’m working on – which were fixed by a fixed timestep. Thanks for writing the article, it saved me tons of time messing around.
Hello, great article! I’v implemented your technique but I’d like your advice about (mega)oversampling.
My project doesn’t do much things so the framerate is insanely high with my PC (3000fps), and the timer of my engine (Ogre) gives me a deltaTime of 0, because it’s has a precision of 1 milisecond, so 1/3000 = 0.00033s = 0.33ms (that’s why I got 0).
I already had this problem with the SDL timer and I guess a QueryPerformanceCounter or any other high precision timer have the same limitation. So I thought putting some ugly Sleep() in the code to obtain a valid deltaTime. How do you think it’s possible to do something about this ?
And even I if want to fix the display framerate, the problem is the same (adding 0 to any accumulator, so it’s never time to update).
Thank you !
use a higher resolution timer, 1ms resolution is next to useless, and is the root cause of your problem
use QueryPerformanceCounter directly!
Everything is now working perfectly, and the interpolation part makes a noticable difference ! Thanks a lot
i have to thank you, too! i’m using your accumulator code in my game project, too.
currently, i’m running under win32 and have a high-res timer. but – i want to port it to linux. under linux, there is apparently no reliable way to get any sort of highres timers. so. what now?
is it possible to somehow calc the mean framereate (e.g. measure number of frames rendered in 1 second) for the whole physics+graphics loop, and then calc the needed number of physics step?
for example:
whe have 20 fps, and physics needs 100Hz
so we would need to do
100/20 = 5 physics loops every frame? is this right?
ok, under linux there are a few options for high res timers:
see http://pixeltoaster.googlecode.com/svn/trunk/PixelToasterUnix.h
and look at the code for the “UnixTimer” class (two different techniques are presented)
both should give you good precision
cheers
Very nice article. I was using this method for a game and it actually caused a very subtle bug. When playing very large in game cut scenes, the audio would become out of sync with the animations. I tracked the problem down to delta time accumulating error. The solution instead was to keep a simulation time and a real time. Then the loop is something like:
while ( (time() – simTime)>=dt )
{
simTime += dt
}
You still get error but it’s less. It also works with a crappy timer
Leigh
Hi
Very nice article.
Now, I want to ask a question.
I’m using NewtonGameDynamic and Genesis3D .
I implemented the GameLoop without the “The final touch”, and I have the problem that you comment:
The final touch
So it seems that all is well. Our simulation is stable and framerate independent but there is still one last thing to do before it is perfect. Consider what will happen if the display framerate is 55fps and the physics is running at 60fps. Basically the time accumulator will have to alternate between taking one and two physics steps each display update to make sure that it keeps up. This irregular amount of physics steps taken per update causes a subtle but visually unpleasant stuttering of the physics simulation on the screen.
My problem is, I don’t understand like I can use the interpolation of the article for my system.
You use OpenGL and it is easy to use the value of the interpolation for rendering the point directly.
Newton uses callback to transform the objects 3D.
My callback is this:
VehicleChassis(Class)>>transform: pBody from: pMatrix
| chassis matrix |
chassis := NewtonRigidBody userDataFrom: pBody.
matrix := NewtonMatrix fromBytes: pMatrix.
“Relocate the GenesisActor”
chassis actor pose: matrix asGeXForm3d.
^NULL
I take the matrix that Newton sends me and I relocate my objects directly.
Would I have to interpolate the matrix before relocating my objetos3D?
Advance thank.
KIKO
PD: Perhaps you could enlarge the example using an engine
sure, well you just need to buffer the position/orientation coming out of newton’s callbacks, then at render time (later in the frame – dont do it within the callback), render an interpolated value
Hi Glenn
Thank you for their attention.
I have a question more.
Suppose you, that I update the physics with a dt=0.016 that is the minimum that NewtonGD requires.
The range is of (1/60.. 1/1000) for NewtonGD.
I would update the physics X times before the render, you suppose 16 times.
With a smaller dt=0.01 I would be update the physics more times, you suppose 25 times.
My question is:
Should I have a buffer the position/orientation coming out of newton’s callbacks of variable size?
For example: 16 for dt=0.016 or 25 for dt=0.01.
Is this correct?.
if it is this way.
How I do make to manage after the update of the physics the render?
I implement the solution with 2 variables (currentMatrix previousMatrix), but I have the problem of the stuttering
I am really confused
Advance thank
i think you should try a simple example first, and get your head around it — its not hard! but becomes complex when introducing middleware and “its way of doing things”
here is what i think you need to do with newton, always update it at 60fps (~16.7 ms per frame), but interpolate between according to render rate, as described in the article above
so newton is always creating state for you on integer frame numbers, exactly 1/60th of a second apart, while your renderer is not always doing this, it is working on arbitrary dt, — so you interpolate between the two nearest integer frame samples to find the position/orientation of your body at the render time
cheers
Hi Glenn
Thank you again.
Excuse that I insist once more. I will try to explain again, what I don’t understand and I will accompany him with my code.
You wrote:
There is one final thing that you need to be careful of when using this technique. Now that our physics simulator is smart enough to step any large deltaTime passed to it in small dt increments, make sure that you clamp the deltaTime passed in from the timer to some maximum value like 0.25 seconds. Why? Well if you alt-tab away from your physics simulation in windows then come back to it 10 minutes later, you’ll be waiting a long time for it to catch up the last 10 minutes of physics in 1/100th of a second increments…
Well, Let us suppose the stage.
deltaTime=0.016 for physics update.
accumulator=0.25 .
while (accumulator>= deltaTime)
{
accumulator -= deltaTime;
NewtonUpdate(deltaTime).
}.
The amount of times that NewtonUpdate () it is called it is: 15 times.
On the other hand, Newton calls 15 times to the callback:
“void PhysicsSetTransform (const NewtonBody* body, const dFloat* matrix). “
In my buffer I have 15 matrix. OK.
Now, is time of render. OK.
In this point is where I don’t know that I should make.
If my buffer would have 2 matrix, it would be easy to interpolate its values. But with 15 matrix?.
If I make an interpolation between the first and the last matrix, this it would not be correct. Right ?.
I implement this last and it doesn’t work. I continue having stutterer problems.
Could you explain a little more, how do I have to make the render?.
My code in Smalltalk:
GenesisMainWindow>>onIdle
“Private – Processes onidle messages.”
[thisApplication peekMessage)not ] whileTrue:[ self application update.
thisApplication peekMessage ifTrue:[^true]].
“application = GenesisSpaceManager”
GenesisSpaceManager>> update
self isReadInputTime ifTrue:[ self readInput].
self physicsManager update . “Perform physics update”
“This is the site where I don’t know that I have to make”
self updateVehicle . “Set the position/orientation with the matrix of Newton callback”
self render.
PhysicsManager>>update
|now elapsed|
now := Time millisecondClockValue.
elapsed := (now – self lastPhysicsUpdate) / 1000.0.
(elapsed > 0.25) ifTrue:[elapsed:=0.25] .
accumulatedTime:=accumulatedTime + elapsed.
[accumulatedTime >= 0.016] whileTrue:[newtonWorld update: 0.016.
accumulatedTime:=accumulatedTime - 0.016 ].
self lastPhysicsUpdate:Time millisecondClockValue.
GenesisSpaceManager>>render
(engine beginFrame:self camera clearScreen: true) ifTrue:[
engine render: aWorld with:self camera time:0].
(engine endFrame).
Advance thank you
KIKO
PD: Sorry for my english.
PD2: I hope not to drain their patience
I am very impressed by the quality of the article too. I’ve read a few more on the subject but none was this clean and eloquent.
One comment though. The interpolation function in your code looks like this:
State state = currentState*alpha + previousState*(1.0f-alpha);
My calculations (and intuition) say it should be:
State state = currentState*(1.0f+alpha) – previousState*alpha;
Am I wrong? Can you double-check your math?
Best regards, Cazy.
i’m certain its correct, why dont you download the example source code, switch the math around and try it?
ps. i always find it intuitively wrong too, and its always tricky to get it the right way around when i code it fresh… but its right i tells ya!
#21 – you seem to be a bit fuzzy on exactly what to interpolate. please read the article again and study the example source code that comes along with the article, the answer *is* in there
once you have the concepts straight, then perhaps try to “refactor” the example source it into a form more like newton (with callbacks on update), then you should get it!
(hint, you’ll need a circular buffer indexed by frame # — or at least, store the last 2 previous state values for each object)
cheers
#22 ok, cazy i’ll prove it via logic, just because i’m feeling a bit evil now
first, take the “left over” bit of time that doesnt fit exactly into our chosen fixed “DeltaTime”
this is basically, currentTime modulus DeltaTime, but in the article i implement it by taking our deltaTime value (the real value from the time), and increasing our currentTime value in whole frame increments
maybe a better way to do this would be to forget about floating point time, and just have “frame” and “accumulator”:
to update time:
const float FrameRate = 60.0f; const float DeltaTime = 1.0f / FrameRate; int frame = 0; float accumulator = 0.0f; while ( true ) { accumulator += GetDeltaTimeFromTimer(); // note: delta time in seconds while ( deltaTime >= DeltaTime ) { frame++; accumulator -= DeltaTime; // (simulate frame) } }the code above may be a bit clearer than the code in the article
ok, so each time through the loop, we know two things:
* our frame number (integer)
* our current accumulator (in seconds)
to calculate alpha, lets take the accumulator value, which will be (by definition) in the range [0, DeltaTime)
note the ")" at the end, it cannot actually equal DeltaTime, it can just approach it (if it did equal DeltaTime, we'd just iterate through the loop once more, and subtract DeltaTime getting it to be zero)
ok, so we need a blend factor. lets call this "alpha"
we want blend in [0,1], so we just take accumulator and divide it be DeltaTime – note that this actually generates a value in the range [0,1)
but what does “alpha” mean? which value of alpha means “100% previous frame” and which side means “100% current frame” ?
to work this out, just look at accumulator:
if we are *exactly* on the previous frame value, accumulator will be zero, and so will alpha
if we are say, 90% near the end of the frame, accumulator will be 9/10ths of the way towards DeltaTime, so alpha will be 0.9
so clearly, if alpha is 0 – we wish to have 100% previousFrame, if alpha is 1 we want 100% of currentFrame
so, the correct interpolation is:
or if this makes it a bit clearer:
(note that if alpha = 0, 1.0f-alpha = 1.0f, which gives 100% previous state)
cheers!
The answer is here: “The solution is to interpolate between the previous physics state and the current state based on how much time is left in the accumulator. This will add a latency of up to dt to your physics simulation, but the visual results are definitely worth it.”
Yes, your math is the correct one for the interpolation function. Sorry for the missunderstanding. Although I was calling it interpolation I was actually talking about extrapolation. The extrapolation gives a real time estimate of the state. If you add (CurrentState-PreviousState) to the interpolation formula, you get the extrapolation formula.
Can you tell me the reason why interpolation is better than extrapolation? They are both just linear estimates of nonlinear physics behaviour. I know there is a reason, I just don’t know it.
Best regards, Cazy.
interpolation is between two known values, so its “perfect” – just lagged by up to one frame
extrapolation is jerky and is predicting ahead, thus gets it wrong, and has to snap and pop to correct
trust me you want interpolation
take the example source code and change it to extrapolation, and let me know how it goes! – maybe it’ll be good for you, i’m conservative so i prefer interpolation
cheers
What confused me is that the actual current time is currentTime + acumulator, so it’s outside the (previousTime, currentTime) interval. But after thinking it trough I realised that what you’re doing is shift the fraction alpha back one inteval. This is complelty legal, as the game loop uses a fixed time step. So CurrentState could be vweyt well named NextState and PreviousState could be named CurrentStep.
Thank you for your time, reading your article and replies was very informative. One other question though (feel free to ignore it): why do you initialize currentTime to 0? Isn’t that going to give a wrong deltaTime the first time the game loop is entered?
Best Regards, Cazy.
good point, fixed!
Hi cheers
I cannot make him to work still, but I think that I am very close.
At the moment, I don’t use QueryPerformanceCounter .
I wanted to ask to you.
How much can this affect in the problem?.
At the moment I has a undersampling problem.
My fps fluctuates between 29 and 35.
Advance thank you
KIKO
chances are, the precision of your timer is probably too low – upgrade to QueryPerformanceCounter and see how it goes
Great article which nicely describes a solution for a “common” problem!
Great article!
I read your atricles printed, id be happy if the would be a printer-friendly version of your stuff too
i’m using wordpress – dont think it supports that, but if you cut & paste the article text into word i think you’d get something nice to print, — could probably even cut & paste into an email app, then print the email, whatever
Indeed a good article on an important topic. However, I don’t agree with your use of deltaTime. This value relies on the accuracy of time(). Even if it’s a high-res timer, the accumulator accumulates inaccuracies over time.
Related to that, I don’t agree with “keep the physics update in sync with the display update”. If it’s a simulator, then shouldn’t the physics be the driving factor? And the display updates follow? Accuracy first?
I propose getting rid of deltaTime and accumulator, and introducing a variable nextPhysicsTime to store the time at which the physics should be updated again. You update the nextPhysicsTime by simply adding dt, which is more accurate than an accumulator that relies on time().
What i’m saying is, the physics time should be synched with real time directly.
This code is pre-”final touch”:
float t = 0.0f;
const float dt = 0.01f;
// absolute time we should do the next physics update(s)
float nextPhysicsTime = time();
while (!quit)
{
while (time() >= nextPhysicsTime)
{
integrate(state, t, dt);
nextPhysicsTime += dt;
t += dt; // not sure what t is
}
render(state);
}
dude, you totally missed the point of the article – read it again
Ok, cool. I do get the point. It is to untie physics from rendering, and to get each update to do updates for a fixed amount of time. There are many reasons for doing that.
When I look at your code again, I see that your deltaTime IS correct, even if time() is not accurate. I’m sorry about the mistake.
I still think the code can be simplified. There is no need to have currentTime, assumulator, endTime etc. You can do the same by having 1 variable nextPhysicsTime and incrementing this by dt on each update.
For what it’s worth, the Java code below produces perfectly smooth animation, if v-refresh is equal to the target fps. If not, it would need your interpolation code.
Dude.
long period = 1000000000L/60; // 60 is target fps
long nextUpdateTime = System.nanoTime();
while (running) {
while (System.nanoTime() >= nextUpdateTime) {
update(…);
nextUpdateTime += period;
}
paintScreen(…);
}
you are right, and i dont code it the way explicitly mentioned in the article here, its just the easiest way to explain it to folks
if you use floating point values to store time values, you are a bloody idiot!
basically, i use 32bit integer vales to represent time, and do all the calculations in 64bit integers
but, i dont want to do a tutorial about fixed point mathematics also… =)
cheers
>…and do all the calculations in 64bit integers
What’s the sake of doing everything in fixedpoint? Is that to only avoid floating value de-normalization and accuracy degradation problems?
On the other hand, as I know (at least on x86) floats are faster to multiply than integers. Division is not faster, but while doing division, CPU can perform integer operations in parallel (except integer multiplication).
I just wanted to give a huge thanks to you Glenn. Your method helped me out incredibly! I have way more control over my physics simulation in my app now! Thanks again!
Thanks for the great article. You have the optimal solution here that I really wish I had known about when I was screwing around with physics simulation Java applets back in high school. The animation was just never quite right.
dr. Padawan – i’m just saying that time should fundamentally by an integer quantity, not anything else!
If you use floating point numbers for time, your time value will get less accurate the longer your program runs for
If you use fixed point, its the same accuracy forever, provided you intelligently handle wrap around (this is not too hard…)
cheers
Hi Glen,
That’s an excellent article. Thanks!
Hi Glenn,
Thank you for this article, as a beginner in game development this is a great help and I will definitely make my game loop like this.
I also like the way you separate your window code from your game code, it makes everything so much more clean.
I got a question though, when I run your example I can still see the dot stuttering from the moment it goes left for the second time and the stuttering stays until it slows down in the middle.
Is that normal? Am I being too picky? Do you have the same effect when you run it or your computer?
Anyway, again, thanks a lot for this.
Regards
David
I was reading your article and tough it was perfect, but I just though “integrate” meant the physics update/game logic/input pooling and I though it was working this this, but after checking the source code, integrate is really a mathematical integration, and I don’t quite understand what it is doing there. I also don’t quite understand the constants used in the function, and what are x and b are supposed to mean in your State structure..
For the Windows alt-tab issue, the other solution is to run the physics code even when the renderering code isn’t happening. This should free up the CPU time being used for graphics, and given the technique in the article wouldn’t need to run perfectly smoothly anyway.
This is especially important in multiplayer games where you can’t just automatically pause the game.
Whilst a intresting article on this topic I did find one flaw though.
In the past where I have had to write such code I have always used a MVC model to map physics to display and control.
Creating a model that runs in its own thread (regardless of system speed.) allows the simulation to be easily sped up ,slowed down and paused, as well as giving it the ability to be decoupled from the render speed..
If a simulation (i.e. snooker ball) it would also be advisable to create a full physics object model so it then becomes possible to run in reverse. (e.g. so drag, etc. can be applied in reverse).
Glenn,
Absolutely superb writing style you have, man — you definitely have the knack to teach others, and well. Thank you for this brilliant article.
-Nick
Hi Again Glenn,
Depressingly, your link to source isn’t working (seems as if folder access to your siteroot/downloads directory has been changed)… Could you fix and email me if you do? I would very much like to see inside that integrate() function.
-Nick
hey nick, the site is in transit right now, so all the old download links are broken, i’ll have that fixed this weekend – but for now i’ll mail you the file
cheers
damian, yes i agree the absolutely correct pattern is a producer/consumer model with the simulation running in another thread or process from the renderer – i’ll be writing a new article about this at some point i hope
I am a programmer and wannabe-game-developer, and am currently trying to tackle a project that is much larger than my skills. Just ’cause.
Being that so, I have to thank you very much on this article, it’s been really helpful. It’s also taken me several hours to wrap my head around the “final touch”. I’ve been able to “free the physics” and, of course, experienced the problem you mentioned.
So here’s how I understand it: In “free the physics”, we are always rendering the latest physics step we have, even though we’re a bit ahead of it in time. On transitioning to “the final touch”, though, we decide to render something that is between the latest physics step and the step BEFORE it. That would mean, as I understand, we’re further away from “the truth” (the state as it would be in current time) than we were before deciding to interpolate, but that means better animation.
Do I understand it correctly?
Thank you again for this,
Marcelo.
yes, you are stepping forward at nice physics intervals like 1/60th of a second, but rendering at another rate – since you have no way to get the exact position at the real time of render, you just interpolate between the two nearest physics steps to get the approximate position at the render time t, so that your rendering is smooth
if you don’t do this, you get temporal aliasing – eg. jittery movement
cheers
Exactly, I am getting this exact problem right now.
What was hard for me to “get” was the part that, on the last code snippet, we’re not rendering something that is the latest physics step we know of, we’re rendering 1 dt BEFORE that!
That was kinda weird for me at first, but it makes a little more sense now. As soon as I can figure out how to get/set all of the “state” of the simulation (I am using a framework, Box2D, so it encapsulates the state), I’ll try that and see how it goes. Thanks again!
Cheers,
Marcelo.
It seems to me that with this method there will always be a remainder. It’s unlikely that the time would happen to fit with a multiple of your dt, so you will always be doing interpolation.
You write: “We can use this remainder value to get a blending factor between the current physics state and the previous state simply by dividing by dt”
If you want to interpolate the next point, you should be getting the the blending factor between the current and the next state, not the previous. So to do this interpolation, you have to also calculate the next step, even though you are not yet taking it.
I’ve discovered a problem with this method.
If the computer cannot keep up, meaning it’s been longer since last frame, then you have to calculate several physics states for that frame.
This will mean that this frame will take even longer to calculate for the computer, and thus when you get to the next frame, even more time has passed, and you will have to do even more calculations for that frame, which will take even longer.
It’s an evil spiral, that means once it just gets slow enough once, for the computer to not be able to keep up, then the accumulation will just keep growing bigger every frame.
sure thats actually correct, but the premise of this article is that you can actually afford to simulate one timestep in <= the actual time it is simulating
so in your case, you should simply use a variable framerate, or optimize your code down so it fits in budget
cheers
if you’ve already got code that can interpolotate a timestamp… if your simulation can’t keep up, you’ll atleast know how much it isn’t keeping up by the accumulator being > than 1/60th (or whatever rate you are intending to get)… and can get a rough interpolotation since the last time.
maybe that didn’t make much sense, but it worked decently enough for me.
Hehe, well if it takes longer than your time step to simulate that amount of time, you’re in a bit of trouble! You probably need to increase the size of your step..
These are some very good articles!
Though I’m slightly baffled by the interpolation used.. You’re dropping back one step then interpolating by alpha towards the most recent known data.. Is that really the best way to handle it? I guess it’s the only accurate data..
Any way I was thinking that having the rendering done in a separate thread would be the best solution, but it adds complexity and makes things harder to debug.. So I was considering going with the single threaded approach for initial revisions and then moving the rendering to another thread.. But do you think this would just cause more pain in the long run than just starting with that approach?
yes i actually prefer the separate thread approach myself, and it has better CPU patterns than the approach in this article, avoiding having to simulate 2 or more sim frames per render frame in the common case, spreading it out properly with frame sleeps — it also avoids the “input aliasing” that you get with this approach, which is subtle, but there
or even better — put the simulation in a different process and connect a “view client” to it, using a simple network model with interpolation/extrapolation
ps. the reason i interpolate previous two frames is to always be accurate, you could extrapolate from the current frame if you want, but this causes discontinuities if the velocity changes abruptly (eg. a bounce…)
cheers
I see now, that the spiral I mentioned can be avoided by making sure the timestep is big enough. Of course there will be a lower limit of how slow the computer can be then, but you can’t expect your games to work on a 286 anyway
I also wondered about the interpolation.
I understand the reason to interpolate and not extrapolate, but it doesn’t make sense though, since the position you are getting is a previous one.
To do the interpolation for the correct position, you should use the current position and the NEXT position, meaning you would have to always calculate the next step, a frame before you actually render it.
Maybe that is what you are already doing, and I just didn’t catch that in your code. I don’t know.
I was also thinking, that your clamp the deltaTime to some max, it would mean that you couldn’t use it for realtime multiplayer games, since one computer could get behind. But I guess it could under all circumstances, since the timers might not run the same on both. I guess in such cases you would need some time signal from the server to keep it accurate. But maybe these differences would be so small that it wouldn’t be important.
By the way, thanks for the article, it was useful for me.
yes thats exactly what i’m doing, interpolating between the previous frame and the current – effectively adding one frame of latency
cheers
Thank you so much! This is awesome! =) I gotta read up on that linear interpolation thingy though.
Hi,
nice article! Although I’ve been using these techniques for a while, I never thought of it this way. Rather, these are classic client/server game design (client doing rendering, server doing physics and stuff). The interesting part however, that one that threw me a bit off, you interpolate between last and current frame (effectively adding a frame of latency). Wouldn’t make more sense to extrapolate (sometimes called prediction) from the current frame onto the next, and compensate when the frame is finished? The reason for this is two-fold, one, as you describe, to smooth the animation, and two (which is more important if you’re a network jock like me) to compensate for packet loss.
in this case there is no need to extrapolate, since the rendering is performed synchronously with the simulation in one process – of course, if you had a server process running the simulation and a client process viewing it, then yeah it would make sense to have support for extrapolation
I am curious: how does one handle interpolation of objects that do not exist in one frame or the other? for instance, a bullet only exists in the frames between being fired and hitting its target. Does one simply not display these objects? Or would something more involved be preferable?
if an object is created, you just set its previous position same as the current, eg. dont interpolate
if the object is deleted, then obviously you dont need to interpolate it because its no longer there
of course, to be smooth about it fade-in fade-out works fine, during which time you’d interpolate normally
cheers
Great article, thank you very much for sharing this with us.
.
I have some small questions though, I apologize in advance if they are actually really easy, which I’m sure they are, with proper knowledge of all the mathematic workings underneath it all, which I haven’t , yet.
I have a pretty good understanding of the gist of it, but since this is about simulating physics over time, I don’t want to rely on my shakey knowledge if I might get help from people who know their stuff
Especially since I’m already having trouble ending a simulation at exactly 10 passed seconds simulation time, but I guess that’s because I’m suing floats, still havent gotten the grasp of how to use fixed point math, yet…
Anyway…
To implement slow motion I would need to scale “dt” in the integrate function in the accumulator while loop, right?
while (accumulator>=dt)
{
previousState = currentState;
integrate(currentState, t, dt * scale); // 0.5 half speed, 2 double speed
t += dt;
accumulator -= dt;
}
It works like a charm for fixed velocities.
But…wouldn’t slow motion or fast forwards break variable ones? Like the spring example in your first article.
When I increased the dt to one second it spazzed out, which makes sense to me since the spring now had to deal with sudden jump/jerks with no data inbetween to move smoothly, appropriately.
So…I guess, slow motioning this would be fine, since it would actually increase the precision of the spring, right?
Speeding it up would break it though, right?
Again I apologize for this…but I really want to get this right.
Fast forward makes me think of tunneling through obstacles and the like as well, and that can’t be good.
Fast forward is onlyviable for spepping through recorded replays?
But this here is designed to be deterministic, right?
Anyone able to get that knot out of my brain, it would be really helpful.
Cheers~!
ideally you would scale the delta time value coming in from the timestep, so you speed up or slow down the simulation, BUT it still steps forward at the same fixed dt
you’ll notice that the interpolation in this article makes the motion of the objects still smooth even in the slow motion case
of course you have to be very sure that you aren’t simulation bound before you FAST forward – because fast forward will involve doing many physics steps per-render frame, which will cause a spiral of death if you can’t keep up…
ps. i used this technique to implement the slow motion mode in “freedom force”, so it works well for that, we didn’t have a fast forward mode, mostly because we were already sim bound at normal speed
good luck!
also, if you want to scrub forward during a replay, just advance dt but don’t render each frame, this way you should be able to scrub forward to the time you want – without having tunnelling issues
also, you may want to remove the dt 0.25 sec clamp in this article when in a fast forward/scrub mode…
Ah, works perfectly!
Also, thank you for your advice on fast forwarding, makes sense too.
Thank you very much for your help~!
Cheers~!
“What VSYNC is disabled and the display framerate fluctuates from frame to frame?” You need an “if” in the sentence.
fixed, thanks
You’re fuckin fantastiiiiiic! Haha
This article really save.. Only 2 words: THANK YOU!
Greetings from Argentina,
Daniel SL