Collision detection in games: AABB, circles and grids

In short: Collision detection checks whether two objects touch; simple shapes such as rectangles and circles are cheap to compute, a grid saves comparisons with many objects.

In more detail: Game characters, projectiles and walls must not simply pass through each other. For this the game checks every frame whether shapes overlap. Pixel-exact comparisons would be too slow, so simplified shells (hitboxes) are used.

In Depth

Rectangle against rectangle (AABB)

AABB stands for “axis-aligned bounding box”, a rectangle without rotation. Two rectangles overlap if they overlap on both axes:

function hit(a, b) {
  return a.x < b.x + b.w &&
         a.x + a.w > b.x &&
         a.y < b.y + b.h &&
         a.y + a.h > b.y;
}

Very fast and sufficient for many 2D games.

Circle against circle

Two circles touch if the distance between their centres is smaller than the sum of the radii. Compare squares (no root):

const dx = a.x - b.x, dy = a.y - b.y, r = a.r + b.r;
return dx*dx + dy*dy < r*r;

Circle against rectangle: determine the rectangle’s nearest point to the circle centre and check its distance.

Many objects: broad phase and narrow phase

Checking all pairs costs n² comparisons. A broad phase sorts roughly first: a grid (spatial hash) divides the world into cells, only the same or neighbouring cells are checked. Quadtrees (2D) and octrees (3D) also divide space hierarchically. Then the narrow phase checks exactly (AABB, circle, polygon).

Response and pitfalls

After a collision the object is pushed out of the wall (smallest overlap) or bounces. Tunneling: very fast objects jump through thin walls in one frame; remedies are smaller time steps or ray tests (raycasts) along the movement. For rotated shapes SAT (separating axis theorem) is used. Physics engines (Box2D, Matter.js, Rapier) take over much of this.

See also: Game loop and delta time, Collision, Game engine