RK4 isn't trapezoidal (which is still first order linear), RK4 is 4th order. Do keep in mind that that there's more involved than most of the basic descriptions of the integrators give, and many sites' descriptions are wrong. Not their descriptions of the algorithms, but rather their description of the algorithms' properties. Personally I'm strongly against RK4, as it's not symplectic and I feel that any integrator used in games should be. Semi-implicit euler is fine for most uses, and velocity verlet is fine but you don't get a lot of bang for your buck.

(Man I really hope I said that correctly.)

While writing a 2D platformer for Android and PC I came across an issue with my physics. My computer, running at 60 fps had a different jump height than my phone, running at 30. Also, the jump height would be different between jumps. I solved this by implementing Euler integration for my physics. Along the way, I also read about velocity Verlet and the fourth order Runge-Kutta method, which also seem to be popular. My question isn't about specific implementation of the 3, I wanted to ask about the three in comparison to integral approximation used in calculus.

Euler integration seems to be a simple left- or right-endpoint rectangular approximation. Velocity Verlet seems to be a midpoint rectangular approximation and last night, while I should have been sleeping, was thinking about RK4 and thought it sounded like a trapezoidal approximation. Is that right?

I largely agree with Promit -- with respect to games there aren't many integrators that make a lot of sense beyond the simplest. My personal preference is the semi-implicit Euler because it is robust and very simple to implement.

Runge-Kutta methods are pretty deep. They represent a whole family of integrators with various properties and orders. The so-called RK4 is the work-horse for a lot of ODE problems. It is often the first integrator that someone working in the area will turn to because it is relatively simple (for Runge-Kutta), good performance, and very robust. However, in games, the benefits of using RK4 are usually not worth the additional complexity.

-Josh

What further reading would you suggest on the integrators Promit?

I wish I had a good source for you. I worked through a large patchwork of discussions, papers, etc. Wikipedia's basic information is good but it lacks organization which makes it difficult to form a complete picture. (And some of the articles are nigh on impenetrable unless you already know what you're reading.) The key point for me was understanding that an integrator A is not simply 'better' or 'worse' than integrator B. There are quite a few different properties that vary and choosing an integrator when doing physics work is practically an art form in its own right. There are a lot out there.

The reason I'm so particular about symplectic integrators for games is they conserve energy, which in practical terms means they're much more resistant to simulation explosions. Our physics work involves a lot of springs, soft bodies, etc and these things do much better with energy conservation. Too much energy and they blow up, too little and they damp unnaturally. Semi-implicit euler and Velocity Verlet are the most accessible of the symplectic integrators, and my personal take is that VV isn't worth the extra computational time. RK4 can be made symplectic but it's not easy and it's not cheap.