Quick Links

Education Edu

Simulations Sims

Math Tools Math

Games Games

Generative ArtArt

Actinoscript Prog

Farmville Farm

 

 


Alkanes

Collision Detection

Click the above-left picture of Collision Detection applet to start the demo full screen.

 
 

Collisions

Once Upon A Time

Long, long ago, back in the days of 386 computers and 80 MB hard drives, when I used to be profitably employed, rather than do the actual programing of some boring mission critical project for which I was being paid, I managed to find the time to write something of a physics simulation in C. Of course, I had recently taken some sort of physics classes at the UW and the concepts of collisions were relatively front place in my mind. Probably 99% of junior programmers who have ever taken a physics class have attempted this at one time or another.

Content on this page requires a newer version of Adobe Flash Player.

Get Adobe Flash player

I recall seeing those happy little circles bouncing so perfectly off one another in the finished product, and being ridiculously proud of the result, though somewhat hesitent to demonstrate it to my co-workers or boss when our group's current project was so far behind schedule. The finished .exe is probably still on the hard drive of some dump-abandoned computer leaking toxic chemicals into the environment.

Of course, now that I've successfully honed my programming skills on more complex math and physics related code, such a little project would be a trivial task. So imagine my surprise, when in the midst of writing the game FizxBlox, that I discovered that the stupid collisions didn't work. It actually is a trivial task to get them to bounce off the outer boundaries of the playing field, but something was definitely amiss with the ball versus ball collisions.

The Balls

Each ball has a radius, position, mass, and velocity. At the start of each frame, the dX and dY of the velocity are added to the current position. Then the highly painful O(n^2) operation of checking for collisions with every other ball is performed. Some smart people someplace other than in front of my computer are able to reduce that O(n^2) by successively partitioning the space into quadrants to reduce the number of other balls to check against, but though the concept made great sense, I couldn't figure out how to code that. In case it needs mentioning, I'm talking about 2D. I wouldn't begin to know what to do with 3D.

The Pain Filled Process

I'm writing in Actionscript 3, so naturally, I first attempt to just use the built in collision detection of object v. object to determine whether or not a collision had occurred. This sometimes results in fast moving objects that coincidentally don't overlap, just passing obliviously through one another. Since the balls are circles, this might be better done just by comparing distances bewteen the objects relative to the combined radii, i.e.,

if (distanceBetweenBallCenters<=sumOfRadii) { aha! a collision }

So much for collision detection. Next you figure out which way the balls are going to go after the collision. Thankfully, googling something like "perfectly elastic collision" will yield all kinds of equations, usually something like the following:

(m1*u1^2)/2 + (m2*u2^2)/2 = (m1*v1^2)/2 + (m2*v2^2)/2

where m indicates mass; u, pre-collision velocity; v, post-collision velocity. This comes from combined kinetic engery (mv^2) of the pair needing to remain constant throughout. BTW, notice how much easier it is to read that equation than one that is properly formated and unburdened by all those pesky parentheses? You're welcome.

If you correctly do the math on this, you eventually produce post-collision velocity equations like these:

v1=(u1*(m1-m2)+2*m2*u2)/(m1+m2)

v2=(u2*(m2-m1)+2*m1*u1)/(m1+m2)

What could possibly be easier? I go about coding this up (incidentally, implementing equations snarfed directly from wikipedia), only to find that it didn't do what I wanted. Balls ignore one another, get trapped inside one another, suddenly change direction when no one else is around, etc. Every now and then, they ignore the boundaries of my gameboard and fly off into infinity.

Ok, so it's not very convenient, but maybe if I start by guaranteeing that none of them are going to be touching when the simulation starts. No joy. How about if I slow them way down. That didn't help. Someone pounds on my door and tries to sell me magazines. Go away. I force all the balls to be the same size, reduce the number of balls to 2. Carp. I give them random colors. None of the mindless fixes do the trick.

The paper

I move to take a piece of paper from my printer. Carp! No paper. Maybe that was why its been beeping. I remove one of my 4 year old's masterpieces from the refrigerator and start scribbling on the back.

Ok. So there are two balls moving and then they touch in a collision.
The line connecting the two centers will be coincident with the normal
I remember something about it being easier to do if you first put both balls in the frame of reference of one of them, that is, one has a velocity of zero, and you subtract it's velocity from the other.
So, pretending that the bottom one has no initial velocity, the top one goes something like this.
I arbitrarily position it at the point of intersection.
Then, I'm pretty sure, the first ball will bounce in a direction as if I'd reflected the input vector across the normal.
So, my input and output angles have to be the same.

So, I have to figure out the angle between two vectors. Incredibly, I actually remember this equation off the top of my head. C^2 = A^2 + B^2 + 2*A*B*cos(angle between them). And then you solve for the angle getting:

angle = acos( (C^2 - A^2 - B^2)/(2*A*B))

I program that up. It fails. I google for the angle between two vectors. I find all this vector notation that looks familiar but slightly confusing: determinants, cross, and dot products, magnitude, normal, matrices.

I fuss with it more. My wife tells me it's dinner time. I'm on a roll. "Later." I try several other things I can't even begin to remember. Google again. Look at Reddit.

OK, so maybe this isn't the correct approach. My library's ebook system has a book purporting to show actual pseudo code for doing this, but it's like pseudo pseudo code and requires that I already have implemented all the pseudo pseudo code functions from the previous 8 chapters that it depends on . No thanks.

Maybe I can remove collisions from my game? No. However, I can just have the balls bounce off a stationary "bumper" that has infinite mass. That doesn't help a whole bunch.

Ok. I have a new dumbed down approach. Instead of doing *real* collisions, I'll figure out whether the ball is above, below, left, or right of the bumper and then just negate the corresponding dX or dY ignoring the other component. Finally something that works, but looks totally dorky and unrealistic.

My wife wants to know what I'm doing on the computer in there. I've been in there all day.. I'm not yet ready to tell her that I'm too stupid to properly code perfectly inelastic collisions. "Just downloading porn." I tell her.

Ok. I've decided. I'm going to implement all those ridiculous pseudo pseudo code functions from the previous 8 chapters of my library's physics game programming book. Another few hours wasted. These assume I've got some magical language that allows me to return any type or number of values, have some sort of 2D vector type and I don't know what else. Oh wait, actionscript 3!

I finally get to the collision detection routine. And the collision resolution routine. I create 2 sample balls with contrived positions & velocities and plug them in. Success!

I plug in more balls. It fails. More than half the time, the balls just pass through one another rather than collide.

I look at the routine that calls the collision detection routine. It has nested for loops going between ever freaking ball and every other. Surely it can't have missed a pair. Maybe it has to do with those conditions in the collision detection routine that I've ignored that deal with embedded or non-colliding balls. I fuss with these. Things get worse. More wasted time.

I've discovered another problem. When the ball bounces away from another, it seems to be doing so, not from where the collision takes places, but from some point inside the other ball. Ok, so I have to adjust my collision resolution routine to

  • Back off the previous motion
  • Move only as far as to the exact point where the collision occurs
  • Move the remaining untravelled distance in the new direction

Crap. I've broken it again. More fixing. My son wants to know what happened to his picture of the dinosaur. "Ask Mommy!"

OK. So that works, but now there's this problem where the balls suddenly speed up at the point of collision. I finally discover that my nested for loops need to make sure they don't process collisions both between A & B and also between B & A.

It's working. It's beautiful! My wife tells me I'm sleeping on the couch tonight. I decide to get rid of all those extraneous pre-chapter 8 pseudo-pseudo code functions I took from the book. Combine everything into one single happy routine. I manage to break it several times in the process.

It's working again. It's relatively short. It's smooth. No wierd jitter or freakish speeding up and passing through another ball.

But sometimes, one ball gets embedded within another. I decide to kludge this by returning NaN for the number value on my collision detection routine if it's embedded. Life is good! Math is fun.

Except, I don't actually understand what the math done in the program does. I'm telling myself I actually coded it, even though I used pseudo code routines from the book. The book didn't have enough pictures for my taste. After all, I did this once, about a hundred years ago.

So, you want to see my code? In your dreams! After all my blood, sweat, and tears. Having to sleep on the couch. A child traumatized for life. You want I should just let you have the fruit of my labor? Well maybe. But from now on, every time you even think of collisions, you have to pay me a royalty of about a million dollars.

Oh, and if you are able to make this work better, smoother, faster, more bionic than mine, in AS3, of course, then please send me what you are able to achieve. I like to learn too. It's just more painful for me.

 

Code

Here's what the document class looks like:

package { import flash.display.MovieClip; import flash.events.MouseEvent; import flash.events.Event; import Circle; public class CollisionDetection extends MovieClip { // Constants: // Public Properties: // Private Properties: private var v1:Array = new Array(); private var v2:Array = new Array(); private var balls:Array=[]; private var nBalls:uint=15; private var maxV:Number=5; private var minR:Number=20; // Initialization: public function CollisionDetection() { for(var bt:uint=0;bt < nBalls;bt++) { var b:Circle = new Circle(); balls.push(b); b.x=Math.random()*stage.stageWidth; b.y=Math.random()*stage.stageHeight; b.dX=(1-2*Math.random())*maxV; b.dY=(1-2*Math.random())*maxV; b.setR(minR*(1+Math.random())); addChild(b); } stage.addEventListener(Event.ENTER_FRAME,doAdvance); } // Public Methods: public function doAdvance(e:Event):void { for(b1=0;b1<balls.length;b1++) balls[b1].movedThisRound=false; for(var b1:uint=0;b1<balls.length;b1++) for(var b2:uint=0;b2<b1;b2++) checkAndResolveCollisions(balls[b1],balls[b2]); for(b1=0;b1<balls.length;b1++) forceWithinBounds(balls[b1]); } public function checkAndResolveCollisions(c1:MovieClip,c2:MovieClip):void { var w:Array=[c1.x-c2.x,c1.y-c2.y]; var r:Number= c1.r+c2.r; var rr:Number= r*r; var ww:Number= w[0]*w[0]+w[1]*w[1]; if (ww>=rr) // embedded, no { var v:Array= [c1.dX-c2.dX,c1.dY-c2.dY]; var a:Number= v[0]*v[0]+v[1]*v[1]; var b:Number= w[0]*v[0]+w[1]*v[1]; var c:Number= ww-rr; var root:Number=b*b-a*c; if (root>=0) // yes, a collision occurs { var t:Number=(-b-Math.sqrt(root))/a; if (t<=1 && t>=0) // yes, moving in correct direction for collision { c1.update(t, false); c2.update(t, false); var n:Array=[c2.x-c1.x,c2.y-c1.y]; // normal from c1 to c2 var mr:Number=c1.m/c2.m; // ratio of masses var dV2:Array=[c2.dX,c2.dY]; // dV of c2 var u:Array=[c1.dX-dV2[0],c1.dY-dV2[1]]; // diff of dVs of C1,C2 var imn:Number=1/Math.sqrt(n[0]*n[0]+n[1]*n[1]); // inverse of normal's magnitude var nn:Array=[n[0]*imn,n[1]*imn]; // normalized normal (mag=1) var mv:Number=Math.sqrt(v[0]*v[0]+v[1]*v[1]); // magnitude of n var cun:Number=mv*Math.cos( // component of u in n Math.atan2(n[1],n[0]) -Math.atan2(u[1],u[0]) ); var sf:Number=cun*imn; // unnamed scale factor var un:Array=[n[0]*sf,n[1]*sf]; // u in dir of normal var ut:Array=[u[0]-un[0],u[1]-un[1]]; // u in dir of tangent var num:Number=mr-1; // numerator of (mr-1)/(mr+1) var invDen:Number=1/(mr+1); // inverse of denominator var vn:Array=[un[0]*num*invDen,un[1]*num*invDen]; var wn:Array=[un[0]*2*mr*invDen,un[1]*2*mr*invDen]; var nuDV1:Array=[ut[0]+vn[0]+dV2[0],ut[1]+vn[1]+dV2[1]]; var nuDV2:Array=[wn[0]+dV2[0],wn[1]+dV2[1]]; c1.dX=nuDV1[0]; c1.dY=nuDV1[1]; c2.dX=nuDV2[0]; c2.dY=nuDV2[1]; c1.update(1-t); c2.update(1-t); } else { c1.update(); c2.update(); } } else { c1.update(); c2.update(); } } else // embedded, yes { c1.update(); c1.x+=w[0]; c1.y+=w[1]; c2.update(); } } public function forceWithinBounds(c:MovieClip):void { if (c.x<c.r) { c.dX=Math.abs(c.dX); c.x=c.r; } else if (c.x>stage.stageWidth-c.r) { c.dX=-Math.abs(c.dX); c.x=stage.stageWidth-c.r; } if (c.y<c.r) { c.dY=Math.abs(c.dY); c.y=c.r; } if (c.y>stage.stageHeight-c.r) { c.dY=-Math.abs(c.dY); c.y=stage.stageHeight-c.r; } } // Protected Methods: } }

Here's what the ball class looks like:

package { import flash.display.MovieClip; public class Circle extends MovieClip { // Constants: // Public Properties: public var dX:Number=0; public var dY:Number=0; public var prevX:Number=0; public var prevY:Number=0; public var r:Number=10; public var m:Number; public var r2d:Number=180/Math.PI; public var movedThisRound:Boolean=false; // Private Properties: // Initialization: public function Circle() { reDraw(); } // Public Methods: public function reDraw():void { m=Math.PI*r*r; with (graphics) { clear(); beginFill(0xFF0000,0.5); drawEllipse(-r,-r,2*r,2*r); endFill(); beginFill(0x0000ff,0.5); moveTo(0,-r); lineTo(-6,-r/2); lineTo(-3,-r/2); lineTo(-3,0); lineTo(+3,0); lineTo(+3,-r/2); lineTo(+6,-r/2); lineTo(0,-r); endFill(); } } public function setR(nuR:Number):void { r=nuR; reDraw(); } public function update(p:Number=1, mtr:Boolean=true):void { if (!movedThisRound || !mtr) { movedThisRound=true; rotation=90+r2d*Math.atan2(dY,dX); if (p==1) { prevX=x; prevY=y; } x+=p*dX; y+=p*dY; } } // Protected Methods: } }