Circle Collision Detection

Introduction

I've gotten many questions lately on this site about collision detection, so it's time I start expanding my physics tutorials with more stuff along these lines.

In this tutorial, we'll look at how to use circles to detect collisions.

The Benefits of Circles

With collision detection, we rarely need pixel-perfect or mesh-perfect collision detection. We can usually get away with something "good enough" while spending fewer CPU cycles checking our collisions. If nothing else, we can at least start with a rough approximation and jump down to the "perfect" collision detection algorithm only if the approximation tells us there might be an intersection.

Three rough approximations are commonly used: circles/spheres, axis-aligned bounding boxes, and oriented bounding boxes (boxes, but potentially rotated).

Of the three, circles and spheres are the easiest to deal with because rotation plays no part. No matter how we rotate a circle or sphere, they don't change shape.

Additionally, the code for detecting if two circles intersect is very simple.

This makes circles a great candidate for getting started—and often, for the whole project.

In this tutorial, we'll look at how to make this work.

Building a Circle Type

In the previous tutorial, we used the built-in BoundingSphere type, provided by MonoGame. Alas, there isn't an equivalent BoundingCircle.

But it is easy to make one! So that's what we'll do.

Struct or Class?

The first question to answer is if we should make this a classor a struct. Those linked tutorials cover the differences at a high level, though I also cover it in a lot more depth in my book.

A Circle is a great candidate for a struct—data-centric, value semantics, and small in size. So that's what we'll do here. (Besides, that allows us to mimic what BoundingSphere does.)

Our first version may look like this:

public struct Circle
{
}

Adding Properties

A circle needs two pieces of information: where it is located and how big it is. We'll add properties for its center, using the Vector2 type, and for its size, using a float.

public struct Circle
{
    public Vector2 Center { get; }
    public float Radius { get; }
}

The radius of a circle is the distance from the center to the edge. We could have used the diameter instead, but the radius is more natural for the math we'll be doing.

Note that you may need to add a using directive for Microsoft.Xna.Framework} at the top of your file to use that Vector2 type, if you are putting this in a new file.

Why properties instead of fields? Well… we could do fields. We don't necessarily want the outside world to modify these fields once created. Having get-only properties ensures that's the case, but we also could have made readonly fields and achieved the same effect.

Using properties preserves space for us to change how we store this data internally, while fields are (ever so slightly) faster to access. Indeed, BoundingSphere used public (non-readonly!) fields.

It's a tradeoff, and you must decide which benefits you prefer, and live with the downsides that come with it. I tend to prefer preserving the ability to change over those marginal performance gains, but there is definitely a compelling argument for the alternative here as well. Feel free to do it otherwise in your own code.

Adding a Constructor

We'll also want to add a constructor:

public Circle(Vector2 center, float radius)
{
    Center = center;
    Radius = radius;
}

Since our circle is read-only (via get-only properties), we will definitely want a way to create a circle with specific, non-zero values. (Note that with a struct, we'll still have that default constructor which will default everything to its zero values. We don't need to explicitly write that ourselves.)

The constructor above gives us the ability to make a new circle at a specific location and size.

This gives us the beginnings of our Circle struct:

public struct Circle
{
    public Vector2 Center { get; }
    public float Radius { get; }
 
    public Circle(Vector2 center, float radius)
    {
        Center = center;
        Radius = radius;
    }
}

Point-In-Circle Checking

We're now ready to begin adding collision and intersection code to our Circle struct. We'll start easy: determining if a point is inside our circle.

The algorithm for deciding this is to determine how far the point is from the center of our circle, and check to see if that distance is less than the radius of the circle. If the point is closer to the center than the radius, it is in the circle. If it is farther, it is outside of the circle.

So we can add in this method:

public bool Contains(Vector2 point)
{
    Vector2 relativePosition = point - Center;
    float distanceBetweenPoints = relativePosition.Length();
 
    if (distanceBetweenPoints <= Radius) return true;
    else return false;
}

At this point, a lot of performance-minded programmers may notice that that Length() method call must compute a square root—and they'd be right. Square roots are not the fastest things to compute, and we can actually avoid it by calling ‘LengthSquared()` instead, and then comparing against the square of the radius. After all, we don’t need to know the actual distance here, just whether it is in the circle. So the following is a slightly faster version, at the tradeoff of being a little harder to read and understand (nearly all performance gains come at the cost of readability and maintainability, unfortunately):

public bool Contains(Vector2 point)
{
    Vector2 relativePosition = point - Center;
    float distanceSquared = relativePosition.LengthSquared();
 
    if (distanceSquared <= Radius * Radius) return true;
    else return false;
}

While discussing variations, I'll mention that I've gone the verbose route above. I'm sorely tempted to use this version instead, which has far fewer lines of code. It achieves that by cutting out short-lived variables and using an expression body instead of a block body, but there is definitely more heavy mental lifting on that one line:

public bool Contains(Vector2 point) => (point - Center).LengthSquared() <= Radius * Radius;

Intersection of Two Circles

We'll also want to check if two circles intersect each other. This is also easy.

The algorithm is to see how far apart the two circle centers are. Once we know that, we see how that distance compares to the combined radii of both circles. If one circle has a radius of 1 and the other has a radius of 2, the circles intersect if their center points are within 3 units.

Here's a version of that:

// The wordy version...
public bool Intersects(Circle other)
{
    Vector2 relativePosition = other.Center - Center;
    float distanceBetweenCenters = relativePosition.Length();
    if(distanceBetweenCenters <= Radius + other.Radius) { return true; }
    else { return false; }
}

As before, we could avoid the square root by squaring the sum of the two radii:

public bool Intersects(Circle other)
{
    Vector2 relativePosition = other.Center - Center;
    float distanceSquared = relativePosition.LengthSquared();
    float combinedRadii = Radius + other.Radius;
    if (distanceSquared <= combinedRadii * combinedRadii) return true;
    else return false;
}

Alas, there isn't a way to get a one-liner here while keeping the logic for squaring the radii simple. If we're willing to forego the performance benefits of avoiding the square root, we can do this:

public bool Intersects(Circle other) => (other.Center - Center).Length() <= Radius + other.Radius;

Any of these three options can work fine. They each have pros and cons. I'll go with that middle version, to pick up the performance gains, which I think may matter if we did a lot of circle intersection checks. I'll accept it won't be a short, expression-bodied method.

Our final code, with our Circle type ready for use in collision detection, looks like this:

public struct Circle
{
    public Vector2 Center { get; }
    public float Radius { get; }
 
    public Circle(Vector2 center, float radius)
    {
        Center = center;
        Radius = radius;
    }
 
    public bool Contains(Vector2 point) => (point - Center).LengthSquared() <= Radius * Radius;
 
    public bool Intersects(Circle other)
    {
        Vector2 relativePosition = other.Center - Center;
        float distance = relativePosition.LengthSquared();
        float combinedRadii = Radius + other.Radius;
        if (distance <= combinedRadii * combinedRadii) return true;
        else return false;
    }
}

Using our Circle Struct

I don't want to get into too many details of using this struct within a larger program because that could get big fast. But I think it is worth describing how you could use this to do circle-based collision detection.

There's a lot of ways to improve upon this, but the simplest approach would be to compute a Circle for each object in your game that needs to be checked for collisions. If we assume each object has a position and size, that is easy. Then we just iterate through every object and check it against every other object, looking for collisions.

The code below could be part of a much larger program, and I won't flesh out all the details here, instead, leaving a lot to your imagination:

private List<(GameObject, GameObject)> FindAllIntersections(List<GameObject> gameObjects)
{
    List<(GameObject, GameObject)> intersections = new ();
    for (int i = 0; i < gameObjects.Count; i++)
    {
        GameObject a = gameObjects[i];
        for (int j = i + 1; j < gameObjects.Count; j++)
        {
            GameObject b = gameObjects[j];
 
            Circle circleA = new Circle(a.Position, a.Size);
            Circle circleB = new Circle(b.Position, b.Size);
 
            if (circleA.Intersects(circleB))
                intersections.Add((a, b));
        }
    }
}

This code takes a list of game objects and then iterates through all possible pairings using those two for loops. We create a circle for each object and check them. If we find an intersection, we add the pairas a tupleto the list of intersections.

In my own experience, I've often found that when I'm doing collision detection, I often want more than just the pairing of objects, especially to resolve the intersection. For example, I may want to know the direction between the two objects to slide them back apart or determine bounce angles. But this is maybe enough for a simple game where the resolution step is trivial- such as simply removing one of the objects.

I hesitate to throw tuples in here, given the complexity of a list of tuples and that whole <(…)> syntax. This is not an unreasonable place for tuples. But if you want to make a small struct, class, or record for this instead, that is also a reasonable option.