Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
There's an SO answer you might fancy stackoverflow.com/questions/2769466/… –  teodron Aug 6 '12 at 12:21
    
Thanks for the link. I'm already aware of it though. –  paldepind Aug 6 '12 at 14:09
add comment

3 Answers 3

up vote 14 down vote accepted

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

share|improve this answer
    
One observation: both Verlet variants can be coded to evaluate the acceleration only once per frame update. –  teodron Aug 8 '12 at 8:10
1  
+1 for brevety! –  Timothy Groote Aug 9 '12 at 12:54
1  
Thanks for the answer! Pretty much what I was looking for. –  paldepind Aug 11 '12 at 14:26
add comment

Euler implementations tend to be very fast, but far less stable than the alternatives. Runge Kutta is slower than Euler, but far more precise and stable.

I'm not very knowledgeable on Verlet integration, so i have no idea how it stacks up against Euler and Runge Kutta.

If you need your simulations to be more exact, or even numerically proof, Runge Kutta is the better of the two.

If you need fast, low cost physics for a simple game, Euler is the better choice.

share|improve this answer
1  
Runge Kutta is by FAR NOT MORE STABLE THAN EULER. It's still Euler, done 8 times per frame instead of 1 (with a bit of prediction and correction but still..) forums.evilmana.com/game-programming-theory/… –  teodron Aug 6 '12 at 12:05
2  
Depends of what you need to be 'stable'. perhaps i should have elaborated, runge kutta is numerically more stable than euler. farside.ph.utexas.edu/teaching/329/lectures/node35.html –  Timothy Groote Aug 6 '12 at 12:07
2  
As far as I can figure out there's no reason why Verlet would be slower than Euler. So compared to Verlet Euler has no speed advantage and it's still much more precise and more stable. Hence I think your claim that Euler is best for a fast and simple physics is incorrect. –  paldepind Aug 6 '12 at 14:20
3  
Here is a blogpost showing the vast difference in accuracy: kahrstrom.com/gamephysics/2011/08/03/euler-vs-verlet –  paldepind Aug 6 '12 at 14:29
1  
Explicit Euler also introduces extra energy into the system (it travels "forward into the unknown" and silently drifts away from the energy level the system was in towards a higher one). That's what happens with spring oscillators where there's no damping involved. The picture can be viewed here: reference.wolfram.com/mathematica/tutorial/NDSolveSPRK.html –  teodron Aug 6 '12 at 14:54
show 3 more comments

First and foremost I think you should use Euler until you experiance a direct need to use a more advanced integration scheme. It is fast and easy to implement.

If you experience stability issues such as systems of springs that never come to rest or if your simulation requires a high level of accuracy then start experimenting with the others.

One that I haven't seen mentioned above is the midpoint method which is very easy to implement and only requires one extra integration step.

share|improve this answer
    
I think Verlet is just a simple and easy to implement –  paldepind Aug 9 '12 at 12:06
    
I've never used it myself but from what I understand you're probably correct. –  Mikael Högström Aug 9 '12 at 14:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.