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:
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.
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.
Attachments (5)
- derp.png (1.7 KB) - added by sam 2 years ago.
- no-rage.png (105.3 KB) - added by sam 2 years ago.
- euler-integration.png (11.2 KB) - added by sam 2 years ago.
- verlet-integration.png (6.3 KB) - added by sam 2 years ago.
- accurate-integral.png (5.8 KB) - added by sam 2 years ago.
Download all attachments as: .zip
Comments
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..
@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:
"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
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.
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.
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.
Why is this true? is it mistake?
I thought a(t) = dv/dt; v(t) = dp/dt;
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.
@Valentin: that is indeed a mistake! I'm gonna fix that immediately, thanks.
@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).
Lol, love that article. Extremely well presented, keep up (good work, humour, ...)!
Is this method of averaging velocities not identical with RK2?
@mmick66: you are right, when acceleration is constant, Velocity Verlet and RK2 become identical.
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
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!
Hi Sam,
I wish i found out about this article earlier.. The visual you presented made things a lot more clear to me! I'm currently trying to get an idea of what the difference is between integrators, but got stuck pretty quickly before stumbling on your article. I get things better when they're presented in a visual way or analogy instead of dry formula's.
As much as your picture cleared up the difference between euler and verlet for constant acceleration for me, I was hoping you could maybe clear a couple other things im not sure about..
You visualize how the area of the verlet integration function is given by: (old_velocity + new_velocity) * 0.5 * dt. So this works better than euler in this specific case, because for a constant acceleration, the graph between the old & new pos would be connected by a line and thus it's area can be perfectly fitted by a trapezoid. Is it safe to conclude that just like euler already has errors for constant acceleration, verlet will have errors just like euler when integrating non constant acceleration? And the error for Euler will even increase in comparison to verlet?
I also read that energy can get lost or is kept equal with some integrators, what does this exactly mean? Has it to do with these errors that add up or decrement during integration?
Is the example that Richard gives in the gravity example (one of the last slides) an example of RK4 not losing energy?: http://www.richardlord.net/presentations/physics-for-flash-games The verlet integrator seems to realisticly come at rest while the rk4 keeps going.. or was it not supposed to come at rest and was this because of "energy leaking" from the system?
And is the gravity example given here an example of errors adding up for verlet in non constant acceleration?: http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/ And why would it perform worse than euler here?
Also this "stability" they sometimes talk about (mostly when discussing springs), how is that related?
Thanks!
Martijn
Your posted method is a degenerate version of velocity verlet (which I'm sure goes by several different names, all of which are confusing), in the case of constant acceleration. The one for the case where you have an acceleration() function (usually the case I guess) is this: http://en.wikipedia.org/wiki/Verlet_integration#Velocity_Verlet
The difference with your method is the velocity, where you just do forward Euler on the velocity, normally velocity Verlet averages the current acceleration and the acceleration of the predicted position. You can keep this acceleration around for the next invocation so you save actually evaluate the force function only once. You'll make a small error in case the acceleration function depends on velocity (drag forces, ...) as well, but hey, can't win 'em all.
As wikipedia says, some implementations even add another correction step, not sure how much it helps but it looks cheap (just one FMA-op).