This is the second post in the series “Programming Tidbits.” These articles consist of useful bits of information or code that I would like to share, but may not be considered a full article.

Sometimes your game may consist of a very large amount of entities that must be checked for collision with each other. In order to increase the speed of your collision tests there are a few methods that you can employ. This is no way an all inclusive article on this subject because there are MANY different methods for improving collision performance, however hopefully this can get you started.

The easiest thing to do is to eliminate as many collision checks as possible, as well as keep the collision checks as simple as you can. I’ll try to explain a few different methods which you can combine to speed up your testing.

The Bad Way

Generally you will be storing multiple entities in some type of array or map. The most common way of checking for collision is to loop through this array and check each entity against one another.

var entity1:Entity;
var entity2:Entity;

for ( var i:int = 0; i < entities.length; i++ )
{
 	entity1 = entities[ i ];

 	for ( var j:int = 0; j < entities.length; j++ )
 	{
 		entity2 = entities[ j ];

 		if( entity1.isOverlapping( entity2 ) )
 		{
 			// Handle Collision
 		}
 	}
}

Reduce Redundancy

Using this method will work, however the more entities you add to the array the slower it will become. The main problem here is that many of your checks are redundant. The more efficient method would be to make sure that you only check each entity once by making a small change to the inner loop:

for ( var j:int = i + 1; j < entities.length; j++ )

Collision Groups

Another way of increasing the speed is to give your entities flags or collision groups. For example, you may flag some entities as “collidable” and you may also decide that some entities cannot collide with each other so you might give them a “group” variable. This eliminates the need for actually running checks against this entity at all.

var entity1:Entity;
var entity2:Entity;

for ( var i:int = 0; i < entities.length; i++ )
{
 	entity1 = entities[ i ];	

 	if( !entity1.isCollidable )
 	{
 		continue;
 	}

 	for ( var j:int = i + 1; j < entities.length; j++ )
 	{
 		entity2 = entities[ j ];

 		if( !entity2.isCollidable || entity1.group == entity2.group )
 		{
 			continue;
 		}

 		if( entity1.isOverlapping( entity2 ) )
 		{
 			// Handle Collision
 		}
 	}
}

Simplify First

The last trick would apply when you are using complex collision such as pixel perfect / polygon collision. Instead of checking each object with the complex collision algorithm, use a simple bounding circle collision test first, and if that test returns true then proceed with the more detailed collision test.

if( entity1.isOverlapping( entity2 ) )
{
	if( entity1.detailedCollisionTest( entity2 )
	{
		// Handle Collision
	}
}

Final Words

Other methods of increasing collision testing speed would be to implement some sort of “broad phase” algorithm, however that is beyond the scope of this article. The methods discussed here should be sufficient for most flash games.

This is the first post in the series “Programming Tidbits.” These articles consist of useful bits of information or code that I would like to share, but may not be considered a full article.

The Wrong Thing…

When programming, a lot of times you may find yourself throwing together some code which uses “Magic Numbers.” A magic number is basically just any static number sitting in your code such as:

public function moveMyCharacter() : void
{
	myCharacter.x += 5;
	myCharacter.y += 5;
}

public function damageEnemy() : void
{
	someEnemy.health -= 20;
}

Why is it bad?

Now obviously that is just a simple example, but let’s say you have code ALL OVER your project using these “magic numbers.” What happens then, if later you want to change these numbers? You have a long and tedious process of finding all times that they are used. Not only that, but you are prone to missing something which will therefore lead to unpredictable code and bugs.

The right thing…

Instead of being mean to yourself, do the right thing and create constants or variables for all of your magic numbers. The usual place to put them is at the top of your class. Even better would be to externalize the data into some sort of settings file ( if the data is worthy of course ). I’ll be discussing externalizing data in a future article if you aren’t quite sure how to go about that…

So here is the code once again, done properly.

// Top of your Class somewhere...
private const MOVE_SPEED:int = 5;
private const HERO_DAMAGE:int = 20;

public function moveMyCharacter() : void
{
	myCharacter.x += MOVE_SPEED;
	myCharacter.y += MOVE_SPEED;
}

public function damageEnemy() : void
{
	someEnemy.health -= HERO_DAMAGE;
}