Understanding basic motion calculations in games: Euler vs. Verlet

During the past month, I have found myself in the position of having to explain the contents of this article to six different persons, either at work or over the Internet. Though there are a lot of articles on the subject, it’s still as if almost everyone gets it wrong. I was still polishing this article when I had the opportunity to explain it ​a seventh time.

And two days ago a coworker told me the source code of a certain framework disagreed with me… The kind of framework that probably has three NDAs preventing me from even thinking about it.

Well that framework got it wrong, too. So now I’m mad at the entire world for no rational reason other than the ever occurring realisation of the amount of wrong out there, and this article is but a catharsis to deal with my uncontrollable rage.

A simple example

Imagine a particle with position Pos and velocity Vel affected by acceleration Accel. Let’s say for the moment that the acceleration is constant. This is the case when only gravity is present.

A typical game engine loop will update position with regards to a timestep (often the duration of a frame) using the following method, known as Euler integration: 

Particle::Update(float dt)
{
    Accel = vec3(0, 0, -9.81); /* Constant acceleration: gravity */
    Vel = Vel + Accel * dt;    /* New, timestep-corrected velocity */
    Pos = Pos + Vel * dt;      /* New, timestep-corrected position */
}

This comes directly from the ​definition of acceleration:

\[a(t) = \frac{\mathrm{d}}{\mathrm{d}t}v(t)\] \[v(t) = \frac{\mathrm{d}}{\mathrm{d}t}p(t)\]

Putting these two differential equations into Euler integration gives us the above code.

Measuring accuracy

Typical particle trajectories would look a bit like this:

These are three runs of the above simulation with the same initial values.

  • once with maximum accuracy,
  • once at 60 frames per second,
  • once at 30 frames per second.

You can notice the slight inaccuracy in the trajectories.

You may think…

“Oh, it could be worse; it’s just the expected inaccuracy with different framerate values.”

Well, no.

Just… no.

If you are updating positions this way and you do not have a really good reason for doing so then either you or the person who taught you is a fucking idiot and should not have been allowed to write so-called physics code in the first place and I most certainly hope to humbly bestow enlightenment upon you in the form of a massive cluebat and don’t you dare stop reading this sentence before I’m finished.

Why this is wrong

When doing ​kinematics, computing position from acceleration is an integration process. First you integrate acceleration with respect to time to get velocity, then you integrate velocity to get position.

\[v(t) = \int_0^t a(t)\,\mathrm{d}t\] \[p(t) = \int_0^t v(t)\,\mathrm{d}t\]

The integral of a function can be seen as the area below its curve. So, how do you properly get the integral of our velocity between t and t + dt, ie. the green area below?

It’s not by doing new_velocity * dt (left image).

It’s not by doing old_velocity * dt either (middle image).

It’s obviously by doing (old_velocity + new_velocity) * 0.5 * dt (right image).

And now for the correct code

This is what the update method should look like. It’s called Velocity Verlet integration (not strictly the same as Verlet integration, but with a similar error order) and it always gives the perfect, exact position of the particle in the case of constant acceleration, even with the nastiest framerate you can think of. Even at two frames per second. 

Particle::Update(float dt)
{
    Accel = vec3(0, 0, -9.81);
    vec3 OldVel = Vel;
    Vel = Vel + Accel * dt;
    Pos = Pos + (OldVel + Vel) * 0.5 * dt;
}

And the resulting trajectories at different framerates:

Further readings

“Oh wow thank you. But what if acceleration is not constant, like in real life?”

Well I am glad you asked.

​Euler integration and ​Verlet integration are part of a family of iterative methods known as the ​Runge-Kutta methods, respectively of first order and second order. There are many more for you to discover and study.

  • Richard Lord did this nice and instructive ​animated presentation about several integration methods.
  • Glenn Fiedler also explains in ​this article why idiots use Euler, and provides a nice introduction to RK4 together with source code.
  • Florian Boesch did a ​thorough coverage of various integration methods for the specific application of gravitation (it is one of the rare cases where Euler seems to actually perform better).

In practice, Verlet will still only give you an approximation of your particle’s position. But it will almost always be a much better approximation than Euler. If you need even more accuracy, look at the ​fourth-order Runge-Kutta (RK4) method. Your physics will suck a lot less, I guarantee it.

Acknowledgements

I would like to thank everyone cited in this article, explicitly or implicitly, as well as the commenters below who spotted mistakes and provided corrections or improvements.

  • Posted: 2011-12-14 00:39 (Updated: 2011-12-15 14:34)
  • Author: sam
  • Categories: rant code physics

Attachments

Comments

1. mikarnage -- 2011-12-14 15:47

Hi,

Nice explanation, I would have liked to see the case about what happens with a spring+mass+friction system : from experience, rather than just a slight loss in precision, you can get into cases where the system gets unstable and explodes, rather than just slowly decreasing in amplitude..

2. sam -- 2011-12-14 16:07

@mikarnage: I would like to write another article about RK4 to illustrate that! Verlet would still help in comparison with Euler, but higher-level methods are really needed. The bane of RK4 is that it is so simple, yet so hard to explain. I hope to be able to get to-the-point diagrams like this one:

3. geolm -- 2011-12-14 18:32

"Your physics will suck a lot less, I guarantee it" true but the CPU cost is too high... that's why havok still use that dirty-euler-integration. Anyway nice article :)

geolm

4. Richard -- 2011-12-14 21:55

Hi Sam

The term "Verlet integration" is more commonly used to describe Störmer's original method, which improves stability in some situations (e.g. with springs) by completely avoiding the use of the velocity when calculating the position. The method you have called "Verlet" goes by many names, including "Velocity Verlet" and "Improved Euler", but to simply call it "Verlet" is not strictly correct. It is, as you say, much better than the standard Euler integration.

​This presentation I did some years ago may be of interest, towards te end it compares the Euler integration (explicit and implicit) with the improved Euler (aka velocity Verlet), the 4th order Runge-Kutta and the Verlet (Störmer's original) in various circumstances.

5. Richard -- 2011-12-14 22:09

Hmm, the link to the presentation didn't work. And I can't add it now because trac thinks I'm spamming. Sorry.

Also, geolm, I last used Havok many years ago and even back then they offered the choice of Euler integrator, velocity Verlet integrator, and 4th order Runge-Kutta. The default was Euler, but the others were offered. What made it particularly flexible is you could chose to use the more accurate integrators on specific objects only.

6. Promit -- 2011-12-14 22:24

Sorry, but using Verlet or RK4 is not a good idea in a physical simulation. Neither integrator is good at preserving energy properly in the system, so you can get pretty severe instabilities as things explode or grind to a halt. For game simulation purposes, you're vastly better off with the semi-implicit Euler method.

7. anonymous -- 2011-12-15 11:34

http://lol.zoy.org/tracmath/571293ea6792e5f554ea216394ac33cd75ecc56b.png

Why is this true? is it mistake?

I thought a(t) = dv/dt; v(t) = dp/dt;

8. Valentin Simonov -- 2011-12-15 11:34

Err, about your definition of acceleration. v(t) = d p(t) / dt a(t) = d v(t) / dt

I wonder how nobody else noticed this.

9. sam -- 2011-12-15 12:15

@Valentin: that is indeed a mistake! I'm gonna fix that immediately, thanks.

10. sam -- 2011-12-15 12:21

@Richard: thank you for the suggestions, I will make it clearer that it is not strictly Verlet. And sorry for Trac's aggressive antispam behaviour: it gets pounded extremely hard by spambots so the Bayesian filter has become trigger-happy. I will put the link back in your comment. (I use this blog system because it lets me write maths and format source code very easily, but it's clearly not the nicest engine out there).

11. marco -- 2011-12-15 12:33

Lol, love that article. Extremely well presented, keep up (good work, humour, ...)!

12. mmick66@gmail.com -- 2012-04-27 20:22

Is this method of averaging velocities not identical with RK2?

13. sam -- 2012-04-28 13:15

@mmick66: you are right, when acceleration is constant, Velocity Verlet and RK2 become identical.

14. TheodorC -- 2013-01-07 16:36

Hi Sam,

I did, not a long time ago, a small survey on popular explicit integration methods. What I found in terms of terminology (unintended wordplay) was that your "Velocity Verlet" is actually the same as the "midpoint method". You can find some of these popular integrators mentioned in Appendix A of this paper -> ​https://www.dropbox.com/s/nfj4it6jjugfhdp/DLOReport.pdf . As I understood it, Velocity Verlet requires using a velocity prediction to find the future position, then correct/update the velocity to obtain a somewhat more synchronized pair (pos, vel). Thus, Velocity Verlet would evaluate the acceleration twice per step: the first time to get the position, then to get the corrected velocity using the updated position and the velocity prediction. Is this view correct, or have I misunderstood it badly?

As a sidenote, it might be worth mentioning some of the traits of symplectic integrators (such as Verlet): they preserve energy for closed systems (or area if you consider a parallelogram of initial conditions). RK4 is not symplectic, although being more accurate than Euler, it still introduces energy in the system and can make it explode. I don't have the links now, but there were some articles mentioning the possibility of making RK4 numerically damp the solution, thus having a somewhat more increased stability (and, of course, no symplicity whatsoever).

All in all, great articles/posts on numerical issues and C++, the community is grateful for you sharing this knowledge in such a concise and pertinent way!

Best wishes, Theodor

15. mcintyre321@gmail.com -- 2013-04-10 17:51

What about storing the position and time the acceleration was last changed, and doing the calculation from there?

Also, should Vel = Vel + (OldAccel + NewAccel) * 0.5 * dt; and if not, why not?

thanks!

Add New Comment


Note: the spam filter is extremely sensitive; don't worry! Even if it is detected as spam, your comment will be manually approved.