If you're sticking in the 2d world, a simple grid partition works really well. Divide you're game world into a 2d grid with buckets at each grid box for holding items which are at least partially in...