Ray casting is a technique usually used in 3D worlds (often for rendering). Ray casting is exactly what it implies a ray is cast from a start point until it hits something (or a max length, so the computer doesn’t die). Ray casting in 2D is great for collision detections, especially fast-moving objects (bullets).

In this post, we will learn the basics of ray casting in 2D, then we will apply it to bullets in a simple environment.

A ray is just a line. It has a start point and an end point. In order to use this method effectively, we need to cast our rays fast. To do this, we will use Bresenham’s line algorithm. It is the fastest way to draw a line. It doesn’t support anti-aliasing, but that isn’t important to us because we won’t ever see the line (if we wanted to see the line, we would just ask flash’s graphics engine to draw a line for us).

We will be using the Vector2D.as class for this as well.

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);

This is a bit tricky. The algorithm only draws lines with a slope of less than 1. In order to draw steeper lines, we reflect the line across y=x to get a smaller slope.

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;
}

private static function swap(x:Number,y:Number):Vector2D {
return new Vector2D(y,x)
}

For more information about Bresenham’s Algorithm, you can read this article.

Now that we can cast rays, we need to determine if they are intersecting with any shape. This is ray casting’s main advantage over the separation of axis theorem. Unlike SAT, ray casting works with convex and concave polygons as well as circles.

Dealing with circles is easy:

for (i = 0; i < ray.length; i++) {//where ray is the array of points returned from the bresenhamLine function
var d:Number = Math2.distance(ray[i].x,ray[i].y,circle.x,circle.y);//get the distance between the point and circle
if(d < circle.radius) return true;//if distance is less than radius, they are touching
}
return false;//if you tested all the points and none were touching, there is no collision

Polygons are a bit more complicated. For this we will test each point against the polygon using the point-in-polygon algorithm.

The point in polygon algorithm detects the edges of the polygon, then it tests how many edges are on both sides of the point. If there are an even number of blue points, then the point is outside the polygon. If there are an odd number of blue points, the point is in the polygon.

In as3:

public static function pointInPoly(point:Vector2D,poly:RayShape):Boolean {

point is a point from the ray. You must loop through each point in the ray until you find one that collides.

var sides:int = poly.vertices.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.vertices[i].y < point.y && poly.vertices[j].y >= point.y) || (poly.vertices[j].y < point.y && poly.vertices[i].y >= point.y)){//detect edges
if(poly.vertices[i].x+(point.y-poly.vertices[i].y)/(poly.vertices[j].y-poly.vertices[i].y)*(poly.vertices[j].x-poly.vertices[i].x) < point.x){//detect edges
oddNodes = !oddNodes;//if that was an edge, switch oddNodes
}
}
j = i;
}
return oddNodes;//return oddNodes
}

Odd nodes is either true or false. True if you are inside the poly, false if you are outside the poly.

A rayshape looks like this:



package com.rocketmandevelopment.collisions.raycasting {

import com.rocketmandevelopment.math.Vector2D;


import flash.display.Graphics;


public class RayShape {

public var vertices:Array;


public function RayShape(vertices:Array){

this.vertices = vertices;

}


public function move(velocity:Vector2D):void {

var len:int = vertices.length

for (var i:int = 0; i < len; i++) {

vertices[i].add(velocity);

}

}


public function setPosition(position:Vector2D):void {

var diff:Vector2D = position.subtract(middle());

var len:int = vertices.length

for (var i:int = 0; i < len; i++) {

vertices[i].add(diff);

}

}


public function middle():Vector2D {

var mid:Vector2D = new Vector2D();

var len:int = vertices.length

for (var i:int = 0; i < len; i++) {

mid.add(vertices[i]);

}

mid.divide(vertices.length);

return mid;

}


public function debugDraw(graphics:Graphics):void {

graphics.lineStyle(0);

graphics.moveTo(vertices[0].x,vertices[0].y);

var len:int = vertices.length

for (var i:int = 0; i < len; i++) {

graphics.lineTo(vertices[i].x,vertices[i].y);

}

}


}

}



All a rayshape does is hold the location of each vertex and move it around.


Be Sociable, Share!