Programming Tidbit #2 - Efficient Multiple Object Collision Testing
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.
(2 votes, average: 5 out of 5)
Loading ...
(3 votes, average: 4.67 out of 5)
