# How to organize game objects? Quadtree?

This topic is 3933 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi! I'm creating a 2d game engine (and a game) and I've come to the point where I need to cut down on the collision checks being done. Right now, every object is checked against every other object for collision. This is, needless to say, incredible inefficient. So what I was thinking was: I need to divide the objects into smaller partitions. Then the objects within each partition could be checked against the other objects within that partition, considerably reducing the amount of collision checks. But the problem is - how should I do that? Can I use a quad tree for that? In that case, wouldn't that require me to "rebuild" the tree every frame? Though even THAT might be more efficient than what's happening right now. Anyway, if you guys got any tips... I'll be very thankful. :) Regards, Hallgeir

##### Share on other sites
An elementary technique is to project your objects onto an axis (for instance, horizontal) and then sort them from left to right along that axis, based on the leftmost point of their projection. O(n log n) total time for this operation. Then, you can traverse the objects from left-to-right, keeping a current batch of objects sorted based on the rightmost point of their projection, such that this rightmost point is to the right of the leftmost point of the currently considered object. Then, any object can only collide with the objects inside the batch, and the batch itself is a priority queue which is handled in O(log n) per insertion/removal.

##### Share on other sites
Interesting! I will look into this. :)

Thanks!

##### Share on other sites
Since your world is 2d then I'd create a 2d grid and each frame hash each objects x,y coordinates into one of the cells. Then to test an object would require only testing the objects in the cells that the object intersects with.

It is a very easy proximity query as far as implementation goes and it is quite efficient.

##### Share on other sites
For David,

You would have to test neighboring cells up to

ceil(max(width,height)/2/cellsize) away from the intersecting cells, where (width,height) come from the largest object

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633679
• Total Posts
3013300
×