generalrelativity

I’m officially free of the shackles of full-time employment since I decided to leave OMGPOP in December of last year. This means I’m now always interested in exceptional projects. Contact me at drew@generalrelativity.org with any questions or interest.

drew General

This is the first in a series on simulating constraints; in this case a particle is constrained to move along a curve in planar space. To follow along, you’ll need to know a little physics, calculus and some algebra, and hopefully you’ve implemented a simple particle system before!

I’ve chosen a parabolic curve. We’re actually going to solve the problem in 2 different ways, so we’ll be seeing 2 separate representations of the curve, the first being the implicit form:

Which looks like this for x {-200…200}:

The first method we’ll use for solving the constraint is described for a circle in this paper by Andrew Witkin. There are some convenient aspects of his example, and so it may not be entirely apparent how to constrain the particle to our parabola. I’ll follow Witkin’s format to show how his formula works in this context.

First, you write a positional constraint which is just our curve equation:

The reason the curve is the constraint is because it implies that when the function’s value at (x,y) is zero, then [x,y] is located on the parabola. Next, we define the velocity constraint, which is the derivative of the positional constraint with respect to time:

If the velocity constraint is satisfied, then we’ll always end up with a valid position. Finally, we find the derivative again with respect to time. This is the acceleration constraint function:

As was the case with velocity → position, if the acceleration constraint is satisfied, so will the velocity. This means that, provided we’re starting with a valid position and velocity, we only ever need to enforce the acceleration constraint on the system.

Let’s do a quick review of Newton’s 2nd law:

Which states that force is equal to mass times acceleration. We’ll be making use of the fact that F represents the sum of all forces acting on the particle. So:

Solving for acceleration gives:

The subscripts ext and c stand for external and constraint respectively. It’s worth pointing out for clarity’s sake that when a term is bold it represents a vector, whereas italicized variables are scalars.

Now we can replace the appearances of x and y’s 2nd derivatives, breaking F into its component parts to allow the constraint force to appear explicitly:

Equation 1

The 2 unknowns now appear, but only in the 1 equation, so we can’t solve yet. If we consider a particle attached to a frictionless wire, it should be apparent that the wire, which is the source of the constraint force, can do no work and so it can not add nor remove energy from the system. The kinetic energy of the system is defined as:

To gain anything useful out of this, we have to consider what direction a force can push without changing T. From examining the derivative of this function with respect to time:

it should be apparent that the constraint force has an important relationship with the velocity vector, specifically that their dot product should equal zero (or else T would change as a direct result of the constraint force). We can use this knowledge to write the constraint force components into a 2nd equation:

Equation 2

This makes sense not just in terms of energy conservation, but also based on the constraint function chain described above. We already know our particle has a legal velocity, and so we don’t want to add any force that would ruin the circle of trust–the constraint force should only pull the external forces onto the acceleration curve.

I first solved for the x constraint component in terms of y from equation 2:

Equation 3

Solving for y’ in the velocity constraint and substituting for x’ in equation 3 reduces the variable count:

Plugging the right-hand side in for F_cx in equation 1 and solving for F_cy yields:

We could explicitly solve for F_cx too, but that’s a non-trivial number of multiplications and a divide. Luckily, we don’t have to because this is for a computational simulation; after F_cy is known, the solution to F_cx is given in equation 3.

Plugged into F=ma, we have the equations of motion for a particle constrained to the parabola x² + 100y = 0.

Parametrized Form

Now we’ll solve the problem a different way, using a reformulation of Newton’s equations called Lagrangian mechanics. Lagrangian mechanics involves finding the number of degrees of freedom (DOF) in a system, then expressing that system in terms of generalized coordinates, one for each DOF. In our example we have a single DOF, even though our particle exists in a 2-dimensional space. First, we phrase our parabola parametrically:

Equation 4

Here, q is our lone generalized coordinate. Noting that x is a vector, the transformation from the generalized coordinate to our particle’s position is given in the parametric equation (4):

The Lagrangian equations of motion for a particle experiencing only conservative forces, as is the case with a particle constrained to a wire, is:

Equation 5

David Eberly gives a full derivation of equation 5 from Newton’s 2nd law in his excellent, if often daunting, Game Physics. F, again, represents all externally applied conservative forces and T is the kinetic energy of the system, which is a function of q and q’. Before we can define T for this system, we have to derive dx/dq and x’ because kinetic energy is dependent upon velocity.

and

Now we can define the kinetic energy of the system as a function of our generalized coordinate because x’ can be expressed entirely in terms of q and its first derivative:

Having determined the kinetic energy function, we can define the rest of the terms in equation 5. We’ll see that its first term includes q’s second derivative, which is the last piece needed to advance the simulation.

Lastly, F, in this case, is just the gravitational force, which we define as the vector mg[0,1]:

Next we plug all of this back into equation 5, which then defines the Lagrangian equations of motion for a particle constrained to the parametrized parabola (q,-q²/100):

Equation 6

Solving for acceleration yields:

Now that we’ve solved for acceleration, we can advance our 2-dimensional simulation by numerically integrating our 1-dimensional differential equations. Below is a demo, showing both methods running side-by-side. If you watch long enough, you’ll see the implicit form (left) eventually leaves the parabola as error accumulates. In contrast, the parametric form will always be on the parabola, but energy will dissipate. These errors are associated with numerical integration inaccuracies and floating point imprecision.

Roll over to run simulation. Left is the implicit form, right is the parametric

Considerations

Each method has advantages and disadvantages. Both offer a relatively easy-to-follow format. Explicitly solving for a constraint force as we did with the implicit curve is more intuitive to me, but the parametric form is more computationally efficient, and the algebra isn’t as messy. A downside to the parametric form is that it isn’t a generic solution–adding new constraints to the system means solving a totally new set of equations of motion.

Below are the separate implementations that each run in a generic dynamics harness. You can see that there is more involved computationally in the implicit form:

Implicit implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var particle:Particle = Particle( p[ 0 ] );
particle.exertForce( G ); //apply gravity
 
var m:Number = particle.mass;
 
var X:Vector3D = particle.position;
var V:Vector3D = particle.velocity;
 
var Fext:Vector3D = particle.force; //generically grab all applied forces
 
var Fc:Vector3D = new Vector3D();
 
//solve for the constraint force
Fc.y = ( -50 * m * V.x * V.x - 100 * X.x * Fext.x - 2500 * Fext.y ) / ( X.x * X.x + 2500 );
Fc.x = ( Fc.y * X.x ) / 50;
 
particle.exertForce( Fc ); //exert the constraint force on the particle

Parametric implementation

1
2
3
4

var q:Number = x[ 0 ];
var qPrime:Number = v[ 0 ];
 
a[ 0 ] = ( -q * qPrime * qPrime - 50 * G * q ) / ( 2500 + q * q );

As mentioned above, both of these are prone to computational error. In the demo, I’m using an RK4 integrator. Using a Euler integration scheme results in visible error within the first second of simulation. Although RK4 does a good job of reducing error, it isn’t perfect. Ideally, an error term is introduced to keep drift in check.

drew ActionScript 3.0, Mathematics, Physics

I’ve been working the past couple months on revamping a lot of Balloono. Check it out.

Gameplay

Ghost Mode

Game Over Screen

drew ActionScript 3.0

It’s a multi-player, color-matching, combo-creating, item-based, hyphen-happy block game! Like all of our games, it’s better played with other people. There’s still a lot of tuning that I’ll be doing in the next week, but I’d like to know what you think.

Play!

drew ActionScript 3.0

http://code.google.com/p/grape-as3/

Grape is the animation library I introduced last post. Its goal is to offer a modular means to animate along parametrized paths.

Here’s the updated demo:

Architecture

Animations have 2 essential component parts: a path and a curve. Paths define position and curves define progression. Both paths and curves are stateless, meaning state is managed by the Animation type and the engine, Grape. This also means paths and curves are freely swappable without a need to clone, etc.

Grape’s Animation type by itself doesn’t assign values to your objects as you’re probably accustomed to with most popular tweening engines. Instead, it simply manages the state of the animation. Its state is a Vector of type Number. This allows the user to reference this state without necessarily tying it to a DisplayObject for instance. When you do want to bind the state of the animation to a DisplayObject, you’ll use a Binding, which simply applies the animation’s state to the appropriate object. The average user probably won’t ever touch a Binding directly, but it’s worth noting.

API

The engine is a singleton called Grape. It has creation methods for the 2 most likely animation scenarios, create2DAnimation and createPropertyAnimation. The latter should be fairly identical to how popular engines work. create2DAnimation will ideally be the typical use-case.

//create the path to animate along
var spiral:Path2D = new SpiralPath2D( new Point( 100, 100 ), 200, 0 );
 
//view is your DisplayObject and 2000 is the duration in milliseconds.
Grape.getInstance.create2DAnimation( view, spiral, 2000 );

And that’s it, your DisplayObject will tween in a spiral with original radius of 200 and end radius of 0 for 2 seconds. You can also set the start time (defaults to instantaneous start), the curve (defaults to linear), whether the animation loops (defaults to false), if the animation is to be played in reverse (defaults to false), and if the animation should reverse on loop (false).

The method returns the animation instance, in the case that you need a reference or would like to handle some of its events:

var anim:Animation = Grape.getInstance.create2DAnimation( view, spiral, 2000 );
 
//add listener for animation complete event
anim.addEventListener( Event.COMPLETE, onAnimationComplete );
 
function onAnimationComplete( event:Event ) : void
{
   //animation done!
}

You can also listen for an event everytime a looping animation loops and each tick of the engine:

//add listener for animation loop event
anim.addEventListener( Animation.LOOP, onAnimationLoop );
 
//listen for Grape's tick
Grape.getInstance().addEventListener( Grape.TICK, onGrapeTick );

Paths

LinearPath2D, CirclePath2D, SpiralPath2D, SineWavePath2D

These are all pretty self explanatory. Linear moves along a line segment. Circle moves around a circle’s edge; you can set the beginning and end radian. Spiral is the same as Circle but also interpolates radius. SineWavePath2D extends LinearPath2D, and so the wave deviates from the line segment.

ComplexPath2D

ComplexPath2D allows you to tween across multiple paths. You supply it a Vector of paths and a Vector of starting cues, specifically the percentage through the tween at which you want the corresponding path to begin.

//create the paths that will be added to the complex path
var spiral:Path2D = new SpiralPath2D( new Point( 100, 100 ), 200, 0 );
var linear1:LinearPath2D = new LinearPath2D( new Point( 100, 100 ), new Point( 200, 200 ) );
var linear2:LinearPath2D = new LinearPath2D( new Point( 200, 200 ), new Point( 200, 100 ) );
var linear3:LinearPath2D = new LinearPath2D( new Point( 200, 100 ), new Point( 100, 100 ) );
 
var paths:Vector.<Path> = Vector.<Path>( [ spiral, linear1, linear2, linear3  ] );
 
//spiral and linear1 will take 25% of the animation's duration, linear2 will take 10%
//and linear3 will take 40%
var cues:Vector.<Number> = Vector.<Number>( [ 0, 0.25, 0.5, 0.6 ] );
 
//create the complex path
var complex:ComplexPath2D = new ComplexPath2D( paths, cues );

Tweening along a twisty train track for example is something that just wouldn’t be possible with any other engine, and forget about trying to apply one cohesive interpolation across the whole path. Complex paths make these stupid easy. And because complex paths are paths, you can nest them inside of each other to create quickly compound, complex animations!

QuadraticBezierPath2D, CubicBezierPath2D

Quadratic Bezier curves are what you’re familiar with from Graphics. Cubic Beziers just offer one extra control point.

var bez:CubicBezierPath2D = new CubicBezierPath2D( new Point( 20, 20 ), new Point( 400, 200 ), new Point( 400, 600 ), new Point( 600, 600 ) );

Bezier’s take one other argument, the Boolean reparametrize. Beziers are like stapling saltwater taffy to the table and lifting it at the center. A really small bit of the curve in terms of its parametrization is left at the staples, while a lot is in your hand near the control points, even though the opposite may be true spatially. What does this mean? It means that even with a linear curve, it’s not likely you can keep constant velocity along the curve. So this Boolean flags whether to reparametrize the curve by arc length. This is a somewhat expensive process and so it defaults to false. Here’s an example of this, the black tween has been reparametrized, the red has not.

LinearSplinePath2D, CosineSplinePath2D, HermiteSplinePath2D, CatmullRomSplinePath2D

Each of the splines takes a Number Vector (x,y pairs) and interpolates between them in their own special way. Linear connects each point linearly, Cosine steps over part of a wavelength to give a (OK, not too nice) curve through each point. Hermite also takes a vector of tangents to give the most amount of control. You can read about them on wikipedia. Catmull-Rom Splines are a subset of Hermite curves. They offer less control, but do not require the user to specify the tangents. Here’s an image of the different interpolations. Top to bottom it’s Linear, Cosine and Catmull-Rom:

This is the code that created the image above:

var p1:Vector.<Number> = Vector.<Number>( [ 20, 20, 100, 100, 120, 50, 300, 300, 400, 50, 500, 200 ] );
var p2:Vector.<Number> = Vector.<Number>( [ 20, 120, 100, 200, 120, 150, 300, 400, 400, 150, 500, 300 ] );
var p3:Vector.<Number> = Vector.<Number>( [ 20, 220, 100, 300, 120, 250, 300, 500, 400, 250, 500, 400 ] );
 
var path:Path2D = new LinearSplinePath2D( p1 );
path.render( graphics );
path = new CosineSplinePath2D( p2 );
path.render( graphics );
path = new CatmullRomSplinePath2D( p3 );
path.render( graphics );

These have great applicability to dynamically generated paths and lots of other game-related functions.

PhysicsPath2D

This should maybe be called projectile instead of physics. You supply initial position, starting velocity and acceleration vectors and how many seconds the entire tween represents.

Debug Rendering

Each path is renderable as a helpful measure. Because of the way paths work, it was easy to handle all paths in one render method, keeping file size down. You can see the spline API above, just pass a graphics instance to draw into.

Alright, I’m excited to see what you make of this and what sorts of cool things you can make! It’s hosted on Google Code under the MIT license. I’ll try to get it commented soon enough, send me any bugs or feature requests.

http://code.google.com/p/grape-as3/

drew ActionScript 3.0, Animation, Flash Player 10

What!? Why would I write another tweening engine? Because it’s awesome! It addresses some of the things that other libraries don’t. I realized that if I wasn’t just animating from here to there, or fading in, I’d end up having to write a custom solution. Even seemingly simple stuff like moving an object in a circle isn’t really doable.

So the solution is to break animations into 2 component parts: a path and a curve. The path represents the spatial component of the animation and the curve represents the temporal.

Currently there’s only a linear curve and a PennerCurve, which can have any Robert Penner-esque easing function assigned to it.

Paths:

• CirclePath2D
• ComplexPath2D
• CubicBezierPath2D
• LinearPath2D
• Path1D
• PhysicsPath2D
• QuadraticBezierPath2D
• SineWavePath2D
• SpiralPath2D

The coolest thing here is the complex path which allows you to combine multiple paths into 1 animation. So the progression of the curve is applied across the whole of the complex path. And, because complex paths are paths themselves, they are nestable!

From the demo below (select ComplexPath2D 2), here’s the most verbose example, which combines 3 circle paths as 1 complex path and nests that inside another complex path containing a bezier and sine wave path:

 
//circle's go center point, radius, start radian, end radian
var c1:CirclePath2D = new CirclePath2D( new Point( 150, 200 ), 50, Math.PI * 2, 0 );
var c2:CirclePath2D = new CirclePath2D( new Point( 250, 200 ), 50, Math.PI, Math.PI * 3 );
var c3:CirclePath2D = new CirclePath2D( new Point( 300, 200 ), 100, Math.PI, Math.PI * 3 );
 
//the complex path takes the list of paths and a list of cue points
var complex:Path = new ComplexPath2D( Vector.<Path>( [ c1, c2, c3 ] ), Vector.<Number>( [ 0, 0.25, 0.5 ] ) );
 
//the bezier classes take the anchor and control points
var bez:CubicBezierPath2D = new CubicBezierPath2D( new Point( 200, 200 ), new Point( 350, 0 ), new Point( 350, 500 ), new Point( 350, 200 ) );
 
//sine wave takes a start and end point, frequency and amplitude
var sine:SineWavePath2D = new SineWavePath2D( new Point( 350, 200 ), new Point( 200, 200 ), 3, 50 );
 
var path:ComplexPath2D = new ComplexPath2D( Vector.<Path>( [ complex, bez, sine ] ), Vector<Number>( [ 0, 0.5, 0.75 ] ) );
 
//the runner binds the view to the animation
runner = new Runner2D( view, path, durationStepper.value, -1, getCurve(), loop.selected, reverse.selected );

Here’s the demo:

I’ll be releasing it under the MIT license in a few days.

drew ActionScript 3.0, Animation

I was tidying up my laptop today and found the slides from a presentation I gave at Schematic a couple years ago on Bezier curves. I can’t find the demos unfortunately, but the slides are pretty funny on their own.

If I find the demos, I’ll post them here.

drew ActionScript 3.0, General, Mathematics

Arrays are memory hogs when compared to their strong-typed, faster, rich and handsome cousins, Vectors, for a whole bunch of reasons that you can read about elsewhere. I was surprised, though, to find how enormous the difference in their memory footprints were:

• (10000000 / 32) uints in a Vector (10000000 bits) = ~7k
• (10000000 / 32) uints in an Array (10000000 bits) = ~1228k

Yikes! But Booleans are far worse:

• 10000000 Booleans in a Vector = ~8k
• 10000000 Booleans in an Array = ~39070k

I didn’t do the math, but I’m fairly sure that’s like 3 terabytes per Boolean. Now, it makes sense that Booleans don’t get packed anywhere close to perfectly… does anyone know how much memory gets opened for a Boolean? Probably 4 bytes, but I don’t know, to be honest.

What’s interesting, however, is that it appears, based on ratio, that Booleans are being intelligently stored by the VM in the case of Vectors. Not as tightly as possible, and hence the probably masturbatory BitVector.

Michael, over at Polygonal Labs, posted a nice and as-usual informative article on bit vectors back when people still knew what AS2 was. There’s also an implementation in his data structures library. We can definitely get much better performance, though, using a Vector.<uint>. Here’s my implementation. The bitwise OR and AND are much faster than Boolean logic of the same case and obviously setting all bits on or off will be faster than iterating over a Boolean Vector. If anyone thinks they’d actually use it, I’d be happy to add all the bitwise operations.

So what would this be used for? Firstly, it naturally extends the ability to store Boolean logic via bitwise operations in an unsigned integer’s bits past its 32 threshold all the way… to n!

I used it recently in mapping key presses to emulate AS2’s Key.isDown convenience method. When a key is pressed, the bit sitting at that key’s code is switched on. When the key is released, the corresponding bit is switched off. Combinations could easily be stored as BitVector masks. Here’s the Key class.

Christer Ericson, in his awesome Real Time Collision Detection suggests using a bit vector in avoiding retesting 2 objects for collision detection. He shows that this can be stored in n(n - 1)/2 bits instead of n², where n is the number of objects. The unique index for any 2 objects is then:

bit = min(2n - min - 3)/2 + max - 1

Where min and max represent the indices of the objects being tested.

Using my BitVector class, the implementation would look something like this:

//offline
var n:uint = objects.length;
var bv:BitVector = new BitVector( null, n * ( n - 1 ) / 2 );
 
//test
function handleCollision( minObj:CollidableObject, maxObj:CollidableObject ) : void
{
 
   var bit:uint = minObj.index * ( 2 * n - minObj.index - 3 ) / 2 + maxObj.index - 1;
   if( !bv.getBit( bit ) )
   {
       //test for collision
      bv.setBit( bit, true );
   }
 
}

BitVector.as
Key.as

drew ActionScript 3.0, Flash Player 10

This is my first multi-player game! You race a tiny silhouetted hamster in a fashionable, plastic globe! I recommend playing it over at OMGPOP so that you’re not constrained to the embedded dimensions here.

drew ActionScript 3.0, Network, Physics

This is a tiny little lib to play multi-framed sprites of different type in a common way. The frame analogy should be familiar.

The concept is that frames are advanced according to a differential. If you set this differential to 1, then it will play a MovieClip, for instance, exactly as it would play by itself. If instead you set it to 0.5 it will run at half-speed. Set it to -2 and it will play in reverse at double speed.

In the demo below, there’s a MovieClip and a tile-sheet-blitted-to-BitmapData of the same animation being controlled by a SpritePlayer. Adjust the slider to see how the differential effects playback.

Demo: Drag the slider to change the frame rate differential.

It’s a pretty sloppy implementation (see: MovieClipWrapper), but it should get the point across. A SpritePlayer has a reference via composition to an implementation of IPlayable, which is implemented as a simple wrapper for the MovieClip and as example in a TileSheetSprite class for the blitting technique. The main method is in solving for the next frame, which is done without any multiplication or modulo operation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public function next() : int
{
 
	var deltaFrame:int = differential >> 0;
	remainder += differential - deltaFrame;
 
	if( Math.abs( remainder ) >= 1.0 )
	{
 
		var rdt:int = remainder >> 0;
 
		deltaFrame += rdt;
		remainder -= rdt;		
 
	}
 
	var nextFrame:int = target.currentFrame + deltaFrame;
 
	if( nextFrame > target.totalFrames ) nextFrame -= target.totalFrames;
	else if( nextFrame < 1 ) nextFrame += target.totalFrames;
 
	target.gotoAndStop( nextFrame );
 
	return target.currentFrame;
 
}

A remainder property is stored to collect the difference between the change in frames, which is an integer, and the differential, which is a float. In one iteration of this algorithm, it is clear that remainder can not be greater than or equal to 1 (or less than or equal to -1). So when it does accumulate to 1 or greater, the delta frame is incremented by the rounded remainder (1 or -1), and this value is subtracted from the remainder. Then the algorithm just wraps nextFrame in the case that it exceeds the range of frames.

So it naturally supports playback in both directions at any differential, though there’s a cap put on the differential so that it’s less than the total number of frames for the sprite being played.

source (MIT License)

drew ActionScript 3.0