Jump to content
  • Advertisement
Sign in to follow this  
Verg

Collision detection loop == better than O(n^2)?

This topic is 3552 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm trying to implement a more efficient 2D collision detection routine... Right now, the routine isn't scalable, meaning that for every sprite I add, you have to add as many collision detection "if/thens" as you have sprites. In other words, there's a collision detection loop that checks each sprite against every other sprite... resulting in O(n^2) complexity. I'm wondering if there's a way to implement a simple event-based collision detection that simply fires an event when two sprites collide. Thanks

Share this post


Link to post
Share on other sites
Advertisement
Look up space partitioning. That way you'll have to check an object for collisions with other objects in its vicinity rather than all objects.

Share this post


Link to post
Share on other sites
You're going to want to look into quadtrees, or some other sort of spacial segmentation method.

The only way to see if a sprite collided with another sprite is a test. But, if a sprite in one area doesn't collide with a given area, then it won't collide with any sprites in that area.

Another handy thing can be to keep lists of nearby objects. Update the list every time an object moves from one segmentation to the next. This way you have quick easy access to all potential collision targets.

Share this post


Link to post
Share on other sites
You also don't need to do collisions between objects which are both not moving. You can have a "sleeping" flag and set it for anything which hasn't moved in a couple of ticks.

And if you aren't already, you should only collide each shape with the shapes "after" it in the list. That way, you get n2/2 rather than just n2. Of course, this is still O(n2) time, but it does reduce the collisions in half for almost no work!

Share this post


Link to post
Share on other sites
Thanks guys. Sounds like it's exactly what we need, unless there's a way to fire an asynchronous event when two textures overlap (which would probably need to be implemented somehow in the hardware).

We'll give it a go. Thanks again.

Share this post


Link to post
Share on other sites
You don't need to generate collision events for objects you're not interested in. For example, I doubt you want a smoke sprite to send collision events when it overlaps a background element. To do this, you'd need some kind of table of object pairs to check, and only test those objects for overlap. Something like "Bullet" and "Enemy" would be in this table, because you're interested in those collisions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!