Collision Detection

Introduction

Collision detection is often a big deal in games. It is important to know when objects in a game collide. In this tutorial, we will cover the basics to get you going with collision detection. We will look at some of the techniques that are used for collision detection, and even do a little of our own.

Collision Detection Methods

There are a lot of ways that collision detection can be done. The most obvious method is to take every single vertex in a model and check to see if any of them are inside of another model. This method, however, is very time consuming to do, especially if you have lots of models, or models with a lot of detail in them. To deal with this problem, game programmers will use an approximation of the model that is easier to check for collisions. The two methods that are most commonly used are bounding boxes and bounding spheres. With these methods, you would basically build a box or sphere around a model that completely covers the model. There will obviously be area that is outside of the model, but still inside of the bounding box or sphere, but an ideal bounding region will limit this as much as possible.

We will focus on bounding spheres in this tutorial, because of their simplicity, and because XNA has a lot of built in support for bounding spheres. The basic idea is that for each model you are using, or for each mesh in a model, you will construct a sphere from it. You determine the middle point of the mesh, which will become the center point for your bounding sphere. You then figure out the farthest vertex in the model or mesh from this centerpoint, and the distance to it is the radius of the bounding sphere.

You can do all of this work outside of the game, so there really isn't a time penalty during the game. During the game, you get the bounding spheres for the models that you are checking, and see if the distance between their centerpoints is less than the radii of the two bounding spheres. If it is, then there is a collision. We will see, in a minute, that XNA really takes care of most of this for us, and simple collision detection is pretty easy to do.

One drawback to this method is that a sphere (or even a bounding box) may not be a good approximation for an object. For instance, imagine you have a long object, like the arrow in the image below. A bounding sphere might be a very bad approximation, because it needs to be large enough to cover the entire object, but this allows a lot of extra space inside of the bounding sphere that is not actually part of the arrow.

screenshot1.png

One commonly used solution to this problem is to approximate the object with multiple spheres, rather than one. This allows for a better approximation of the object, as shown below.

screenshot2.png

The drawback to this method is that now you are comparing with many bounding spheres, which may be inefficient if the other object is far away from the arrow.

A step beyond this is to have a hierarchical model. In this case, you would use both the large sphere, and the small spheres. When checking to see if the arrow has collided with another object, you would first compare with the big bounding sphere. If this is not a collision, you know that there is no collision, and you can continue with the game. However, if it is a collision, then you go ahead and compare with the more detailed spheres. This way, you only have to do this extra work when it is needed. If the object lies within these more detailed spheres, then it is recognized as a collision. In fact, you can have as many levels as you want, which may come in handy in a very intricate model. Another improvement to this method is to use multiple types of approximation techniques together. For instance, you can combine the bounding spheres with bounding boxes. For some objects, bounding spheres are a better approximation of the object. For others, bounding boxes are. A system that allows either will be more accurate than one that strictly uses one or the other.

While a more advanced system like this is ideal, for now we are simply going to work with the basic bounding sphere method.

Collision Detection with Bounding Spheres

The code to actually do collision detection is fairly simple, and it is easy to add to any game that you are already working on. I've included some code below in case you don't have a place to already put it. This is the code that I will be using in this tutorial, as well. It relies on stuff that we did in the using 3D models tutorial, as well as the simple 3D animation tutorial, and to a lesser degree, the BasicEffect lighting tutorial. If you haven't gone through those tutorials, it might be helpful to go through them now. You should be able to copy and paste this code into a new game project. Additionally, this code uses the SimpleShip model from the 3D Model Library, which you can download and include in your project like we have done before. Add both the .fbx file and the texture file to your project, and then exclude the texture from your project so that it doesn't get handled twice by the content pipeline. You can use a model of your own instead, too, if you want.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using Microsoft.Xna.Framework.Net;
using Microsoft.Xna.Framework.Storage;
 
namespace CollisionDetection
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;
 
        Model model;
        Vector3 ship1Location = new Vector3(0, -20, 0);
        Vector3 ship2Location = new Vector3(0, 0, 0);
        Matrix view = Matrix.CreateLookAt(new Vector3(10, 10, 10), new Vector3(0, 0, 0), Vector3.UnitZ);
        Matrix projection = Matrix.CreatePerspectiveFieldOfView(MathHelper.ToRadians(45), 800f / 600f, 0.1f, 100f);
 
        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }
 
        protected override void Initialize()
        {
            base.Initialize();
        }
 
        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
 
            model = Content.Load<Model>("Ship");
        }
 
        protected override void UnloadContent()
        {
        }
 
        protected override void Update(GameTime gameTime)
        {
            // Allows the game to exit
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                this.Exit();
 
            ship1Location += new Vector3(0, 0.1f, 0);
            ship2Location += new Vector3(0, 0.003f, 0);
 
            base.Update(gameTime);
        }
 
        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.Black);
 
            Matrix ship1WorldMatrix = Matrix.CreateTranslation(ship1Location);
            Matrix ship2WorldMatrix = Matrix.CreateTranslation(ship2Location);
            DrawModel(model, ship1WorldMatrix, view, projection);
            DrawModel(model, ship2WorldMatrix, view, projection);
 
            base.Draw(gameTime);
        }
 
        private void DrawModel(Model model, Matrix world, Matrix view, Matrix projection)
        {
            foreach (ModelMesh mesh in model.Meshes)
            {
                foreach (BasicEffect effect in mesh.Effects)
                {
                    effect.EnableDefaultLighting();
                    effect.World = world;
                    effect.View = view;
                    effect.Projection = projection;
                }
 
                mesh.Draw();
            }
        }
    }
}

When you run this code, you should see something similar to the image below, where two ships are moving along, one faster than the other. When the fast one catches up to the slow one, it will pass through it and come out in front of it. A screenshot of the program running is below:

screenshot3.png

The actual code for collision detection is fairly simple. We first need the two models that represent the objects that we are working with. These will include BoundingSphere objects for each of the meshes in the model. In addition, we will need to know how the model has been transformed in the world, since the bounding spheres of the model are in model coordinates. That is, if the object in the game is located 20 units down the x-axis, we will need to move our bounding sphere from the model 20 units down the x-axis so that it is in the right spot. So the method that we create for collision detection will require two model objects and two Matrix objects for the transformations. We will then compare each of the bounding spheres in one model to the bounding spheres in the other. If any overlap, then we have a collision. If we get through them all without any overlaps, then there is no collision. So here is the code to do this:

private bool IsCollision(Model model1, Matrix world1, Model model2, Matrix world2)
{
    for (int meshIndex1 = 0; meshIndex1 < model1.Meshes.Count; meshIndex1++)
    {
        BoundingSphere sphere1 = model1.Meshes[meshIndex1].BoundingSphere;
        sphere1 = sphere1.Transform(world1);
 
        for (int meshIndex2 = 0; meshIndex2 < model2.Meshes.Count; meshIndex2++)
        {
            BoundingSphere sphere2 = model2.Meshes[meshIndex2].BoundingSphere;
            sphere2 = sphere2.Transform(world2);
 
            if (sphere1.Intersects(sphere2))
                return true;
        }
    }
    return false;
}

In the Update() method, we will want to add some code to check for collisions between objects. In the original code above, there are only two ships in the scene that we are checking. If you have more objects, you will need to check each pair of objects. Add the following code to your Update() method, which will call the collision detection method, and if a collision is found, restart the fast ship at its beginning location. That way you can tell if the collision detection is working.

Matrix ship1WorldMatrix = Matrix.CreateTranslation(ship1Location);
Matrix ship2WorldMatrix = Matrix.CreateTranslation(ship2Location);
 
if (IsCollision(model, ship1WorldMatrix, model, ship2WorldMatrix))
{
    ship1Location = new Vector3(0, -20, 0);
}

Once this is done, you should be able to run the game again, and see that when the ships touch each other, the fast ship restarts back where it did originally, which means your collision detection is working correctly!

Below is the completed code for the collision detection.

Click here for the completed project: CollisionDetection.zip

What's Next?

Now that you've done this simple collision detection, you might want to try out some of the more advanced collision detection methods, like bounding boxes and hierarchical models. As of right now, I don't have any other game physics tutorials, but you might want to go back and check out some of the other more advanced tutorials.


Troubleshooting.png Having problems with this tutorial? Try the troubleshooting page!