FuelCell: "Ships" Passing in the Night

Discusses collision detection in a 3D game and demonstrates basic collision checking between the fuel carrier vehicle and the other game objects on the playing field.

The main points of this topic are:

  • Custom Debugging Strategies

The Complete Sample

The code in this tutorial illustrates the technique described in the text. A complete code sample for this tutorial is available for you to download, including full source code and any additional supporting files required by the sample.

Download FuelCell_6_Sample.zip.

Note

You must download the above sample code in order to access the 3D models used in this tutorial step.

Out of My Way!

Currently, the game is not very challenging (and impossible to win). The player can drive through barriers and fuel cells without retrieving them. The only boundaries are the edges of the playing field, added in Step 4. It's time to implement the main feature of the game: collision detection.

Collision detection is a technique used in nearly all games, whether they are 2D or 3D. It simulates (to varying degrees) the interaction of real world objects. Without collision detection, objects in the game world could be seamlessly rendered within the space of the objects with which they collide. In most cases, this is unacceptable. The player expects to "collide" with objects in the game world and not merge with them. The desired behavior in FuelCell is to allow the player free motion around the playing field as long as he or she avoids the barriers. However, if the player attempts to drive through any part of a barrier, the player's current motion stops. Players must drive around the barriers, as they would in the real world. The behavior for fuel cells is a bit different. When a player "collides" with a fuel cell, the fuel cell object is marked as retrieved and no longer is drawn in the game world. This simulates the retrieval of the fuel cell. In the final step, the game display tracks these retrievals. The game ends when the player retrieves all the fuel cells.

FuelCell's implementation of collision detection is based on the BoundingSphere class. Collison detection with bounding spheres is a good approach for a variety of reasons:

  • Bounding spheres (in addition to bounding boxes and frustums) are already available (courtesy of the XNA Framework) for use in your code.
  • Bounding spheres do not have to be rotated if the enclosed object is rotated. This is not true when using bounding boxes or frustums. This saves some coding and reduces the complexity of the implementation.
  • Bounding spheres are automatically generated for sub-meshes by the XNA Framework. Each mesh has a related bounding sphere, accessible with the BoundingSphere property of the ModelMesh object.

It's time to dive back into the code and take advantage of some of these features as we implement the collision detection.

Adding the Bounding Sphere Model

During development, it's incredibly useful to render your bounding spheres along with its related model. This makes debugging the collision detection code much easier when things don't seem to be working properly. FuelCell represents the bounding sphere as a spherical wire-frame model, whose radius is 1 unit. When rendering the bounding sphere of a model, it is easily scaled (using the radius of the model's bounding sphere) and placed by setting the bounding sphere's center to the current position of the model.

For example, if the radius of the bounding sphere of a mesh is 4, the bounding sphere model is scaled by 4, which matches the size of the original bounding sphere.

In order to use this technique, you need to add and initialize a spherical model with a radius of 1 unit. Luckily, the sphere1uR.x model is the model you need.

  1. Add the sphere1uR.x and White.png files to the Models/Content directory of the FuelCell project.

  2. Exclude the White.png file from the project.

  3. In FuelCellGame.cs, declare a member variable (called boundingSphere) of type GameObject, after the declaration of the game camera.

  4. In the existing Initialize method, initialize the new variable after initializing the game camera:

    boundingSphere = new GameObject();
    
  5. In the existing LoadContent method, load the bounding sphere model after loading of the playing field model:

    boundingSphere.Model = Content.Load<Model>("Models/sphere1uR");
    

Once the model is loaded, you can use it to render the bounding spheres of your game objects. The only data you'll need to track is the size and position of each object's bounding sphere. For FuelCell, there are three types of bounding spheres: fuel carrier, fuel cell, and barrier. You can use the bounding sphere model for each type as long as you scale and position the model before rendering it. For simplicity's sake, the rendering code for a game object and its bounding sphere are kept together. Because the procedure for doing this is the same for both fuel cells and barriers, you will only walk through the fuel cell side of things. After that, we'll discuss the barrier implementation at a higher level.

Calculating the Boundary of the Fuel Cell Model

Do you remember the member variable you added previously to the GameObject class, BoundingSphere? This is the step that finally makes use of that variable, with the help of a bit of code. The first step involves calculating a decent approximation of the bounding sphere of the game object's model. We'll use the CreateMerged method. It's a quick and cheap way to calculate the bounding spheres of simple models. We'll start with the initial bounding sphere and, for every two spheres encountered in the model, we'll merge them. This continues until no more bounding spheres are left.

Note

For single mesh models, like those in FuelCell, this approach works perfectly. However, the approach begins to lose accuracy when applied to a complex model. This is why there are entire shelves of books devoted to solving this problem at your local bookstore.

Since we need the bounding sphere values from the model's sub-meshes, a good place for the initial calculation of this variable is in the LoadContent of the fuel cell model. Add the following code after any existing code:

BoundingSphere = CalculateBoundingSphere();

This code makes a call to a helper function (CalculateBoundingSphere) that approximates the bounding sphere of the model, returning a new bounding sphere. The result is stored in the BoundingSphere variable. The Y-coordinate is set to 0. This causes the upper half of the bounding sphere to project out of the playing field. Since the widest part of the sphere is at the playing field level, it provides a good approximation when testing collision between fuel cells and the fuel carrier.

Add the helper method to the GameObject class, after any existing code:

protected BoundingSphere CalculateBoundingSphere()
{
    BoundingSphere mergedSphere = new BoundingSphere();
    BoundingSphere[] boundingSpheres;
    int index = 0;
    int meshCount = Model.Meshes.Count;

    boundingSpheres = new BoundingSphere[meshCount];
    foreach (ModelMesh mesh in Model.Meshes)
    {
        boundingSpheres[index++] = mesh.BoundingSphere;
    }

    mergedSphere = boundingSpheres[0];
    if ((Model.Meshes.Count) > 1)
    {
        index = 1;
        do
        {
            mergedSphere = BoundingSphere.CreateMerged(mergedSphere, 
                boundingSpheres[index]);
            index++;
        } while (index < Model.Meshes.Count);
    }
    mergedSphere.Center.Y = 0;
    return mergedSphere;
}

At this point, the bounding sphere has an approximate center (clamped to 0 on the Y axis) and radius. Remember the code you added in Step 5 that placed the fuel cells and barriers? After adding the bounding sphere calculation code, the approximated bounding sphere now has the proper coordinates of the related model. In the next step, you'll add code to render both fuel cells and their bounding spheres.

Drawing the Spheres

In the Draw function, replace the existing foreach loop that draws the fuel cells with the following:

foreach (FuelCell fuelCell in fuelCells)
{
    if (!fuelCell.Retrieved)
    {
        fuelCell.Draw(gameCamera.ViewMatrix, 
            gameCamera.ProjectionMatrix);
        RasterizerState rs = new RasterizerState();
        rs.FillMode = FillMode.WireFrame;
        GraphicsDevice.RasterizerState = rs;
        fuelCell.DrawBoundingSphere(gameCamera.ViewMatrix, 
            gameCamera.ProjectionMatrix, boundingSphere);

        rs = new RasterizerState();
        rs.FillMode = FillMode.Solid;
        GraphicsDevice.RasterizerState = rs;
    }
}

What's new about this code? The most important changes are the graphics device state changes and the call to DrawBoundingSphere. The state changes are necessary to render the sphere model as a white wireframe model. We did this for two reasons: so the underlying model wouldn't be obscured, and the bounding sphere model would be easily visible. The switch to wireframe rendering is made by setting FillMode to FillMode.WireFrame. Once the sphere model is drawn, the fill mode is set back to the default, FillMode.Solid. The second change is the call to a new draw function of the GameObject class, DrawBoundingSphere. Add the following code after the CalculateBoundingSphere method:

internal void DrawBoundingSphere(Matrix view, Matrix projection, 
    GameObject boundingSphereModel)
{
    Matrix scaleMatrix = Matrix.CreateScale(BoundingSphere.Radius);
    Matrix translateMatrix = 
        Matrix.CreateTranslation(BoundingSphere.Center);
    Matrix worldMatrix = scaleMatrix * translateMatrix;

    foreach (ModelMesh mesh in boundingSphereModel.Model.Meshes)
    {
        foreach (BasicEffect effect in mesh.Effects)
        {
            effect.World = worldMatrix;
            effect.View = view;
            effect.Projection = projection;
        }
        mesh.Draw();
    }
}

Even though the two methods are similar, there are some important differences. First, the bounding sphere model is scaled using the radius of the fuel cell's bounding sphere instead of a constant factor. Second, the nice default lighting is turned off. This makes the model "pop" a bit more amidst the other models rendered with default lighting.

At this point, rebuild the game and start it. You'll notice that the fuel cells now have wireframe spheres surrounding them. You'll also notice that the spheres are pretty bad approximations of the fuel cell's boundaries. We'll get to that eventually. For now, let's add the code that updates and renders the bounding spheres for the fuel carrier and barriers.

Implementing the Remaining Bounding Spheres

First, let's update the barrier-related code since the barriers don't move, which results in less code to write.

  • Modify the LoadContent method to calculate the initial bounding sphere.
  • In the Draw method, modify the foreach loop (that draws the barriers) to draw the related bounding sphere.

Next up, the fuel carrier. It's the same procedure except for some extra code at the end to handle vehicle movement and fuel cell collision.

  • Modify the LoadContent method to calculate the initial bounding sphere.
  • Modify the FuelCarrier.Update method to update the bounding sphere location with the future position of the fuel carrier.
  • In the Draw method, modify the fuel carrier draw code to also draw the related bounding sphere.

This completes the modifications to draw all the bounding spheres. If you rebuild and run the game, you'll now see lots of wire-frame spheres. But there is still more work (related to fuel carrier collision detection) to make these bounding spheres useful. At this point, the fuel carrier still ignores the fuel cell and barrier bounding spheres. Let's fix this now.

Collision Checking for the Fuel Carrier

There are two collision events that need implementation: collision with a fuel cell and collision with a barrier. If you remember, you already implemented the playing field edge collision code.

Fuel cell collision is important because that it is the only way the player can score points and win the game. You need to add code that checks for collisions between a fuel cell and the fuel carrier. If they collide, you need to mark the fuel cell as retrieved, update the retrieved fuel cells counter, and not draw the fuel cell in the future. This gives the impression that the fuel cell has been picked up by the fuel carrier.

Begin by modifying the FuelCellGame.Update method to check for collision between the fuel cell and the fuel carrier. Add the following code after the game camera update:

foreach (FuelCell fuelCell in fuelCells)
    fuelCell.Update(fuelCarrier.BoundingSphere);

Add the FuelCell.Update method, called with the preceding code. Place it after the Draw method:

internal void Update(BoundingSphere vehicleBoundingSphere)
{
    if (vehicleBoundingSphere.Intersects(this.BoundingSphere))
        this.Retrieved = true;
}

This checks for intersection between the bounding spheres of the carrier and the fuel cell.

Go ahead and remove the now-redundant check (located in FuelCell.Draw) to see if the fuel cell is retrieved before drawing. That check is now being made in the FuelCellGame.Draw method. This completes the code support for the first collision event.

The second event requires less code because, for the most part, the infrastructure already exists. The existing ValidateMovement method will be updated to check for barrier collision in addition to game field boundary collision.

Calculate the future position of the bounding sphere, based on the future position of the fuel carrier. Add the following code to the beginning of the FuelCarrier.ValidateMovement method:

BoundingSphere futureBoundingSphere = BoundingSphere;
futureBoundingSphere.Center.X = futurePosition.X;
futureBoundingSphere.Center.Z = futurePosition.Z;

In the same method, add the following code to the end of the current code but before the last return call:

//Don't allow driving through a barrier
if (CheckForBarrierCollision(futureBoundingSphere, barriers))
    return false;

Finally, add the new CheckForBarrierCollision method:

private bool CheckForBarrierCollision(
    BoundingSphere vehicleBoundingSphere, Barrier[] barriers)
{
    for (int curBarrier = 0; curBarrier < barriers.Length; curBarrier++)
    {
        if (vehicleBoundingSphere.Intersects(
            barriers[curBarrier].BoundingSphere))
            return true;
    }
    return false;
}

Initial Bounding Sphere Results

Once you rebuild and run FuelCell, look at the size of the default bounding spheres. For each object, the bounding sphere is quite large. In some cases, the addition of bounding sphere volumes creates situations where the code prevents the vehicle from passing through barriers that are far enough apart for the vehicle itself. The collision detection, as it stands now, is pretty good considering that this is the result if you do nothing but use the default bounding sphere parameters. However, with a simple modification to the code we can improve the experience of the player. The modification involves applying another scaling factor to the bounding spheres of each game object. This allows realistic interaction between the vehicle and the game world.

The implementation requires scaling factors for each object type. A good place for these is in the GameConstants.cs file. Add the following declarations to the end of the GameConstants class:

//bounding sphere scaling factors
public const float FuelCarrierBoundingSphereFactor = .8f;
public const float FuelCellBoundingSphereFactor = .5f;
public const float BarrierBoundingSphereFactor = .7f;

There are factors for the fuel carrier, fuel cells, and barriers.

The second modification is to the LoadContent methods of the fuel carrier, fuel cell, and barrier classes. After the bounding sphere is first calculated, the radius is then modified by the appropriate factor. This shrinks the radius of the bounding sphere, creating a tighter fit with the object's visible boundary.

Modify the FuelCell.LoadContent method by adding the following code after the bounding sphere calculation:

BoundingSphere scaledSphere;
scaledSphere = BoundingSphere;
scaledSphere.Radius *= GameConstants.FuelCellBoundingSphereFactor;
BoundingSphere = 
    new BoundingSphere(scaledSphere.Center, scaledSphere.Radius);

Modify the FuelCarrier.LoadContent method by adding the following code after the bounding sphere calculation:

BoundingSphere scaledSphere;
scaledSphere = BoundingSphere;
scaledSphere.Radius *= 
    GameConstants.FuelCarrierBoundingSphereFactor;
BoundingSphere = 
    new BoundingSphere(scaledSphere.Center, scaledSphere.Radius);

Modify the Barrier.LoadContent method by adding the following code after the bounding sphere calculation:

BoundingSphere scaledSphere;
scaledSphere = BoundingSphere;
scaledSphere.Radius *= GameConstants.BarrierBoundingSphereFactor;
BoundingSphere = 
    new BoundingSphere(scaledSphere.Center, scaledSphere.Radius);

Rebuild and run the game. The bounding spheres are noticeably smaller, and they no longer enclose the game models. However, the important area (a band on the ground going around the game object) matches the outline of the model fairly accurately. At this point, the collision detection is good enough for our purposes. However, with a little effort, the placement and size of the bounding spheres could be modified even further to produce more accurate collision detection. Like most things in game development, the more time you spend on a feature, the better it gets (remember that trilemma we discussed earlier?). There's one more step before we can call it done. In the last step, we'll add some new screens (for example, start, win or lose), game state tracking and HUD elements, and a few other items.

See Also

Conceptual

FuelCell Example Game