Simple Collision Culling with XNA

XNA Lesson 1 Part Two -- Difficulty: Moderate

June 21st, 2007 -- Collision processing and Culling.

Collision processing:
Collisions types based on object types would be important to setup the proper collision effects. For instance, you may not want your player to collide with certain objects, like scenery (grass, flowers). In a game like Halo for example, when you walk over a weapon, you don't want to bump into it and have it slow down the player as if they were hitting an obstacle. But you still want the game to recognize that you're touching the weapon so that it will let you pick it up.

Here is a simple example:

Weapon peaShooter = new Weapon();    // Weapon derives from Entity class
Obstacle oakTree = new Obstacle();   // Obstacle derives from Entity class

// Inside of the game's update loop
foreach ( Entity sourceEntity in entityList )
{
    // If the player is colliding with an entity, process the collision
    if ( ActivePlayer.CheckForCollision( sourceEntity ) == true )
        ActivePlayer.ProcessCollision( sourceEntity );
}

// Inside of the Player class
private void ProcessCollision( Entity sourceEntity )
{
    if ( sourceEntity.Type == EntityType.Weapon )
        this.AddToInventory( sourceEntity );  // No collision effects needed, just grab weapon
    else if ( sourceEntity.Type == EntityType.Obstacle )
        this.CollisionEffect( sourceEntity ); // Have player hit obstacle
    else     // You must have a way to process any type of entity, this shouldn't be reached
        throw new Exception( "Entity type must be initialized before collision processing" );

Alternatively, you could use a switch statement instead of an if, else block.

Collision culling:
You now have a way to setup different effects depending on collisions with different types of entities, but what if you have 60 entities on the map? You would be checking all 60 entities for collision every frame! If the map is large enough to have 60 entities, there's a good chance that they're spread out around the map, and most are not near the player. So why would we want to check entities that aren't close enough to even worry about? Exactly, we wouldn't. So we setup a culling algorithm that will weed away anything not close by, and take the number of entities checked to a minimum.

There should be a heirarchy to the culling, you want to do the fastest math that will eliminate the most entities to begin with:
Step 1: Eliminate any entities that aren't close -- in this case I will be using the CheckAdjacentRegions() function we made in the last lesson.
Step 2: Check if the BoundingSpheres of the player and entity are close enough to touch.

// Inside of the Player class
bool CheckForCollision( Entity sourceEntity )
{
    // Check if the entity is even close enough to matter
    if ( this.CheckAdjacentRegions( sourceEntity ) == true )
    {
        // Check if BoundingSpheres are touching
        if ( this.CheckSphereCollision( sourceEntity ) == true )
            return true;
    }

    return false;
}

CheckSphereCollision would simply take the Square Root of the distance.X squared, distance.Y squared, and distance.Z squared and see if it was less than the sum of the radii of the two entities BoundingSpheres.

The original CheckForCollision() function we just made above would give you a basic collision between two entities based on a sphere that surrounded the entities. If you wanted the collision to be more precise you would want to check collision between mesh spheres rather than entire model spheres.

// Inside of the Player class
bool CheckForCollision( Entity sourceEntity )
{
    // Check if the entity is even close enough to matter
    if ( this.CheckAdjacentRegions( sourceEntity ) == true )
    {
        // Check if BoundingSpheres are touching
        if ( this.CheckSphereCollision( sourceEntity ) == true )
        {
            // Check if any other mesh spheres are colliding as well
            foreach ( ModelMesh sourceMesh in sourceEntity.Model.Meshes )
            {
                foreach ( ModelMesh playerMesh in ActivePlayer.Model.Meshes )
                {
                     if ( CheckMeshCollision ( sourceMesh, playerMesh ) == true )
                         return true;
                }
            }
        }
    }

    return false;
}

This would allow you to have a more precise collision. However, models can contain quite a few meshes, if this is the case with your models, you may have to cull out even more collision checks. You could experiment with having entities in which only certain meshes are checked for collision, such as the outer meshes only. If this were the case then each entity would need a predefined List that contained the meshes, that way you weren't going through all of them each time.

Please be aware that there is even more precise collision out there, such as per-vertex collision. However reading in of vertices from a model is difficult in XNA, and in order to do so you would have to create your own custom content writer/reader. Even after you get the vertices read in and parsed properly, you'll have to create your own per-vertex collision algorithm.

Next