title: Runge-Kutta (RK4) integration for game physics
body: <p>Gaffer on Games has a <a href="http://gafferongames.com/game-physics/integration-basics/" rel="noreferrer">great article</a> about using <a href="http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods" rel="noreferrer">RK4 integration</a> for better game physics. The implementation is straightforward, but the math behind it confuses me. I understand derivatives and integrals on a conceptual level, but haven't manipulated equations in a long while.</p>
  
  <p>Here's the brunt of Gaffer's implementation:</p>
  
  <pre><code>void integrate(State &amp;state, float t, float dt)
  {
       Derivative a = evaluate(state, t, 0.0f, Derivative());
       Derivative b = evaluate(state, t+dt*0.5f, dt*0.5f, a);
       Derivative c = evaluate(state, t+dt*0.5f, dt*0.5f, b);
       Derivative d = evaluate(state, t+dt, dt, c);
  
       const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx);
       const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv)
  
       state.x = state.x + dxdt * dt;
       state.v = state.v + dvdt * dt;
  }
  </code></pre>
  
  <p>Can anybody explain in simple terms how RK4 works? Specifically, why are we averaging the derivatives at <code>0.0f</code>, <code>0.5f</code>, <code>0.5f</code>, and <code>1.0f?</code> How is averaging derivatives up to the 4th order different from doing a simple euler integration with a smaller timestep?</p>
  
  <hr>
  
  <p>After reading the accepted answer below, and several other articles, I have a grasp on how RK4 works. To answer my own questions:</p>
  
  <p><strong>Can anybody explain in simple terms how RK4 works?</strong></p>
  
  <blockquote>
    <p>RK4 takes advantage of the fact that
    we can get a much better approximation
    of a function if we use its
    higher-order derivatives rather than
    just the first or second derivative.
    That's why the <a href="http://en.wikipedia.org/wiki/Taylor_series" rel="noreferrer">Taylor series</a>
    converges much faster than Euler
    approximations. (take a look at the
    animation on the right side of that
    page)</p>
  </blockquote>
  
  <p><strong>Specifically, why are we averaging the derivatives at <code>0.0f</code>, <code>0.5f</code>, <code>0.5f</code>, and <code>1.0f</code>?</strong></p>
  
  <blockquote>
    <p>The Runge-Kutta method is an
    approximation of a function that
    samples derivatives of several points
    within a timestep, unlike the Taylor
    series which only samples derivatives
    of a single point. After sampling
    these derivatives we need to know how
    to weigh each sample to get the
    closest approximation possible. An
    easy way to do this is to pick
    constants that coincide with the
    Taylor series, which is how the
    constants of a Runge-Kutta equation
    are determined.</p>
    
    <p><a href="http://web.mit.edu/10.001/Web/Course_Notes/Differential_Equations_Notes/node5.html" rel="noreferrer">This article</a> made it clearer for
    me. Notice how <code>(15)</code> is the Taylor
    series expansion while <code>(17)</code> is the
    Runge-Kutta derivation.</p>
  </blockquote>
  
  <p><strong>How is averaging derivatives up to the 4th order different from doing a simple euler integration with a smaller timestep?</strong></p>
  
  <blockquote>
    <p>Mathematically, it converges much
    faster than doing many Euler
    approximations. Of course, with enough
    Euler approximations we can gain equal
    accuracy to RK4, but the computational
    power needed doesn't justify using
    Euler.</p>
  </blockquote>