First Post

So, I thought I’d try playing around with game physics. A long time ago, when I was about 14, I started programming. I really wanted to become a game programmer, and started learning C and C++, writing DOS programs on my 486. Writing directly to video memory (0A000h) in VGA mode 13h, optimizing the code with little assembler snippets. My highpoint was a demo for a friends BBS written completely in assembler, with a lovely lens effect and flames:

Soon though, my interest shifted more towards physics, and later mathematics, and I ended up with a PhD in mathematics earned by investigating wonderful properties of infinite dimensional representations of semi-simple Lie algebras. Now, many years down the line, my interest has move back towards programming, and I’ve decided to try and understand at least the basics of game physics modeling.

So, I started looking at simple integration methods. I was well acquainted with Euler and Runge-Kutta integration, but soon read about Verlet integration. Whereas in Euler integration you keep track of the position and velocity of a particle, in Verlet integration you keep track of the current and previous position of a particle. In that respect, they are equivalent, since you can get a velocity from the current and previous position, and vice versa. Where they differ are in the dynamics, how the new data are computed based on the current acceleration.

In Euler integration, you do

\(p_1 = p_0 + \Delta t v_0\),
\(v_1 = v_0 + \Delta t a_0\),

where \(v_0\) and \(p_0\) are the previous position and velocity, \(v_1\) and \(p_1\) are the new position and velocity, \(\Delta t\) is the time difference between frames, and \(a_0\) is the acceleration. Basically, at each time point you extrapolate what the position and velocity will be in the future based on the current velocity, position and acceleration.

In Verlet integration, you do the following instead:

\(p_1 = 2p_0 – p_{-1} + \Delta t^2a_0\),

where \(p_0\) is the current position, \(p_{-1}\) is the previous position, and \(p_1\) is the next position. If we solve the above equation for \(a_0\), we get

\(\displaystyle a_0 = \frac{p_1 – 2p_0 + x_{-1}}{\Delta t^2} = \frac{(p_1 – p_0) – (p_0 – p_{-1})}{\Delta t^2} = \frac{\frac{p_1 – p_0}{\Delta t} – \frac{p_0 – p_{-1}}{\Delta t}}{\Delta t}\).

Getting creative with our notation, we can write this as

\(\displaystyle a_0 = \frac{v_{\scriptstyle 1/2} – v_{-1/2}}{\Delta t}\),

i.e. we effectively use the velocity between our timepoints to compute the new positon \(p_1\). For various reasons, this gives a much better approximation than Euler integration. Actually, if the acceleration is constant, Verlet integration gives exact results.

So, to try this out I wrote a little test using OpenGL of a ball on a string affected by gravity, using Verlet integration. The string is modelled as a sequence of stiff springs, so in this example I also have constraints on the position of the endpoints of the springs, but I’ll leave that for the next point.