AS3 - How do I find where a line collides with a rectangular object?

Question

I am developing a game with Flixel as a base, and part of what I need is a way to check for collisions along a line (a line from point A to point B, specifically). Best way to explain this is I have a laser beam shooting from one ship to another object (or to a point in space if nothing is overlapping the line). I want the line to reach only until it hits an object. How can I determine mathematically / programatically where along a line the line is running into an object?

I could try measuring the length of the line and checking points for collision until one does, but that seems like way too much overhead to do every frame when I'm sure there is a mathematical way to determine it.

Edit: Before checking an object for collision with the line itself, I would first eliminate any objects not within the line's bounding box - defined by the x of the left-most point, the y of the top-most point, the x of the right-most point, and the y of the bottom-most point. This will limit line-collision checks to a few objects.

Edit again: My question seems to still not be fully clear, sorry. Some of the solutions would probably work, but I'm looking for a simple, preferably mathematical solution. And when I say "rectangle" I mean one whose sides are locked to the x and y axis, not a rotatable rectangle. So a line is not a rectangle of width 0 unless it's at 90 or -90 degrees (assuming 0 degrees points to the right of the screen).

Here's a visual representation of what I'm trying to find:

Answer 1

So, you have a line segment (A-B) and I gather that line segment is moving, and you want to know at what point the line segment will collide with another line segment (your ship, whatever).

So mathematically what you want is to check when two lines intersect (two lines will always intersect unless parallel) and then check if the point where they intersect is on your screen. First you need to convert the line segments to line equations, something like this:

typedef struct {
    GLfloat A;
    GLfloat B;
    GLfloat C;
} Line;

static inline Line LineMakeFromCoords(GLfloat x1, GLfloat y1, GLfloat x2, GLfloat y2) {
    return (Line) {y2-y1, x1-x2, (y2-y1)*x1+(x1-x2)*y1};
}

static inline Line LineMakeFromSegment(Segment segment) {
    return LineMakeFromCoords(segment.P1.x,segment.P1.y,segment.P2.x,segment.P2.y);
}

Then check if they intersect

static inline Point2D IntersectLines(Line line1, Line line2) {
    GLfloat det = line1.A*line2.B - line2.A*line1.B;
     if(det == 0){
    //Lines are parallel
            return (Point2D) {0.0, 0.0};  // FIXME should return nil
     }else{
            return (Point2D) {(line2.B*line1.C - line1.B*line2.C)/det, (line1.A*line2.C - line2.A*line1.C)/det};
     }  
}

Point2D will give you the intersect point, of course you have to test you line segment against all the ship's line segments, which can be a bit time consuming, that's were collision boxes, etc enter the picture.

The math is all in wikipedia, check there if you need more info.

Edit:

Add-on to follow up comment:

Same as before test your segment for collision against all four segments of the rectangle, you will get one of 3 cases:

1. No collision/collision point not on screen(remember the collision tests are against lines, not line segments, and lines will always intersect unless parallel), taunt Player for missing :-)
2. One collision, draw/do whatever you want the segment you're asking will be A-C (C collision point)

3. Two collisions, check the size of each resulting segment (A-C1) and (A-C2) using something like the code below and keep the one with the shortest size.

   static inline float SegmentSizeFromPoints(Vertice3D P1, Vertice3D P2) {
        return sqrtf(powf((P1.x - P2.x),2.0) + pow((P1.y - P2.y),2.0));
   }
   

The tricky bit when dealing with collisions, is figuring out ways of minimizing the number of tests you have to make.

Answer 2

1. Find the formula for the line y = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1
2. Find the bounding boxes for your sprites
3. For each sprite's bounding box:
4. For each corner of the current bounding box:
5. Enter the x value of the corner's coordinate into the line formula (from 1) and subtract the y value of the coordinate from the result
6. Record the sign from the calculation in 5
7. If all 4 signs are equal, then no collision has/will occur. If any sign is different, then a collision is possible, do further checks.

Answer 3

I'm not mathematically gifted but I think you could do something like this:

1. Measure the distance from the centre of the block and the laser beam.
2. Measure the distance between the centre of the block and the edge of the block at a given angle (there would be a formula for this I just don't know what it is).

Subtract the result of point 1 from the result of point 2.

Good thing about this is that if point 1 is larger than point 2 you know there hasn't been a collision yet.

Alternatively use box2d, and just use b2ContactPoint

Answer 4

You should look at the Separating Axis Theorem. This is generally used for polygons, but I think that you can make it work for a line and a polygon.

I found a link that explains it in a concise manner, here.