Collision detection algorithm

Just wondering how collision detection is done in the most easy and fast way, i e how is it done in most games?
I'm pretty new to game programming and most games I've made use if statements comparing obects' coordinates with each other, something like this:

if (x > obstacle_x && x < obstacle_x + obstacle_width && y > obstacle_y && y < obstacle_y + obstacle_height) {
//do stuff
}

However this takes a lot of time to write and it becomes quite ineffective to check every single obstacle if there are lots of them. Is there no better and easier way?

You can create flags. And when your character touches something, it signals a flag. Then all you have to read is if (collisionflag == 1)
{
blow up spaceship
}

Collision detection between 2 objects in 2D can be done using bounding rectangles and/or circles.

It's important, however, to define which objects/obstacles to perform collision detection with. Since checking for collision with all the objects in your world every frame update is not a smart idea. There are various approaches, the simplest one I can think of for a 2D map is to make a 2D grid composed of squares or rectangles. Each square or rectangle (called cell) remembers (knows, or more specifically points to) a list of obstacles inside it. Whenever you need to check collision, you calculate the cell in which the player lies. Then you check collision with obstacles found in this cell (and neighbouring cells since the player can be on more than one cell - on their intersection)

This is a very simple approach. Trees (like quad trees) can also be used, although I don't think their functionality is needed in a 2D world.

Circle collision detection :
Notes :
[list=1][*] I'll try to keep things in the C way (I won't use OOP), since I don't know whether you use C or C++. However, I'll use C++ style comments '//' and C++ type definition (without typedef) and variable declartion (declare a variable when needed, not in the beginning of the function) So if you use C, you'll have to make some changes.[*] The code's not optimized for performance.[/list=1]

Code:

//////////////////////////////////////////////////////
// Types 
//

// A 2D vector, for storing center information
struct Vec2_t
{
	float x,y;
};

// Holds the result of the collision detection. 2 circles/rectangles are either touching, 
// overlapping (colliding) or separate (non-colliding)
enum ECollisionState
{
	CS_SEPARATE,
	CS_OVERLAP,
	CS_TOUCH
};

//////////////////////////////////////////////////////
// Functions
//

// Subtracts 2 vectors : Returns (vOne - vTwo)
Vec2_t VectorSubtract(Vec2_t vOne,Vec2_t vTwo)
{
	Vec2_t vRet;
	vRet.x = vOne.x - vTwo.x;
	vRet.y = vOne.y - vTwo.y;
	return vRet;
}

// Returns the magnitude of a vector
float VectorMagnitude(Vec2_t vVector)
{
	// Magnitude = SquareRoot(vVector.x^2,vVector.y^2)
	return sqrt(vVector.x * vVector.x + vVector.y * vVector.y);
}

First we define a circle, a circle's defined by a center and a radius :

Code:

struct Circle_t
{
	Vec2_t vCenter;
	float fRadius;
};

Now, we need the actual collision algorithm. To perform the collision detection, we calculate what can be called a safe distance. The safe distance is the sum of the radii of the 2 circles.
Let the distance between the centers of the 2 circles be distance.
If Distance > Safe distance : The circles are separate.
If Distance == Safe distance : The circles are touching.
If Distance < [i]Safe distance[/i[ : The circles are overlapping.

So what's actually left to do is calculate the distance between the centers of the circles. This can be done by subtracting any of the 2 center vectors from the others, and getting the magnitude of the result

Code:

float GetDistance(Vec2_t avCenter[2])
{
	// Distance vector = avCenter[0] - avCenter[1]
	Vec2_t vDistance = VectorSubtract(avCenter[0],avCenter[1]);
	// Distance = Magnitude of vDistance
	return VectorMagnitude(vDistance);
}

Now you have the distance, you have the safe distance, so you do the collision check.

The function would look like :
ECollisionState CheckCircleCollision(Circle_t aCircle[2])
{
Calculate Safe distance
Get Distance between 2 circles
Compare and return the appropriate result
}

If you need to know the alternate rectangle collision detection algorithm (similar to the circle one, relying on calculating safe distances), please say so.

Wow, that what I call an explanation. Thanks alot, I'll try to implement it in the game I'm currently making.
I'm using allegro, with Dev-C++ (coding in C++) btw.

If you need to know the alternate rectangle collision detection algorithm (similar to the circle one, relying on calculating safe distances), please say so.

It would be great if you could explain that too.

Sometimes its better to check whether your objects
do not collide,
whether than if they do, i.e

if (object1.x + object1.sizex < object2.x)
// 1 check, they dont collide
// only one calculation needed

you get the idea, you could also do the y coord, base it on how fast the object is moving, etc.

-Vulcan

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.