Thursday, November 15, 2007

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?

6 comments:

Lionel said...

mmm...I've done something similar but I don't see why you insert points instead of object.
obviously, the object you insert need to have certain properties (like position) but this seems more handy :

objects_in_same_case = hashmap.query(object)
if not object_in_same_case:
hashmap.insert(object)
else:
object = collide(object, objects_in_same_case)
if object:
hashmap.insert(object)


(the code is verbose on purpose)
(arg...tabulation missing)

Simon Wittber said...

Yeah, the code is pretty useless as it is. The point was merely to demonstrate the concept in Python.

To make it useful, the hashmap must store objects, not points. Lines 21 and 36 need to append an object, not a point! :)

Then the query method will return a list of colliding objects, not just points.

Anonymous said...

you could try either quadtree:
http://pypi.python.org/pypi/Quadtree/
http://trac.gispython.org/projects/PCL/wiki/QuadTree
or Rtree at the same locations. it's used for GIS stuff, but it may work in this scenario.

Nyrath said...

An aquaintance of mine observed that to be perfectly safe, objects near the edge of a cell boundary need to be listed in both cells. An object near a corner could end up in 4 or 8 cells.

david pasquinelli said...

"An aquaintance of mine observed that to be perfectly safe, objects near the edge of a cell boundary need to be listed in both cells. An object near a corner could end up in 4 or 8 cells."

to be perfectly safe, if you're dealing with entities that have volume/area (not points) then you need to account for objects larger then grid cells. these could overlap an arbitrary number of grid cells.

if you're only dealing with points, you don't need to consider border conditions, since points have no volume.

Daniel Waterworth said...

try this, the rects are pygame.Rect compatible.

import math

def pixelise(v, value):
return int(math.floor(v / value))

class SpatialHashMap:
def __init__(self, size):
self.data = {}
self.size = size

#add an object
def add(self, obj):
for x in xrange(pixelise(obj.rect.left, self.size), pixelise(obj.rect.right, self.size)+1):
for y in xrange(pixelise(obj.rect.top, self.size), pixelise(obj.rect.bottom, self.size)+1):
self.data.setdefault((x, y), set()).add(obj)
#remove an object
def remove(self, obj):
for x in xrange(pixelise(obj.rect.left, self.size), pixelise(obj.rect.right, self.size)+1):
for y in xrange(pixelise(obj.rect.top, self.size), pixelise(obj.rect.bottom, self.size)+1):
self.data[(x, y)].remove(obj)
#find all objects that collide with rect
def hits(self, rect):
objs = set()
for x in xrange(pixelise(rect.left, self.size), pixelise(rect.right, self.size)+1):
for y in xrange(pixelise(rect.top, self.size), pixelise(rect.bottom, self.size)+1):
for obj in self.data.get((x, y), []):
if not obj in objs:
objs.add(obj)
if rect.colliderect(obj.rect):
yield obj
# move an object
def move(self, obj, nrect):
self.remove(obj)
obj.rect = nrect
self.add(obj)

Popular Posts