Before there was BoxCAD…
There was…
RBS! (Rigid Body Simulator)
About a year ago, I had an idea for a funny little game in Visual Basic (yes, Visual Basic). What was supposed to take a few hours ended up taking most of 2008…
My game concept depended on realistic physics – but I didn’t know the first thing about physics. So I decided to tackle that problem separately, before trying to build the game. So, out came my notebook, and dozens of arduous trig equations later – I’d gotten nowhere. So – to Google I went (I usually make an effort to figure stuff out before hitting the The Oracle – it’s good for my self-esteem).
It wasn’t long before I stumbled upon the infamous Paper by Thomas Jakobsen on Verlet integration (as a fast, though not-as-accurate alternative to Euler).
Euler integration is what you get if you take the physics equations out of a physics textbook and plunk ‘em down in your code. It’s conceptually straightforward (though devilish details abound). Verlet integration was immediately fascinating to me because it was very non-intuitive. I had to work through several iterations of a point’s movement just to see what was going on.
Verlet integration simplifies a whole lotta crap in certain areas. The major factor is – a node can be manually translated arbitrarily, and the algorithm will factor in the new position, automatically handling velocity, rotation (for a multi-node body), etc. This differs from Euler where – if you manually translate a body, you’ve gone done screwed up the equations, and the results are unpredictable. The correct way to modify position in a Euler system is indirectly, by applying forces to the node as necessary to change it’s acceleration, therefore velocity, therefore position.
What does this ability to manually translate nodes mean for us? For me, the important factor was – massively simplified constraints. My objective with the verlet engine was to be able to create distance constraints, thus ragdoll systems. Looking at the image to the left, a distance constraint is an interaction between two nodes that attempts to maintain a constant separation. The blue line in the image is the constraint. The basic idea is – after each constraint-free position-computation by the engine, all nodes/bodies will be in a new location; the next step in the physics engine is to check how those new positions conform to the constraints. Position correction is applied to those nodes/bodies who are more or less than the specified distance apart.
In a Euler system, you would apply a corrective forceto the offending nodes, since you’re not allowed to manually move them. Performing the necessary computations is no walk in the park. Verlet, on the other hand, doeslet you manually translate nodes – which means, to maintain the constraint, you do something like this:
Step 1: Find the difference between the current distance between the nodes, and the specified constraint distanced.
Step 2: Distribute half of that difference to each node (assuming node masses are the same).
If you’re constraint is specified as 5 units, and after computing position, the distance between the nodes is 6 units – then you pull both nodes in by 0.5 units (half of the difference).
And that’s it. The integration takes care of forces, acceleration, momentum, rotation – everything.
I very distinctly the first run after getting my verlet implementation to compile for the first time. It was truly eerie, seeing such complex behavior come out of so little code!
In a system with many inter-related constraints (see image to the right), it requires several passes over the correction algorithm to converge on the system’s solution satisfactorily. That’s not really a problem though, as the algorithms are very fast.
ANYway, after plugging away at my verlet engine for a couple of months, I had RBS to show. At that point, I was in love with physics engines, and had completely forgotten my “few hours of coding” game idea.
With the original, more advanced RBS (Visual Basic), there are some ideas I’d actually like to explore, if I ever get back to it. In the image (at the top of the post), the nodes are colored by velocity. Playing with different configurations of colors/constraints/physics can produce some very mesmorizing and interesting effects.
Somewhere in there, I took on the task of learning ActionScript – Flash’s language. Before long there was the flash-based, simplified RBS (link to source at the bottom of this post). It didn’t take long to realize I was wasting my time with AS2. So I upgraded to AS3. That opened up a few doors. Among them was the availability of open-source physics engines. Out of curiosity, I downloaded and played with a couple – APE and Box2D. I didn’t care for APE, as it had some quirky collision handling, with shapes getting stuck inside one-another frequently (if they were moving fast). For that simple – and probably easily correctable - reason, I tilted towards Box2D.
I built a small “practice” project to experiment with. Suddenly, it is 7 months later, and BoxCAD consists of about 37 files and thousands of lines of code – by far the most complex project I’ve experienced.
BoxCAD is a very exciting project, and I have big plans for it. But sometimes – it’s therapeutic to mess around with the very simple RBS flash app. Try it. 
And if you’re curious, here’s the verlet source code. Just keep in mind – this was a “Flash Initiation” project, so it’s pretty durn sloppy.
External Links:
http://www.teknikus.dk/tj/gdc2001.htm - Advanced Character Physics (Thomas Jakobson)
http://box2d.org/ - home of the Box2D Physics Engine – courtesy of Erin Catto
http://www.cove.org/ape/ - APE physics engine – which I have yet to really explore.
