Collision Detection With Spatial Hash Maps

What spatial hash maps are can be summarized as follows.

Spatial hash maps are a process by which the distribution of objects in a 3D or 2D space is projected onto a 1D hash table.

What Do You Need It For?

As the title suggests, spatial hash maps are a simple and efficient solution for detecting collisions between large numbers of objects.

To check whether any given object in space collides with others, a common brute-force approach is to calculate the distance to every other object in the space and return the objects whose distance falls below a set threshold. If you now need to compute collisions for all n objects per frame, the cost per frame would be O(n2). With every additional object, the cost grows exponentially.

This approach is particularly unsuitable for use cases like RTS games, where large numbers of units need to be handled. This is where spatial hash maps come into play.

The Basic Principle

Imagine a 2D space—100 x 100 units—where each cell is 25 units wide. The size of the cells essentially defines our resolution for collision detection.

If you number these cells from top-left to bottom-right and sort the objects into these cells, they can be represented as a one-dimensional list. This makes it clear that checking whether objects collide can be done quickly. Objects in cell 2 can never collide with objects in cell 4. Checking for a collision would therefore have a cost of O(1).

The one-dimensional list and inserting objects into it is the core aspect of spatial hash maps. An object's 2D coordinates are mapped to an index in the hash map using a hash function, and inserted accordingly. Unlike conventional hash sets, where entries are deliberately spread across the list, spatial hash maps try to preserve the spatial aspect and maintain spatial proximity.

Area-Wide Collision

But what happens when objects enter the space that are larger than one unit? In that case, an object could end up in two cells at the same time.

To account for this case, the four points of the bounding box must be taken into consideration. The bounding box can take any geometric shape. In this case, let's assume it's a square. Here, the hash value would be calculated for each of the four corner points, and the object would be written into each of those cells, provided it wasn't already stored there.

This approach doesn't work, however, if the object grows larger than a single cell. In that case, for a square bounding box, an interpolated midpoint on each edge, plus a center point, would need to be taken into account. That would ensure the object can't "span" an entire cell.

Unit Movement

What's interesting when comparing the cost of the brute-force approach and spatial hash maps is that we haven't yet talked about updating unit positions. Here, the cost for the brute-force approach would be 0, since no data structure exists that's used for collision detection. Units move around without affecting the calculation itself. The cost of updating the spatial hash map to reflect unit movement is O(n). For every unit, the hash values need to be recalculated and the cells refilled.

In summary, the overall cost of a spatial hash map would still be far more efficient, even though updating it is comparatively more expensive.