At the end of these great slides, the author compares all the different integrators presented. One way or another, they all fall short except for Improved Euler Integration and Runge Kutta 4 Integration, which both pass all tests.

I suppose I should mention that I am working on a 2D game that isn't very physics intensive. I'm just curious as to where Improved Euler Integration would fall short and RK4 would have to be used instead.

My game consists mostly of simple gravity (jumping and falling), movement along the X and Y axes, and bounding box collision. Is it worthwhile to implement RK4 or would Improved Euler be sufficient? I see many discussions where Euler Integration's users are chastised, but from what I can see, Improved Euler is quivalent in simple 2D matters. I imagine it'd also be faster.

  • \$\begingroup\$ offtopic, but those area great slides, very clear with the examples and all. Thanks for that link! \$\endgroup\$
    – Roy T.
    Mar 10 '12 at 8:06
  • \$\begingroup\$ If this is indeed off topic here it'd probably be a good fit at Computational Science. \$\endgroup\$
    – David Z
    Mar 11 '12 at 7:12
  • \$\begingroup\$ Also: Time-Corrected Verlet Integration - looks similar to Improved Euler: too lazy to figure out if it is exactly the same. TCV is great because you can be lenient with your fixed time step (other integrators want a guaranteed fixed time-step). \$\endgroup\$ Mar 14 '12 at 9:54
  • 1
    \$\begingroup\$ Can't edit: I see he mentions it. I am not sure if his implementation is bugged in terms of the initial conditions requirement as outlined by the article: but I have never seen that gravity issue with my implementation of TCV if I calculate the initial conditions correctly. \$\endgroup\$ Mar 14 '12 at 10:03

I personally prefer Velocity Verlet for most simulations. In my experience with this method, it is quite suitable for pretty stiff equations. It seems like this "improved Euler" method is pretty similar to the Velocity Verlet one and relies on a class of integration methods known as predictor-corrector. You can read a lot of things on these methods nowadays, starting with David Baraff's "Large steps in cloth simulation" where the power of implicit methods really shines. Their downfall is that you:

  1. have to approximate Jacobians or Hessians and then have to,
  2. compute a fair amount of matrix inverses per frame.

So if you're not a math guru, you could get your fingers stuck. Just experiment with whichever method you want and then settle for the one that seems to perform best for you. Simple is not always better, but for interactive framerates I only know one word: compromise.

Some additional resources you might want to look at:

Jakobsen is a sort of genius for coming up with such a simple idea for pretentious problem (his specialty is Cryptography if not mistaking, but he succeeded in proving the mathematical equivalence of his method to a class of Gauss-Seidel iterative algorithm, which is convergent). For simplicity, go for this first before delving deep into implicit methods.

LATER EDIT: I recently got a paper on this issue of using explicit integrators for soft or semi-rigid body simulation and what their performance and quality impact is. This paper should serve as a guide for choosing a certain integrator, depending on the scenario.

  • 1
    \$\begingroup\$ +1 This was actually a really good quality answer in terms of content: but it was a tad too difficult to digest (wall of text). I found that good formatting always helps get up-votes. I improved it and hopefully you get the up-votes you deserve. \$\endgroup\$ Mar 14 '12 at 11:24
  • \$\begingroup\$ Thanks Jonathan, I've done it hastily, disregarding the "reader friendly" procedure, but I had to mention those few sources as they're really very frequently used even today). \$\endgroup\$
    – teodron
    Mar 14 '12 at 11:50

Q: Why use the advanced Runge Kutta?
A: Because it's very exact.

Q: Why not?
A: Because you are making a game and a very exact physics engine doesn't matter, it just has to be good enough to fool the player.

By the way, if you have got heavy dampening on collision, like most platformers would, a simple Euler is just fine.

I strongly recommend that you unlike the code in the presentation use fixed step physics, which saves you some potential glitches, and lets you solve the problem of the ball gaining or losing energy in a very simple fashion. Just go for the middle ground between explicit and implicit integration:

velocity += 0.5 * acceleration;
position += velocity;
velocity += 0.5 * acceleration;

What the presentation doesn't show is how to handle collisions so that objects don't appear to go beyond the boundaries. The simple solution to that problem is to use a high update frequency. A more complex but potentially better performing solution is to move objects back at the time of collision, exact implementation depends on desired physics behaviour.

  • 1
    \$\begingroup\$ +1 for "fooling the player" - but I have personally had 'very simple' systems explode because of euler integration. \$\endgroup\$ Mar 14 '12 at 9:49
  • \$\begingroup\$ @JonathanDickinson I'd say that it's not because of Euler integration, but rather because of a mix of circumstances, Euler integration being just one of them. If you have an example I'm sure that I can find a way of avoiding exploding systems. \$\endgroup\$ Mar 14 '12 at 11:14
  • \$\begingroup\$ Oh it's on some really old VB6 stuff (when I was literally about 14) of mine before I learnt about RK/Verlet - I don't even have the code anymore: which gives high credence to the fact that it might have been something else in the mix :). \$\endgroup\$ Mar 14 '12 at 11:16
  • 1
    \$\begingroup\$ I guess I should add that as soon as you start messing with attraction between objects rather than just simple gravity it does seem reasonable to me to step up the integration method, it may not be strictly necessary, but if you have got the processing power the only downside is slightly more complex code. \$\endgroup\$ Mar 14 '12 at 11:19

The presentation has error. The method referred to by presenter as "Improved Euler" is actually Velocity Verlet method!

See here for more authoritative source: http://www.physics.udel.edu/~bnikolic/teaching/phys660/numerical_ode/node5.html

Also same equations are in Wikipedia.

A common immediate improvement over Euler's method is Midpoint method which what presenter probably had in mind but ended up mistaking Velocity Verlet as improved Euler. The only different between Midpoint method and Velocity Verlet is that velocity is average of last and next acceleration instead of just dependent on last acceleration.


Not the answer you're looking for? Browse other questions tagged .