Collision Detection Fundamentals

The Brute-Force Approach: Checking Everything

The simplest way to detect collisions is to check every object against every other object in the scene. For a list of N objects, this means performing roughly N²/2 comparisons every single frame. This is known as a brute-force or O(N^2) algorithm.

While this method is easy to implement and works perfectly for a small number of objects, it quickly becomes a major performance bottleneck as the number of objects grows.

To understand why this is a problem, watch the following short clip.

As you can see, most of the checks are wasted on pairs of objects that are nowhere near each other. So, how do professional game engines solve this?

Broad Phase and Narrow Phase

To avoid the O(N^2) trap, collision detection is typically split into two stages:

1. Broad Phase: The goal is to quickly eliminate pairs of objects that cannot be colliding. This is done using fast, simple tests and spatial partitioning techniques (which we'll explore in the next lesson). The output is a much smaller list of "potentially colliding" pairs.
2. Narrow Phase: For each potentially colliding pair from the broad phase, a more precise and computationally expensive intersection test is performed to determine if they are actually colliding. The aabb_intersect and sphere_intersect functions you've already written are narrow-phase tests.

For today's lesson, we will implement a system that performs only the narrow phase on all possible pairs. This is equivalent to a broad phase that simply returns every pair. It's not efficient, but it's a necessary first step to get a working system that we can optimize later.

Implementing the Collision System

Let's start building. The core of our system will be a function that iterates through all entity pairs, performs checks, and stores the results.

1. Defining a Collision Record

First, when we detect a collision, we need a way to store that information. Let's create a new header file, collision.h, to define a struct for this purpose.

// collision.h




#ifndef COLLISION_H
#define COLLISION_H

// A struct to hold information about a single collision event
typedef struct {
    int entity_a; // The ID of the first entity
    int entity_b; // The ID of the second entity
    // We can add more data later, like penetration depth or contact point
} Collision;




#endif // COLLISION_H

2. Local vs. World Space Colliders

A crucial detail: the AABB and Sphere data stored in our Collider components are in local space. This means their positions are relative to the entity's own origin (0,0,0). Our intersection functions, however, need to operate on coordinates in world space.

Before we can check for a collision between two entities, we must first calculate the world-space position of their colliders using their Transform components.

• For an AABB: world_aabb.min = entity_transform.position + local_aabb.min
• For a Sphere: world_sphere.center = entity_transform.position + local_sphere.center

This correctly positions the colliders in the game world before the check.

3. Handling Mixed Collider Types (AABB vs. Sphere)

Our system needs to handle checks between AABB vs AABB and Sphere vs Sphere. But what about AABB vs Sphere? We need a new intersection function for this.

The logic for an AABB-Sphere test is as follows:

1. Find the point on the AABB that is closest to the sphere's center.
2. Calculate the distance between that closest point and the sphere's center.
3. If that distance is less than the sphere's radius, they are colliding.

Let's add this function to our physics library.

// In physics.h (add the function prototype)
bool aabb_sphere_intersect(const AABB* aabb, const Sphere* sphere);

// In physics.c (add the implementation)



#include <cglm/cglm.h> // For glm_clamp

bool aabb_sphere_intersect(const AABB* aabb, const Sphere* sphere) {
    // Find the point on the AABB closest to the sphere's center
    float closest_x = fmaxf(aabb->min[0], fminf(sphere->center[0], aabb->max[0]));
    float closest_y = fmaxf(aabb->min[1], fminf(sphere->center[1], aabb->max[1]));
    float closest_z = fmaxf(aabb->min[2], fminf(sphere->center[2], aabb->max[2]));

    vec3 closest_point = {closest_x, closest_y, closest_z};

    // Calculate the distance squared between the closest point and the sphere center
    vec3 distance_vec;
    glm_vec3_sub(sphere->center, closest_point, distance_vec);
    float distance_sq = glm_vec3_dot(distance_vec, distance_vec);

    // If the distance squared is less than the radius squared, they intersect
    return distance_sq < (sphere->radius * sphere->radius);
}

4. The collision_system_update Function

Now we have all the pieces to build our main system. The following article provides an excellent template for the core logic, which we will adapt from C++ to our C-based ECS.

Let's create collision_system.h and collision_system.c for our implementation.

// collision_system.h




#ifndef COLLISION_SYSTEM_H
#define COLLISION_SYSTEM_H




#include "ecs.h"
#include "collision.h"

/**
 * Checks all entities for collisions and populates a list of collision events.
 * @param world A pointer to the game world.
 * @param collisions An array to store detected collisions.
 * @param max_collisions The maximum number of collisions the array can hold.
 * @return The number of collisions detected.
 */
int collision_system_update(World* world, Collision* collisions, int max_collisions);




#endif // COLLISION_SYSTEM_H

// collision_system.c




#include "collision_system.h"
#include "physics.h" // Our intersection functions
#include <string.h>   // For memcpy

// Helper function to dispatch the correct collision check
static bool check_collision(const Collider* col_a, const Transform* trans_a,
                            const Collider* col_b, const Transform* trans_b) {
    // Create world-space copies of the colliders
    Collider world_col_a = *col_a;
    Collider world_col_b = *col_b;

    if (world_col_a.type == COLLIDER_TYPE_AABB) {
        glm_vec3_add(trans_a->position, world_col_a.data.aabb.min, world_col_a.data.aabb.min);
        glm_vec3_add(trans_a->position, world_col_a.data.aabb.max, world_col_a.data.aabb.max);
    } else if (world_col_a.type == COLLIDER_TYPE_SPHERE) {
        glm_vec3_add(trans_a->position, world_col_a.data.sphere.center, world_col_a.data.sphere.center);
    }

    if (world_col_b.type == COLLIDER_TYPE_AABB) {
        glm_vec3_add(trans_b->position, world_col_b.data.aabb.min, world_col_b.data.aabb.min);
        glm_vec3_add(trans_b->position, world_col_b.data.aabb.max, world_col_b.data.aabb.max);
    } else if (world_col_b.type == COLLIDER_TYPE_SPHERE) {
        glm_vec3_add(trans_b->position, world_col_b.data.sphere.center, world_col_b.data.sphere.center);
    }

    // --- Dispatch the correct intersection test ---
    if (world_col_a.type == COLLIDER_TYPE_AABB && world_col_b.type == COLLIDER_TYPE_AABB) {
        return aabb_intersect(&world_col_a.data.aabb, &world_col_b.data.aabb);
    }
    if (world_col_a.type == COLLIDER_TYPE_SPHERE && world_col_b.type == COLLIDER_TYPE_SPHERE) {
        return sphere_intersect(&world_col_a.data.sphere, &world_col_b.data.sphere);
    }
    if (world_col_a.type == COLLIDER_TYPE_AABB && world_col_b.type == COLLIDER_TYPE_SPHERE) {
        return aabb_sphere_intersect(&world_col_a.data.aabb, &world_col_b.data.sphere);
    }
    if (world_col_a.type == COLLIDER_TYPE_SPHERE && world_col_b.type == COLLIDER_TYPE_AABB) {
        return aabb_sphere_intersect(&world_col_b.data.aabb, &world_col_a.data.sphere);
    }

    return false;
}

int collision_system_update(World* world, Collision* collisions, int max_collisions) {
    int collision_count = 0;
    const int required_mask = COMPONENT_TRANSFORM | COMPONENT_COLLIDER;

    // Iterate through all unique pairs of entities
    for (int i = 0; i < MAX_ENTITIES; ++i) {
        // Check if entity 'i' has the components we need
        if ((world->masks[i] & required_mask) != required_mask) {
            continue;
        }

        for (int j = i + 1; j < MAX_ENTITIES; ++j) {
            // Check if entity 'j' has the components we need
            if ((world->masks[j] & required_mask) != required_mask) {
                continue;
            }

            // Perform the collision check
            if (check_collision(&world->colliders[i], &world->transforms[i],
                                &world->colliders[j], &world->transforms[j])) {
                
                if (collision_count < max_collisions) {
                    collisions[collision_count].entity_a = i;
                    collisions[collision_count].entity_b = j;
                    collision_count++;
                }
            }
        }
    }
    return collision_count;
}

5. Testing the System

Finally, let's update main.c to create some entities and use our new system to check for collisions between them.

// In main.c



#include <stdio.h>
#include "ecs.h"
#include "collision_system.h"

int main(void) {
    World world;
    world_init(&world);

    printf("--- Collision System Test ---\n");

    // --- Create Entities ---
    // A static box at the origin
    int box1 = world_create_entity(&world);
    entity_add_transform(&world, box1, (Transform){{0.0f, 0.0f, 0.0f}});
    entity_add_collider_aabb(&world, box1, (AABB){{-0.5f, -0.5f, -0.5f}, {0.5f, 0.5f, 0.5f}});
    printf("Created Box 1 (AABB) with ID: %d at (0, 0, 0)\n", box1);

    // A second box, overlapping the first
    int box2 = world_create_entity(&world);
    entity_add_transform(&world, box2, (Transform){{0.8f, 0.0f, 0.0f}});
    entity_add_collider_aabb(&world, box2, (AABB){{-0.5f, -0.5f, -0.5f}, {0.5f, 0.5f, 0.5f}});
    printf("Created Box 2 (AABB) with ID: %d at (0.8, 0, 0)\n", box2);

    // A sphere, colliding with box1
    int sphere1 = world_create_entity(&world);
    entity_add_transform(&world, sphere1, (Transform){{0.0f, 1.0f, 0.0f}});
    entity_add_collider_sphere(&world, sphere1, (Sphere){{0.0f, 0.0f, 0.0f}, 0.6f});
    printf("Created Sphere 1 with ID: %d at (0, 1.0, 0)\n", sphere1);

    // A distant sphere, not colliding with anything
    int sphere2 = world_create_entity(&world);
    entity_add_transform(&world, sphere2, (Transform){{5.0f, 5.0f, 5.0f}});
    entity_add_collider_sphere(&world, sphere2, (Sphere){{0.0f, 0.0f, 0.0f}, 0.5f});
    printf("Created Sphere 2 with ID: %d at (5, 5, 5)\n", sphere2);
    
    // --- Run the Collision System ---
    Collision collision_list[16];
    int num_collisions = collision_system_update(&world, collision_list, 16);

    printf("\n--- Detected Collisions (%d) ---\n", num_collisions);
    for (int i = 0; i < num_collisions; ++i) {
        printf("Collision between entity %d and entity %d\n",
               collision_list[i].entity_a,
               collision_list[i].entity_b);
    }

    return 0;
}

Compile and run your program. You should see output indicating that collisions were detected between box1 and box2, and between box1 and sphere1, but not for any other pairs. Success! You have a working collision detection system.

Conclusion

Excellent work! You have now implemented the logical heart of a collision detection engine. While simple, it's a complete system that correctly identifies intersecting objects in your game world.

Key Takeaways:

• A "system" in an ECS architecture contains the logic that operates on components.
• The brute-force O(N^2) collision check involves iterating through all unique pairs of entities.
• Professional engines split detection into a broad phase (finding potential collisions) and a narrow phase (confirming actual collisions). Our system currently only performs a narrow phase on all pairs.
• Collider components store data in local space, which must be converted to world space using the entity's Transform before checking.
• We can use if/else or switch statements to dispatch the correct intersection test based on the ColliderType of the two entities.

Preview of the Next Lesson:
Our current system works, but it won't scale. In the next lesson, we will implement our first proper broad-phase optimization. You will learn how to use spatial partitioning (specifically, a uniform grid) to dramatically reduce the number of pairs we need to check, bringing your engine's performance much closer to that of a commercial-grade solution.