Dynamic Circle/Circle Collision Detection in ActionScript 3
(Updated 09.30.07)
collision detection demo click and drag to move a circle or its velocity vector
source
INTRODUCTION
Determining whether 2 circles are colliding is one of the simplest types of collision detection. You simply evaluate the sum of the circles’ radii and the distance between them. If that sum is greater than the distance, the circles in question are coincident. This call is made at each time step in a simulation.
This works well in most cases and is most often optimized to evaluate the square of the sum of the radii and the square of the distance between circles- which offers the same response without an expensive square root call.
THE PROBLEM
But what if our circles are moving really fast? At the beginning of the interval they may not be colliding and likewise at the end; but it’s quite probable that at some point within that interval, the circles do collide.
THE SOLUTION
We can evaluate as many as 2 possible collisions (given constant velocity)- their initial collision and the moment at which they are adjacent again (if they passed through each other without effecting each other’s movement). There aren’t necessarily 2 solutions; and the second solution does little good for us here anyway. So we’re left wanting to derive:
(A) if the circles will collide in a given interval and if so,
(B) when they first collide in relation to that interval.
This solution is presented in Real-Time Collision Detection by Christer Ericson. He does a much better job of explaining the following derivation than I can, but here we go anyway!
DERIVATION
Because we’re presuming constant velocity over the interval 0 ≤ t ≤ 1, the position of a circle is equal to:
Where X is its current position and v, velocity. So at the beginning of the interval, the circle’s position is equal to X + v * 0 = X, and X + some portion of v for any t value greater than 0. What we need is a function of t that evaluates the distance between the 2 circles according to this parameterization:
Where
and 
When f is equal to the sum of the 2 circles’ radii, the circles are coincident:
Where r is respective radius. Evaluating distance means we need to compute a square root, which as mentioned above is undesirable. We can square both sides of the equation instead:
The square of the sum of vectors expands into dot products just like a scalar polynomial expands into multiplications:
Moving all terms to the left side, and naming each constant based on its relationship with t in agreement with the equation’s quadratic nature, we have:
Where
and
Which is a quadratic equation where b is known to be a multiple of 2. Its roots are:
EFFICIENCY CONSIDERATIONS
Every calculation requires processing and ActionScript is certainly not the exception! We want to organize our detection method such that nothing is defined/calculated before it is necessary. If we can eliminate the possibility of collision before defining a variable- we should! It’s a common mistake to solve without consideration of the algorithm’s real job- to offer an answer to our collision query as quickly as possible. And that’s the driving force here.
IMPLEMENTATION
This example utilizes CircleParticles with public properties representing radius, position and velocity. The Collision type takes 2 of these CircleParticles at instantiation. Its method detect evaluates collision over the interval implied by these CircleParticle’s velocities.
Given collision, it sets a time variable (t) to the point at which in that interval collision first occurs. A basic understanding of vector arithmetic and quadratic equations should be sufficient to wholly understand this function:
/** * Detects whether 2 {@link CircleParticle} instances will collide within an implicit timestep of 1 * * Given collision, {@link #t} is set to the percentage of the interval at which collision occurs. * ie: 0 if collision occurs at the beginning of the interval and 1.0 at the end of the interval * * The event of collision is given by the quadratic equation ax^2 + 2bx + c = 0 offers the resolution: * x = ( -b - Math.sqrt( b^2 - ac ) ) / a, the smaller of 2 possible roots * * Note that we return from the algorithm before declaring/defining any unnecessary variables * * * @return {@code true} if collision is detected, {@code false} otherwise * */ public function detect() : Boolean { //difference vector of the 2 circles' positions var cDiff:Vector = c2.position.getDifference( c1.position ); /** * {@code c} the squared distance between circles minus the squared sum of their radii * this offers a means to check for intersection at the start of the interval * without making an expensive square root call * * ie: if the sum of the circles' radii squared > the distance between them squared, * they are overlapping * */ var c:Number = cDiff.dot( cDiff ) - ( c1.radius + c2.radius ) * ( c1.radius + c2.radius ); if( c < 0 ) { //initial overlap condition- return with time 0 t = 0; return true; } //difference between circles' velocities var vDiff:Vector = c2.velocity.getDifference( c1.velocity ); var a:Number = vDiff.dot( vDiff ); if( a < Collision.OMEGA ) return false; //circles not moving relative each other var b:Number = vDiff.dot( cDiff ); if( b >= 0 ) return false; //circles moving apart var d:Number = b * b - a * c; if( d < 0 ) return false; //no solution to the quadratic equation- circles don't intersect //evaluate the time of collision t = ( -b - Math.sqrt( d ) ) / a; return t <= 1; }
NOTE: While there is not a single trigonometric function call in this detection method, some of its assertions are based on the law of cosines.
REACTION
So, assuming collision at exactly halfway through the interval, our Collision’s t property is set to 0.5. We can now move on to react to the collision.
The idea or our Collision’s react method is to take our knowledge of the moment of collision within the interval and apply that to our CircleParticles. We first move the circles along their velocity vectors scaled by the collision interval. We then calculate the transfer of momentum along the axis of collision and move the circles from their position at collision along their new velocity vectors by the remainder of the interval:
/** * Reacts to a collision between {@link #c1} and {@link #c2} at specified time {@link #t} * * * We project the ghost particles along the velocity vector of c1 and c2 by * t * circle.velocity. * (Description is outdated- needs updating) * Then we normalize the collision vector and amplify by the magnitude of the * opposing circle's velocity to obtain each ghost's velocity. Their velocities * are then multiplied by 1 - t to give us each reaction vector in reference to the * remaining span of the interval. * * * @param g1 ghost particle representative of {@link c1} at moment of collision * @param g2 ghost particle representative of {@link c2} at moment of collision * */ public function react( g1:CircleParticle, g2:CircleParticle ) : void { //assign the position at percentage t along each velocity vector to each ghost g1.position = c1.position.getSum( c1.velocity.getProduct( t ) ); g2.position = c2.position.getSum( c2.velocity.getProduct( t ) ); //difference vector between circles at time of collision var cDiff:Vector = g2.position.getDifference( g1.position ); //normalized var collisionNormal:Vector = cDiff.getUnit(); //relative velocity of circles var relativeVelocity:Vector = c1.velocity.getDifference( c2.velocity ); //coefficient of restitution range of 0 - 1.0 //0 is completely inelastic (lump of clay) and 1 is purely elastic (superball) var restitution:Number = Math.sqrt( c1.elasticity * c2.elasticity ); //the impulse created at collision- //this is given by the following equation (j is used to represent impulse) //j = -( 1 + e )vAB . n / n . n( 1 / mA + 1 / mB ) //where e is the coefficient of restitution, vAB is the relative velocity //n is the collision normal and mA/mB are the respective masses of the different circles // "."s represent the vector dot product var impulse:Number = collisionNormal.dot( relativeVelocity.getProduct( -( 1 + restitution ) ) ); impulse /= collisionNormal.dot( collisionNormal.getProduct( 1 / c1.mass + 1 / c2.mass ) ); //scale each impulse along the collision normal by the circles' respective masses var reactionA:Vector = collisionNormal.getProduct( impulse / c1.mass ); var reactionB:Vector = collisionNormal.getProduct( -impulse / c2.mass ); //Multiply this by the the remainder of the interval (1 - t) g1.velocity = c1.velocity.getSum( reactionA ).getProduct( 1 - t ); g2.velocity = c2.velocity.getSum( reactionB ).getProduct( 1 - t ); }