The collision system described in earlier posts is appropriate for when two entities collide in a vacuum. For some games (Asteroids and Pong come to mind), that’s all that is needed. However, there are additional considerations to make for other types of games. Eventually, this engine should work for a number of types of games; for now, the goal is to build a lightweight platformer engine. What we need, then, is a collision system designed for platformers.

What’s wrong with the old system?

There were two big problems with the old system. First, because of the implementation of impulse, all inanimate objects remained in motion once acted upon; if the player pushed a box, for example, it would receive an impulse and start sliding along until it hit a wall. To fix this, we would need to implement friction.

More problematic was the second problem, that resolving one collision can cause another. By taking each pair of entities one at a time and resolving them without considering whether the resolution actually caused another collision, the old collision system was order-dependent. Rather than producing a consistent, correct result, it produced an inconsistent, incorrect result depending on which collisions were handled first.

The old collision system left collisions on the screen like this.

Designing a Better Collision System

There are three requirements the new collision system should meet. First, it should be order-independent. It should produce the same result no matter which collisions are processed first. Second, it should be stateless, that is, the collision system should not depend on each entity knowing information about its relation to other entities and the world around it. Finally, it should be able to work with any number of colliding objects.

The solution is a chained collision system. The algorithm is fairly simple. We resolve collisions as before, but right after the resolution vector is applied, we check to see if the resolution has caused additional collisions. If it has, we chain the collision by making a recursive call to [CollisionSystem resolveCollisionsBetween::] and updating the original colliders’ positions based on the resolution vector of the second collision. Because it’s recursive, it works for any number of chained collisions — the player can try to push a box into another box into another box into a wall and this algorithm will determine that the boxes shouldn’t move, for example. Here’s what the new collision resolution method will look like, simplified.

// Resolve collisions between two entities and return the amount entity A moved
- (CGPoint)resolveCollisionsBetween:(Entity *)a and:(Entity *)b
{
	Transform *transformA = [a componentOfType:[Transform class]];
	Transform *transformB = [b componentOfType:[Transform class]];
	
	Physics *physicsA = [a componentOfType:[Physics class]];
	Physics *physicsB = [b componentOfType:[Physics class]];
	
	if([self entity:a collidesWithEntity:b])
	{
		CGPoint resolution = [self resolutionBetweenEntity:a andEntity:b];
		
		if(!CGPointEqualToPoint(resolution, CGPointZero))
		{
			double ratioA = [physicsA mass] / ( [physicsA mass] + [physicsB mass] );
			double ratioB = 1 - ratioA;
			
			CGPoint deltaA = [self scale:resolution by:ratioA];
			CGPoint deltaB = [self scale:resolution by:-ratioB];
			
			// Resolve the collision
			
			[self translate:[transformA position] by:deltaA];
			[self translate:[transformB position] by:deltaB];
			
			// Check to see if resolution caused another collision
			
			for(Entity *c in [self entitiesThatCollideWithEntity:a])
			{
				CGPoint resolutionA = [self resolveCollisionsBetween:c and:a];
				
				// Adjust the transform and the resolution vector by the amount returned from the recursive call
				[self translate:[transformA position] by:resolutionA];
				[self translate:deltaA by:resolutionA];
			}
			
			for(Entity *c in [self entitiesThatCollideWithEntity:b])
			{
				CGPoint resolutionB = [self resolveCollisionsBetween:c and:b];
				
				// Adjust the transform and the resolution vector by the amount returned from the recursive call
				[self translate:[transformB position] by:resolutionB];
				[self translate:deltaB by:resolutionB];
			}
			
			return deltaA;
		}
	}
	
	return CGPointZero;
}

The concept is simple: if the resolution of a collision causes another collision, resolve it right away, recursively, rather than waiting to resolve it in the main update loop of the collision system. If the resolution of the sub-collision causes one of the original colliding entities to move, the other original collider needs to move with it. In this sense, as the chaining method recurses through collisions, the original colliders are treated as a single unit rather than as separate entities.

When we use collision chaining, the collision caused by the entity-to-entity resolution acts on both entities as a single unit.

Although the algorithm works in theory, there are a couple more things we have to do before it will actually work. First, we need to adjust the resolution ratio calculation to use the sum of the mass of the entities that are being treated as a unit, rather than only using the mass of the directly colliding entity itself. This can be accomplished by adding another parameter to the method that is the amount of mass that should be added to the second entity’s mass. If one of the original entities is static, we will want to treat the unit as static as well, so we should also add a forceStatic parameter to the method that makes the algorithm treat the second entity as static, regardless of whether it actually is static. The method signature would end up looking something like this:

- (CGPoint)resolveCollisionsBetweenEntity:(Entity *)a andEntity:(Entity *)b withAdditionalMass:(double)addedMass andForcingStatic:(BOOL)shouldForceStatic;

The second thing we have to do is fill in the body of the [CollisionSystem entitiesThatCollideWithEntity:] method. The most basic approach is to simply return self.entities, since [CollisionSystem resolveCollisionsBetween::] returns a zero vector when the two entities don’t collide. This basic approach will bog down the system with a lot of unnecessary checks, though. A better option is to use spatial partitioning to only check entities that are nearby. Spatial partitioning would also speed up the collision system in general. I will discuss the use of spatial partitioning in a future article.

In my next article, we will finish implementing collision chaining.