Landing Screen

Check out the game page (there’s a quick gameplay trailer), or go grab it from the app store!

As a fun little introduction to what we’ll be solving, look at the multi-body simulation below. The wheel has a torque applied and each body experiences a gravitational force. 1 ground constraint, 3 revolute joints and a prismatic joint constrain the system. Click the checkbox to toggle torque.

Demo: Roll over to simulate slider-crank.

The reason I wanted to write this article is because I found an imbalance between theory and implementation in the decent amount of freely available literature on the topic. The major rift exists, I think, because actual implementation involves radical optimizations that transform the tidy mathematical nature of the theory. In the concrete process and examples below, we’ll avoid this deviation with the hope that the material presented is a bit more accessible.

Global Form of the Constraint Problem

When we solved the particle-to-curve problem, it was sufficient to write the equations of motion in terms of the parabolic constraint. In the case that multiple constraints are acting upon a physical element, we need to write the equations of motion in terms of all constraints, because solving one may violate another. We could decide on a system configuration and solve each constraint force to derive the equations of motion, but that would be a lot of work; and not just once, but for each unique configuration.

Instead, we can construct a linear system of the form Ax = b, which can be solved for x generically. This allows us to piece together constraints anyway we like, which is a much more manageable way of setting up a simulation than sketching out the equations of motion for a giant, complex configuration. Now all we have to do is create this system, which basically just involves a lot of organization.

First, we need to compile the state of the system into a vector, q:

where n is the number of bodies. Each body is defined by an index, its position along the world x and y-axes and its orientation (θ). Next, we compile all constraints imposed on the system into the global constraint vector, C:

where s is the number of constraint equations. Everything we need to construct the aforementioned linear system is either directly derived from q and C, or ordered to match these vectors. Now we’ll see what we’re really working toward (see Witkin for derivation):

Equation 1:

This looks a little scary at first, but it’s actually not that bad. M^-1 is a diagonal matrix of dimension 3n, where each element on the diagonal is the inverse intertial term associated with the element at the corresponding index in q:

Where m_k is the mass of body k and I_k is the moment of inertia about the center of mass of body k. Looking at q, we see that mass is associated with translation and moment of inertia is associated with rotation, which is what we know from the Newton-Euler equations.

F_ext is the global vector of all external forces and torques exerted on the bodies:

which is of dimension 3n, also. Here, τ_k is the torque acting on body k. We could now write the unconstrained equations of motion as:

which should make sense of all the purposeful ordering we’ve seen so far.

Next, we’ll define the only radically new term introduced in Equation 1, J. This is known as the Jacobian of C and is an s-by-3n matrix, being composed of 1 row per constraint function (element of C) and 3 columns per body (x, y and θ). Row i is the gradient of the ith constraint function with respect to q:

Since a constraint generally involves at most 2 bodies, the gradient will be composed of mostly zeroes. The global Jacobian is:

This all might seem a bit abstract right now, but we’ll see that these terms are easy to construct in practice when we derive a few constraints. The time derivative of the Jacobian is built the same way, but with the velocity constraint vector:

The coefficients ks and kd of equation 1 are spring and drag terms, respectively, and used to correct error. Because each constraint equation should equal zero when satisfied, the amount of error is defined in the evaluation of the constraint functions.

Finally, we show how Equation 1 relates to the general form of a linear system mentioned above:

A is an s-by-s matrix, and x and b are vectors of dimension s. Solving for λ leads to the global constraint force vector:

Finally, the equations of motion for the constrained system can be written abstractly as:

Now we have a method for formulating constraints which can participate in the global system:

1. Write the positional constraint, C, as a function of q.
2. Take the derivative of C to solve for the velocity constraint.
3. Solve for the Jacobian of C.
4. Solve for the derivative of the Jacobian with respect to time.

Computer Implementation

public class Constraint
{
 
	//index in global constraint vector
	public var index:uint;
 
	//indicates the number of constraint functions
	//this is equal to the number of system DOF it removes
	internal function get numJacobianRows() : uint
	{
		//abstract
		return 0;
	}
 
	//populate the system matrices and vectors
	internal function solve( J:MatrixND, JDot:MatrixND, C:Vector. ) : void
	{
		//abstract
	}
 
}

Note that while we use C’ to solve for J’, we don’t actually need to explicitly contribute to the velocity constraint because C’ = Jq’ and can be solved at the global level without additional input from the individual constraints. Although this adds computational overhead, I like the generality achieved. Further, because we can alternatively solve for J’ by directly taking the derivative of J with respect to time, solving for C’ becomes seemingly unnecessary altogether. That said, I’ve found that the intuition-confirming statement a velocity constraint makes is worth the little bit of extra differentiation.

Now we’ll see how the global system is constructed and solved. Below is the relevant portion of the ConstraintSolver class, minus some declarations for conciseness’ sake. It allows each constraint to evaluate its very own special part of the structure via the above interface:

public class ConstraintSolver
{
 
	private var numJacobianRows:uint; //global # of constraint functions
	private var ode:DynamicsODE; 
 
	public function addConstraint( constraint:Constraint, initialize:Boolean = false ) : void
	{
		constraint.index = numJacobianRows;
		numJacobianRows += constraint.numJacobianRows;
		constraints.push( constraint );
		if( initialize ) initSystem();
	}
 
	public function initSystem() : void
	{
		W = new MatrixND( ode.length, ode.length, false );
		W.diagonal = ode.invMass;
		J = new MatrixND( numJacobianRows, W.m, false );
		JDot = new MatrixND( numJacobianRows, W.m, false );
		C = new Vector.( numJacobianRows, true );
		b = new Vector.( numJacobianRows, true );
		lambda = new Vector.( numJacobianRows, true );
	}
 
	public function solve() : void
	{
 
		for each( var constraint:Constraint in _constraints )
		{
			constraint.solve( J, JDot, C );
		}
 
		var JW:MatrixND = J.times( W );
		var JT:MatrixND = J.transpose;
		var JWJT:MatrixND = JW.times( JT );
 
		//J'q'
		var JDotqDot:Vector. = JDot.timesVector( ode.v );
		var JWFext:Vector. = JW.timesVector( ode.f );
 
		//C' = Jq'
		var CDot:Vector. = J.timesVector( ode.v );
 
		//b = -J'q' - JWQ - Cks - C'kd
		for( var i:int = 0; i < numJacobianRows; i++ )
		{
			b[ i ] = -JDotqDot[ i ] - JWFext[ i ] - C[ i ] * ks - CDot[ i ] * kd;
		}
 
		//solve the system
		JWJT.solveAnalytical( lambda, b );
 
		//constraint force = JTx
		var Fc:Vector. = JT.timesVector( lambda );
 
		//add the constraint force to the external forces
		for( i = 0; i < ode.length; i++ )
		{
			ode.f[ i ] += Fc[ i ];
		}
 
	}
 
}

With this structure in mind, we’ll now go through the process of deriving and implementing a couple constraints.

Ground Constraint

The first constraint we’ll derive with this method is the ground constraint, which keeps a body fixed in space. The body is not permitted to translate or rotate. First, we write the positional contraint:

where c_x is where the body is fixed along the global x-axis, c_y along the y, and c_θ the fixed orientation of the body. Note that 0 is the zero vector, [0,0,0]. Next, we solve the velocity constraint by taking the derivative of C_ground with respect to time:

which simply and intuitively states that linear and angular velocity are zero. This is what we expect considering the constraint prevents the body from experiencing any motion. Next, we derive J:

And, finally, the derivative of J w.r.t. time:

That was not so bad at all! The Jacobian can be a bit off-putting at times and make the problem seem more complicated than it is–just remember that we’re simply creating a matrix where each row is the gradient of a constraint function. In practice, you wouldn’t want to simulate the ground constraint, but it’s a good exercise because of how simple the math is. Other joints will have more complex positional constraints, but the underlying framework for formulating these quantities is the same.

The GroundConstraint class:

public class GroundConstraint extends Constraint
{
 
	public var body:Body2D;
 
	private var U:Point;
	private var theta:Number;
 
	public function GroundConstraint( body:Body2D )
	{
		super();
 
		this.body = body;
 
		U = body.position.clone();
		theta = body.theta;
 
	}
 
	override internal function get numJacobianRows() : uint
	{
		//removes all DOF
		return 3;
	}
 
	override internal function solve( J:MatrixND, JDot:MatrixND, C:Vector. ) : void
	{
 
		J.A[ index ][ body.index 	] = 1;
		J.A[ index ][ body.index + 1 	] = 0;
		J.A[ index ][ body.index + 2 	] = 0;
 
		J.A[ index + 1 ][ body.index 		] = 0;
		J.A[ index + 1 ][ body.index + 1 	] = 1;
		J.A[ index + 1 ][ body.index + 2 	] = 0;
 
		J.A[ index + 2 ][ body.index 		] = 0;
		J.A[ index + 2 ][ body.index + 1 	] = 0;
		J.A[ index + 2 ][ body.index + 2 	] = 1;
 
		JDot.A[ index ][ body.index 		] = 0;
		JDot.A[ index ][ body.index + 1 	] = 0;
		JDot.A[ index ][ body.index + 2 	] = 0;
 
		JDot.A[ index + 1 ][ body.index 	] = 0;
		JDot.A[ index + 1 ][ body.index + 1 	] = 0;
		JDot.A[ index + 1 ][ body.index + 2 	] = 0;
 
		JDot.A[ index + 2 ][ body.index 	] = 0;
		JDot.A[ index + 2 ][ body.index + 1 	] = 0;
		JDot.A[ index + 2 ][ body.index + 2 	] = 0;
 
		//positional error
		C[ index 	] = body.x - U.x;
		C[ index + 1 	] = body.y - U.y;
		C[ index + 2 	] = body.theta - theta;
 
	}
 
}

Here we finally see how the indexing of the constraint and the body play into the global vectors and matrices.

Revolute Joint

A revolute joint, in two dimensions, is like paper pinned up on a wall. The paper is prevented from falling to the ground, but can spin freely. To formulate the joint constraint, we need a mathematical representation of a point on a rigid body.

Point on Rigid Body

First, we’ll define the terms used to describe rigid body state. Just as with a particle, x is the body’s position vector:

A 2D body is also characterized by its orientation about the axis poking out of the screen. This is represented as the 2D rotation matrix, A:

Which is clearly parametrized by the angle, θ. Given these representations, we can solve for the world-space position of any point, P, that is defined in the body’s local coordinate frame. We designate this term r:

Equation 2:

Where u is the vector pointing from the body’s origin to P. Equation 2 can be decomposed from vector form into 2 scalar equations:

Figure 1: Rigid Body Transfromation

Figure 1 shows a rigid body’s local coordinate system and that same system transformed into world-space. Note that in the body’s local coordinate frame, all points and vectors are constants, whereas in the global frame, they are functions of time. Equation 2 can be written more explicitly to reflect this:

Although we’ll prefer the abbreviated form of equation 2, it’s important to remember which terms are functions of time, as we differentiate this function below.

Figure 2: Revolute Joint

The revolute joint pins 1 body to another at a shared point in world space. Because we can represent this point in terms of each body as shown in equation 2, the positional constraint is easy to write:

which states that the distance between the 2 bodies at these respective points is zero. Differentiating with respect to time leads to the velocity constraint:

indicating that the relative velocity of the bodies at these points is zero. Next, we evaluate the Jacobian of C_revolute:

And, finally, the time derivative of the Jacobian:

The RevoluteJoint class:

public class RevoluteJoint extends Constraint implements IRenderable
{
 
	public var b1:Body2D;
	public var b2:Body2D;
 
	private var u1:Point;
	private var u2:Point;
 
	public function RevoluteJoint( b1:Body2D, b2:Body2D, U:Point )
	{
 
		super();
 
		this.b1 = b1;
		this.b2 = b2;
 
                //convert U to b1's local coordinate frame
		var T:Matrix = b1.A.clone();
		T.invert();
		u1 = T.transformPoint( U.subtract( b1.position ) );
 
                //convert U to b2's local coordinate frame
		T = b2.A.clone();
		T.invert();
		u2 = T.transformPoint( U.subtract( b2.position ) );
 
	}
 
	override internal function get numJacobianRows() : uint
	{
		//removes 2 DOF
		return 2;
	}
 
	override internal function solve( J:MatrixND, JDot:MatrixND, C:Vector. ) : void
	{
 
		var uxc1:Number = u1.x * b1.A.a;	var uxc2:Number = u2.x * b2.A.a;
		var uyc1:Number = u1.y * b1.A.a;	var uyc2:Number = u2.y * b2.A.a;
		var uxs1:Number = u1.x * b1.A.b;	var uxs2:Number = u2.x * b2.A.b;
		var uys1:Number = u1.y * b1.A.b;	var uys2:Number = u2.y * b2.A.b;
 
		//J
		J.A[ index ][ b1.index 		] = 1;
		J.A[ index ][ b1.index + 1 	] = 0;
		J.A[ index ][ b1.index + 2 	] = -uyc1 - uxs1;
 
		J.A[ index + 1 ][ b1.index 		] = 0;
		J.A[ index + 1 ][ b1.index + 1 	] = 1;
		J.A[ index + 1 ][ b1.index + 2 	] = uxc1 - uys1;
 
		J.A[ index ][ b2.index 		] = -1;
		J.A[ index ][ b2.index + 1 	] = 0;
		J.A[ index ][ b2.index + 2 	] = uyc2 + uxs2;
 
		J.A[ index + 1 ][ b2.index 		] = 0;
		J.A[ index + 1 ][ b2.index + 1 	] = -1;
		J.A[ index + 1 ][ b2.index + 2 	] = -uxc2 + uys2;
 
		//J'
		JDot.A[ index ][ b1.index 		] = 0;
		JDot.A[ index ][ b1.index + 1 	] = 0;
		JDot.A[ index ][ b1.index + 2 	] = b1.av * ( -uxc1 + uys1 );
 
		JDot.A[ index + 1 ][ b1.index 	] = 0;
		JDot.A[ index + 1 ][ b1.index + 1 	] = 0;
		JDot.A[ index + 1 ][ b1.index + 2 	] = b1.av * ( -uyc1 - uxs1 );
 
		JDot.A[ index ][ b2.index 	] = 0;
		JDot.A[ index ][ b2.index + 1 	] = 0;
		JDot.A[ index ][ b2.index + 2 	] = b2.av * ( uxc2 - uys2 );
 
		JDot.A[ index + 1 ][ b2.index 	] = 0;
		JDot.A[ index + 1 ][ b2.index + 1 	] = 0;
		JDot.A[ index + 1 ][ b2.index + 2 	] = b2.av * ( uyc2 + uxs2 );
 
		//positional error
		C[ index 	] = b1.x + uxc1 - uys1 - b2.x - uxc2 + uys2;
		C[ index + 1 	] = b1.y + uxs1 + uyc1 - b2.y - uxs2 - uyc2;
 
	}
 
}

Considerations

We’ve followed the mathematical formulas closely, which has left us with a computationally inefficient application. Hopefully this trade has been for a solid understanding that lays the foundation for the reader to implement a system of constraints. As a next step, I recommend reading Erin Catto’s paper, Iterative Dynamics with Temporal Coherence, which highlights several optimizations in both time and memory.

Just as was the case with the particle-to-curve simulation, an RK4 integrator was necessary to not accumulate an insurmountable amount of error. The choice of the spring and drag coefficients becomes less trivial than expected and aid in the degradation of accuracy.

In later articles, we’ll switch from acceleration to a velocity-based constraint solver. This is simpler, more efficient and capable of handling a wider variety of constraint problems.

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

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

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.

Move onto part 2, where we cover joints and global constraints.

Gameplay

Ghost Mode

Game Over Screen

Play!

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. = Vector.( [ 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. = Vector.( [ 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. = Vector.( [ 20, 20, 100, 100, 120, 50, 300, 300, 400, 50, 500, 200 ] );
var p2:Vector. = Vector.( [ 20, 120, 100, 200, 120, 150, 300, 400, 400, 150, 500, 300 ] );
var p3:Vector. = Vector.( [ 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/

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.

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

• (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