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;

1 Answer 1


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.

  • \$\begingroup\$ Although thinking about it now, probably not ideal as this would be pretty damn cpu instensive \$\endgroup\$
    – dbomb101
    Aug 16, 2011 at 12:45
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$
    – Ray Dey
    Aug 16, 2011 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .