physics - Pros and cons of different integrators

When creating things like physics in games you need an integrator. I've seen Verlet integration mentioned several places as a great alternative to Euler integration. For instance in the famous document by Thomas Jakobsen. However in this article Glenn Fiedler writes:

Rather than introduce you to the vast array of different integrators that exist, I’m going to cut to the chase and go straight to the best. This integrator is called the Runge Kutta order 4 integrator aka RK4.

So apparently there's no silver bullet. What is the pros and cons of different integrators? Regarding simplicity, speed, accuracy, stability, etc. Which integrators is most suitable for which types of games? When would you use Verlet, RK4 or others? Should you ever use Euler?

Answer

Pros and cons of both methods:

RK4 Pros:

1. accuracy (thanks to its better approximation series it yields a 4th order precission)


2. artificial/inherently induced damping (a bit like implicit methods do it) adds stability (whereas a simple Euler step doesn't - it does the opposite actually, introducing ghost energy that builds up and could plunge the system into chaos)

RK4 Cons:

1. computation expense: while not that demanding in comparison to implicit methods or hybrid IMEX methods, RK4 is 4 times more expensive than the explicit Euler since it requires that many more function evaluations. This shows when aiming for the bleeding edge of optimization.


2. still unstable: depending on the types of forces involved, RK4 can be just as unstable as Euler. On average, RK4 is a bit more stable and tends to draw this benefit from its endowed damping "skills".


3. Non-symplectic: numerical damping comes with a cost - you cannot simulate systems where energy/volume/etc. loss shouldn't apply a visible effect over time (e.g. Molecular Dynamics, Potential Field derived forces, variational problems)

Verlet Pros:

1. once or two times the complexity of an Euler step (depending on your Verlet flavour: position or velocity).


2. symplectic: conserves internal energy



3. second order accuracy: many games do not require high precision floating point results, and second order is more than pleasing for the eye in a game scenario (plus: it was used in a non-gaming scenario simulation when it was "discovered", so it's not that bad)

Verlet Cons:

1. stable, but still: probably the best explicit method in terms of stability. It tends to win the edge when hard constraints are added to the system, thus allowing for less head-aches when implementing projected constraints in position based dynamics engines. It sets off to infinity if the system is perturbed with large external forces and no damping/friction is added. Even so, there are certain numerically imposed limits to how large the internal (spring) forces can be, but they're higher on average than what RK4 can do


2. lower accuracy: not useful if you want high precission estimations


3. requires, on average, smaller time-steps than RK4 for some simulations (RK4 benefits from both its accuracy and internal damping)

Using one over the other depends on the scenario. If stiffness and large external forces and virtual energies are a problem, then consider other methods having the "implicit" word in their description/title.

---

Note some authors/books use the term semi-implicit Euler for an actual explicit Euler integrator called the symplectic Euler method (or Euler Cromer) from which Verlet is actually derived. Verlet is also called by some people the "leapfrog method". Velocity Verlet and the midpoint method are fairly similar since an estimation at a time step of t + 0.5*dt is required for a predictor-corrector-like step. IMEX methods (implicit-explicit) are also used to name two similar but not identical approaches: separate the computations into stiff and non-stiff parts and use different integrators on them (the explicit for non-stiff, implicit for stiff) OR solve for the velocity with an implicit update step and update the position in an explicit manner (this is a hybrid semi-implicit method falling on the IMEX class of methods because the stiff parts affect the acceleration computation the most). Implicit methods are more cumbersome and require solving a system of simultaneous non-linear equations for the entire configuration. Implicit methods are used for deformable bodies and usually aren't used for decoupled rigid bodies.

As stated in one of the comments, if you can, do not use Euler. Use either the midpoint method, the semi-implicit Euler or, at the same expense, the position-Verlet. All of them have slightly higher accuracy and sensibly more stability than the explicit Euler integrator.

Recommended mini-comparison reading:

http://wiki.vdrift.net/Numerical_Integration