Jakub Arnold's Blog

Let's Write a 2D Platformer From Scratch Using HTML5 and JavaScript, Part 3: Collision Detection

This article is a part 3 of the Let’s Write a 2D Platformer From Scratch Using HTML5 and JavaScript series.

The previous post ended with a very ad-hoc solution to collision detection. We barely managed to get vertical movement working, and didn’t even get started on gravity. There’s a reason for that. Once the player starts moving vertically, we need something better than just checking against the top left corner we immediately run into issues such as passing through walls below the player, as shown in this image:

player stuck in a wall

What we really want is some concept of a collider, which represents the rigid body of an object. There is however one important distinction. We are only concerning ourselves with collision detection, not full rigid body physics, such as is implemented in Box2D. While physics engines provide a huge range of possibilities and features, they are also sometimes difficult to control, such as when using elevators, moving platforms, or climbing slopes. What we’ll do instead is implement simple horizontal and vertical raycasts which will together with a bit of code provide great control over how the player moves in the world. Ray casting is basically like shooting a laser and seeing where it lands. It will allow us to see which object is the closest in a specific direction, and how far is it.

Some platformers can benefity greatly from the use of a physics engines, such as the popular Little Big Planet. Other platformers, such as Super Mario Bros., which require highly precise controls might be better off being implemented using raycasts, as they give the programmer more control. Physics engines are more inclined to work with things like forces, friction, velocities, etc., while the raycast approach is more in the terms of something like if the player is hugging a wall he can press the jump button where the hugging a wall is determined by doing a raycast on both sides of the player and seeing how far is the closest wall.

To keep things simple we still constrain the game to box-shaped objects instead of arbitrary polygons. Each tile is a square, as is the player. But to make things at least somewhat interesting we’ll allow arbitrary shaped boxes, as long as they’re not rotated. This is commonly called an Axis-Aligned Bounding Box (AABB for short).

As a small sidenote, there are already tons of existing libraries for vector math, collision detection, or even specifically ray vs AABB collision detection. I initially didn’t intend to do this part completely from scratch and at least use a small vector wrapper like victor.js, but the library looks basically dead and there are some outstanding issues left unfixed. Then there’s gl-matrix which seems to be up to date, but seems to be more concerned about performance and WebGL than anything else, which isn’t the priority in this series.

Similarly, there is ray-aabb-intersection and ray-aabb which are both more general than what we’ll implement here, but at the same time I feel that one has to ask themselves the question, why are we doing this? If the goal is to write production quality code, we probably wouldn’t pick small libraries which haven’t had any activity for 2-3 years. If the goal is learning, then we get the most out of it by implementing things ourselves.

I wouldn’t be against using a production quality collision library and focus on learning other things, but there doesn’t seem to be one available for JavaScript, comparable to something like ncollide for Rust, and I don’t feel like bringing in the whole of Box2D just yet when we’re starting out. It will probably come handy in a future blog post when we’ll need a more robust solution to collisions and physics.

Horizontal raycast against AABBs

Before we move on, let us define a few things:

When we define these properties, we’re thinking in the HTML5 Canvas’ system of coordinates where positive X means right and positive Y means down. This is different than what the usual Cartesian system of coordinates, which considers its bottom left corner as origin, and positive Y going up.

Just looking at the definitions, they basically give us the answer already. We could just copy paste the definitions, adjust the comparisons for each of the 12 cases (3 for each direction, and there are 4 directions) and be done. But let’s try to be smart and generalize the conditionals at least a little bit.

var Direction = {
    UP: "up",
    DOWN: "down",
    LEFT: "left",
    RIGHT: "right"
};

// A ray is defined by its origin and direction.
function Ray(x, y, dir) {
    this.origin = { x: x, y: y };
    this.direction = dir;
}

// AABB is defined by its top-left corner, width and height.
function AABB(x, y, w, h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
}

function compareInterval(value, low, high) {
    // This shouldn't necessarily be required, but it allows us to just specify
    // the bounds of an interval, without checking which of the two is low and which is high.
    if (low > high) {
        var tmp = high;
        high = low;
        low = tmp;
    }

    // And then we simply check if the value lies outside of the interval
    if (value < low) {
        return -1;
    } else if (low <= value && value <= high) {
        return 0;
    } else if (value > high) {
        return 1;
    }
}

function intersect(ray, aabb) {
    switch (ray.direction) {
        case Direction.UP:
        case Direction.DOWN:
        case Direction.LEFT:
        case Direction.RIGHT:
            if (ray.origin.x <= aabb.x) {
                if (compareInterval(ray.origin.y, aabb.y, aabb.y + aabb.h) == 0) {
                    return { x: aabb.x, y: ray.origin.y };
                } else {
                    return null;
                }
            } else {
                return null;
            }
    }
}

Before we move on any further, we should probably test this code to see if it works, since subtle bugs in collision detection could be hard to debug later on when we try to use it in a game. While the spirit of these articles is let’s write everything ourselves, I don’t feel that writing our own testing framework would be of any benefit, and if you’ve read this far, you can probably do it without many issues (at least for the synchronous testing, which is what we’ll be doing here).

We’ll use QUnit, because it was the only one that literally had a copy-paste-this-and-it-works, which makes it ideal for the JSFiddle based format of these articles. If you have suggestions for a better testing library, please do share them in the comments, but keep in mind that this series is not about setting up the most elaborate build system. If it needs a command line tool to run/build, it’s already too much of a hassle.

Here’s a few tests for the Direction.RIGHT case:

Implementing the other three directions isn’t really challenging as everything is symmetrical. We just have to be careful not to make any mistakes when passing down coordinates. Here’s a full intersect function:

function intersect(ray, aabb) {
    switch (ray.direction) {
        case Direction.UP:
            if (ray.origin.y >= aabb.y + aabb.h) {
                if (compareInterval(ray.origin.x, aabb.x, aabb.x + aabb.w) == 0) {
                    return { x: ray.origin.x, y: aabb.y + aabb.h };
                } else {
                    return null;
                }
            } else {
                return null;
            }
        case Direction.DOWN:
            if (ray.origin.y <= aabb.y) {
                if (compareInterval(ray.origin.x, aabb.x, aabb.x + aabb.w) == 0) {
                    return { x: ray.origin.x, y: aabb.y };
                } else {
                    return null;
                }
            } else {
                return null;
            }
        case Direction.LEFT:
            if (ray.origin.x >= aabb.x + aabb.w) {
                if (compareInterval(ray.origin.y, aabb.y, aabb.y + aabb.h) == 0) {
                    return { x: aabb.x + aabb.w, y: ray.origin.y };
                } else {
                    return null;
                }
            } else {
                return null;
            }
        case Direction.RIGHT:
            if (ray.origin.x <= aabb.x) {
                if (compareInterval(ray.origin.y, aabb.y, aabb.y + aabb.h) == 0) {
                    return { x: aabb.x, y: ray.origin.y };
                } else {
                    return null;
                }
            } else {
                return null;
            }
    }
}

And here’s a JSFiddle with test cases for all four of the directions:

We can also create a simple wrapper to calculate the distance of an AABB:

function distance(a, b) {
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
}

function raycastDistance(ray, aabb) {
    var point = intersect(ray, aabb);

    if (point) {
        return distance(ray.origin, point);
    } else {
        return null;
    }
}

Raycasts against multiple box colliders

So far we implemented an intersect function which takes a ray and an AABB and calculates the intersection point if there is one. While this is useful, it would be far more useful to have a function which simply takes a ray and returns the closest box collider (AABB) the ray hits if there is one. There are numerous ways we could do this. In the ideal case, we’d use a spatial data structure (such as a quad tree or a spatial hash) to figure out the areas through which the ray is cast, and then check against colliders within that area. This avoid iterating the whole world on each raycast. Adding a more intelligent selection of colliders can be done separate from the rest of the code we’ll write here which is why we’ll simply iterate all of the colliders and return the intersection with the closest one.

The code would look something like this:

function raycast(ray, world) {
    var collisions = world.colliders.map(function(aabb) {
        var intersection = intersect(ray, aabb);
        var result = {
            collider: aabb,
            intersection: intersect(ray, aabb)
        };

        if (result.intersection) {
            result.distance = distance(ray.origin, result.intersection);
        }

        return result;
    }).filter(function(collision) {
        return collision.intersection;
    });

    collisions.sort(function(c1, c2) {
        return c1.distance - c2.distance;
    });

    // JavaScript is happy with out of bound indexing, which means this line is still
    // valid even if there are no collisions.
    return collisions[0];
}

Now all we need is to fill a world with colliders and we can do arbitrary raycasts in horizontal/vertical directions and see what we hit. Let’s now go back to our game and test this out. I’ve added a few debug drawing helpers to visualize the rays and the distance from the collider.

Click on the canvas and press A and D to move. You can also click on the JavaScript tab to see the full code for this example.

An important thing to note is that we get 0 distance when touching the wall. This is due to the <= vs < comparisons, which make it easier for us to detect touching walls. It might be worth nothing here that if our colliders weren’t aligned to integer coordinates, we might run into numerical errors.

Collisions on all sides

In order for the player to move around both up/down and left/right we need to detect collisions on all of the edges, so that the player stays blocked by a wall even if only a part of his collider is blocked. We do this by using two raycasts on each side, and storing the results on the player object.

A lot of the old collision code can be replaced with simple conditionals checking the computed distance against the velocity. Note the added lodash library. While it doesn’t provide anything we couldn’t implement ourselves I wanted to keep the code samples on point, and implementing stuff like _.flatten and _.min wouldn’t serve any purpose in this article.

We also inset each ray a little bit into the player box by a small offset off so that the ray doesn’t collide with boxes next to the player in a different direction. For example, a LEFT ray could collide with the ground beneath the player, which is not what we want, as the ground collision will be detected separately by the bottom rays. This is why the BOTTOM LEFT ray is lifted up a little bit to avoid touching the ground.

Click on the canvas and press A and D to move. You can also click on the JavaScript tab to see the full code for this example.

Gravity

Introducing gravity isn’t terribly difficult. We implement it just like in real life, a force causing downward acceleration. This is easier than it sounds, acceleration simply means velocity change per second, which we can implement by adding vertical velocity to the player, and then updating the velocity with a gravitational constant on each frame.

Click on the canvas and press A and D to move and W to jump. You can also click on the JavaScript tab to see the full code for this example.

Overall, after we have the collision rays implemented, the rest of the logic is just a matter of writing out a few conditionals that handle each case.

There is one bug though, which we won’t fix. When the player moves in a perfectly diagonal direction as they’re falling and lands on a corner of a wall the collision won’t detect the wall and the player will fall through. This is because both of the rays on the corner are inset a small amount, causing the player to fall a little bit inside the wall. After that, the collision detection part will notice the rays start inside a wall and return null (because the player is technically inside the box at that point).

player falling through a corner

This goes to show that even simple as casting a few rays against boxes can have lots of edge cases that need to be handled. It is also a good argument for not implementing physics from scratch in a game that will go in productiton, as even a simple case like this isn’t trivial to get completely right.

Conclusion

We’ve implemented basic collision handling and gravity. The game finally plays like a very simple platformer. We won’t be diving into physics anymore, at least not in the sense of implementing them ourselves. Instead, we’ll look at tweening next so that we can add a few simple animations to the game.

This article is a part 3 of the Let’s Write a 2D Platformer From Scratch Using HTML5 and JavaScript series.

References

Related
Gamedev