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
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
Therefore, the test above should become:
for i = 1,99 do
for j = i,100 do
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