Collision Detection and Time Complexity: How do I make checking for collisions easier?

Question

I'm trying to write a program that handles detection of various objects. The objects have an origin, width, height, and velocity. Is there a way to set up a data structure/algorithm so that every object isn't checking with every other object?

Some sample code of the problem I'm trying to avoid:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
       }
    }
}

Answer 1

As mentioned by other answer(s), you can use a quadtree structure to make your collision detection faster.

I would recommend the GEOS open-source C++ library, which has a good quadtree implementation. Here are the docs for their quadtree class.

So your pseudo code would look like this:

Quadtree quadtree;
// Create and populate the quadtree.
// Change it whenever the balls move.

// Here's the intersection loop:
for (int i=0; i<ballCount; ++i) {
    Envelope envelope = ...;  // Get the bounds (envelope) of ball i
    std::vector<void*> possiblyIntersectingBalls;
    quadtree.query(envelope, possiblyIntersectingBalls);
    // Now loop over the members of possiblyIntersectingBalls to check
    // if they really intersect, since quadtree only checks bounding
    // box intersection.
}