Posts RSS Comments RSS Del.icio.us Digg Technorati Blinklist Furl reddit 66 Posts and Comments till now
This wordpress theme is downloaded from wordpress themes website.

Cross-platform SDL 2 game loop time steps, RK4 integration

Summary

Separate game updates from rendering – use a fixed timestep for game updates.  This can cause a spiral of death if you run on a slow computer, so here are some ways to deal with this.  You can use a small physics timestep.  Or you can dynamically make your timestep bigger (when the host is slows down), but then your simulation is no longer deterministic in terms of floating point calculations (if you wanted to do a replay, you can record when the timestep size changes).  Or you can allow your simulation to slow down (ie be slower than real-time).

For physics integration you can use Euler integration if you have a constant velocity or a constant acceleration.  If you timestep with (pos += v*dt + 0.5*a*dt*dt) then that is accurate as long as (v, a) are constant over the timestep.  If you have a non-constant acceleration (possibly from non-constant force vectors), then you either need a better physics equation (for Euler integration) with variables that are constant over the timestep, or you can approximate by integrating with RK4 (or RK2, Verlet, etc).

When using a constant time step, you end up with a fraction.  Suppose you just calculated current state for update 10, but your time is at update 10.3  You can just use current state (from update 10) but then you get temporal aliasing (jumping between update 10 and update 11).  Or you can extrapolate current + prediction (you can use a low computation cost prediction such as constant velocity), but you may see some jumping due to incorrect prediction.  Or you can interpolate between current and previous, based on one physics update in the past (so you’d have a latency of one physics step).

Visual effects (like particles) that do not affect game logic do not need a fixed time step, and do not need interpolation (or extrapolation).  This is assuming you don’t need your visual effects (like particles) to be deterministic or consistent.  Depending on how fast the host computer is, you could make your visual effects run more often (or less often).  However, you’d never need to simulate a visual effect (eg particles) more than once per render frame.

The rest of this post is verbose (not concise) rambling notes.  What happened was I often take notes when I’m reading (or thinking).  These particular notes I took reading about game loops (and RK4 integration), but they got disorganized.  I may (or may not) tweak these notes.

Game Loop time step

I did some code cleanup to decouple from SDLTest, to start with a minimal amount of code, and to organize the code for some small cross-platform demos.

I made a game loop based on this article – http://gafferongames.com/game-physics/fix-your-timestep/ .  It’s a good article and well-explained, going from simpler to more complex.  Here’s my simple game loop for the “Free the physics” part using an SDL timer (I removed my comments to make it shorter):

   1: while (!g_bDone)

   2: {

   3:     while (SDL_PollEvent(&event))

   4:     {

   5:         HandleSdlEvent(event);

   6:     }

   7:     newTime = SDL_GetTicks();

   8:     frameTime = newTime - currentTime;

   9:     const Uint32 maxFrameTime = 1000; // 1 sec per frame is the slowest we allow

  10:     if( frameTime > maxFrameTime)

  11:         frameTime = maxFrameTime;

  12:     currentTime = newTime;

  13:     accumulator += frameTime;

  14:     while( accumulator >= dTime )

  15:     {

  16:         Simulate(dTime); // simulate a "frame" of logic at a different FPS than we simulate a frame of rendering

  17:         accumulator -= dTime;

  18:         time += dTime;

  20:     Render();
  19:     }

  21:     SDL_GL_SwapWindow(g_state->windows[0]);

  22: }

The article’s example time() uses QueryPerformanceCounter() for Windows and Microseconds() for Apple.  I wrote a version using SDL_GetTicks().  SDL_GetTicks() is an integer of ms, while time() returns a float in seconds.

If we get a frameTime bigger than maxFrameTime, then the simulation slows down.  An alternative is to reduce the size of dTime, but then the simulation would not be deterministic – we’d be doing different calculations in terms of floating point rounding.  In general, the ability to reduce the size of a timestep (dTime) would allow you to run on a slower computer.

Game Loop interpolation vs. extrapolation (prediction)

Here’s another article ( http://www.koonsolo.com/news/dewitters-gameloop/ ) that focuses more on the graphics frame rate and less on physics (ie no details about RK4 integration, or dealing with non-constant acceleration).

Like the previous article, this article advises to do “Constant Game Speed independent of Variable FPS”.  Both articles also advise using interpolation: game code runs on it’s own frames per second, so when you draw/render your frames, it is possible that it’s in between 2 gameticks. Let’s say you have just updated your gamestate for the 10Th time, and now you are going to render the scene. This render will be in between the 10Th and 11Th game update. So it is possible that the render is at about 10.3.

koonsolo.com article predicts (extrapolates) into the future.  He does this by using a constant speed between physics updates (ie between update 10.0 and 10.3).  So we do a full physics update for 9 and 10 and 11.  But for 10.3, we do current (10) + a low-computation-cost prediction.  This low-computation-cost prediction is to just assume a constant velocity.  Then when we get to physics update 11, we’ll do the full (more expensive) update.

gafferongames.com article interpolates between previous state and current state.  This means his rendering is one physics step behind.  The advantage is that this method of interpolation is accurate (does not risk doing an incorrect prediction).  Author Comment: 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…).  Author Comment: interpolating between the previous frame and the current – effectively adding one frame of latency.  Author comment: you can interpolate, you can extrapolate — if you interpolate you’ll add *up to* one frame of latency depending on how much accumulator you have left. the alternative is to extrapolate forward networking style and trade latency for misprediction.

The extrapolation (prediction) method of interpolation is more needed for network games, where you have a bigger delay (possible packet loss).  I remember doing this “dead reckoning” prediction for Super IsoBomb networking back in college ( http://www.mepem.com/resume_RIT_pre-SimNow/IsoBomb/IsoResearch.html ).

Comment: You are correct in that the velocity does not need to be interpolated. The code interpolates the entire physics state for the object but in fact the only interpolated quantity which is actually used is the position.

In summary three choices for what position to render:
A) current => just display the latest (bad – causes temporal aliasing)
B) interpolate current and previous => you get an accurate value between current and previous with one frame of latency (eg for 10.3 we use 9.3)
C) extrapolation: current + interpolate a low-computation-cost prediction (for example, use a constant velocity)

Game Logic Physics vs. Visual Effects

Comment: I’ve implemented interpolation for my physics engine, but I was wondering if I could circumvent the interpolation step for my particle emitter. Looping through hundreds of particles to interpolate seems unnecessary because a variable timestep for particles is efficient.  I was thinking about adding an additional update call before the interpolation, and passing in accumulator, which updates my particles.

Author: Yes that is a good plan. For particles and other visual effects it is typical to not fix time step for those, interpolation and the double copy of state is a waste

Game Loop limit FPS

Summary from koonsolo.com:
* A constant frame rate can be a good and simple solution for mobile devices
* but when you want to get everything the hardware has got, best use a game loop where the FPS is completely independent of the game speed, using a prediction function for high framerates
* If you don’t want to bother with a prediction function, you can work with a maximum frame rate, but finding the right game update rate for both slow and fast hardware can be tricky

Another tweak to the above game loop would be to cap the graphics frame rate (such as by the monitor refresh rate).  As described here ( http://stackoverflow.com/questions/3102888/game-development-how-to-limit-fps ).  For example, if the number of microseconds per frame is 1000000 / frames_per_second, then before rendering you could sleep for (1000000 / frames_per_second) – elapsed_microseconds.

Game Loop with RK4 for Physics, overview

At first I didn’t completely understand the RK4 (Runge-Kutta order 4 integrator) parts, but then I noticed the time step article author had a previous article explaining RK4, http://gafferongames.com/game-physics/integration-basics/ .  If the physics side of our simulation only uses constant velocities to affect position, then Euler integration is accurate.  However, in certain more complex scenarios Euler integration is not accurate (or even fails horribly), so we need a more accurate (but not perfect) method such as RK4.  Here’s my notes on the RK4 article:

Numerical integration, Euler integration (note p & v & f are vectors such as 3D with x y z components) (constant force & mass => constant acceleration):
p = p + v*dt;
v = v + (f/m)*dt; // f=ma, a=f/m, so we use f/m instead of directly specifying a

Euler integration as done above is only accurate if the rate of change is constant over the timestep.  It’s accurate to integrate position over time with a constant velocity.  it’s accurate to integrate velocity over time with a constant acceleration.  But as shown above, Euler is not accurate when we integrate position over time with non-constant velocity (if we have a constant acceleration, then our velocity is non-constant).

Aside: the article’s example above is artificial.  For constant acceleration, Euler is accurate if you add 0.5*a*t*t, see “Constant Acceleration” section below.

For non-constant acceleration, RK4 is not perfectly accurate, but it’s more accurate than Euler integration.  RK4 works by evaluating (sampling) the derivatives at four points in the timestep, then it combines these samples with a weighted average.

Game Loop with RK4 for Physics, detail

The article’s example defines object state (position, velocity) and its derivative (derivative of position = velocity, derivative of velocity = acceleration).

evaluate() advances physics state one time step (t + dt) by doing a Euler Integration step (with input derivatives p, v).  Then it uses that integrated state to calculate output derivatives (p, v) using this new state.  To calculate output dv, it uses acceleration().  evaluate()’s only return value is the output derivatives (it does not return the integrated state).

acceleration() – the article’s example is spring and damper force assuming unit mass (Hooke’s law).  The implementation depends on what you want to simulate.  You might calculate a force here, and rename the function as force().

integrate() does RK4 integration for t to t+dt.  It evaluate()’s four sample derivatives.  Each evaluate takes the same value for (state, t) but different value sfor (time, derivative).  a uses (0, 0); b uses (dt*0.5, a); c uses (dt*0.5, b); d uses (dt, c).  Then integrate() takes a weighted sum (a + 2*(b+c) + d)/6 (“comes from the Taylor Series expansion”).  Then integrate() uses that weighted sum to advance state (p, v) over timestep dt.

Game Loop with RK4 for Physics, summary & notes from comments section

For constant velocity or constant acceleration, Euler Integration is fine (so RK4 is not needed).  Author comment: well if the car physics has constant acceleration it would be OK, but if the acceleration was non-constant (eg. changing gears, or changing the weight on the accelerator), then RK4 will give you less error than euler.  That’s really the point of this article, as per the best integrator for a simple constant acceleration situation, try this one: s = ut + 1/2at^2 it’s an exact solution

For anything beyond that (such as non-constant acceleration, force, momentum), one option is RK4.  RK4 can be used for single values, vectors, or even quaternions and matrices for rotational dynamics.  The article’s RK4 code can easily be modified to use 3d vectors, and to customize the acceleration() function.  A further example would be to switch from integrating velocity directly from acceleration(), and instead integrate momentum from force().

Comment: For multiple bodies with RK4, you integrate both bodies together, ideally you have a single method that returns an array of forces to apply to the points — you cant update each body independently with RK4.

Comment: Don’t disparage Verlet methods – RK4 is accurate enough for game simulations, but unfortunately does not conserve energy over long periods of time (which doesn’t really matter for game physics, but does if you want to do real physics). Google “symplectic integrators” for more details. [Verlet integration]

Author comment: i would not recommend RK4 unless your simulation suits this model well – RK4 is easy once you understand it, but structuring your simulation in this way is non-traditional, and difficult unless you are doing everything with spring forces

Author comment: for any interesting simulation acceleration is a continuous function of other variables such as current velocity (for example, drag), and position (springs). since these quantities change over the frame, the force which is a function of them also changes over the frame. in these cases, RK4 provides better accuracy – because [it] is able to detect and correct for these changes in acceleration over the timestep

Author comment: To get the benefits of RK4 it is essential that you recalculate all forces at each step of RK4, otherwise your drag force is constant over the frame time – and you are really just doing an euler integration

Constant Acceleration?

Someone in the comments points out it’s accurate to do “Euler integration” (or is it “ballistic integration”?) if acceleration is constant over the timestep:

d’ = d + v*t + 0.5*a*t*t
v’ = v + a*t

Later in the comments, someone explained: I’m intrigued, if acceleration is applied during the timestep, then the velocity isn’t constant and so the position must be calculated with respect to the acceleration. So, why wouldn’t the following work?

while ( t <= 10 )
{
float accel ( force / mass );
position+= (velocity*dt) + ((accel*(dt*dt))/2);
velocity+= accel * dt;
t+= dt;
}

The article’s author replied: that would actually work perfectly, and without error – given [constant] acceleration, but what about the case where acceleration is non-linear?  In this case RK4 works much better, because it can take into account change down to the fourth derivative, any error in RK4 is O(5) from the taylor’s series expansion.  So in the general case RK4 is better than the integrator that you present, but if you have a linear acceleration only, perhaps a ballistic point under constant gravity, then the integrator you presented works just fine.

I wrote a simple test program to show that with a constant acceleration, you can get 100% accuracy (ignoring double precision issues) without RK4.  The result was the same for for doing t in one timestep as doing t in 100 timesteps:

   1: void test()

   2: {

   3:     // p = p + v*dt + a*0.5*dt*dt

   4:     // v = v + a*dt

   5:     double p, v, a, dt, t;

   6:     double pStart = 50;

   7:     double vStart = 3;

   8:     a = 1;

   9:     t = 100.0;

  10:     dt = 1.0;

  11:  

  12:     // first try the full 100 in one step

  13:     p = pStart + vStart*t + a*0.5*t*t;

  14:     v = vStart + a*t;

  15:     printf("full: %.2f, %.2f\n", p, v); // 5350.00, 103.00

  16:  

  17:     p = pStart;

  18:     v = vStart;

  19:     for (double tSoFar = 0; tSoFar < 100.0; tSoFar += dt)

  20:     {

  21:         p = p + v*dt + a*0.5*dt*dt;

  22:         v = v + a*dt;

  23:         printf("%6.2f: %7.2f, %6.2f\n", tSoFar + 1.0, p, v);

  24:     }

  25: }

Author Comment: s = ut + 1/2at^2 gives exact results, but simple euler integration like this: v += a * dt, s += v * dt does not.  The reason being that the constant acceleration means that velocity is changing constantly, so the inaccuracy is incurred in the s += v * dt term

Game Loop code

TODO post my updated game loop that takes above notes into account?

Performance

Another article, http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/ , points out that you can adjust your time time step for a less accurate method to make it more accurate (but slower).  This is an issue to consider with different integration methods (Euler, RK2, RK4, Verlet).

Trackback this post | Feed on Comments to this post

Leave a Reply