Sign in to follow this  

How to organize game objects? Quadtree?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this