Verlet Integration

I did a presentation a while ago about about some of my work with physics engines in flash (at the University of Birmingham). A large section of the talk focussed on verlet integration, which is the method I use to move particles in all of the engines I write. In my opinion if you're playing with large numbers of particles, this is the best way of manipulating them! I first got introduced to Verlet through a fantastic article by Thomas Jakobsen of IO Interactive, about his work on the Hitman physics engine, which was used in the game.

So where do we begin... Maths, always maths. A bit of fairly basic calculus and some Taylor expansions see us through to the final expression for verlet integration and I won't go into the details but the the core idea is that by calculating the position of a particle at the next time-step using the difference between its current position and its previous position, the margin of error can be dramatically reduced.

Here is the final derived expression.

You should be able to see that if we multiply out by the time interval delta-t we are given an expression for the position at the next point in time, which is how we'll use the equation.

This is especially useful in molecular dynamics where positions might be easier to measure than velocities. Obviously if we know positions at two time steps we can also calculate the resulting velocities which is fantastic for collisions and so on.

So, the basic algorithm.

Each particle needs to store two locations, its current location (x,y) and its previous location (px,py). To calculate its next position all we have to do is take the differences between these positions and move the current location by that much. You'll notice that the velocity lags on step behind the positions. This is ideal for calculating collisions for games!

In actionscript pseudocode:

var current:Point = (0,0);

var previous:Point = (0,0);

var tx:Number = 0;
var ty:Number = 0;

tx = current.x;
ty = current.y;

current.x += (current.x - previous.x + F)*R
current.y += (current.y - previous.y + F)*R

previous.x = tx;
previous.y = ty;

As you can see the current value is stored, then the difference between the current and previous value is added on to the current value and the "previous current value" is stored as the previous value. Just 6 lines of code for the main loop, pretty nice.

Another nice feature using the verlet operator is the F and the R values that I have added in.

From a physical perspective F acts as a force, and R acts as resistance. For example if you have some particles in space, gravity might act on them. Gravity acts downwards (this is +ve y axis in flash) so we'll call F in the vertical direction 9.81 (or how ever strong you want your gravity to be) and hey presto, your particle should fall! Now what about air resistance, our giant digital particles will be bouncing off millions of tiny little air particles when they slow down. Obviously as they go faster their speed will increase so the resistive force should also increase. If you set R to 0.99 the velocity will be retarded, and this retardation will be increased as the velocity increases (this isn't in fact entirely true to a real life interpretation of air resistance but it will definitely suffice in a computer game). There we have it, a particle system with forces and resistance.

This very same system can easily include a third dimension, since all of the dimension vectors are completely independent of one another. Hang around and I'll talk about constraints and collision detection using verlet integration.

Enjoy your newfound particle system knowledge.