I have a 2D world with a positive coordinate system. (0,0) is the top-left of the map and every object has positive co-ordinates.
For example, in the following pixel array, A is the origin at (0,0) and B is an object at (4,3).
0 1 2 3 4 5 6 7 8
0 A - - - - - - - -
1 - - - - - - - - -
2 - - - - - - - - -
3 - - - - B - - - -
4 - - - - - - - - -
5 - - - - - - - - -
6 - - - - - - - - -
Next, each object has an (x,y) position as well as a width and height.
The (x,y) position is the top left of the object and it spans a certain width right and height down.
Let's take B at (4,3) with a width of 3 and a height of 3. Therefore, B occupies the following space on the map:
0 1 2 3 4 5 6 7 8
0 A - - - - - - - -
1 - - - - - - - - -
2 - - - - - - - - -
3 - - - - +---+ - -
4 - - - - | B | - -
5 - - - - +---+ - -
6 - - - - - - - - -
Next, let's assume I can clearly determine if two objects collide.
But there are 5,000 objects. I could easily implement a very naive method such as:
for each object o in world:
for each object j in world:
if o != j and o.collides(j):
print: Collision between o and j!
However, this is clearly an O(n^2) method with a traditional list. If I used a binary search tree or sorted array to store all of the objects, I could reduce this down to O(nlogn) because searching BSTs and sorted arrays is a O(logn) operation.
Is this the absolute best I can do? Is there no better way to do this? Is there a way to maybe reduce the amount of objects B can collide with?
Since B is only 3,3 wide and high, clearly it is confined to only interacting with objects within 3 of its bounds. Could this be the key to limiting the physical objects it might interact with?
Code is not necessary unless you feel very nice. I'm more interested in theory and what my options are. Any discussion is welcome. Thank you!
