Is there a way to increase the collision check efficiency of a system of n objects?

I'm making a game that consists of many onscreen objects, one of which is the player. I need to know which objects are colliding every iteration.

``````for (o in objects)
{
o.stuff();
for (other in objects)
if (collision(o, other))
doStuff();

bla.draw();
}
``````

This has O(n^2), which I'm told is bad. How do I do this more efficiently, is it even possible? I'm doing this in Javascript, and n will usually be lower than 30, will it be a problem if this stays the same?

-
Have you tried running the code to see how it performs? – thedaian Feb 21 '12 at 15:42
No, I havent, I'm just asuming it's bad because of the O(n^2). – jcora Feb 21 '12 at 15:47
Only 30 objects? I would have recommended spatial partitioning, but it would be fruitless with only 30 objects. There are some minor optimizations that others have pointed out, but they are all minor optimizations on the scale you are talking about. – John McDonald Feb 21 '12 at 17:50

With only 30 objects max, you shouldn't need much optimization at all other than to not check the same two pairs against each other more than once per frame. Which the code sample below will cover. But if you're interesting in different optimizations that a physics engine would use then continue reading through the rest of this post.

What you will need is a spatial partitioning implementation, such as an Octree (for 3D games) or Quadtree (for 2D games). These partition the world into sub-sections, and then each sub-section is partitioned further in the same manor, until they have subdivided to a minimum size. This allows you to very quickly check which other objects are in the same region of the world as another, which limits the amount of collisions you must check against.

In addition to spatial partitioning I would recommend creating an AABB (Axis-aligned bounding box) for each of your physics objects. This allows you to check the AABB of one object against another, which is much faster than a detailed per-poly check between objects.

This can be taken another step further for complicated or large physics objects, where you can sub-divided the physics mesh itself, giving each sub-shape its own AABB that you can check against only if two object's AABBs are overlapping.

Most physics engines will deactivate active physics simulation on physics bodies once they come to a rest. When a physics body is deactivated, it need only check for collision each frame, and if anything collides with it then it will reactivate. This keeps simulation times down.

Also, many physics engines use 'simulation islands', which is where a group of physics bodies that are close together are grouped together. If everything in the simulation island is at rest then the simulation island itself deactives. The benefit of the simulation island is that all of the bodies inside of it can stop checking for collisions once the island is inactive, and the only check each frame is to see if something entered the AABB of the island. Only once something enters the AABB of the island will each of the bodies within the island need to check for collisions. The simulation island also reactivates if any body inside of it starts to move again on its own. If a body moves far enough from the center of the group, it is removed from the island.

In the end you're left with something like this (in pseudo-code):

``````// Go through each leaf node in the octree. This could be more efficient
// by keeping a list of leaf nodes with objects in it.
for ( node in octreeLeafNodes )
{
// We only need to check for collision if more than one object
// or island is in the bounds of this octree node.
if ( node.numAABBsInBounds > 1)
{
for ( int i = 0; i < AABBNodes.size(); ++i )
{
// Using i+1 here allows us to skip duplicate checks between AABBS
// e.g (If there are 5 bodies, and i = 0, we only check i against
//      indexes 1,2,3,4. Once i = 1, we only check i against indexes
//      2,3,4)
for ( int j = i + 1; j < AABBNodes.size(); ++j )
{
if ( AABBOverlaps( AABBNodes[i], AABBNodes[j] ) )
{
// If the AABB we checked against was a simulation island
// then we now check against the nodes in the simulation island

// Once you find overlaps between two actual object AABBs
// you can now check sub-nodes with each object, if you went
// that far in optimizing physics meshes.
{
}
}
}
}
``````

I would also recommend not having so many loops within loops like this, the above sample was just so you got the idea, I would break it up into multiple functions that give you the same functionality as something like what is shown above.

Also, make sure not to alter the AABBNodes container while looping through it, as that could mean missed collision checks. This may sound like common sense, but you would be surprised how easy it is to have things reacting to collisions cause changes you wouldn't anticipate. For example if a collision caused one of the colliding objects to change position enough to remove them from the AABB of the Octree node you were checking then it could alter that container. To solve this I recommend keeping a list of all collision events that occur during the checks, and then after all checks are complete run through the list and send out any collision events.

-
Very consistent answer with nice and useful technical precisions to open reader mind to existing methods. +1 – Valkea Feb 21 '12 at 16:17

Your example test each pair of objects multiple times.

Let's take a very simple example with an array containing 0,1,2,3

With your code you get this:

• At loop 0 you test against 1, 2 and 3
• At loop 1 you test against 0, 2 and 3 ===> (0-1 already tested)
• At loop 2 you test against 0, 1 and 3 ===> (0-2 / 1-2 already tested)
• At loop 3 you test against 0, 1 and 2 ===> (0-3 / 1-3 / 2-3 already tested)

Now lets see the following code:

``````for(i=0;i<=objects.length;i++)
{
objects[i].stuff();

for(j=i+1;j<=objects.length;j++)
{
if (collision(objects[i], objects[j]))
doStuff();
}

bla.draw();
}
``````

If we use the array containing 0,1,2,3 once again, we have the following behaviour:

• At loop 0 you test against 1, 2, 3
• At loop 1 you test against 2, 3
• At loop 2 you test against 3
• At loop 3 you test against nothing

With the second algorithm we have got 6 collision tests while the previous one asked for 12 collisions tests.

-
This algorithm makes `N(N-1)/2` comparisons which is still O(N^2) performance. – Kai Feb 21 '12 at 16:36
Well with 30 objects as requested that means 465 collisions tests against 870...it's probably similar from your point of view, but not from mine. Furthermore, the solution offered in the other answer is the exactly same algorithm :) – Valkea Feb 21 '12 at 17:14
@Valkea: Well, part of it is. :) – Nic Foster Feb 21 '12 at 18:21
@NicFoster: yes you are right ;) I was speaking strictly about the collision test between the selected objects, not about the partitioning part of the algorithm which is obviously a very valuable addition that I didn't even thought to add in my example when I was writing it. – Valkea Feb 21 '12 at 18:46
Is this called amortization? Anyway, thanks! – jcora Feb 27 '12 at 19:06

Design your algorithm around your needs, but keep the implemetation detail encapsulated. Even in Javascript, basic OOP concepts apply.

For `N =~ 30, O(N*N)` is not a concern, and your linear search is likely to be just as fast as any alternative out there. But you don't want to hard-code assumptions into your code. In pseudocode, you'd have an interface

``````interface itemContainer {
remove(BoundingBox);
BoundingBox[] getIntersections();
}
``````

That describes what your list-of-items can do. Then you can write a ArrayContainer class that implements this interface. In Javascript, the code would look like this:

``````function ArrayContainer() { ... } // this uses an array to store my objects
ArrayContainer.prototype.add = function(box) { ... };
ArrayContainer.prototype.remove = function(box) { ... };
ArrayContainer.prototype.getIntersections = function() { ... };

function QuadTreeContainer { ... } // this uses a quadtree to store my objects
``````

And here is example code that creates 300 bounding boxes and gets all the intersections. If you've implemented ArrayContainer and QuadTreeContainer correctly, the only thing you would need to change in your code is change `var allMyObjects = new ArrayContainer()` to `var allMyObjects = QuadTreeContainer()`.

``````var r = Math.random;
var allMyObjects = new ArrayContainer();
for(var i=0; i<300; i++)
var intersections = allMyObjects.getIntersections();
``````

I went ahead and whipped up the implementation for the standard ArrayContainer here:

http://jsfiddle.net/SKkN5/1/

-
Note: This answer was motivated by Bane's complaint that his codebase was getting too big, messy, and hard to manage. Although it doesn't add much to the discussion on using an Array vs a Tree, I hope it's a relevant answer as how to specifically he could go about organizing his code better. – Jimmy Feb 21 '12 at 21:27

You should also consider the types of objects than can sensibly collide.

For example the player probably needs to be checked for collision with everything except his own bullets. However enemies may only need checking against the player bullets. Bullets almost certainly don't need to collide with each other.

To implement this efficiently you probably want to keep separate lists of objects, one per object type.

-