This method is best suited when uniformly or very similarly sized objects are being tracked. If objects do not differ much in size, each cell should be the size of the largest object. This makes it so only the center of each object needs to be tracked.

Example below:

Overlap from shapes in non-adjacent cells is impossible if the cells are as large or larger than every shape tracked. If shapes end up being larger, however, overlap is possible, and we need to track the shape in every grid cell it exists.

If the cells are smaller that the largest object overlap will exist as demonstrated below.

If this happens, we need to track more than just an object’s center (covered below). There are a few ways to solve this: increase the grid size, use another detection system, or track more than just an object’s center. Increasing the grid size can have unexpected consequences.

If the cells are too large, there will be an excess of results in each cell, eliminating efficiency and increasing computation to or towards On^2. As the picture to the left demonstrates. Every object in each cell must be checked against each other for overlap.

Spatial grid tracking can be accomplished using a hash table or a 2/3d array. A 2d array is fairly straightforward. 

My next post will cover creating a hash table, generating a cell’s key (from coordinates), finding neighbors, and detecting overlap. It will be followed by a post on creating bounding shapes to cover objects larger than a grid’s cell size.