Collision detection and resolution

Collision detection refers to all methods that detect when a body is touching another. Some examples are checking if a bullet hit an enemy, if a player is touching the floor, if we're close enough to talk to an NPC, and many more. This feature is essential in a lot of games, and in this article we'll describe how to implement it.

When detecting whether two bodies are touching, the method we choose depends on the exact shape of the bodies. For better performance, we can choose specific shapes that are fast to compute, and it just so happens that the rectangles we've been using are such a shape. These are also called AABB (axis aligned bounding box), which means the sides of the rectangle are parallel with the x $x$ and y $y$ axes of the coordinate system.

Checking if two rectangles are touching is rather easy. If the rectanagles have an overlap in both the x $x$ and y $y$ axes, then they overlap.

Two rectangles are said to overlap in either the x $x$ or y $y$ axis if the edges of one rectangles is between the two edges of the other rectangle. In this figure, the four possible cases are shown: no overlap in either axis, overlap in the x $x$ axis only, overlap in the y $y$ axis only, and overlap in both the x $x$ and y $y$ axes. In the final case when there's overlap in both axes the rectangles are visibly one on top of the other.

Let's make a function that check the overlap of two bodies. Given two BodyComponent instances b1 and b2, the checkOverlap function will return true or false depending if they overlap or not.

function checkOverlap(b1, b2) {
    if (b1.position.x + b1.width < b2.position.x ||    // if the right edge of b1 is to the left of the left edge of b2
        b1.position.x > b2.position.x + b2.width ||    // if the left edge of b1 is to the right of the right edge of b2
        b1.position.y + b1.height < b2.position.y ||   // if the bottom edge of b1 is above the top edge of b2
        b1.position.y > b2.position.y + b2.height) {    // if the top edge of b1 is below the bottom edge of b2
        return false;                                    // then there's no overlap
    }
    return true;
}

The above code is actually a great example of a logical transformation. The following statements are equivalent, so we can use any of them as the basis for our function:

Assume the rectangles don't intersect. If one edge of a rectagle in an axis sits between the two edges of the other rectangle, we have a overlap in that axis. If we have an overlap in both axes, the rectangles intersect.
Assume the rectangles intersect. If there is any axis where there is no overlap, then the rectangles don't intersect.

It turns out the second options is easier to program, easier to understand, and more performant, therefore the code above represents the second option.

Now that we have our function, we can put it in a system and use it with an appropriate component. Let's create a directory called collision and as usual, let's create the component first, name it collisionComponent.js, and let's also put the following code there:

import Component from "../ecs/component";

export default class CollisionComponent extends Component {
    constructor(bodyComponent, collisionTag) {
        super();
        this.bodyComponent = bodyComponent;
        this.collisionTag = collisionTag;
        this.collisionCallbacks = {}
    }

    setCollisionCallback(targetCollisionTag, callback) {
        this.collisionCallbacks[targetCollisionTag] = callback;
    }
}

Compared to the components in the previous chapters, the CollisionComponent has a few additional properties that are worth mentioning, the first being the collisionTag. This is a string that is attached to a CollisionComponent and is used to differentiate the types of objects that will be colliding, for example player, enemy, food, poison, etc.

The second important property is the setCollisionCallback method. With this method we can set a callback that will trigger when the CollisionComponent overlaps with another CollisionComponent that has a collisionTag equal to targetCollisionTag. These callbacks are stored in the collisionCallbacks object.

The approach of using collisionTag gives us two primary benefits. The first is that it allows us to have different behavior when colliding with objects of different tags. The second is that we can optimize the performance of the entire CollisionSystem by skipping any two bodies with tags that don't have registered callbacks. For example, if nothing is supposed to happen when a body tagged with food touches another body tagged with food, then we can just skip the comparison between these bodies. This optimization will be explored in a later chapter.

The CollisionSystem is what will actually be doing the overlap checks between the CollisionComponent pairs. The code looks like this:

import System from "../ecs/system";
import CollisionComponent from "./collisionComponent";

export default class CollisionSystem extends System {
    constructor() {
        super();
    }

    update() {
        const collisionInstances = [];
        for(let i = 0; i < this.components.length - 1; i++) {
            for(let j = i + 1; j < this.components.length; j++) {
                if(checkOverlap(this.components[i].bodyComponent, this.components[j].bodyComponent)) {
                    if(this.components[i].collisionCallbacks[this.components[j].collisionTag]) {
                        collisionInstances.push(this.components[i].collisionCallbacks[this.components[j].collisionTag]);
                    }
                    if(this.components[j].collisionCallbacks[this.components[i].collisionTag]) {
                        collisionInstances.push(this.components[j].collisionCallbacks[this.components[i].collisionTag]);
                    }
                }
            }
        }

        for(let collisionInstance of collisionInstances) {
            collisionInstance();
        }
    }

    createCollisionComponent(bodyComponent, collisionTag) {
        let collisionComponent = new CollisionComponent(bodyComponent, collisionTag);
        this.components.push(collisionComponent);
        return collisionComponent;
    }
}

function checkOverlap(b1, b2) {
    if (b1.position.x + b1.width < b2.position.x ||
        b1.position.x > b2.position.x + b2.width ||
        b1.position.y + b1.height < b2.position.y ||
        b1.position.y > b2.position.y + b2.height) {
        return false;
    }
    return true;
}

Like before, we can use the checkOverlap function to check if two bodies overlap. However, this time it has been integrated into the CollisionSystem. Importantly, the system checks all the CollisionComponent pairs, and if they overlap, the corresponding callbacks are scheduled to be called after all pairs are checked. This is done by storing the callbacks in the collisionInstances array, and then calling them all once all pairs have been checked.

The reason why we don't call the callback immediately is that we want to make sure that the callback does not change the state of the game, for example, by removing a body, or by changing the position of a body.

Let's imagine a scenario where a player touches two powerups at the same time, one that gives the player a boost, and the other teleports the player to a new location. If we touch both powerups at the same time, there is no way to know which one will be called first. If we call the boost powerup first, then the teleport powerup will be called after the boost powerup, and the player will get both powerups. On the other hand, if we call the teleport powerup first, the player will be teleported away, and by the time the collision between the player and the boost is checked, they will no longer be touching and the player will not get the boost.

Behavior like the one described above is a great source of subtle and arbitrary bugs. The order in which we iterate through the pairs of CollisionComponents is unpredictable, and can depend upon many factors outside of our control. We must always be on the lookout for these situations and make sure that our engine is both predictable and consistent.

Important to note is that by since we're comparing each pair of CollisionComponents, the number of comparisons is roughly equal to the square of the number of CollisionComponents. This number quickly becomes large, even with as little as 20-30 CollisionComponents there will be 400-900 comparisons. For this reason, we'll be improving and optimizing this code in the next chapter. However, for demonstration purposes or for small examples the current code is fine.

Since collision detection is used extensively in a game, it's important to make it fast. Luckily, there are plenty of opportunities to optimize the code. In the next chapter, we'll apply some optimizations to the CollisionSystem that will make it significantly faster.

Next: Timing, sequencing, and scheduling