Sign in to follow this  
Ysaneya

A discussion about fixed time steps

Recommended Posts

Ysaneya    1383
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 this post


Link to post
Share on other sites
siaspete    208
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.
2. Reduce your update rate, to say 50/second instead of 100, depending on your preference.

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 this post


Link to post
Share on other sites
Ysaneya    1383
Quote:
Original post by siaspete
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


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 this post


Link to post
Share on other sites
Dmytry    1151
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 this post


Link to post
Share on other sites
Ysaneya    1383
Quote:
Original post by siaspete
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.


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 this post


Link to post
Share on other sites
siaspete    208
Quote:
Original post by Ysaneya
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..

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 Ysaneya
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" ...

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

Share this post


Link to post
Share on other sites
Dmytry    1151
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 this post


Link to post
Share on other sites
Rockoon1    104
Quote:
Original post by Ysaneya
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).


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 this post


Link to post
Share on other sites
David Bonnet    170
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 this post


Link to post
Share on other sites
SimmerD    1210
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 this post


Link to post
Share on other sites
lonesock    807
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 this post


Link to post
Share on other sites
Dmytry    1151
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 this post


Link to post
Share on other sites
voguemaster    183
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 this post


Link to post
Share on other sites
Dmytry    1151
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 this post


Link to post
Share on other sites
Woodchuck    246
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 Dmytry
The 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 this post


Link to post
Share on other sites
Woodchuck    246
Quote:
Original post by Woodchuck
Can'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 this post


Link to post
Share on other sites
Ysaneya    1383
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 this post


Link to post
Share on other sites
Woodchuck    246
Quote:
Original post by Woodchuck
Quote:
Original post by Woodchuck
Can'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.

Share this post


Link to post
Share on other sites
Dmytry    1151
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this