Intersection Tests in 2D

export const EPSILON: number = 1e-8;

export function abs(value: number): number {
  return value < 0 ? -value : value;
}

export function clamp(value: number, min: number, max: number): number {
  if (value < min) {
    return min;
  } else if (value > max) {
    return max;
  } else {
    return value;
  }
}

export function sign(value: number): number {
  return value < 0 ? -1 : 1;
}

We’ll also need a 2D point. We could just use a literal {x: 0, y: 0} object, but you have to normalize and copy things quite a bit when doing collision detection, so it makes things a bit more readable to formalize it as a class.

export class Point {
  public x: number;
  public y: number;

  constructor(x: number = 0, y: number = 0) {
    this.x = x;
    this.y = y;
  }

  public clone(): Point {
    return new Point(this.x, this.y);
  }

  public normalize(): number {
    let length = this.x * this.x + this.y * this.y;
    if (length > 0) {
      length = Math.sqrt(length);
      const inverseLength = 1.0 / length;
      this.x *= inverseLength;
      this.y *= inverseLength;
    } else {
      this.x = 1;
      this.y = 0;
    }
    return length;
  }
}

Types of Tests

Collision and physics libraries generally assign things to two categories: static objects at rest, and dynamic moving objects. Full physics libraries often solve things in more complicated (and more efficient) ways, and optimize for cases of many objects moving at once and colliding against one another.

But, for most simple 2D games, it’s usually enough to do a collision test between the object you’re moving now (while moving it in the code), and the rest of the world. The world for this type of game rarely contains so many objects that this hurts your performance, and it makes the problem far easier to solve. It also makes it easier to fine tune the physics system, which is often very important for platformers.

As such, the functions in this code are all written for static vs static or moving vs static object tests, to keep things simple.

Intersection Tests

Intersection tests are a static vs static test. They check whether two static objects are overlapping. They have a boolean result (colliding or not), with a vector which tells you how you could move the objects so that they’re no longer overlapping.

Intersection tests will return a Hit object when a collision occurs:

type Collider = AABB;

export class Hit {
  public collider: Collider;
  public pos: Point;
  public delta: Point;
  public normal: Point;
  public time: number;

  constructor(collider: Collider) {
    this.collider = collider;
    this.pos = new Point();
    this.delta = new Point();
    this.normal = new Point();
    this.time = 0;
  }
}

• hit.pos is the point of contact between the two objects (or an estimation of it, in some sweep tests).
• hit.normal is the surface normal at the point of contact.
• hit.delta is the overlap between the two objects, and is a vector that can be added to the colliding object’s position to move it back to a non-colliding state.
• hit.time is only defined for segment and sweep intersections, and is a fraction from 0 to 1 indicating how far along the line the collision occurred. (This is the \(t\) value for the line equation \(L(t) = A + t(B - A)\))

Sweep Tests

Sweep tests are a moving vs static test. They take two objects, sweep one along a line of movement, and determine when it first collides with the other object along that path of movement.

Normal intersection tests are helpful for static objects, but they aren’t the best choice to collide a moving object. If you are trying to collide an object A against two objects, B and C, you can easily get into an ambiguous situation where the collision isn’t as easy to resolve.

Our intersection tests can only determine what the best way to resolve a collision with an object is for that one object, independent of any other objects you want to collide with. This means that correcting for a collision with object B moves you into a state where are colliding with object C, and the same thing happens with object C.

Instead, you can use a sweep test to take the path of movement into account, and stop objects from ever moving into other objects.

Sweep tests return a Sweep object:

export class Sweep {
  public hit: Hit | null;
  public pos: Point;
  public time: number;

  constructor() {
    this.hit = null;
    this.pos = new Point();
    this.time = 1;
  }
}

• sweep.hit is a Hit object if there was a collision, or null if not.
• sweep.pos is the furthest point the object reached along the swept path before it hit something.
• sweep.time is a copy of sweep.hit.time, offset by epsilon, or 1 if the object didn’t hit anything during the sweep.

Axis-Aligned Bounding Boxes

Axis-aligned bounding boxes (AABBs) are bounding rectangles that do not rotate. This means that their edges are always aligned with the main X and Y axes, which makes collision detection much simpler. These examples specify an AABB via a center point and box’s half size for each axis (that is, the box’s “radius” on each axis).

export class AABB {
  public pos: Point;
  public half: Point;

  constructor(pos: Point, half: Point) {
    this.pos = pos;
    this.half = half;
  }

The library has four axis-aligned bounding box (AABB) tests: AABB vs point, AABB vs segment (raycast), AABB vs AABB, and AABB vs swept AABB.

AABB vs Point

This test is very simple, but I’ve included it for completeness. If a point is behind all of the edges of the box, it’s colliding. The function returns a Hit object, or null if the two do not collide. hit.pos and hit.delta will be set to the nearest edge of the box.

This code first finds the overlap on the X and Y axis. If the overlap is less than zero for either, a collision is not possible. Otherwise, we find the axis with the smallest overlap and use that to create an intersection point on the edge of the box.

  public intersectPoint(point: Point): Hit | null {
    const dx = point.x - this.pos.x;
    const px = this.half.x - abs(dx);
    if (px <= 0) {
      return null;
    }

    const dy = point.y - this.pos.y;
    const py = this.half.y - abs(dy);
    if (py <= 0) {
      return null;
    }

    const hit = new Hit(this);
    if (px < py) {
      const sx = sign(dx);
      hit.delta.x = px * sx;
      hit.normal.x = sx;
      hit.pos.x = this.pos.x + (this.half.x * sx);
      hit.pos.y = point.y;
    } else {
      const sy = sign(dy);
      hit.delta.y = py * sy;
      hit.normal.y = sy;
      hit.pos.x = point.x;
      hit.pos.y = this.pos.y + (this.half.y * sy);
    }
    return hit;
  }

AABB vs Segment

Games use segment intersection tests all the time, for everything from line of sight to checking whether a bullet hit a monster. This is the most complicated of the four AABB tests, and is commonly known as a slab test. It finds the time of the line’s intersection with the near and far edges of each axis of the AABB. If they overlap, the segment is intersecting.

What are the near and far edges? Well, in our examples to the right, the direction of the segment is from the top left to the bottom right. This means that the near edges of the box are the top and left edges, and the far edges of the box are the bottom and right edges.

Note that the intersection points might not actually be on the box or the segment. They will be at the intersection of the infinite lines of the box’s edges and the infinite line of the segment.

This is a weird concept, so don’t feel bad if it takes a while for it to sink in. For further reading, I recommend IRT p.65,104 and WilliamsEtAl05.

The function calculates the collision times along the line for each edge of the box. It returns a Hit object (with an extra time property), or null if the two do not overlap. paddingX and paddingY will be added to the radius of the bounding box, if specified.

  public intersectSegment(pos: Point, delta: Point, paddingX: number = 0,
                          paddingY: number = 0): Hit | null {

You might notice we haven’t defined a segment argument. A segment from point \(A\) to point \(B\) can be expressed with the equation \(S(t) = A + t(B - A)\), for \(0 <= t <= 1\). In this equation, \(t\) is the time along the line, or percentage distance from \(A\) to \(B\). Instead of formalizing the concept of a segment, we use this equation and create a variable pos with the value of \(A\), and a variable delta with the value of \(B - A\).

Next, we need to find the linear time at which point the segment intersects with the box’s near and far edges.

We can calculate this by subtracting the position of the edge from the segment’s start position, then dividing by the segment’s delta. Scaling is done here using multiplication instead of division to deal with floating point issues.

    const scaleX = 1.0 / delta.x;
    const scaleY = 1.0 / delta.y;
    const signX = sign(scaleX);
    const signY = sign(scaleY);
    const nearTimeX = (this.pos.x - signX * (this.half.x + paddingX) - pos.x) * scaleX;
    const nearTimeY = (this.pos.y - signY * (this.half.y + paddingY) - pos.y) * scaleY;
    const farTimeX = (this.pos.x + signX * (this.half.x + paddingX) - pos.x) * scaleX;
    const farTimeY = (this.pos.y + signY * (this.half.y + paddingY) - pos.y) * scaleY;

Now we have to compare these times to see if a collision is possible.

If the closest time of collision on either axis is further than the far time on the opposite axis, we can’t be colliding. For instance, in the example to the right, because the segment’s infinite line intersected the infinite line of the box’s top edge, before it ever hit the line for the left edge, we know the intersection occurred before the segment ever reached the box. We don’t need to do any more checks, because we know a collision isn’t possible.

    if (nearTimeX > farTimeY || nearTimeY > farTimeX) {
      return null;
    }

Otherwise, find the greater of the near times, and the lesser of the far times — we want the times that got closest to the slab. We can check these two times to determine whether the collision occurred on the segment.

    const nearTime = nearTimeX > nearTimeY ? nearTimeX : nearTimeY;
    const farTime = farTimeX < farTimeY ? farTimeX : farTimeY;

If the near time is greater than or equal to 1, the line starts in front of the nearest edge, but finishes before it reaches it. That is, it means it further than a whole segment length away. If the far time is less than or equal to 0, the line starts in front of the far side of the box, and points away from the box.

    if (nearTime >= 1 || farTime <= 0) {
      return null;
    }

If we’ve gotten this far a collision of some sort is happening. If the near time is greater than zero, the segment starts outside and is entering the box. Otherwise, the segment starts inside the box, and is exiting it. If we’re entering the box, we can set the hit time to the near time, since that’s the point along the segment at which it collided. If it’s inside, it’s colliding at the very starting of the line, so just set the hit time to zero.

    const hit = new Hit(this);
    hit.time = clamp(nearTime, 0, 1);
    if (nearTimeX > nearTimeY) {
      hit.normal.x = -signX;
      hit.normal.y = 0;
    } else {
      hit.normal.x = 0;
      hit.normal.y = -signY;
    }
    hit.delta.x = (1.0 - hit.time) * -delta.x;
    hit.delta.y = (1.0 - hit.time) * -delta.y;
    hit.pos.x = pos.x + delta.x * hit.time;
    hit.pos.y = pos.y + delta.y * hit.time;
    return hit;
  }

AABB vs AABB

This test uses a separating axis test, which checks for overlaps between the two boxes on each axis. If either axis is not overlapping, the boxes aren’t colliding.

The function returns a Hit object, or null if the two static boxes do not overlap, and gives the axis of least overlap as the contact point. That is, it sets hit.delta so that the colliding box will be pushed out of the nearest edge. This can cause weird behavior for moving boxes, so you should use sweepAABB instead for moving boxes.

This code is very similar to the intersectPoint function above.

  public intersectAABB(box: AABB): Hit | null {
    const dx = box.pos.x - this.pos.x;
    const px = (box.half.x + this.half.x) - abs(dx);
    if (px <= 0) {
      return null;
    }

    const dy = box.pos.y - this.pos.y;
    const py = (box.half.y + this.half.y) - abs(dy);
    if (py <= 0) {
      return null;
    }

    const hit = new Hit(this);
    if (px < py) {
      const sx = sign(dx);
      hit.delta.x = px * sx;
      hit.normal.x = sx;
      hit.pos.x = this.pos.x + (this.half.x * sx);
      hit.pos.y = box.pos.y;
    } else {
      const sy = sign(dy);
      hit.delta.y = py * sy;
      hit.normal.y = sy;
      hit.pos.x = box.pos.x;
      hit.pos.y = this.pos.y + (this.half.y * sy);
    }
    return hit;
  }

AABB vs Swept AABB

Swept volume tests are awesome — they tell you whether object A hits object B at any point along a movement path. This problem seems hard, until someone tells you the magic word: Minkowski. If you inflate the static box by the size of the moving box, you can just test the movement segment against the padded static box. The point at which the segment intersects the padded box tells you where the moving box first collided with the static box.

sweepAABB finds the intersection of this box and another moving box, where the delta argument is a point describing the movement of the box. It returns a Sweep object. sweep.hit will be a Hit object if the two collided, or null if they did not overlap.

  public sweepAABB(box: AABB, delta: Point): Sweep {
    const sweep = new Sweep();

If the sweep isn’t actually moving anywhere, just do a static test. It’s faster and will give us a better result for that case.

    if (delta.x === 0 && delta.y === 0) {
      sweep.pos.x = box.pos.x;
      sweep.pos.y = box.pos.y;
      sweep.hit = this.intersectAABB(box);
      sweep.time = sweep.hit ? (sweep.hit.time = 0) : 1;
      return sweep;
    }

Otherwise, call into intersectSegment instead, where the segment is the center of the moving box, with the same delta. We pass the moving box’s half size as padding. If we get a hit, we need to adjust the hit pos. Since a segment vs box test was used, the hit pos is the center of the box. This offsets it to the edge of the box, as close to the segment of movement as possible.

    sweep.hit = this.intersectSegment(box.pos, delta, box.half.x, box.half.y);
    if (sweep.hit) {
      sweep.time = clamp(sweep.hit.time - EPSILON, 0, 1);
      sweep.pos.x = box.pos.x + delta.x * sweep.time;
      sweep.pos.y = box.pos.y + delta.y * sweep.time;
      const direction = delta.clone();
      direction.normalize();
      sweep.hit.pos.x = clamp(
        sweep.hit.pos.x + direction.x * box.half.x,
        this.pos.x - this.half.x, this.pos.x + this.half.x);
      sweep.hit.pos.y = clamp(
        sweep.hit.pos.y + direction.y * box.half.y,
        this.pos.y - this.half.y, this.pos.y + this.half.y);
    } else {
      sweep.pos.x = box.pos.x + delta.x;
      sweep.pos.y = box.pos.y + delta.y;
      sweep.time = 1;
    }
    return sweep;
  }

Sweeping an AABB Through Multiple Objects

So, let’s say we have an AABB we want to move from one point to another, without allowing it to collide with a list of static AABBs. To do this, we need to call sweepAABB on each static object, and keep track of the sweep that moved the least distance — that is, the nearest collision to the start of the path.

  public sweepInto(staticColliders: Collider[], delta: Point): Sweep {
    let nearest = new Sweep();
    nearest.time = 1;
    nearest.pos.x = this.pos.x + delta.x;
    nearest.pos.y = this.pos.y + delta.y;
    for (let i = 0, il = staticColliders.length; i < il; i++) {
      const sweep = staticColliders[i].sweepAABB(this, delta);
      if (sweep.time < nearest.time) {
        nearest = sweep;
      }
    }
    return nearest;
  }
}

It’s a common use case to have a single object that needs to move through a world, colliding with many other objects. Note that solving this problem efficiently requires two steps:

1. A broad phase, which does not do precise collision detection, but which can very quickly reject large chunks of the world which are not likely to be colliding. That is, you don’t have to try to calculate how two objects are colliding if you know they’re in entirely different rooms.
2. A narrow phase, which finds, given a set of items which are likely to be colliding, the earliest point at which the moving object collided with one of the items.

The first step is out of scope for this library, but these tests are great for solving the narrow phase. You can usually get away without a broad phase for simple games, however, if you aren’t colliding against a huge number of objects.