Jump to content
  • Advertisement
Sign in to follow this  
leiavoia

Sweep&Prune Variant (please critique)

This topic is 5036 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

SCENARIO: I have a bidirectional 2D world full of objects composed of polygons for collision detection. The actual collision detection part is working well, but is based on a quadtree which i suspect is causing slowdown with large numbers of objects. I need a framework for spatial partitioning that is: - Fast - Has Large numbers of objects (~1000 or less) - Capable of handling any size object. A true quadtree is an expandable/collapsable structure that saves memory over a grid approach, but is not so quick. I am not concerned about memory usage (most PCs have more than they need anyway). POTENTIAL SOLUTION: Organize all objects simultaniously into 4 lists appropriately sorted: Xmins Xmaxes Ymins Ymaxes And "cross bookkeep" to keep the location of objects in those four lists within the object itself for quick access. When i want to know what other objects an object collides with i make a list composed of these criteria: 1) all objects sorted in the "Xmins" list that have an xmax value less than the object's xmin 2) all objects sorted in the "Xmaxes" list that have an xmin value greater than the object's xmax. 3) all objects sorted in the "Ymins" list that have an ymax value less than the object's ymin 4) all objects sorted in the "Ymaxes" list that have an ymin value greater than the object's ymax. For each criteria, i'm basically just travlling up or down the particular list from my current object's location until i hit a value that's outside the objects bounding box, stop, then check the other criteria. When an object moves, it simply bubbles up or down the list (and usually not very far either). This might be simpler than doing a lot of "am i in this node?" bounding box checking like i'm doing now. That's it in a nutshell. I'm not even sure if i'm thinking this out right, so if you can critique or suggest an alternative, i'd appreciate the advice. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!