Back in July, we looked at how to use Ray Casting for collision detection. We also learned how to use the Separation of Axis Theorem. I recently had a request for a way to use the Shapes we created here with the Ray Casting method. First, lets do a quick review of the shape classes.

The SAT Shape Classes

The BaseShape class is the class that all shapes extend. It has the basic properties, position, rotation and scale as well as the transform matrix that transforms the vertices based on rotation, scale and position. It has getters and setters for each of those properties and all the setters update the matrix. It has only two real methods. A destroy method that destroys the shape to free up the memory. The other function uses the matrix and transforms all the vertices and return them. The Circle class extends the BaseShape class. It adds one property, a radius. It also has a transformedRadius property that returns the scaled radius (if you adjust the scaleX property on the circle). The final shape class is the Polygon. This takes care of all the shapes you should need (squares, rectangles, other convex polygons, etc.).  The polygon class adds one more method, one that returns all the lines in the polygon. This makes a line between each vertex to form the polygon. You can download the shape classes here.

Using Ray Casting

To use Ray Casting, I have a class called CollisionDetector with several static methods. The first method I use for ray casting is called rayCastingCollision. It looks like this:

public static function rayCastingCollision(lineStart:Vector2D, lineEnd:Vector2D, shapes:Array):Boolean {
//shapes is an array of BaseShapes
for(var i:int = 0; i < shapes.length; i++) {
if(shapes[i] is Circle) {
//if the shape is a circle
if(circleLineTest(shapes[i], lineStart, lineEnd)) {//do a circle test
return true;
}

} else {//if it's not a circle
//it's a polygon
var line:Array = bresenhamLine(lineStart, lineEnd);//create an line
for(var j:int = 0; j < line.length; j++) {
if(pointInPoly(line[j], shapes[i])) {//check the polygon
return true;

}
}
}
}
return false;
}

Lets start with the line circle collision. It’s relatively simple to do.


private static function circleLineTest(circle:Circle, lineStart:Vector2D, lineEnd:Vector2D):Boolean {
//set up some variables we will use to check for a collision
var d:Vector2D = lineEnd.cloneVector().subtract(lineStart);
//vector representing the length of the line
var f:Vector2D = lineStart.cloneVector().subtract(circle.position);
//vector representing distance from start of line to circle center
var a:Number = d.dotProduct(d);

var b:Number = 2 * f.dotProduct(d);

var c:Number = f.dotProduct(f) - circle.radius * circle.radius;

var discrm:Number = b * b - 4 * a * c;
//quadric equation
if(discrm < 0) {

return false;

} else {

discrm = Math.sqrt(discrm);

var t1:Number = (-b + discrm) / (2 * a);

var t2:Number = (-b - discrm) / (2 * a);

if(t1 >= 0 && t1 <= 1) {

return true

} else {

return false

}

}

return false

}

The next part of the code involves polygon line collisions. These are a bit more difficult because we don’t know anything about the polygon. It could be concave or convex, it doesn’t really matter. The first thing we do is create an array of Vector2D’s to represent the line using the Bresenham Algorithm, which is the fastest way to create a line between two points.

public static function bresenhamLine(start:Vector2D, end:Vector2D):Array {
var points:Array = []; //the array of all the points on the line
var steep:Boolean = Math.abs(end.y - start.y) > Math.abs(end.x - start.x);
//check if rise is greater than run
var swapped:Boolean = false;
if(steep) {
start = swap(start.x, start.y); //reflecting the line
end = swap(end.x, end.y);
}
if(start.x > end.x) { //make sure the line goes downward
var t:Number = start.x;
start.x = end.x;
end.x = t;
t = start.y;
start.y = end.y;
end.y = t;
swapped = true;
}
var deltax:Number = end.x - start.x; //x slope
var deltay:Number = Math.abs(end.y - start.y); //y slope, positive because the lines always go down
var error:Number = deltax / 2; //error is used instead of tracking the y values.
var ystep:Number;
var y:Number = start.y;
if(start.y < end.y) {
ystep = 1;
} else {
ystep = -1;
}
for(var x:int = start.x; x < end.x; x++) { //for each point
if(steep) {
points.push(new Vector2D(y, x)); //if its steep, push flipped version
} else {
points.push(new Vector2D(x, y)); //push normal
}
error -= deltay; //change the error
if(error < 0) {
y += ystep; //if the error is too much, adjust the ystep
error += deltax;
}
}
if(swapped) {
points.reverse();
}
return points;
}

That’s nothing to complicated. It just creates a bunch of points along the line to allow us to test if there is a collision between the polygon and line.
Finally we run this simple function to check if there is a collision between the line and polygon:

public static function pointInPoly(point:Vector2D, poly:Polygon):Boolean {
var sides:int = poly.transformedVertices.length; //amount of sides the polygon has
var i:int = 0;
var j:int = sides - 1;
var oddNodes:Boolean = false; //how many sides have we passed through?
for(i = 0; i < sides; i++) { //for each side
if((poly.transformedVertices[i].y < point.y && poly.transformedVertices[j].y >= point.y) || (poly.transformedVertices[j].y < point.y && poly.transformedVertices[i].y >= point.y)) { //detect edges
if(poly.transformedVertices[i].x + (point.y - poly.transformedVertices[i].y) / (poly.transformedVertices[j].y - poly.transformedVertices[i].y) * (poly.transformedVertices[j].x - poly.transformedVertices[i].x) < point.x) { //detect edges
oddNodes = !oddNodes; //if that was an edge, switch oddNodes
}
}
j = i;
}
return oddNodes; //return oddNodes
}

We learned all about this function here, so you can check that out if you want to learn how this function works.

Be Sociable, Share!