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;

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 '11 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 '11 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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