Why use Runge Kutta Integration over Improved Euler Integration?

Question

I was reading these slides (very good by the way!), and if you skip all the way to the end the author compares all the different integrators presented.

In one way or another, they all fall short except for Improved Euler Integration and Runge Kutta 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 was just curious as to where Improved Euler Integration would fall short and Runge Kutta would have to be used instead.

My game mostly just consists of simple gravity (jumping and falling), movement along the X and Y axis, and bounding box collision. Would it be worth it to use Runge Kutta in that case or would Improved Euler integration be sufficient? I see in many discussions where users of Euler Integration are chastised but from what I can see it seems equivalent in simple 2D matters (the improved one, that is). Also, I'd imagine it'd be quite faster than Runge Kutta.

Thanks!

Edit: So apparently Euler Integration and Improved Euler Integration are a part of the family of Runge Kutta integration. That may have been confusing. When I am referring to Runge Kutta in this post I mean RK4.

Answer 1

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.

Answer 2

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's "Advanced Character Physics"
• James McCarthy's "Comparison of Simulation Techniques using Particle Systems"

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.