Collision detection made easy!

[Sammo]

Here's a class that handles the maths behind collision detections (not a hitTest in sight :) ).


class Collisions {
private static var intercectionPoint:Object;
private static var intercectionCoordinates:Array;

/*
* pointToCircle determines whether a coordinate is inside the boundries of a circle.
* It takes two parameters, a custom object for the point: {x, y}
* and a custom object for the circle: {x, y, radius}, with x and y being the center coordinates.
*/
static function pointToCircle(point:Object, circle:Object):Boolean {
var dx:Number = circle.x - point.x;
var dy:Number = circle.y - point.y;
var distance:Number = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
return (distance <= circle.radius) ? true : false;
}

/*
* circleToCircle determines whether or not two circles are colliding.
* It takes two parameters, one for each circle to check against. Each is in the form
* of an object: {x, y, xmov, ymov, radius}
*/
static function circleToCircle(circle1:Object, circle2:Object):Boolean {
var radii:Number = circle1.radius + circle2.radius;

// You are not expected to understand this. But for the hell of it:
// radii = sqrt((x2-x1)^2 + (y2-t1)^2) where xn or yn = circleN.x + circleN.xmov * t, where
// t = time. We can rearranged this to get a quadratic for t. When solved if t is between 0 and 1,
// we have had a collision since our last check. Over 1 it's going to happen in the future.

// at^2 + bt + c = 0
var a:Number = (-2 * circle1.xmov * circle2.xmov + Math.pow(circle1.xmov, 2) + Math.pow(circle2.xmov, 2)) +
(-2 * circle1.ymov * circle2.ymov + Math.pow(circle1.ymov, 2) + Math.pow(circle2.ymov, 2));
var b:Number = (-2 * circle1.x * circle2.xmov - 2 * circle2.x * circle1.xmov + 2 * circle1.x * circle1.xmov +
2 * circle2.x * circle2.xmov) + (-2 * circle1.y * circle2.ymov - 2 * circle2.y * circle1.ymov +
2 * circle1.y * circle1.ymov + 2 * circle2.y * circle2.ymov);
var c:Number = (-2 * circle1.x * circle2.x + Math.pow(circle1.x, 2) + Math.pow(circle2.x, 2)) + (-2 * circle1.y *
circle2.y + Math.pow(circle1.y, 2) + Math.pow(circle2.y, 2) - Math.pow(radii, 2));

// Use the quadratic formula to get two values for time:
var t:Array = [];
t[0] = (-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / 2 * a;
t[1] = (-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / 2 * a;

var collided:Boolean;
if (t[0] > 0 && t[1] <= 1) {
collided = true;
}
if (t[1] > 0 && t[1] <= 1) {
if (collided = undefined || t[1] < t[0]) {
collided = true;
}
}

if (collided) {
intercectionCoordinates = [{x: circle1.x, y: circle1.y}, {x: circle2.x, y: circle2.y}];
return true;
} else {
return false;
}
}

/*
* lineToLine determines whether or not two lines are intercepting.
* It takes two parameters, two points per line.
* In the format of: {x1, y1, x2, y2}
*/
static function lineToLine(line1:Object, line2:Object):Boolean {
// Gradients of the lines.
line1.m = (line1.y2 - line1.y1) / (line1.x2 - line1.x1);
line2.m = (line2.y2 - line2.y1) / (line2.x2 - line2.x1);
// Parallel lines do not intercept.
if (line1.m == line2.m) return false

// y - y1 = m(x - x1)
// The coordinates of intercection
var x:Number = (line1.m * line1.x1 - line2.m * line2.x1 - line1.y1 + line2.y1) / (line1.m - line2.m);
var y:Number = line1.m * x - line1.m * line1.x1 + line1.y1;
intercectionPoint = {x: x, y: y};

// Checking to see if the coordinates are on the line segments.
if (range(x, line1.x1, line1.x2) || range(y, line1.y1, line1.y2)) {
if (range(x, line2.x1, line2.x2) || range(y, line2.y1, line2.y2))
return true;
}
return false;
}

/*
* lineToCircle determines if a collision between a circle and a line has or is happening
* It takes two parameters, an object for the line and an object for the circle.
* The line takes the format: {x1, y1, x2, y2} and the circle object: {x, y, xmov, ymov, radius}
*/
static function lineToCircle(line:Object, circle:Object):Boolean {
circle.m = circle.ymov / circle.xmov;
if (circle.m == Infinity) circle.m = 1000000;
if (circle.m == -Infinity) circle.m = -1000000;
circle.c = circle.y - circle.m * circle.x;

// y = mx + c
line.m = (line.y2 - line.y1) / (line.x2 - line.x1);
line.c = line.y1 - line.m * line.x1;
line.angle = Math.atan2(line.y2 - line.y1, line.x2 - line.x1);

// Point of interception
var x:Number = (circle.c - line.c) / (line.m - circle.m);
var y:Number = line.m * x + line.c;

var theta:Number = Math.atan2(circle.ymov, circle.xmov);
var gamma:Number = theta - line.angle
var r:Number = circle.radius / Math.sin(gamma);
x = x - r * Math.cos(theta);
y = y - r * Math.sin(theta);

var distance:Number = Math.sqrt(Math.pow(x - circle.x, 2) + Math.pow(y - circle.y, 2));
var velocity:Number = Math.sqrt(Math.pow(circle.xmov, 2) + Math.pow(circle.ymov, 2));
var frames:Number = distance / velocity;

var perpendicular:Object = {};
perpendicular.m = -1/line.m;
perpendicular.c = y - perpendicular.m * x;

// Point of contact
var contact:Object = {};
contact.x = (line.c - perpendicular.c) / (perpendicular.m - line.m);
contact.y = perpendicular.m * contact.x + perpendicular.c;
if (range(contact.x, line.x1, line.x2) || range(contact.y, line.y1, line.y2)) {
// Collision is within line segment
if (frames <= 1 && frames > 0) {
intercectionCoordinates = [{x: contact.x, y: contact.y}, {x: circle.x, y: circle.y}];
return true;
}
} else {
return false;
}
}


/*
* This one's easy :)
* pointToCircle checks to see if a point is within a rectangle.
* The point object requires: {x, y}
* The rectangle object requires: {x, y, width, height}
* Where x and y are the centre points for the rectangle.
*/
static function pointToRectangle(point:Object, rectangle:Object):Boolean {
var walls:Object = {
left: rectangle.x - rectangle.width/2,
right: rectangle.x + rectangle.width/2,
top: rectangle.y - rectangle.height/2,
bottom: rectangle.y + rectangle.height/2
};
return (range(point.x, walls.left, walls.right) && range(point.y, walls.top, walls.bottom)) ? true : false;
}

/*
* rectangleToRectangle checks to see if two rectangles are intersecting
* It takes two identical objects, one for each rectangle that follow the form:
* {x, y, width, height} where x and y are the center points;
*/
static function rectangleToRectangle(rectangle1:Object, rectangle2:Object):Boolean {
var walls1:Object = {};
var walls2:Object = {};
walls1.left = rectangle1.x - rectangle1.width/2;
walls1.right = rectangle1.x + rectangle1.width/2;
walls1.top = rectangle1.y - rectangle1.height/2;
walls1.bottom = rectangle1.y + rectangle1.height/2;

walls2.left = rectangle2.x - rectangle2.width/2;
walls2.right = rectangle2.x + rectangle2.width/2;
walls2.top = rectangle2.y - rectangle2.height/2;
walls2.bottom = rectangle2.y + rectangle2.height/2;

if ((walls1.right > walls2.left && walls1.left < walls2.right) && (walls1.bottom > walls2.top && walls1.top < walls2.bottom)) {
intercectionCoordinates = [{x: rectangle1.x, y: rectangle1.y}, {x: rectangle2.x, y: rectangle2.y}];
return true
} else {
return false;
}
}

/* Get Methods */

/*
* Returns the interception point from the last lineToLine check performed.
*/
static function get lastIntercectionPoint():Object {
return intercectionPoint;
}

/*
* Returns an array of coordinates of the objects involved in the last collision, at the moment of collision.
*/
static function get lastIntercectionCoordinates():Array {
return intercectionCoordinates;
}


/* Private Method(s) */
private static function range(point:Number, start:Number, end:Number):Boolean {
return (point > start && point < end) ? true : (point < start && point > end) ? true : false;
}
}

How to use it:
For all these examples, the variables circle1, circle2, rectangle1 and rectangle2 are all movieclips of their shape.

pointToCircle

function onMouseDown() {
var point:Object = {x: _xmouse, y: _ymouse};
var circle:Object = {x: circle1._x, y: circle1._y, radius: circle1._width/2};
if (Collisions.pointToCircle(point, circle)) {
trace("Hit!");
} else {
trace("Miss!");
}
}
Pretty simple for this one. This is frame dependent.

circleToCircle

function onEnterFrame() {
circle1._x += 1;
circle1._y += 2;
circle2._x -= 1;

var c1:Object = {x: circle1._x, y: circle1._y, xmov: 1, ymov: 2, radius: circle1._width/2};
var c2:Object = {x: circle2._x, y:circle2._y, xmov: -1, ymov: 0, radius: circle2._width/2};
if (Collisions.circleToCircle(c1, c2)) {
trace("Hit!");
} else {
trace("Miss!");
}
}
If a collision exists, you can access the points of each circle at that moment by accessing: Collisions.lastIntercectionCoordinates, which returns an array, [c1, c2]. This check is frame independent!

lineToLine

var line1:Object = {x1: 20, y1: 20, x2: 350, y2: 350};
var line2:Object = {x1: 40, y1: 300, x2: 400, y2: 30};
lineStyle(2, 0x000000);
moveTo(line1.x1, line1.y1);
lineTo(line1.x2, line1.y2);
moveTo(line2.x1, line2.y1);
lineTo(line2.x2, line2.y2);

if (Collisions.lineToLine(line1, line2)) {
trace("Collision at " + Collisions.lastIntercectionPoint);
} else {
trace("Miss!");
}
This checks to see if the line segments intercect, not the line's trajectory (where all lines that aren't parallel will eventually collide). You can see the use of Collisions.lastIntercectionPoint to return the point at which the lines collide.

lineToCircle

var line:Object = {x1: 350, y1: 20, x2: 300, y2: 350};
lineStyle(2, 0x000000);
moveTo(line.x1, line.y1);
lineTo(line.x2, line.y2);

function onEnterFrame() {
circle1._x += 2;
circle1._y += 1;

var circle:Object = {x: circle1._x, y: circle1._y, xmov: 2, ymov: 1, radius: circle1._width/2};
if (Collisions.lineToCircle(line, circle)) {
trace("Hit!");
} else {
trace("Miss!");
}
}
Collisions.lastIntercectionCoordinates is also available for this function, the first item in the array being the point on the line that the circle will collide with first and the second item being the x and y points of the circle at the moment of collision. This check is frame independent!

pointToRectangle

function onMouseDown() {
var point:Object = {x: _xmouse, y: _ymouse};
var rectangle:Object = {x: rectangle1._x, y: rectangle1._y, width: rectangle1._width, height: rectangle1._height};
if (Collisions.pointToRectangle(point, rectangle)) {
trace("Hit!");
} else {
trace("Miss!");
}
}
Same principal as the pointToCircle check only.. with.. a rectangle. Frame dependent.

rectangleToRectangle

function onEnterFrame() {
rectangle1._x += 2;
rectangle1._y += 1;
rectangle2._x -= 1;

var r1:Object = {x: rectangle1._x, y: rectangle1._y, width: rectangle1._width, height: rectangle1._height};
var r2:Object = {x: rectangle2._x, y: rectangle2._y, width: rectangle2._width, height: rectangle2._height};

if (Collisions.rectangleToRectangle(r1, r2)) {
trace("Hit!");
} else {
trace("Miss!");
}
}
Collisions.lastIntercectionCoordinates will return the coordinates of the two rectangles at the point of the last collision. Frame dependent.

There you go. I hope this helps, don't be afraid to ask any questions you have in this thread.

[andrewfitz]

What's the speed of this? Is it fast if you have like 50 mc on the stage checking each other?

[Sammo]

What's the speed of this? Is it fast if you have like 50 mc on the stage checking each other?
Honestly, I haven't done any benchmarks. There isn't really anything to compare it against anyway.

I'm sure frame dependent checks would be faster than independent but you then get the age old problem of having an mc on the left of a line and then on the right a frame later with no collision detected, which, in my opinion is deffinatly worth solving.

[Snipergen]

a demo would make this topic more interesting... :)

and for collisions...

please check out www.fisixengine.com !!!!!!

[jjcorreia]

Looking over it briefly, it looks like it could use some optimizations. Still nice.

[Sammo]

a demo would make this topic more interesting... :)

and for collisions...

please check out www.fisixengine.com !!!!!!
It's a utility class, so there's nothing really to see other than how it works in code. But I will try to find time to make a small app that uses it for tomorrow.

And I've seen the Fisix engine, but it's very different to this class. It's an entire engine to handle physics, this is simply a class that makes it (much) easier to tell when two MovieClips are colliding.

[Sammo]

Updated it. Fixed a bug in the circleToCircle method and added am optional callback feature to all methods.


class Collisions {
private static var intercectionPoint:Object;
private static var intercectionCoordinates:Array;

/*
* pointToCircle determines whether a coordinate is inside the boundries of a circle.
* It takes two parameters, a custom object for the point: {x, y}
* and a custom object for the circle: {x, y, radius}, with x and y being the center coordinates.
*/
static function pointToCircle(point:Object, circle:Object, callback:Function):Boolean {
var dx:Number = circle.x - point.x;
var dy:Number = circle.y - point.y;
var distance:Number = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
if (distance <= circle.radius) {
if (callback) callback(point, circle);
return true;
} else {
return false;
}
}

/*
* circleToCircle determines whether or not two circles are colliding.
* It takes two parameters, one for each circle to check against. Each is in the form
* of an object: {x, y, xmov, ymov, radius}
*/
static function circleToCircle(circle1:Object, circle2:Object, callback:Function):Boolean {
var radii:Number = circle1.radius + circle2.radius;

// You are not expected to understand this. But for the hell of it:
// radii = sqrt((x2-x1)^2 + (y2-t1)^2) where xn or yn = circleN.x + circleN.xmov * t, where
// t = time. We can rearranged this to get a quadratic for t. When solved if t is between 0 and 1,
// we have had a collision since our last check. Over 1 it's going to happen in the future.

// at^2 + bt + c = 0 */
var a = (-2 * circle1.xmov * circle2.xmov + Math.pow(circle1.xmov, 2) + Math.pow(circle2.xmov, 2)) +
(-2 * circle1.ymov * circle2.ymov + Math.pow(circle1.ymov, 2) + Math.pow(circle2.ymov, 2));
var b = (-2 * circle1.x * circle2.xmov - 2 * circle2.x * circle1.xmov + 2 * circle1.x * circle1.xmov + 2 * circle2.x * circle2.xmov) +
(-2 * circle1.y * circle2.ymov - 2 * circle2.y * circle1.ymov + 2 * circle1.y * circle1.ymov + 2 * circle2.y * circle2.ymov);
var c = (-2 * circle1.x * circle2.x + Math.pow(circle1.x, 2) + Math.pow(circle2.x, 2)) +
(-2 * circle1.y * circle2.y + Math.pow(circle1.y, 2) + Math.pow(circle2.y, 2)) - Math.pow(radii, 2);

// Use the quadratic formula to get two values for time:
var t:Array = [];
t[0] = (-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / (2 * a);
t[1] = (-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / (2 * a);
var time:Number;

var collided:Boolean;
if (t[0] > 0 && t[0] <= 1) {
time = t[0];
collided = true;
}
if (t[1] > 0 && t[1] <= 1) {
if (collided = undefined || t[1] < t[0]) {
time = t[1];
collided = true;
}
}

if (collided) {
intercectionCoordinates = [{x: circle1.x, y: circle1.y}, {x: circle2.x, y: circle2.y}];
if (callback) callback(circle1, circle2, time);
return true;
} else {
return false;
}
}

/*
* lineToLine determines whether or not two lines are intercepting.
* It takes two parameters, two points per line.
* In the format of: {x1, y1, x2, y2}
*/
static function lineToLine(line1:Object, line2:Object, callback:Function):Boolean {
// Gradients of the lines.
line1.m = (line1.y2 - line1.y1) / (line1.x2 - line1.x1);
line2.m = (line2.y2 - line2.y1) / (line2.x2 - line2.x1);
// Parallel lines do not intercept.
if (line1.m == line2.m) return false

// y - y1 = m(x - x1)
// The coordinates of intercection
var x:Number = (line1.m * line1.x1 - line2.m * line2.x1 - line1.y1 + line2.y1) / (line1.m - line2.m);
var y:Number = line1.m * x - line1.m * line1.x1 + line1.y1;
intercectionPoint = {x: x, y: y};

// Checking to see if the coordinates are on the line segments.
if (range(x, line1.x1, line1.x2) || range(y, line1.y1, line1.y2)) {
if (range(x, line2.x1, line2.x2) || range(y, line2.y1, line2.y2)) {
if (callback) callback(line1, line2);
return true;
}
}
return false;
}

/*
* lineToCircle determines if a collision between a circle and a line has or is happening
* It takes two parameters, an object for the line and an object for the circle.
* The line takes the format: {x1, y1, x2, y2} and the circle object: {x, y, xmov, ymov, radius}
*/
static function lineToCircle(line:Object, circle:Object, callback:Function):Boolean {
circle.m = circle.ymov / circle.xmov;
if (circle.m == Infinity) circle.m = 1000000;
if (circle.m == -Infinity) circle.m = -1000000;
circle.c = circle.y - circle.m * circle.x;

// y = mx + c
line.m = (line.y2 - line.y1) / (line.x2 - line.x1);
line.c = line.y1 - line.m * line.x1;
line.angle = Math.atan2(line.y2 - line.y1, line.x2 - line.x1);

// Point of interception
var x:Number = (circle.c - line.c) / (line.m - circle.m);
var y:Number = line.m * x + line.c;

var theta:Number = Math.atan2(circle.ymov, circle.xmov);
var gamma:Number = theta - line.angle
var r:Number = circle.radius / Math.sin(gamma);
x = x - r * Math.cos(theta);
y = y - r * Math.sin(theta);

var distance:Number = Math.sqrt(Math.pow(x - circle.x, 2) + Math.pow(y - circle.y, 2));
var velocity:Number = Math.sqrt(Math.pow(circle.xmov, 2) + Math.pow(circle.ymov, 2));
var frames:Number = distance / velocity;

var perpendicular:Object = {};
perpendicular.m = -1/line.m;
perpendicular.c = y - perpendicular.m * x;

// Point of contact
var contact:Object = {};
contact.x = (line.c - perpendicular.c) / (perpendicular.m - line.m);
contact.y = perpendicular.m * contact.x + perpendicular.c;
if (range(contact.x, line.x1, line.x2) || range(contact.y, line.y1, line.y2)) {
// Collision is within line segment
if (frames <= 1 && frames > 0) {
intercectionCoordinates = [{x: contact.x, y: contact.y}, {x: circle.x, y: circle.y}];
if (callback) callback(line, circle, frames);
return true;
}
} else {
return false;
}
}


/*
* This one's easy :)
* pointToCircle checks to see if a point is within a rectangle.
* The point object requires: {x, y}
* The rectangle object requires: {x, y, width, height}
* Where x and y are the centre points for the rectangle.
*/
static function pointToRectangle(point:Object, rectangle:Object, callback:Function):Boolean {
var walls:Object = {
left: rectangle.x - rectangle.width/2,
right: rectangle.x + rectangle.width/2,
top: rectangle.y - rectangle.height/2,
bottom: rectangle.y + rectangle.height/2
};
if (range(point.x, walls.left, walls.right) && range(point.y, walls.top, walls.bottom)) {
if (callback) callback(point, rectangle);
return true;
} else {
return false;
}
}

/*
* rectangleToRectangle checks to see if two rectangles are intersecting
* It takes two identical objects, one for each rectangle that follow the form:
* {x, y, width, height} where x and y are the center points;
*/
static function rectangleToRectangle(rectangle1:Object, rectangle2:Object, callback:Function):Boolean {
var walls1:Object = {};
var walls2:Object = {};
walls1.left = rectangle1.x - rectangle1.width/2;
walls1.right = rectangle1.x + rectangle1.width/2;
walls1.top = rectangle1.y - rectangle1.height/2;
walls1.bottom = rectangle1.y + rectangle1.height/2;

walls2.left = rectangle2.x - rectangle2.width/2;
walls2.right = rectangle2.x + rectangle2.width/2;
walls2.top = rectangle2.y - rectangle2.height/2;
walls2.bottom = rectangle2.y + rectangle2.height/2;

if ((walls1.right > walls2.left && walls1.left < walls2.right) && (walls1.bottom > walls2.top && walls1.top < walls2.bottom)) {
intercectionCoordinates = [{x: rectangle1.x, y: rectangle1.y}, {x: rectangle2.x, y: rectangle2.y}];
if (callback) callback(rectangle1, rectangle2);
return true
} else {
return false;
}
}

/* Get Methods */

/*
* Returns the interception point from the last lineToLine check performed.
*/
static function get lastIntercectionPoint():Object {
return intercectionPoint;
}

/*
* Returns an array of coordinates of the objects involved in the last collision, at the moment of collision.
*/
static function get lastIntercectionCoordinates():Array {
return intercectionCoordinates;
}


/* Private Method(s) */
private static function range(point:Number, start:Number, end:Number):Boolean {
return (point > start && point < end) ? true : (point < start && point > end) ? true : false;
}
}

The callback allows you to react to a collision:

function onEnterFrame() {
circle1._x += 2;
circle1._y += 1;
circle2._x -= 1;

var c1:Object = {x: circle1._x, y: circle1._y, xmov: 2, ymov: 1, radius: circle1._width/2};
var c2:Object = {x: circle2._x, y: circle2._y, xmov: -1, ymov: 0, radius: circle2._width/2};

Collisions.circleToCircle(c1, c2, function() {
points = Collisions.lastIntercectionCoordinates;
for (var i = 0; i < points.length; i++) {
var dot = attachMovie("dot", "dot"+points[i].x, getNextHighestDepth());
dot._x = points[i].x;
dot._y = points[i].y;
}
});
}