Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
Quick Links
Categories
- 7.8K All Categories
- 11 Help with translations
- 4.2K General questions
- 107 Roadmap
- 358 Game & application design
- 316 Plugins
- 70 User experience
- 75 Marketplace
- 291 Code snippets
- 34 Building a team?
- 269 Suggestions & requests
- 352 Announce your apps made with Gideros.
- 90 Step by step tutorials
- 668 Bugs and issues
- 195 Introduce yourself
- 239 Announcements
- 106 Forum talk
- 404 Relax cafe
Broad-Phase Libs for fast 2D Collision Detection
Roland_Y
Member
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.
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:
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
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 |
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 |
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
Tagged:
+1 -1 (+2 / -0 )Share on Facebook