Spatial Data Structure for Games

Question

I need to implement a spatial data structure to store rectangles then be able to find all rectangles that intersect a given rectangle. This will be implemented in JavaScript.

So far I am developing a Quad Tree to cut down the search space but because it is for a game, all objects that move will need to update its position in the tree. Back to square one.

Are there any data-structures or methods to help? It will need to process around 10,000 objects so brute force isn't good enough.

Answer 1

A hash table works fairly well as an approximate intersection test. Hash tables are used as part of a more sophisticated algorithm for detecting collisions in ODE.

Logically, this test divides the space into a regular grid. Each grid cell is labeled with a list of objects that intersect that cell. The grid is initialized by scanning all objects. I don't know javascript, so I'll use python-ish pseudocode.

for each ob in objects:
  for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
    for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
      hashtable[hash(x, y)].append(ob)

To find collisions with a given object, look up near-collisions in the hash table and then apply an exact collision test to each one.

near_collisions = []
for each x in [floor(ob.x_min / grid_size) .. floor(ob.x_max / grid_size)]:
  for each y in [floor(ob.y_min / grid_size) .. floor(ob.y_max / grid_size)]:
    near_collisions = near_collisions ++ hashtable[hash(x, y)]

remove duplicates from near_collisions

for each ob2 in near_collisions:
  if exact_collision_test(ob, ob2):
    do_something