Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a tile based engine and in the middle of translating out the example wall avoidance alogrithm in the book AI programming by example. I was wondering if the method below can be modified so that it takes a rectangle instead of vector C and D and still produce the same output ?

/-------------------- LineIntersection2D-------------------------
//  Given 2 lines in 2D space AB, CD this returns true if an 
//  intersection occurs and sets dist to the distance the intersection
//  occurs along AB. Also sets the 2d vector point to the point of
//  intersection
inline bool LineIntersection2D(Vector2D   A,
                               Vector2D   B,
                               Vector2D   C, 
                               Vector2D   D,
                               double&     dist,
                               Vector2D&  point)

  double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y);
    double rBot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);

    double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y);
    double sBot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);

    if ( (rBot == 0) || (sBot == 0))
        //lines are parallel
        return false;

    double r = rTop/rBot;
    double s = sTop/sBot;

    if( (r > 0) && (r < 1) && (s > 0) && (s < 1) )
    dist = Vec2DDistance(A,B) * r;

    point = A + r * (B - A);

    return true;

        dist = 0;

    return false;
share|improve this question
up vote 4 down vote accepted

Sorry to state the obvious, but rectangles are essentially 4 lines.

Why not just reuse the code and have something like:

RectangleIntersectionWithLine( Vector2D a, Vector2D b, BoundingBox box )  
    LineIntersection2D( a, b, box.Min, Vector2D( box.Min.x, box.Max.y ) );  
    LineIntersection2D( a, b, box.Min, Vector2D( box.Max.x, box.Min.y ) );  
    LineIntersection2D( a, b, box.Max, Vector2D( box.Min.x, box.Max.y ) );  
    LineIntersection2D( a, b, box.Max, Vector2D( box.Max.x, box.Min.y ) );  

I leave the return values, etc up to you.

share|improve this answer
haha its well deserved, thanks for the help – dbomb101 Aug 16 '11 at 12:38
Although thinking about it now, probably not ideal as this would be pretty damn cpu instensive – dbomb101 Aug 16 '11 at 12:45
You could just do a broadphase check using a simple bounding box intersection before you do it if CPU cycles are what you're worried about. I wouldn't worry about it though, if your game is lacking in performance, it's most likely something stupid. Don't prematurely optimize, CPU's are more capable than what people give them credit for :) – Ray Dey Aug 16 '11 at 13:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.