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 TypeScript, 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 TypeScript file. The animated examples on this page are also written in TypeScript, using the library.
Let’s define a couple helpers that we’ll use through the code.
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;
}
}
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 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;
}
}
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.time
, offset by epsilon, or 1 if the object
didn’t hit anything during the sweep.
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.
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;
}
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;
}
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;
}
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;
}
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:
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.