Collision Detection

Introduction

Collision detection is often a big deal in games. It is important to know when objects in a game collide. This tutorial will cover the basics to get you going with collision detection. We will look at some of the techniques 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 they are inside another model. However, this method is very time-consuming, especially if you have many models or extremely detailed ones. To deal with this problem, game programmers will use an approximation of the model that is easier to check for collisions. The two most commonly used methods are bounding boxes and bounding spheres. With these methods, you would build a box or sphere around a model that completely covers the model. There will obviously be an area outside the model but still inside 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 MonoGame has a lot of built-in support for bounding spheres. The basic idea is that you will construct a sphere from each model you are using or for each mesh in a model. 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 center point, 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 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 center points is less than the radii of the two bounding spheres. If it is, then there is a collision. In a minute, we will see that MonoGame takes care of most of this for us, and simple collision detection is pretty easy.

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 bad approximation because it needs to be large enough to cover the entire object, but this allows a lot of extra space inside the bounding sphere that is not 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 you are now comparing with many bounding spheres, which may be inefficient if the other object is far from the arrow.

A step beyond this is to have a hierarchical model. In this case, you would use both the large and small spheres. When checking to see if the arrow has collided with another object, you would first compare it with the big bounding sphere. If this is not a collision, you know there is no collision and can continue with the game. However, if it is a collision, then you compare it with the more detailed spheres. This way, you only have to do this extra work when needed. If the object lies within these more detailed spheres, it is recognized as a collision. You can have as many levels as you want, which may be useful 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, we will simply work with the basic bounding sphere method for now.

Collision Detection with Bounding Spheres

The code for collision detection is fairly simple and easy to add to any game you are already working on. I've included some code below if you don't have a place to 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 as 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 could also use your own model.

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
 
namespace CollisionDetection
{
    public class Game1 : 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 / 480f, 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 Update(GameTime gameTime)
        {
            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                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 representing the objects 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. If the object in the game is located 20 units down the x-axis, we must move our bounding sphere from the model 20 units down the x-axis to be in the right spot. So, the method 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 overlaps, 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 collision detection.

view source code

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 more advanced collision detection methods, like bounding boxes and hierarchical models. 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!