← All articles

Broad and narrow phase collision detection systems

If you don’t know about the big O notation, I recommend you read about it here first. This post gives you an idea of what broad and narrow phase algorithms are and how they are used in physics engines.

Broad phase collision detection#

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using an O(n^2) algorithm, but when you add more and more objects to the simulator it becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the number of tests by implementing a broad phase into our collision system. It is responsible for eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

Spatial Hash - More info - O(n log(n)) algorithm

If I remember correctly they can be O(1) in the best case and O(n^2) in the worst case.

It is important to remember that the broad phase only keeps track of the distance between objects. If they are close enough to create a potential collision, the objects are paired. To determine if two objects are close enough to create a collision, we use something called an AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that encapsulates the whole object. It is cheaper to test box vs. box instead of a lot of polygons vs. polygon.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow phase collision detection#

Once the broad phase collider has done its job, we are left with a couple of pairs that need further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.

We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the pink dot marks a contact point.

There are also a few different narrow phase algorithms. Two examples of such algorithms are listed here:

SAT (Separate Axis Theorem) - More info

Distance Grid - More info

More in Game Development

All 26 Game Development articles →