The rectangle collision detection is explained here. However, there's something I forgot to say
about the circle collision detection. In order to remove the sqrt() call
you can square both sides of the comparisons. That is, instead of getting the magnitude of the
distance vector, get square its magnitude (x ^ 2 + y ^ 2) and use (fSafeDistance * fSafeDistance)
instead of fSafeDistance.
Notes :
(1) I attached an image that would (hopefully) help you understand the rectangle collision algorithm better.
(2) In the code below, I made all class members public in order to avoid declaring and defining
accessors (which would take some time, and I don't have much time)
(3) I put all the explanation in the code as an example of code documentation.
(4) I've done little testing to the code, and it ran well. Although I can't guarantee it will do
so forever. So you'd better check it yourself.
(5) All the checks done here are for static objects. Handling moving objects requires some
more work, and it's not discussed here.
(6) If you don't like getting the code as well as the explanation say so. I like coding stuff (as
a form of training & reminding myself of things I don't use often), but if you'd prefer having
some pseudo code instead. Say so.
(7) Sorry for replying a couple of days late, I didn't have time to write except today.
Code:
// Just putting this here so that everything's contained in one piece of code
// <old>
enum ECollisionState
{
CS_SEPARATE,
CS_OVERLAP,
CS_TOUCH
};
struct Vec2_t
{
float x,y;
};
// </old>
// Vector class inherits from vector struct : If you're planning for C compatibility, you should
// define C functions that provides any functionality provided by this vector class
// These C functions should work with the struct instead
class CVec2 : public Vec2_t
{
// Methods
public: // Construction & destruction
// ----------------------------------------------------------------
// Name : CVec2
// Access : public
// Ret : None
// Exception(s) : None
// Desc : Empty default constructor
// Arguments : None
// ----------------------------------------------------------------
CVec2() {}
// ----------------------------------------------------------------
// Name : CVec2
// Access : public
// Ret : CVec2
// Exception(s) : None
// Desc : Constructs a 2D vector given its 2 components
// Arguments :
// float fX - X component
// float fY - Y component
// ----------------------------------------------------------------
inline CVec2(float fX,float fY) { x = fX; y = fY;}
// Methods
public: // Operations : I only defined operations necessary for the algorithms
// You should add all what you need
// ----------------------------------------------------------------
// Name : operator +
// Access : public
// Ret : CVec2
// Exception(s) : None
// Desc : Adds the given vector to this vector and returns
// the result
// Arguments :
// CVec2& rvVec - Reference to the vector to be added to this vector
// ----------------------------------------------------------------
inline CVec2 operator +(CVec2& rvVec)
{
return CVec2(x + rvVec.x, y + rvVec.y);
}
// ----------------------------------------------------------------
// Name : operator -
// Access : public
// Ret : CVec2
// Exception(s) : None
// Desc : Subtracts the given vector from the current
// vector and returns the result
// Arguments :
// CVec2& rvVec - Reference to the vector to be subtracted from this vector
// ----------------------------------------------------------------
inline CVec2 operator -(CVec2& rvVec)
{
return CVec2(x - rvVec.x, y - rvVec.y);
}
// ----------------------------------------------------------------
// Name : GetMagnitudeSqr
// Access : public
// Ret : float
// Exception(s) : None
// Desc : Returns square the magnitude of the vector
// Arguments : None
// ----------------------------------------------------------------
inline float GetMagnitudeSqr()
{
// Magnitude = SquareRoot(x ^ 2 + y ^ 2)
// MagnitudeSquared = x ^ 2 + y ^ 2
return (x * x, y * y);
}
// ----------------------------------------------------------------
// Name : Absolute
// Access : public
// Ret : void
// Exception(s) : None
// Desc : Makes the vector components +ve
// Arguments : None
// ----------------------------------------------------------------
inline void Absolute()
{
x = (x >= 0)? x : -x;
y = (y >= 0)? y : -y;
}
};
// The CD_ stands for CollisionDetection. I like to use such a naming convention
// You can use namespaces instead if you wish, or just omit the CD_.
class CD_CRectangle
{
// Data
public:
// The Center of the rectangle & the X,Y extensions of the rectangle (length & width)
CVec2 m_vCenter,m_vDimensions;
// Methods
public: // Construction and destruction
// ----------------------------------------------------------------
// Name : CD_CRectangle
// Access : public
// Ret : None
// Exception(s) : None
// Desc : Empty default constructor
// Arguments : None
// ----------------------------------------------------------------
CD_CRectangle() {}
// ----------------------------------------------------------------
// Name : CD_CRectangle
// Access : public
// Ret : None
// Exception(s) : None
// Desc : Constructs the rectangle from a center, and the
// dimensions
// Arguments :
// CVec2& rvCenter - The center vector
// CVec2& rvDimensions - The dimensions
// ----------------------------------------------------------------
CD_CRectangle(CVec2& rvCenter,CVec2& rvDimensions)
{
// Save local copies
m_vCenter = rvCenter;
m_vDimensions = rvDimensions;
}
// Methods
public: // Collision checking
// ----------------------------------------------------------------
// Name : CheckCollision
// Access : public
// Ret : ECollisionState (CS_OVERLAP || CS_SEPARATE || CS_TOUCH)
// Exception(s) : None
// Desc : Checks the state of the 2 rectangles (overlapping ||
// separate || touching)
// Arguments :
// CD_CRectangle& rRectangle - Reference to the rectangle we're checking
// ----------------------------------------------------------------
ECollisionState CheckCollision(CD_CRectangle& rRectangle);
};
// ----------------------------------------------------------------
// Name : CheckCollision
// Access : public
// Ret : ECollisionState (CS_OVERLAP || CS_SEPARATE || CS_TOUCH)
// Exception(s) : None
// Desc : Checks the state of the 2 rectangles (overlapping ||
// separate || touching)
// Arguments :
// CD_CRectangle& rRectangle - Reference to the rectangle we're checking
//
// How it works :
// First of all, it calculates 2 safe distances, a horizontal one
// and a vertical one. Then, it calculates the vector joining the centers
// of the 2 rectangles, this gives us 2 distances : a horizontal separation
// (x component of the vector) and a vertical one (y component).
// However, one of them might be negative (since it's a component of the vector)
// so we take the absolute horizontal and vertical separations using
// CVec2::Absolute()
//
// Then we can check as follows:
// 1 - If there's no collision, then either :
// (a) horizontal separation > safe horizontal distance : Figure (1a)
// in the attached image.
// Note that the image shows a special case (but it's useful for illustration)
// (b) vertical separation > safe vertical distance : Figure (1b)
//
// 2 - If there's collision, then these 2 conditions MUST be true (both must be true) :
// (a) Horizontal separation < safe horizontal distance
// (b) Vertical separation < safe vertical distance
//
// This is illustrated in Figure (2)
//
// 3 - If they're touching, one of the following cases is true :
// (a) Horizontal separation == safe horizontal distance &&
// Vertical separation < safe vertical distance :
// This happens when the 2 rectangles are beside each other.
//
// (b) Vertical separation == safe vertical distance &&
// Horizontal separation < safe horizontal distance :
// This happens when one of them is on top of the other
//
// In the code, however, we don't check for the 3rd case. We check for the
// 1st & 2nd cases. If both checks fail, then we have the 3rd case.
// ----------------------------------------------------------------
ECollisionState CD_CRectangle::CheckCollision(CD_CRectangle& rRectangle)
{
// Calculate the safe distance
CVec2 vSafeDistance = m_vDimensions + rRectangle.m_vDimensions,
vSeparation;
// #1 : Calculate the separation : vector joining centers
// #2 : Make sure its values are +ve
(vSeparation = (m_vCenter - rRectangle.m_vCenter)).Absolute();
// Check for separate-state as explained in (1)
if(vSeparation.x > vSafeDistance.x || vSeparation.y > vSafeDistance.y)
return CS_SEPARATE;
// Check for collision-state as explained in (2)
if(vSeparation.x < vSafeDistance.x && vSeparation.y < vSafeDistance.y)
return CS_OVERLAP;
// Now they must be touching
return CS_TOUCH;
}
Rectangle and circle collision detection are nice for relatively large objects.
However, for thin inclined objects they're disastrous and will give you ugly results.
For example, an inclined line with its bounding rectangle would look like (ASCII Art, if something
wrong happens and the following isn't displayed in monospaced font. Copy it and paste it in any
word processor/text editor that uses monospaced font so that you can view it) :
Code:
.-------.
|\ |
| \ |
| \ |
| \ |
| \ |
| \ |
|______\|
Since the algorithm forces the object to act as a rectangle, it will be very noticable with such
a thin object as a line. To solve that you'd need to use oriented rectangles or direct line collision
checks.
I've never tried oriented rectangle checking before, so I'll try to write a little about line collision next
time god-willing. Although you'd have to wait for some time, cause I'm somewhat busy nowadays.