# Examples of wall avoidance algorithm dealing with rectangles instead of lines?

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

else
{
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.

• 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