How to organize game objects? Quadtree?
Author
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
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.
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.
It is a very easy proximity query as far as implementation goes and it is quite efficient.
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
