Collision detection loop == better than O(n^2)?
Author
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
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.
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.
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.
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!
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!
Author
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.
We'll give it a go. Thanks again.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
