Collision Detection: Circle vs Circle

What is collision detection?

Wikipedia defines collision detection as “the computational problem of detecting the intersection of two or more objects”. In real life you cannot go through objects but in a computer simulation objects can overlap and go through each other. In order to resemble reality we need a way to detect when objects are overlapping.

Imagine two billiard balls, one of them is moving towards the other. In the real world they collide and each ball goes in a different direction. When programming a simulation we need to check every frame for collision, and when a collision is found resolve it.

Collision detection is a broad and complex problem, and if that wasn’t enough it is also coupled with simulations and physics.

In this article I will only talk about collision detection of two or more circles in 2 dimensions(although the same algorithm works for 3D spheres), and to make it a little more fun I will explain one of the many ways of making things interact besides checking if they are colliding or not.

Here’s a preview of what we will be implementing.

Prerequisites

I have to draw the knowledge required line somewhere, and this is it. Nothing of what i’m about to explain/use is hard or complex. You can learn it in a few minutes. The internet is full of guides and this one will do the job just fine.

These are the things you need to know:

  • What is a circle’s radius
  • What is a vector
  • Subtracting two vectors
  • Magnitude of a vector
  • Normalizing a vector
  • Scaling a vector

I will be programming in C since it’s my favourite language, feel free to translate the code to your language and style of your choice. Let’s start by defining vector and circle structs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
typedef struct vec2
{
    float x, y;
} vec2;

typedef struct circle
{
    vec2 Center; // Center are the coordinates of the circle center
    float Radius;
} circle;

Now let’s define some functions we will need.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vec2 Subtract(vec2 A, vec2 B)
{
    vec2 Result = {0};

    Result.x = A.x - B.x;
    Result.y = A.y - B.y;

    return Result;
}

float Magnitude(vec2 A)
{
    return sqrtf(A.x * A.x + A.y * A.y);
}

vec2 Normalize(vec2 A)
{
    vec2 Result = {0};

    float Length = Magnitude(A);
    Result.x = A.x / Length;
    Result.y = A.y / Length;

    return Result;
}

Checking if two circles collide

Checking if two circles collide is really easy. If the distance between the two circle’s center is less than the sum of their radii, they are colliding. Play around with the following example and you should get the idea. The black line represents the distance between the two circles, and the radii sum is just the sum of both circle’s radii.

The code

The following function returns just a boolean, wether the input circles are colliding or not.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
bool Collide(circle A, circle B)
{
    vec2 Difference = Subtract(A.Center, B.Center);
    float Distance  = Magnitude(Difference);
    float RadiiSum  = A.Radius + B.Radius;

    if(Distance < RadiiSum)
    {
        return true;
    }
    else
    {
	return false;
    }
}

Basic collision interaction

Here we are going to do the red and blue circle interaction seen on the first section.

In order to move the circles apart we need what is called the “minimum translation vector”, in other words it’s how much the circles are overlapping. With this length, we can simply move both circles apart or just one as i did with the red one.

To get the minimum translation vector we subtract the distance from the radiisum and take the absolute value of the result. After that we need to get the normalized direction vector of the distance. After that we just need to add the movement to the red circle.

Math in words makes everyone dizzy, and i’m not good at explaining. Code is a more elegant medium.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void Simulate(circle A, circle *B)
{
    // Be aware that circle B is a pointer, this is because we are
    // going to update it's position. B is the same as the red circle
    // in the previous demo window.

    // Abs -> Absolute value
    // MTD -> Minimum translation distance
    if(Collide(A, *B))
    {
	float RadiiSum = A.Radius + B->Radius;
	float MTD = Abs(Distance - RadiiSum);
	vec2 Direction = Normalize(Subtract(A.Center, B->Center));
	B->x += Direction.x * MTD;
	B->Y += Direction.y * MTD;
    }
}

This last section is a bit more complicated, if you don’t understand something, i recommend doing sketches on pen and paper, that usually helps me.

I’m happy you read this whole thing, thank you, you are awesome.

Until next time.

comments powered by Disqus