Intersection Tests in 2D

This library is a collection of common 2D collision detection tests. Hopefully this saves you from the pain of hunting them down yourself, or trying to rip them out of physics libraries.

If you’re looking for further reading, you are hurting yourself if you don’t buy Real-Time Collision Detection. It is easily the best purchase you could make if you are learning about collision detection. There is also an excellent list of different algorithms here.

The code is written in CoffeeScript, but it’s simple and should be easily portable to your language of choice. If you just want to see the code, take a look at the compiled JS file. It’s stripped of comments and fairly readable.

  1. Helpers
  2. Types of Tests
    1. Intersection Tests
    2. Sweep Tests
  3. Axis-Aligned Bounding Boxes
    1. AABB vs Point
    2. AABB vs Segment
    3. AABB vs AABB
    4. AABB vs Swept AABB
  4. Sweeping an AABB Through Multiple Objects

Helpers

Let’s define a couple helpers that we’ll use through the code.

intersect = exports ? (this.intersect ?= {})

intersect.epsilon = epsilon = 1e-8

intersect.abs = abs = (value) ->
  if value < 0 then -value else value

intersect.clamp = clamp = (value, min, max) ->
  if value < min
    min
  else if value > max
    max
  else
    value

intersect.sign = sign = (value) ->
  if value < 0 then -1 else 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.

intersect.Point = class Point
  constructor: (x=0, y=0) ->
    this.x = x
    this.y = y

  clone: ->
    return new Point(this.x, this.y)

  normalize: ->
    length = this.x * this.x + this.y * this.y
    if length > 0
      length = Math.sqrt(length)
      inverseLength = 1.0 / length
      this.x *= inverseLength
      this.y *= inverseLength
    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

A intersects with B and needs to be pushed out

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:

intersect.Hit = class Hit
  constructor: (collider) ->
    this.collider = collider
    this.pos = new Point()
    this.delta = new Point()
    this.normal = new Point()

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.

A intersects both B and C, and is incorrectly pushed into a bad state

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 ambigious 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:

intersect.Sweep = class Sweep
  constructor: ->
    this.hit = null
    this.pos = new Point()
    this.time = 1

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).

intersect.AABB = class AABB
  constructor: (pos, half) ->
    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.

  intersectPoint: (point) ->
    dx = point.x - this.pos.x
    px = this.half.x - abs(dx)
    return null if px <= 0

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

    hit = new Hit(this)
    if px < py
      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
      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.

Near x is greater than far y
Near x is greater than far y

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 infinte 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.

  intersectSegment: (pos, delta, paddingX=0, paddingY=0) ->

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 describe it it as a start pos and a delta vector to the end of the line.

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.

    scaleX = 1.0 / delta.x
    scaleY = 1.0 / delta.y
    signX = sign(scaleX)
    signY = sign(scaleY)
    nearTimeX = (this.pos.x - signX * (this.half.x + paddingX) - pos.x) * scaleX
    nearTimeY = (this.pos.y - signY * (this.half.y + paddingY) - pos.y) * scaleY
    farTimeX = (this.pos.x + signX * (this.half.x + paddingX) - pos.x) * scaleX
    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.

Near x is greater than far y

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 or 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.

    nearTime = if nearTimeX > nearTimeY then nearTimeX else nearTimeY
    farTime = if farTimeX < farTimeY then farTimeX else farTimeY
Behind the segment
In front of the segment

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 or 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.

    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 = hit.time * delta.x
    hit.delta.y = hit.time * delta.y
    hit.pos.x = pos.x + hit.delta.x
    hit.pos.y = pos.y + hit.delta.y
    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.

  intersectAABB: (box) ->
    dx = box.pos.x - this.pos.x
    px = (box.half.x + this.half.x) - abs(dx)
    return null if px <= 0

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

    hit = new Hit(this)
    if px < py
      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
      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

The sweep test prevents A from moving into B
If B is padded with the size of A, this segment test is the same as sweeping A.

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.

  sweepAABB: (box, delta) ->
    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 and delta.y == 0
      sweep.pos.x = box.pos.x
      sweep.pos.y = box.pos.y
      sweep.hit = this.intersectAABB(box)
      if sweep.hit?
        sweep.time = sweep.hit.time = 0
      else
        sweep.time = 1

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, along the segment of movement.

    else
      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
        direction = delta.clone()
        direction.normalize()
        sweep.hit.pos.x += direction.x * box.half.x
        sweep.hit.pos.y += direction.y * box.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.

  sweepInto: (staticColliders, delta) ->
    nearest = new Sweep()
    nearest.time = 1
    nearest.pos.x = this.pos.x + delta.x
    nearest.pos.y = this.pos.y + delta.y
    for collider in staticColliders
      sweep = collider.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.

h