Reader Matt Sarnak asked for details on how I do collision detection on the complex landscapes in Whirlygig 360. I decided to respond with a post about it since this could be useful to other people.

First of all, I use FlatRedBall, which provides a variety of game-design tools such as the Sprite Editor, Polygon Editor, Particle Editor and more. I created a long and kinda boring video last year that shows how the tools work together: FlatRedBall Toolkit Demo.

Collision detection can be expensive, meaning it can eat up a lot of processor cycles. For example, if you have 50 objects and every object must be tested against the other objects that’s about 50 * 50 or 2,500 tests per loop (technically, an object doesn’t have to be tested against itself so the actual number of tests will be slightly smaller). If your update cycle is running at the same speed as your framerate (often it will run faster) that loop will happen 60 times per second. That’s 150,000 tests per second. If your objects are all circular you can simply do a distance test to see if the objects are further apart than the sum of their radii. If they are rectangles it’s only slightly harder. But if they are complex shapes it can get really messy. The Xbox360 is a graphics powerhouse but can choke on heavy processor use.

FlatRedBall, if used correctly, can perform collision detection in up to three phases:

  • Phase I partitions the screen into columns (or rows, depending on how your levels are built). Lets say you are testing bullets against level geometry. If a bullet is on the right side of the screen, you don’t need to test it against all of the polygons on the left side of the screen. This immediately cuts the volume of tests you have to do exponentially!
  • Phase 2 is sphere testing. A sphere is drawn around the two polygons to be tested and the spheres are tested against each other. If they don’t overlap…we don’t need to test any deeper.
  • Phase 3 is deep testing. This should be avoided as often as possible because this is the most expensive type of test. Polygons are carefully tested against each other to see if they truly overlap.

So, with the above in mind, when designing your collision maps: use spheres if possible. Next use axis-aligned rectangles. Finally, use polygons for objects that are too complex to be represented by a sphere or rectangle.

Second, don’t make your polygons too big. When I first designed the level collision I assumed that bigger is better…fewer objects to test against, right? Wrong. Bigger polygons span more partitions and must be tested against more frequently. They also make bigger spheres. This means that large polygons are always deep-phase tested which grinds things to a halt. At the same time, you don’t want to make them too small because that adds up to a lot of iterations. The only formula I know for finding the balance is: try and see :P

When I migrated Whirlygig 360 from PC to Xbox this was the main issue I faced. My quad-core, multi-threaded PC processor ate collision testing for breakfast. The Xbox360 choked to death! Here’s how one of my revised levels looks in the FRBDK tools:

 

The scene in the Sprite Editor:

Looks really complex right? If we were doing pixel-perfect collision here we’d be lighting a processor on fire!

 

The collision map in the Polygon Editor:

Here are some polygons. They look ugly, right? Doesn’t matter…performance is the key here :)

 

The Polygon Editor with Scene loaded for reference (File>Load Scene):

To create those polygons I load a scene into the Polygon Editor and simply trace around it. Here’ I’ve used AARs where I can and kept polygons fairly small. Note that fast-moving objects may “tunnel” through thin polygons.

 

Code Examples:

Note that these do NOT use partitioning. There’s some basic optimization stuff here but I’ve gotten decent performance without partitioning. I will implement partitioning prior to Whirlygig 360 release.

 

Main Collision Method:

private void CollisionActivity()
{
	// bounce player off edge of screen and level geom
	Player.Collision.CollideAgainstBounce(level_bounds, 0f, 1f, 0.5f);
	Player.Collision.CollideAgainstBounce(level_collision, 0f, 1f, 0.5f);

	// loop through enemies
	for (int i = (Enemies.Count - 1); i > -1; i--)
	{
		Enemy enemy = (Enemy)Enemies[i];

		// if enemy is outside of active area they can't shoot
		if (enemy.Collision.CollideAgainst(level_active_area))
		{
			enemy.ShootingEnabled = true;
		}
		else
		{
			enemy.ShootingEnabled = false;
		}

		// optimization : all level collision is in the bottom left
		// so don't test if enemy is in top-right quarter.
		if (enemy.Position.Y < 0 || enemy.Position.X < 150)
		{
			enemy.Collision.CollideAgainstBounce(level_collision, 0f, 1f, 0.5f);
		}
	}

	// the main method, loops through shots and tests against everything
	for (int i = (Shots.Count - 1); i > -1; i--)
	{
		Shot shot = Shots[i];

		// series of sub-methods to make testing easier.
		// these return true if the shot hit something.
		if (ShotLeftBounds(shot) || ShotHitLevel(shot) || ShotHitPlayer(shot) || ShotHitEnemy(shot))
		{
			// this is only here in case we add logic after this.
			// if a shot has hit something we don't want to do
			// any more testing!
			continue;
		}
	}
}

Sub Method (for readibility):

private bool ShotHitEnemy(Shot shot)
{
	// loop through enemies
	for (int e = (Enemies.Count - 1); e > -1; e--)
	{
		// create reference
		Enemy enemy = (Enemy)Enemies[e];

		// if not on same team...damage!
		if (shot.Owner.TeamIndex != enemy.TeamIndex)
		{
			// collide with simple physics
			if (shot.Collision.CollideAgainstBounce(enemy.Collision, 0f, 1f, 0))
			{
				// if player owns this shot, affect player stats
				if (shot.Owner == Player)
				{
					GlobalData.PlayerSessionData.ShotsHit += 1;
					GlobalData.PlayerSessionData.DamageDealt += shot.ShotDamage;
				}

				// cause damage to enemy
				enemy.Damage(shot.ShotDamage);

				// trigger shot impact
				// plays a particle effect and passes impact type
				// ImpactType is used to determine the sound played (ping vs thump)
				shot.ImpactTarget(false, Entities.Shots.Shot.ImpactType.ImpactEntity);

				// we collided so ShotHitEnemy is true
				return true;
			}
		}
	}

	// we didn't hit an enemy: ShotHitEnemy is false
	return false;
}