Collision Detection With Spatial Grid Partitioning

mgcadmin 11-10-2026

Lets say you are running a simulation of a bunch of rubber balls thrown into a room. Upon hitting a wall, the ball should "bounce" i.e., reverse direction and possibly it's heading. This is simple enough to do so long as the ball object knows the dimensions of the room object within which it's "bouncing". But what about having more than one ball? Surely they should react to eachother... How can we have the balls react to not only the walls of the room or stationary obstacles, but also other moving objects?

Todays post I'm going to talk about some elementary collision detection methods which are applicable to many areas of software development. This technique shows up in game development, graphics processing, GIS, and even some less obvious uses, like multi-dimensional range searching. Lets get to it.

The Naiive Approach

When it comes to collision detection the simplest method, and the one that most people probably think of first is to just iterate over the container holding the ball objects, and test to see if the x/y coordinates are the same as (or close enough to) another entities coordinates, we consider the two entities to have collided. This leads us to the following quadrartic algorithm:

         for (int i = 0; i < flock.size()-1; i++) {
                for (int j = i+1; j < flock.size(); j++) {
                    float dx = flock[i].getX() - flock[j].getX();
                    float dy = flock[i].getY() - flock[j].getY();
                    if ((std::abs(dx) + std::abs(dy)) < 2) {
                        flock[i].reflect();
                        flock[j].reflect();
                    }
                }
            }

Depending on the number of entities this may well be "good enough". If you want to be able to have hundreds or thousands of balls bouncing at the same time we're going to need something a bit more efficient. There are a few data structures which can help us with this task, the simplest being something called...

Spatial Grid Partitioning

Spatial Grid Partitioning works by erm, parititoning our grid. Say you have a map that is 100 units wide by 50 units tall, and each space on our map is one unit. This creates our "base map tiling" to create our x/y coordinate system. We're then going to create a second grid which breaks down our base map into individual sections, like so:

Now when we test for collisions, instead of testing each entity against every entity, no matter where they are on the map, as we did above, we only test for collisions with entities that we know are already close to us, which we can do with help of a fairly simple data structure.

constexpr int maxG = 10;

class PartitionGrid {
    private:
        struct node {
            int id;
            float x, y;
            node* next;
            node(int i, float X, float Y, node* n) : id(i), x(X), y(Y), next(n) { }
        };
        node* grid[maxG][maxG];
        int size;
    public:
        PartitionGrid();
        void insert(int id, float x, float y);
        vector<int> check(int id, float x, float y, int r);
};

We initialize the grid so that each partition is the head of a linked list.

PartitionGrid() {
    for (int i = 0; i < maxG; i++)
          for (int j = 0; j < maxG; j++)
               grid[i][j] = nullptr;
      size = maxG;
}

In effect, this data structure is an adaptation of an open chaining hash table, where we hash x/y coodinates to grouped buckets. To find which bucket to add a point to, we just divide the x coordinate and y coordinate by the number of buckets. You can play around with the size of the buckets to see what works best for your use case.

       void insert(int id, float x, float y) {
            int px = x/size;
            int py = y/size;
            grid[py][px] = new node(id, x, y, grid[py][px]);
        }

To get a list of points that fall within R-spaces of a central x/y coordinate the following method creates a "bounding box" centered around the point in question. We then use the coordinates of the bounding box to index into the correct partitions buckets. If any of our partitions contain a point that falls inside the boundary of that box, we add it to the result list.

        vector<int> check(int id, float x, float y, int r) {
            int x1 = x-r, y1 = y-r, x2 = x+r, y2 = y+r;
            vector<int> result;
            for (int i = x1/size; i <= x2/size; i++) {
                for (int j = y1/size; j <= y2/size; j++) {
                    for (node* it = grid[j][i]; it != nullptr; it = it->next) {
                        if (it->x >= x1 && it->x <= x2 && it->y >= y1 && it->y <= y2) {
                            result.push_back(it->id);
                        }
                    } 
                }
            }
            return result;
        }

Using this data structure we now have everything we need to reduce our collision detection algorithm from O(n^2) to O(n), lets see how.

The Linear Solution

To check if we have a collision, we do a preprocessing step where we populate the partitions by inserting our points. Once built we iterate over the container of entities and use the current entities position as the centering coordinates for the bounding box check method. 

The size of the bounding box will be the same dimensions as our entity, so if any points are returned as falling inside that box, than our entities have collided.

            PartitionGrid range;
            for (int i = 0; i < flock.size(); i++) {
                range.insert(i, flock[i].getX(), flock[i].getY());
            }
            for (int i = 0; i < flock.size(); i++) {
                vector<int> result = range.check(i, flock[i].getX(), flock[i].getY(), 1);
                if (!result.empty()) {
                    flock[i].reflect();
                    for (auto r : result) {
                        flock[r].reflect();
                    }
                }
            }

Using this method we can now scale to thousands of entities without worrying about our collision detection system becoming a performance bottoleneck. Anyway, thats what I got for today, until next time Happy Hacking!

---