algorithm - 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.

I made something like this:

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?

Answer

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-divide 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 against its AABB each frame, and if anything collides with the AABB then it then it will reactivate and do a more granular collision check. 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.