Spatial Hashing

Often, when building a game, you need to test if objects are colliding. The objects could be spaceships, rocks, mouse pointers, laser beams... whatever. The simple approach is to iterate over all your objects, and test if they collide with a specific point.

If you do this using a linear algorithm, you'll quickly find that as you get more and more objects, your collision detection code will slow down at the same rate.

To get around this, you can test against a smaller set of objects, by using a spatial index. A spatial index (in this example, a Spatial Hash / Hash Map) stores all object positions, and can quickly tell you what objects _might_ be colliding in a certain area. You can then iterate through this smaller list, testing for exact collisions if needed. This is called a broad phase collision detection strategy.

from math import floor

class HashMap(object):
    """
    Hashmap is a a spatial index which can be used for a broad-phase
    collision detection strategy.
    """
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.grid = {}

    @classmethod
    def from_points(cls, cell_size, points):
        """
        Build a HashMap from a list of points.
        """
        hashmap = cls(cell_size)
        setdefault = hashmap.grid.setdefault
        key = hashmap.key
        for point in points:
            setdefault(key(point),[]).append(point)
        return hashmap

    def key(self, point):
        cell_size = self.cell_size
        return (
            int((floor(point[0]/cell_size))*cell_size),
            int((floor(point[1]/cell_size))*cell_size),
            int((floor(point[2]/cell_size))*cell_size)
        )

    def insert(self, point):
        """
        Insert point into the hashmap.
        """
        self.grid.setdefault(self.key(point), []).append(point)
   
    def query(self, point):
        """
        Return all objects in the cell specified by point.
        """
        return self.grid.setdefault(self.key(point), [])

The above class implements a spatial hash. A simple way of putting it is: "we store these points in a grid, and you can retrieve an entire grid cell with its points."

if __name__ == '__main__':

    from random import uniform
    from time import time

    NUM_POINTS = 100000
    new_point = lambda: (
        uniform(-100,100),uniform(-100,100),uniform(-100,100)
    )

    points = [new_point() for i in xrange(NUM_POINTS)]
    T = time()
    hashmap = HashMap.from_points(10, points)
    print 1.0 / (time() - T), '%d point builds per second.' % NUM_POINTS

    T = time()
    hashmap.query((0,0,0))
    print 1.0 / (time() - T), '%d point queries per second.' % NUM_POINTS

This example inserts 10000 points into the hashmap, using a cell size of 10. This means, when we query point (0,0,0), we retrieve all points in the cube defined by (0,0,0),(10,10,10).

On my machine, I can build a 10000 point hashmap 2.7 times per second, and query it 70000 times per second. This makes it great for colliding static points, but not so great for colliding moving points. I imagine the from_points method could be improved somewhat. Any suggestions?