Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat | DONATE
Broad-Phase Libs for fast 2D Collision Detection — Gideros Forum

Broad-Phase Libs for fast 2D Collision Detection

Roland_YRoland_Y Member
edited October 2012 in Code snippets
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

Likes: talis, aarefandi

+1 -1 (+2 / -0 )Share on Facebook
Sign In or Register to comment.