Jump to content
  • Advertisement
Sign in to follow this  

Sweep&Prune Variant (please critique)

This topic is 5466 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
Sign in to follow this  

  • Advertisement

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!