Broad-Phase Libs for fast 2D Collision Detection

Roland_Y

Hi all,

Collision detection] is a fundamental topic, featured in a wide range of applications, such as computer games, physically-based simulations, etc. Although simple with a few number of entities, it can turn into a bottleneck, especially when dealing with growing numbers of moving objects, and cause some framerate drops.

Suppose that we are rendering 100 objects, and we need to check (each frame) if they are colliding (i.e overlapping) or not. The first common (and naive) approach would be testing each object against others.

for i = 1,100 do for j = 1,100 do if i~=j then collisionTest(object[i], object[j]) end end end

This will result in 9900 collision tests.

A second approach (a bit more clever one) would take advantage of the commutative nature of collisions (i.e A-collides-B equals B-collides-A).

Therefore, the test above should become:

for i = 1,99 do for j = i,100 do collisionTest(object[i], object[j]) end end

What will result in 4950 collision tests.

This is better, but we can still narrow down a lot more the number of required checks using broad-phase collision detection algorithms.
This process identifies groups of objects that are so close enough that they may potentially collide.

Thus, we can perform an effective collision check on those objects to achieve the same result.

Find here some of these algorithms implemented in Lua, with documentation and examples of use.
Hope it helps for your games!

Github repository: Broad-Phase Algorithms