[Algorithm] 2D Collision Detection

I have posted a series about simple game programming in Python call ‘Fun’ on this blog. One of the common interactions between objects in games is the collision between objects. As such, all game engine or framework has a compilation of methods for detecting collision.

The basic idea is that despite the different geometry shapes of the objects, we can create a boundary that covers the entire object, called the bounding box or hitbox and check for collision conditions based on these boxes. Even though collion may not be pixel perfect, but this looks good and performant enough, especially when there are multiple entities. So you are trading between aesthetic and frame per second (fps) here.

Based on the number of dimension (2D vs. 3D) and how accurate the checking is, the algorithm can become pretty complex. As this is well-beyond my scope, I will only introduce the most basic collision detection algorithm that’s used in simple 2D games.

Axis-Aligned Bounding Box

One of the simpler form of collision detection between 2 rectangles is the Axis-Aligned Bounding Box algorithm. It involes a set of conditions based on the alignment of the axis. If you don’t understand, don’t worry. I do not get it the first time as well. Let’s take a look at the figure above.

The idea is that the blue area always formed when the two rectangles collide. And we are checking the requirements for the forming of blue area. The conditions is ultimately based on the axis (or side) of the two rectangles.

let black = { x: 5, y: 5, width: 20, height: 15 };
let red = { x: 20, y: 15, width: 30, height: 20 };

if (
  black.x < red.x + red.width &&
  black.x + black.width > red.x &&
  black.y < red.y + red.height &&
  black.y + black.height > red.y
)
  return true;

Drawing out the two rectangle accurately and try substituing the value of [x, y, width, height]. You will see that it returns true. We are checking that there’s no gap between any of the 4 sides of the rectangles. And this will be true for all cases, for example, when you switch only the y coordinates of the rectangles, or in the case that one rectangle envelopes completely the other. Try drawing out differect cases on paper and go through the algorithm. This algorithm, like many others, comes from the mathematical field, and you can extend this for 3D checking by adding conditions for the z-axis.

[To be continued…]