In every game that you will ever build, a solid collision detection & resolution system exists as one of the pillars of a good game engine.

The first part of the phrase, collision detection, refers to your engine’s ability to detect when two entities are colliding. For example, when a bullet hits an enemy or when a player jumps on the platform, the entity penetrates another entity there is a collision. In the physical world, you cannot penetrate other objects — well, at least not on the first date. Your hand cannot penetrate the table, and sprites cannot penetrate the platform.

Resolution refers to how you solve these penetrations. For the example where the player penetrates the platform, you just move the player right above the platform. For the bullet that penetrates the enemy, you can kill the bullet and damage or kill the enemy.

When I embarked upon creating my first game engine, I had a tough time trying to find a nice way to handle collision detection. Regardless if your engine is in 2D space or 3D space, you can abstract and extract certain functionality that is universal.  This post will talk about how I structure my collision detection routines.

Thinking about it more abstractly, when we do collision detection, we do it in this order:

• We first need to gather all the possible pairs of potential collidables
• Detect collisions between the collidable pairs
• Resolve any collisions

First, I set up a struct that will hold a collision:

struct Collision
{
	Collidable * first;
	Collidable * second;
 
	// hitnormal with respect to *first*
	Vector2D hitNormal;  // Vector3D if in 3D
 
	// How much did the two entities overlap?
	float overlapDistX;
	float overlapDistY;
};

The Collision struct holds two pointers to the two Collidable entities that are, well, colliding. The hitnormal refers to a normal vector of the collision. You can store other information, such as collision overlap.

Next, I’ll show you how to structure your collision detection/resolution routine:

void DetectAndResolve( World & world )
{
	// First, collect all valid collidables in the world
	std::vector validCollidables;
	CollectValidCollidables( validCollidables, world  );
 
	// Keep running until all collisions are resolved
	while( true )
	{
		// Collects all possible pairs
		std::pair< Collidable*, Collidable* > possiblePairs;
		CollectCollidablePairs( possiblePairs );
 
		// Detect collision between pairs in _possiblePairs_
		// and push them into _collisions_ vector.
		std::vector< Collision > collisions;
		DetectCollisionBetweenPairs( possiblePairs, collisions );
 
		// If no collisions detected, quit the loop
		if ( collisions.empty() ) break;
 
		// Resolve all collisions
		ResolveCollisions( collisions );
 
		// Clear the vectors for next iteration
		possiblePairs.clear();
		collisions.clear();
	}
}

Let me walk through what just happened.

std::vector validCollidables;
CollectValidCollidables( validCollidables, world  );

We collect the valid collidables first. Non-valid collidables include hidden objects, invulnerable sprites, non-collidables tiles, etc. Essentially, this step gathers all the Collidable entities in the world and stores in one vector.

Next step, we use the vector of valid collidables and builds pairs. These pairs exist as potential candidate for collision.

std::pair< Collidable*, Collidable* > possiblePairs;
CollectCollidablePairs( possiblePairs );

We collect these pairs and prepare to use the them to detect collision between the two collidable entities. You can optimize this step in various ways. For example, if your engine is tiled, two tiles will never collide since they exist statically in world; thus, you can ignore pairs that are tiles. If you’re really ambitious, you can split your World via quad trees or use BSP to optimize.

std::vector< Collision > collisions;
DetectCollisionBetweenPairs( possiblePairs, collisions );

Now that you have the pairs. You go through each pair and detect if they collide in the world. If they collide, you build a Collision struct with the colliding pairs and push them into collisions vector.

If there are no more collisions left, you can quit resolving collisions since the task has been completed:

if ( collisions.empty() ) break;

If there are any collisions, you resolve them:

ResolveCollisions( collisions );

Resolution can mean several things; from bouncing, clamping, killing, sticking, etc, there are several ways to resolve a collision. The bottom line is that by the end of the collision resolution, the two entities should not be colliding.

Finally, these functions reside in the while loop:

while( true )
{
	...
}

Sometimes, when you resolve a collision, the entities gets displaced and it consequently collides with another entity. This while loop means that it will continue to detect and resolve until there are no more collisions left in the world. This system is referred to as a “perfect” collision resolution. However, this is not very practical since there is a looming possibility of an infinite loop. A good example would be if a entity was stuck between two objects. Thus, not alot of game engines use this technique. Instead, what you might want to is cap it to run a specific number of times — 10 is a good number.

So there it is. I provided a framework for developing collisions and it was good. Hope that helps.