Introduction

At the heart of every game design is interaction - interaction between the player and a simulated game world. This simulation imposes rules about how interaction is allowed to unfold, and in nearly all cases is built upon the mechanism of collision detection - detecting when one sprite touches or overlaps another within the game world.

Consider the basic mechanics of many classic games:

• In Space Invaders, bullets from the player’s turret destroy invading aliens, while alien’s bullets chew away the player’s shields and kill the player if they strike him or her.
• In the Super Mario Bros. series, jumping on an enemy squishes them - yet letting the enemy walk into Mario will kill him.
• In the Sonic series, running over an enemy while spinning will destroy that enemy, freeing the trapped animal within, yet walking into the same enemy will hurt Sonic.

In each of these examples, the basis for interacting with other sprites is collision detection, and, depending on the nature of the collision, different in-game effects are triggered.

So how do we detect collisions between two sprites? That is the subject of this chapter.

Collision Shapes

Perhaps the most straightforward approach is the use of a collision shape (also called a collision primitive or bounding area). This is a simplified representation of the sprite - simplified in a way that allows for easy mathematical detection of collision events. The collision shape mimics the shape of the overall sprite:

For a good visualization of collision shapes and the mathematics behind the collision detection, visit Jeffrey Thompson’s Collision Detection Page

Thus, circular sprites are represented by circles, and rectangular sprites by rectangles. Very small sprites (like circles) can be approximated by a point. Circles, rectangles, and points are by far the most common of 2D collision shapes, because the mathematics involved in detecting collisions with these shapes is very straightforward, and because the memory required to store these collision shapes is minimal.

Bounding points are typically defined with a single point (x & y). Bounding circles are typically defined with a center point (x & y) and a radius. Bounding rectangles are typically defined by a position (x & y) and a width and height - although an alternate definition using left, top, right, and bottom values is also sometimes used. Also, while the position often refers to the upper left corner, it can also be set in the center of the rectangle, or at the middle bottom, or anywhere else that is convenient - as long as the positioning is consistent throughout the game code, it won’t be an issue.

These values can be stored as either an integer or floating point number. When rendered on-screen, any fractional values will be converted to whole pixels, but using floats can preserve more detail until that point.

Here are some straightforward struct representations for each:

public struct BoundingCircle
{
  public float X;
  public float Y;
  public float Radius;
}

public struct BoundingRectangle
{
  public float X;
  public float Y;
  public float Width;
  public float Height;
}

public struct BoundingPoint
{
  public float X;
  public float Y;
}

Point on Point Collisions

Because a point has no size, two points collide only if they have the same x and y values. In other words, two points collide if they are the same point. This is simple to implement in code:

/// <summary>
/// Detects a collision between two points
/// </summary>
/// <param name="p1">the first point</param>
/// <param name="p2">the second point</param>
/// <returns>true when colliding, false otherwise</returns>
public static bool Collides(BoundingPoint p1, BoundingPoint p2)
{
    return p1.X == p2.X && p1.Y == p2.Y;
}

Circle on Circle Collisions

Only slightly harder than checking for collisions between two points is a collision between two circles. Remember a circle is defined as all points that are $ radius $ distance from the $ center $. For two circles to collide, some of these points must fall within the region defined by the other. If we were to draw a line from center to center:

We can very quickly see that if the length of this line is greater than the sum of the radii of the circle, the two circles do not overlap. We can calculate the distance between the circles using the distance formula:

This can then be compared to the sum of the two circle’s radii, giving us an indication of the relationship between the two shapes:

However, computing the square root is a costly operation in computational terms, so we will typically square both sides of the equation and use a comparison of the squares instead:

From these inequalities we can very easily write a test for determining if our shapes collide.

/// <summary>
/// Detects a collision between two circles
/// </summary>
/// <param name="c1">the first circle</param>
/// <param name="c2">the second circle</param>
/// <returns>true for a collision, false otherwise</returns>
public static bool Collides(BoundingCircle c1, BoundingCircle c2)
{
    return Math.Pow(c1.Radius + c2.Radius, 2) >= Math.Pow(c2.X - c1.X, 2) + Math.Pow(c2.Y - c1.Y, 2);
}

Rectangle on Rectangle Collisions

There are many possible algorithms to use in detecting when a rectangle collides with another rectangle, each with its own strengths and weaknesses. Again, we can turn to a graphical representation to help us generate our test:

From this first image, we might assume that two rectangles collide if one of their corners falls within the other. Thus, we might think that simply checking if any of the corners of one rectangle fall within the other would give us our result. But that overlooks one important case:

As this example makes clear, the important concept is that one rectangle must overlap the other rectangle in two dimensions (both the X and the Y) for a collision to occur. Thus, we could check:

Horizontally:

• if a’s left side falls within b’s horizontal span
• or if a’s right side falls within b’s horizontal span
• or if b’s left side falls within a’s horizontal span
• or if b’s right side falls within a’s horizontal span

and vertically:

• if a’s top side falls within b’s vertical span
• or if a’s bottom side falls within b’s vertical span
• or if b’s top side falls within a’s vertical span
• or if b’s bottom side falls within a’s vertical span

That is a lot of cases! It also makes for a monster boolean expression, an does a lot of operations. As with many boolean expressions, we can instead consider the negation - proving that the two rectangles do not overlap. This is far simpler; all we need to prove is that the two do not overlap horizontally or vertically. Thus we can check:

Horizontally:

• if a is to the left of b
• or if a is to the right of b

or Vertically:

• if a is above b
• or if a is below b

/// <summary>
/// Detects a collision between two rectangles
/// </summary>
/// <param name="r1">The first rectangle</param>
/// <param name="r2">The second rectangle</param>
/// <returns>true on collision, false otherwise</returns>
public static bool Collides(BoundingRectangle r1, BoundingRectangle r2)
{
    return !(r1.X + r1.Width < r2.X    // r1 is to the left of r2
            || r1.X > r2.X + r2.Width     // r1 is to the right of r2
            || r1.Y + r1.Height < r2.Y    // r1 is above r2 
            || r1.Y > r2.Y + r2.Height); // r1 is below r2
}

Point on Circle Collisions

To determine if a point and circle collide is a degenerate case of circle on circle collision where one circle has a radius of 0. THus:

Which can be rewritten to avoid the square root as:

And in code:

/// <summary>
/// Detects a collision between a circle and point
/// </summary>
/// <param name="c">the circle</param>
/// <param name="p">the point</param>
/// <returns>true on collision, false otherwise</returns>
public static bool Collides(BoundingCircle c, BoundingPoint p)
{
    return Math.Pow(c.Radius, 2) >= Math.Pow(c.X - p.X, 2) + Math.Pow(c.Y - p.Y, 2);
}

Point on Rectangle Collisions

Similarly, a point and rectangle collide if the point falls within the bounds or on an edge of the rectangle.

/// <summary>
/// Detects a collision between a rectangle and a point
/// </summary>
/// <param name="r">The rectangle</param>
/// <param name="p">The point</param>
/// <returns>true on collision, false otherwise</returns>
public static bool Collides(BoundingRectangle r, BoundingPoint p)
{
    return p.X >= r.X && p.X <= r.X + r.Width && p.Y >= r.Y && p.Y <= r.Y + r.Height;
}

Circle on Rectangle Collisions

A circle-on-rectangle collision is a bit more challenging. To understand our strategy, let’s start with a number line:

Notice the red line from 0 to 4? What is the closest point that falls within that line to the value -2? To the value 5? To the value 3? The answers are: 0, 3, and 4. Basically, if the point falls within the section, it is the point itself. Otherwise it is the closest endpoint. Mathematically, this is the clamp operation, and MonoGame provides a method to calculate it: MathHelper.Clamp(float value, float min, float max). It will clamp the provided value to the provided min and max.

If we clamp the circle’s center point to the extents of the rectangle, the result is the nearest point in or on the rectangle to the center of the circle. If the distance between the center and the nearest point is greater than the radius of the circle, then we know the two aren’t intersecting. We can write this using the point/circle test we declared earlier:

/// <summary>
/// Determines if there is a collision between a circle and rectangle
/// </summary>
/// <param name="r">The bounding rectangle</param>
/// <param name="c">The bounding circle</param>
/// <returns>true for collision, false otherwise</returns>
public static bool Collides(BoundingRectangle r, BoundingCircle c)
{
    BoundingPoint p;
    p.X = MathHelper.Clamp(c.X, r.X, r.X + r.Width);
    p.Y = MathHelper.Clamp(c.Y, r.Y, r.Y + r.Height);
    return Collides(c, p);
}

Collision Helper

There are many ways we could organize the methods we saw in the previous section, but one particularly apt one is to organize them into a static helper class, much like our Math and MathHelper classes, i.e. CollisionHelper:

/// <summary>
/// A class containing collision detection methods
/// </summary>
public static class CollisionHelper
{
    /// <summary>
    /// Detects a collision between two points
    /// </summary>
    /// <param name="p1">the first point</param>
    /// <param name="p2">the second point</param>
    /// <returns>true when colliding, false otherwise</returns>
    public static bool Collides(BoundingPoint p1, BoundingPoint p2)
    {
        return p1.X == p2.X && p1.Y == p2.Y;
    }

    // ... more static collision detection methods
}

With such a helper in place, we could also go back and expand our structures, i.e.:

/// <summary>
/// A class representing a bounding point for determining collisions
/// </summary>
public struct BoundingPoint
{
    public float X;
    public float Y;

    /// <summary>
    /// Constructs a BoundingPoint with the provided coordinates
    /// </summary>
    /// <param name="x">The x coordinate</param>
    /// <param name="y">The y coordinate</param>
    public BoundingPoint(float x, float y)
    {
        X = x;
        Y = y;
    }
    
    /// <summary>
    /// Determines if this BoundingPoint collides with another BoundingPoint
    /// </summary>
    /// <param name="o">the other bounding point</param>
    /// <returns>true on collision, false otherwise</returns>
    public bool CollidesWith(BoundingPoint o)
    {
        return CollisionHelper.Collides(o, this);
    }

    /// <summary>
    /// Determines if this BoundingPoint collides with a BoundingCircle
    /// </summary>
    /// <param name="c">the BoundingCircle</param>
    /// <returns>true on collision, false otherwise</returns>
    public bool CollidesWith(BoundingCircle c)
    {
        return CollisionHelper.Collides(c, this);
    }

    /// <summary>
    /// Determines if this BoundingPoint collides with a BoundingCircle
    /// </summary>
    /// <param name="r">the BoundingRectangle</param>
    /// <returns>true on collision, false otherwise</returns>
    public bool CollidesWith(BoundingRectangle r)
    {
        return CollisionHelper.Collides(r, this);
    }
}

We could, of course, directly implement the collision methods within the structs, but this approach avoids duplicating code. It also more closely follows the style of the XNA framework.

Separating Axis Theorem

But what about sprites with shapes don’t map to a circle or rectangle, such as this spaceship sprite:

We could represent this sprite with a bounding polygon:

The polygon can be represented as a data structure using a collection of vectors from its origin (the same origin we use in rendering the sprite) to the points defining its corners:

/// <summary>
/// A struct representing a convex bounding polygon
/// </summary>
public struct BoundingPolygon
{
    /// <summary>
    /// The corners of the bounding polygon, 
    /// in relation to its origin
    /// </summary>
    public IEnumerable<Vector2> Corners;

    /// <summary>
    /// The center of the polygon in the game world
    /// </summary>
    public Vector2 Center;
}

But can we detect collisions between arbitrary polygons? Yes we can, but it requires more work (which is why many sprites stick to a rectangular or circular shape).

Separating Axis Theorem

To detect polygon collisions algorithmically, we turn to the separating axis theorem , which states:

For any n-dimensional euclidean space, if we can find a hyperplane separating two closed, compact sets of points we can say there is no intersection between the sets.

As games typically only deal with 2- or 3-dimensional space, we can re-express these general claims in a more specific form:

For 2-dimensional space: If we can find a separating axis between two convex shapes, we can say there is no intersection between them.

For 3-dimensional space: If we can find a separating plane between two convex shapes we can say there is no intersection between them.

This is actually common-sense if you think about it. If you can draw a line between two shapes without touching either one, they do not overlap. In a drawing, this is quite easy to do - but we don’t have the luxury of using our human minds to solve this problem; instead we’ll need to develop an algorithmic process to do the same.

We can accomplish this by projecting the shapes onto an axis and checking for overlap. If we can find one axis where the projections don’t overlap, then we can say that the two shapes don’t collide (you can see this in the figure to the left). This is exactly the process we used with the bounding box collision test earlier - we simply tested the x and y-axis for separation.

Mathematically, we represent this by projecting the shapes onto an axis - think of it as casting a shadow. If we can find an axis where the two shadows don’t overlap, then we know the two don’t intersect:

How do we accomplish the projection? Consider each edge (the line between vertices in our polygon) as vector $ A $, and the projection axis as vector $ B $, as in the following figure:

We have two formula that can be useful for interpreting this figure: the trigonometric definition of cosine (1) and the geometric definition of the cross-product (2).

$$ cos\theta = \frac{|projection\ of\ A\ onto\ B|}{|A|} \tag{1} $$ $$ A \cdot B = |A||B|cos\theta \tag{2} $$

These two equations can be combined to find a formula for projection (3):

Thus, given two vectors - one for the axis (which needs to be a unit vector), and one to a corner of our collision polygon, we can project the corner onto the axis. If we do this for all corners, we can find the minimum and maximum projection from the polygon.

A helper method to do this might be:

private static MinMax FindMaxMinProjection(BoundingPolygon poly, Vector2 axis)
{
    var projection = Vector2.Dot(poly.Corners[0], axis);
    var max = projection;
    var min = projection;
    for (var i = 1; i < poly.Corners.Length; i++)
    {
        projection = Vector2.Dot(poly.Corners[i], axis);
        max = max > projection ? max : projection;
        min = min < projection ? min : projection;
    }
    return new MinMax(min, max);
}

And the class to represent the minimum and maximum bounds:

/// <summary>
/// An object representing minimum and maximum bounds
/// </summary>
private struct MinMax
{
    /// <summary>
    /// The minimum bound
    /// </summary>
    public float Min;

    /// <summary>
    /// The maximum bound
    /// </summary>
    public float Max;

    /// <summary>
    /// Constructs a new MinMax pair
    /// </summary>
    public MinMax(float min, float max)
    {
        Min = min;
        Max = max;
    }
}

Since we would only be using this class within the collision helper, we could declare it within that class and make it private - one of the few times it makes sense to declare a private class.

If we determine the minimum and maximum projection for both shapes, we can see if they overlap:

If there is no overlap, then we have found a separating axis, and can terminate the search.

But just which axes should we test? Ideally we’d like a minimal set that promises if a separating axis does exist, it will be found. Geometrically, it can be shown that the bare minimum we need to test is an axis parallel to each edge normal of the polygon - that is, an axis at a right angle to the polygon’s edge. Each edge has two normals, a left and right:

In 2D, an edge normal is a unit vector (of length 1) perpendicular to the edge vector (a vector along the edge). We can calculate it by exchanging the x and y components and negating one of them.

Depending on the order we’ve declared our points (clockwise or anti-clockwise) one of these normals will face out of the polygon, while the other will face in. As long as we’re consistent, either direction will work. We calculate the normals by iterating over our points and creating vectors to represent each edge, and then calculating a perpendicular vector to that edge.

If we were to keep using a struct to represent our collision shape, we could add a field for the normals and implement the normal generation within the constructor:

/// <summary>
/// A struct representing a convex bounding polygon
/// </summary>
public struct BoundingPolygon
{
    /// <summary>
    /// The corners of the bounding polygon, 
    /// in relation to its center
    /// </summary>
    public Vector2[] Corners;

    /// <summary>
    /// The center of the polygon in the game world
    /// </summary>
    public Vector2 Center;

    /// <summary>
    /// The normals of each corner of this bounding polygon
    /// </summary>
    public Vector2[] Normals;


    /// <summary>
    /// Constructs a new arbitrary convex bounding polygon
    /// </summary>
    /// <remarks>
    /// In order to be used with Separating Axis Theorem, 
    /// the bounding polygon MUST be convex.
    /// </remarks>
    /// <param name="center">The center of the polygon</param>
    /// <param name="corners">The corners of the polygon</param>
    public BoundingPolygon(Vector2 center, IEnumerable<Vector2> corners)
    {
        // Store the center and corners
        Center = center;
        Corners = corners.ToArray();
        // Determine the normal vectors for the sides of the shape
        // We can use a hashset to avoid duplicating normals
        var normals = new HashSet<Vector2>();
        // Calculate the first edge by subtracting the first from the last corner
        var edge = Corners[Corners.Length - 1] - Corners[0];
        // Then determine a perpendicular vector 
        var perp = new Vector2(edge.Y, -edge.X);
        // Then normalize 
        perp.Normalize();
        // Add the normal to the list
        normals.Add(perp);
        // Repeat for the remaining edges
        for (var i = 1; i < Corners.Length; i++)
        {
            edge = Corners[i] - Corners[i - 1];
            perp = new Vector2(edge.Y, -edge.X);
            perp.Normalize();
            normals.Add(perp);
        }
        // Store the normals
        Normals = normals.ToArray();
    }    

To detect a collision between two BoundingPolygons, we iterate over their combined normals, generating the MinMax of each and testing it for an overlap. Implemented as a method in our CollisionHelper, it would look like something like this:

/// <summary>
/// Detects a collision between two convex polygons
/// </summary>
/// <param name="p1">the first polygon</param>
/// <param name="p2">the second polygon</param>
/// <returns>true when colliding, false otherwise</returns>
public static bool Collides(BoundingPolygon p1, BoundingPolygon p2)
{
    // Check the first polygon's normals
    foreach(var normal in p1.Normals)
    {
        // Determine the minimum and maximum projection 
        // for both polygons
        var mm1 = FindMaxMinProjection(p1, normal);
        var mm2 = FindMaxMinProjection(p2, normal);
        // Test for separation (as soon as we find a separating axis,
        // we know there is no possibility of collision, so we can 
        // exit early)
        if (mm1.Max < mm2.Min || mm2.Max < mm1.Min) return false;
    }
    // Repeat for the second polygon's normals
    foreach (var normal in p2.Normals)
    {
        // Determine the minimum and maximum projection 
        // for both polygons
        var mm1 = FindMaxMinProjection(p1, normal);
        var mm2 = FindMaxMinProjection(p2, normal);
        // Test for separation (as soon as we find a separating axis,
        // we know there is no possibility of collision, so we can 
        // exit early)
        if (mm1.Max < mm2.Min || mm2.Max < mm1.Min) return false;
    }
    // If we reach this point, no separating axis was found
    // and the two polygons are colliding
    return true;
}

We can also treat our other collision shapes as special cases, handling the projection onto an axis based on their characteristics (i.e. a circle will always have a min and max of projection of center - radius and projection of center + radius).

Per-Pixel Collision Detection

Another brute-force approach that can be used with raster graphics when a high degree of accuracy is needed is per-pixel collision detection. This process assumes that a portion of the raster graphics being examined are composed of transparent pixels (i.e. not a part of the object portrayed).

Consider the figure above - there are two raster graphics that overlap. To determine if they collide on a per-pixel basis, we must compare every overlapping pixel between the two images (the purple area). To do this, we must 1) establish the size of the overlapping area, 2) map pixel indices within that area to an index in each graphic, and 3) compare the corresponding pixels in each graphic to see if they are both non-transparent (and therefore colliding).

The following pseudocode does just that for an overlapping area of 200x300 pixels, with the overlapping area beginning at (600, 0) in raster graphic 1 and (0, 10) in raster graphic 2:

for(x = 0; x < 200; x++) {
    for(y = 0; y < 300; y++) {
        if( !(isTransparent(raster1[x + 600][y]) || isTransparent(raster2[x][y+10]) ) {
          return true;
        }
    }
   return false;
}

Note that we short-circuit our investigation as soon as we find an overlapping pixel that is not transparent in at least one of the raster arrays. Yet our worse-case scenario is $ O(width x height) $ of the overlapping region.

Implementing per-pixel collision detection in MonoGame requires us to extract the texture data with Texture2D.GetData(), into which we need to pass an array of Color, i.e. given a Texture2D variable texture:

var textureData = new Color[texture.Width * texture.Height];
texture.GetData(textureData);

Then we can access the individual colors in the array. However, we must also account for how the texture is positioned in the world. This gets even more complicated if the texture has been scaled or rotated. Ratstating describes one approach to tackling this in his post C# XNA Per Pixel Collision Detection on Rotated Objects.

Multiphase Collision Detection

It should be clear that the per-pixel and SAT-based approaches can become very computationally expensive. For this reason, games that need fine-grained collision detection often resort to a multi-phase approach, which utilizes two or more processing passes. Each pass uses an increasingly sophisticated (and therefore costly) collision detection algorithm to find collisions, but only tests those objects that previous passes identified as “possibly colliding”. The more simple methods employed in the first few passes typically can reject a great deal of possible collisions, reducing the number of more expensive comparisons that will be tried later.

The first pass typically consists of testing using axis-aligned bounding boxes or bounding circles, which bound (enclose) the object. As we have already seen, there are very quick collision tests to use with both axis-aligned bounding boxes and with circles. And pair of objects whose bounding areas register a collision are placed in a queue (as a pair) for testing in the next pass.

The next pass will typically resort to a SAT-based algorithm using a simplified outline of the shape in question. This may be the final pass, or it may be used to identify shapes for per-pixel collision detection (or the second pass may be per-pixel detection).

In games that use hierarchical sprite representations (where a sprite may be composed of sub-sprites), the first pass is a bounding area for the entire sprite, but the second pass compares individual parts (often bounding areas for each subpart), which can then be further refined by a SAT or per-pixel approach.

Summary

In this chapter we looked at implementing collision detection using bounding shapes, the separating axis theorem, and per-pixel evaluation. We discussed the merits of the different approaches, and saw how multiphase collision detection can avoid expensive collision detection tests.

There are other techniques we can use to avoid unneeded collision tests as well. We’ll talk about one of these, spatial partitioning in an upcoming chapter.