2D collision detection

Algorithms to detect collision in 2D games depend on the type of shapes that can collide (e.g. Rectangle to Rectangle, Rectangle to Circle, Circle to Circle). Generally you will have a simple generic shape that covers the entity known as a "hitbox" so even though collision may not be pixel perfect, it will look good enough and be performant across multiple entities. This article provides a review of the most common techniques used to provide collision detection in 2D games.

Axis-Aligned Bounding Box

一种简单碰撞发生于两个轴对齐的矩形之间 —意味着没有旋转。这个算法检测两个图形的４个边之间是否有间隔。任何间隔意味着没有碰撞发生。

var rect1 = {x: 5, y: 5, width: 50, height: 50}
var rect2 = {x: 20, y: 10, width: 10, height: 10}
if (rect1.x < rect2.x + rect2.width &&
   rect1.x + rect1.width > rect2.x &&
   rect1.y < rect2.y + rect2.height &&
   rect1.height + rect1.y > rect2.y) {
    // collision detected!
}
// filling in the values =>
if (5 < 30 &&
    55 > 20 &&
    5 < 20 &&
    55 > 10) {
    // collision detected!
}

Note: You can see a live example of Axis-Aligned Bounding Box collision detection on jsFiddle, to illustrate how this code would work in practice. Here is another example without Canvas or external libraries.

圆形碰撞

两个圆形的碰撞时另一种简单图形的碰撞。这个算法检测当两个圆形的圆心距离小于两个圆形的半径相加。

var circle1 = {radius: 20, x: 5, y: 5};
var circle2 = {radius: 12, x: 10, y: 5};
var dx = circle1.x - circle2.x;
var dy = circle1.y - circle2.y;
var distance = Math.sqrt(dx * dx + dy * dy);
if (distance < circle1.radius + circle2.radius) {
    // collision detected!
}

Note: You can see a live example of Circle collision detection on jsFiddle, to illustrate how this code would work in practice.

Separating Axis Theorem

This is a collision algorithm that can detect a collision between any two *convex* polygons. It's more complicated to implement than the above methods but is more powerful. The complexity of an algorithm like this means we will need to consider performance optimization, covered in the next section.

Implementing SAT is out of scope for this page so see the recommended tutorials below:

Collision Performance

While some of these algorithms for collision detection are simple enough to calculate, it can be a waste of cycles to test *every* entity with every other entity. Usually games will split collision into two phases, broad and narrow.

Broad Phase

Broad phase should give you a list of entities that *could* be colliding. This can be implemented with a spacial data structure that will give you a rough idea of where the entity exists and what exist around it. Some examples of spacial data structures are Quad Trees, R-Trees or a Spacial Hashmap.

Narrow Phase

When you have a small list of entities to check you will want to use a narrow phase algorithm (like the ones listed above) to provide a certain answer as to whether there is a collision or not.