I need an effective way to test for collisions between many objects. I'm making a particle simulator and need to test for collisions between all the particles. I have a method that takes each object and compares it to every other objects frame to see if they collide, but once there are several hundred particles the program runs noticeably slower. I'm wondering if there is a more effective way to test for collisions.
Got a tip for us?
Let us know
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
iOS Collision Testing
- Thread starter xcodeNewbie
- Start date
- Sort by reaction score
I'm making a platforming game and posted the same issue a few days ago.
The suggestions I got:
- Use C-Arrays rather than NSArrays to improve speed.
- Use CGRectIntersectsRect(rect1, rect2) to detect collisions.
Granted, my program is only dealing with 2D objects. Also, so far i've only tested it with 10 objects or so, so I'm not sure how fast it'll be able to go when I have several dozen objects...
The suggestions I got:
- Use C-Arrays rather than NSArrays to improve speed.
- Use CGRectIntersectsRect(rect1, rect2) to detect collisions.
Granted, my program is only dealing with 2D objects. Also, so far i've only tested it with 10 objects or so, so I'm not sure how fast it'll be able to go when I have several dozen objects...
The typical way to improve collision-detection time is to adopt a space partitioning scheme.
http://en.wikipedia.org/wiki/Space_partitioning
This is not always a simple thing to do, although the concept behind it is simple.
Basically, you divide the space into two (or more) parts. For example, in a 2D space, you can draw a vertical line down the middle. Now, in order to check for collisions, you only need to check the objects in the left half against other objects in the left half. Same for the right half. This works because there is no possible way for one object to be in the left half and the right half at the same time. In short, nothing in the left half can possibly collide with anything in the right half, and vice versa, so checking for possible collisions is unnecessary: the answer will always be No.
The basic concept can be applied recursively. That is, each half-space can itself be divided in half. And so on, until you reach some practical limit, such as having more sub-spaces than pixels.
While simple in concept, however, the practical aspects get complicated quickly.
First, moving objects can move between subspaces. So an object that started in the left half can end up in the right half. This can happen at any point in time, if the velocity and trajectory of an object are sufficient.
Second, any object that isn't a particle of zero size can overlap a boundary, residing partly in one half and partly in the other half.
Third, any object (even infinitesimal particles) can lie exactly on the boundary between partitions. Objects exactly on the boundary can be adjacent to objects in either space, which means you have to check both subspaces for collisions or other object interactions.
Fourth, if all (or most) objects end up in only one of the halves, then you haven't gained anything. So keeping the subspaces balanced is part of what must be done to manage performance, given the dynamics of the moving objects.
http://en.wikipedia.org/wiki/Space_partitioning
This is not always a simple thing to do, although the concept behind it is simple.
Basically, you divide the space into two (or more) parts. For example, in a 2D space, you can draw a vertical line down the middle. Now, in order to check for collisions, you only need to check the objects in the left half against other objects in the left half. Same for the right half. This works because there is no possible way for one object to be in the left half and the right half at the same time. In short, nothing in the left half can possibly collide with anything in the right half, and vice versa, so checking for possible collisions is unnecessary: the answer will always be No.
The basic concept can be applied recursively. That is, each half-space can itself be divided in half. And so on, until you reach some practical limit, such as having more sub-spaces than pixels.
While simple in concept, however, the practical aspects get complicated quickly.
First, moving objects can move between subspaces. So an object that started in the left half can end up in the right half. This can happen at any point in time, if the velocity and trajectory of an object are sufficient.
Second, any object that isn't a particle of zero size can overlap a boundary, residing partly in one half and partly in the other half.
Third, any object (even infinitesimal particles) can lie exactly on the boundary between partitions. Objects exactly on the boundary can be adjacent to objects in either space, which means you have to check both subspaces for collisions or other object interactions.
Fourth, if all (or most) objects end up in only one of the halves, then you haven't gained anything. So keeping the subspaces balanced is part of what must be done to manage performance, given the dynamics of the moving objects.
For implementation examples and details try googling Quad Tree Spatial Indexing, I think this will help alot.
Another thing you can do is hit caching. Basically if object 1 collides with object 3. The next time you check for a collison, check object 1 against object 3 first. The idea being that if object 1 has collided with object 3, then the next time around it will be more likely to collide with object 3 than another object. (Of course this depends on how your objects behave, but it is something worth considering).
Lastly, there are a lot of smart people that have thought about this.. have you considered just using a third party physics engine like Chipmunk or Box2D if your objects are moving a 2D space. I don't know of any 3D physics engines but there must be some.