# A discussion about fixed time steps

## Recommended Posts

I've recently encountered a problem in my game and i'm not sure how to fix it. As you know, most physics engines use equation solvers that assume a constant time step in order for the simulation to be stable and consistent. Most beginners incorrectly tie their rendering framerate to their physics framerate:
float curTime = getTime();
while (!quit)
{
float newTime = getTime();
float elapsed = curTime - newTime;
curTime = newTime;
do_physics(elapsed);
do_render(elapsed);
}

... which leads to unstable behaviors. Of course, assuming a constant time step:
float curTime = getTime();
const float timeStep = 1.0f / 100.0f; // 100 Hz
while (!quit)
{
float newTime = getTime();
float elapsed = curTime - newTime;
curTime = newTime;
do_physics(timeStep);
do_render(elapsed);
}

... is even worse, since now, you're renderer-framerate dependent. So far i've been using a better approach, that i think pretty much everybody use now, using an accumulator:
float curTime = getTime();
const float timeStep = 1.0f / 100.0f; // 100 Hz
float accTime = 0; // accumulated time step
while (!quit)
{
float newTime = getTime();
float elapsed = curTime - newTime;
curTime = newTime;
accTime += elapsed;
while (accTime > timeStep)
{
accTime -= timeStep;
do_physics(timeStep);
}
do_render(elapsed);
}

Unfortunately i'm getting fundamental problems with it, too. The problem with it is that it behaves "well" as long as the performance is high. But as soon as the framerate goes down, OR if the time to execute this "do_physics" call is too high, it enters into an infinite loop: because at frame N-1 the value of "elapsed" was high, it increases the number of calls to "do_physics", which in turn will reduce the performance and increase the value of "elapsed" in the next frame. See a trend ? Once the code is starting to fall into that never-ending spiral, your program is basically freezing. Of course, adding a limit to the number of time steps allowed per frame doesn't help to avoid falling into that spiral in the first place, and you get single-digits framerate while your rendering framerate has theorically returned to "normal" since long. I'm looking for suggestions to fix this problem, and avoid the performance effect onto the time step.. Y.

##### Share on other sites
I've used the method in Gaffer's articles with good effect, even under low frame rates (~10 FPS). I don't know how your way differs, but maybe it can help you out.

http://www.gaffer.org/articles/Timestep.html

Hope this helps,
Pete

##### Share on other sites
Reading over your post again, it seems that the problem is that you can't guarantee that on average your do_physics takes less time than your timestep, which is an unwritten requirement for fixing the timestep.

I can only think of two solutions:
1. Optimise do_physics to take less than a 100th of a second.

With complex physics becoming more present in modern games, a good solution to this problem would be very handy. Anyone got any other ideas?

Pete

##### Share on other sites
Quote:
 Original post by siaspeteI've used the method in Gaffer's articles with good effect, even under low frame rates (~10 FPS). I don't know how your way differs, but maybe it can help you out.http://www.gaffer.org/articles/Timestep.htmlHope this helps,Pete

And you did not suffer from the problem i described ? When your framerate starts to slow down, it makes the number of physics steps explode..

I've already read that article you read to. I find it interesting that he says you should understand all the "subtleties", calls his technique "perfect" and recommends it for "all game systems" ...

Y.

##### Share on other sites
Clearly, you are in trouble when the physics takes more real time to compute than the virtual physics dt update that you get from physics.

Basically, to detect such a situation you can try doing something like this:
double physics_dt=0.01;double k=0.5;// some arbitrary constant, specifying how much physics step must decrease lag , at minimum. double real_time=CurrentTime();double virtual_time=real_time;while(playing){ double lag=real_time-virtual_time;// additionally, you can check lag in loop doing sleep(0) // until lag becomes greater than physics_dt.// to avoid doing re-renders when the state is not changed. double initial_lag=lag; while(lag>physics_dt){// you can use lag>0 if you want.  DoPhysics(dt);  virtual_time+=physics_dt;  real_time=CurrentTime();  double new_lag=real_time-virtual_time;  if(lag-new_lag<physics_dt*k){    the physics does not make lag much shorter.    You can do something about it right there,    or do it only if new_lag exceeds some treshold,     or increment counter and do something     if lag>initial_lag after too many steps.  }  lag=new_lag; } Render();}

BTW, don't use floating point for time. It has too bad precision, especially if game runs for long (may be especially important for server). I had this problem in one of my programs.

Another BTW, it may be good idea to make world run with negative lag and interpolate in the render. This way you could have physics framerate at something like 20fps and have rendering work at higher framerate. With good solver, 20fps or less is allright.

##### Share on other sites
Quote:
 Original post by siaspeteReading over your post again, it seems that the problem is that you can't guarantee that on average your do_physics takes less time than your timestep, which is an unwritten requirement for fixing the timestep.

That's not completely true. A low rendering framerate for a given frame will in turn increase the number of time steps to run in the next frame. Even if each time step is taking well under 10 ms to execute, the amount of them will cause the downwards spiral and it'll start to become worse and worse for the next frames (each time step staying with "okay-ish" performance).

Quote:
 Original post by siaspeteI can only think of two solutions:1. Optimise do_physics to take less than a 100th of a second.

Won't solve the issue, as mentionned in the previous paragraph.

Quote:
 Original post by siaspete2. Reduce your update rate, to say 50/second instead of 100, depending on your preference.

Won't solve the issue, will simply make it less likely to happen. Take a computer that is twice slower, and you'll get it back.

Y.

##### Share on other sites
Quote:
 Original post by YsaneyaAnd you did not suffer from the problem i described ? When your framerate starts to slow down, it makes the number of physics steps explode..

My physics was very simple, so the number of physics steps per render was pretty stable at low frame rates. Something like 10 updates per draw. It was the draw which was slow, so that didn't matter.

Quote:
 Original post by YsaneyaI've already read that article you read to. I find it interesting that he says you should understand all the "subtleties", calls his technique "perfect" and recommends it for "all game systems" ...

Yes, you're right there - it's clearly neither.

##### Share on other sites
Some clarification: the idea of my method is that there's lag between virtual time (game time) and real time (the time in world where i live in).
The physics steps, essentially, is done to shorten the lag [after it has been increased by the rendering]. When physics is too slow and fails to shorten the lag or shorten the lag too little (and does this for few updates in the row) you really need to "do something" (e.g. switch physics to lower rate, or inform player that his hardware is too bad)

It is kind of like how automatic control systems (autopilots etc) works. Except for autopilots it is strictly verified that in no situation the updates may happen slower than real time.

##### Share on other sites
Quote:
 Original post by YsaneyaThat's not completely true. A low rendering framerate for a given frame will in turn increase the number of time steps to run in the next frame. Even if each time step is taking well under 10 ms to execute, the amount of them will cause the downwards spiral and it'll start to become worse and worse for the next frames (each time step staying with "okay-ish" performance).

There simply cannot be a downward spiral into an infinite loop if your physics update is faster than your timestep.

Personally, I think a 10ms timestep is probably way too small given the problems you are experiencing.. have you considered a much bigger timestep (100ms) and interpolation between steps for rendering?

In any event.. you should always cap the number of physics steps per frame for those situations where an unexpected slowdown is unavoidable (user tabs out, background app hits the disk, etc) this also applies to variable timestep physics where you would cap dt to something reasonable.

##### Share on other sites
I usually do like this :

  while(1){    ticks = SDL_GetTicks();    process_events();    for(i = 10; i--;) physics_simul();    draw();    delay = SDL_GetTicks() - ticks;    if((delay >= 0) && (delay < 20)){      SDL_Delay(20 - delay);  // 20 ms -> 50 fps    }  }

This way, if physics_simul() takes less than 2 ms, you get a constant framerate of 50Hz, and you can use a fixed timestep (of 2ms in this case) for the physics.

##### Share on other sites
I ran into this as well.

My physics steps are always 16 ms period.

I calculate how many integral timesteps should be done since last frame. I then cap this at 4 ( making the game time slow down < 16 fps ). I then use the remainder of the msecs ( 0 - 15 ) to blend between the last two physics frames for the visuals.

So, if it gets too slow, I slow down time to avoid the 'well of despair'.

I also changed the way I looped my physics to speed things up.

Instead of looping around the whole physics code 3 or 4 times, I pass in the timestep ( 16 msecs ) and the # of loops to do.

That way each object can loop on its own, rather than looping over the whole scene. This change was a large fps boost, b/c rather than regathering all the tris near an object for collision 3 or 4 times, you gather them once, and just apply the physics 3 or 4 times in a row.

You won't get exactly the same results this way, but it is much faster, and still more accurate than just passing in 3 * 16 or 4 * 16 msecs to your physics routine.

##### Share on other sites
You could have a soft limit on time steps (say 10), and then if you hit that, do a single variable timestep, just as an emergency measure to get caught up. You will lose some accuracy/consistency, however the death spiral is _also_ inaccurate [8^)

##### Share on other sites
granted i have no pseudocode, but couldn't determine the timestep for the physics based on the time elapsed from frame to frame?

##### Share on other sites
The problem is that if timestep varies with frame rate, the results you get are not consistent across network or across different situations.
How much it is an issue depends to complexity of the interactions and simulation methods used etc. Except trivial cases, physics in gamesis never exact. In many cases you have increase of tiniest difference (e.g. colliding balls in billiard and similar things)
When there is few objects, state may be synchronized over network, but when there is many, you really need a way to send only essential information like player's actions.

My pseudocode for example explicitly computes lag between gameworld time and real time, which makes it easier to detect whever physics steps fail to decrease the lag(when physics step takes longer to compute than timestep) and it gets into spiral.

##### Share on other sites
You guys are talking about do_physics and solver time steps but what about collision detection time steps ?

One thing that is not immediately clear to me is the time step used for collision detection. In various texts I've read that the time step can also change when it is appropriate.

Can anyone shed some light on this ?

##### Share on other sites
With collisions, it is possible to find collision time more or less exactly, whever it is on timestep or between timesteps.
If you are talking about "collision detection" that only checks for whever objects overlap or not, i'd think it would be better to implement proper collision detection.

##### Share on other sites
Can't you use a multiple of the time step ? The equation are the same except a factor no (i mean the result of integral) ?

Quote:
 Original post by DmytryThe problem is that if timestep varies with frame rate, the results you get are not consistent across network or across different situations.

You can greatly increase the speed too, by precompute terms\integral that are fonction of the time.

[Edited by - Woodchuck on May 28, 2006 6:54:24 AM]

##### Share on other sites
Quote:
 Original post by WoodchuckCan't you use a multiple of the time step ?

I'm surely not clear about this. I mean, use first for update the biggest multiple of the time step that fit in the frame dt, and repeat with the remaining dt.

##### Share on other sites
I tried something like that. The idea was to have a maximum amount of time allocated for physics (15 ms), and given the time it took to solve the time steps in the previous frame, calculate the max. amount of time steps available in the current frame (so, if it took 4 ms/step in the prev frame, i process at most 3 in the current frame). I was multiplying the time step by 2 each time. The code looks like this:

	if (m_time > m_timeStep){	/// determine the number of steps to process	CTime ct;	TFloat step = m_timeStep;	TUInt wantedSteps = (TUInt)(m_time / step);	TUInt realSteps = (TUInt)(m_targetTTP / m_lastTTP);	if (realSteps < 1)		realSteps = 1;	while (wantedSteps > realSteps && wantedSteps > 1)	{		step *= 2.0f;		wantedSteps = (TUInt)(m_time / step);	}	realSteps = MMin(realSteps, wantedSteps);	for (TUInt t = 0; t < realSteps; t++)	{		m_time -= step;		_doPhysics(step);	}	m_lastTTP = (ct.getElapsed() * 1000.0f) / (TFloat)realSteps;}

It works, but the main problem remains: the "behavior" of bodies is still framerate dependent. Hence my spaceships turn a bit faster under low frameates than high ones..

Y.

##### Share on other sites
Quote:
Original post by Woodchuck
Quote:
 Original post by WoodchuckCan't you use a multiple of the time step ?

I'm surely not clear about this. I mean, use first for update the biggest multiple of the time step that fit in the frame dt, and repeat with the remaining dt.

Oops big error.

For a given frame, you have a dt. Find the multiple of time step that fit in this dt, and apply your update with this number. Your equation terms that are function of the time may be multiply by timeStepWidth*TimeStepCount. There is no more errors that with one time step. All of this, assuming you have precompute the right result (or an approximation) of the integral.

Sorry i'm wrong.

##### Share on other sites
Quote:
 Original post by Ysaneya... Hence my spaceships turn a bit faster under low frameates than high ones..Y.

that's strange....
if you don't do rigid body simulation for spaceships, if angular velocity is w then turn after time dt is axis-angle with axis w and angle = |w|*dt
With angular acceleration it should turn slower at large dt as there's some dt^2 error.

I feel with quaternions it is possible to get exact solution for given angular velocity, acceleration and time, "somehow". It's quite interesting problem. Tho it isn't clear for me yet how to do that.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628284
• Total Posts
2981829

• 10
• 10
• 10
• 11
• 17