Jump to content
  • Advertisement
Sign in to follow this  

Sweep and prune

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

I have been looking at the sweep and prune algorithm and I have tried a basic 1D test to check for collisions. The way I implemented it was by using incremental movements for each set of endpoints. When a max end point crosses a min end point I mark that pair as colliding. The thing I'm not sure about is how to handle when the object moves a distance greater than the distance between the end points of the neighbouring set. Say the objects are 5 units wide but but the objects move by 10 units. How do you handle the case where objects could completely skip over each another like that?

Share this post

Link to post
Share on other sites
The idea behind sweep and prune is to sort the list each frame ! Because most objects moves only short distances, most objects are already at the right list position or near their target list position. In this case a simple bubblesort is extremly efficient (in best case O(N) ).

Don't do any special handling to update your datastructure, just sort the object list after moving all of your objects, don't sort them after just moving one object! After moving some objects your datastructure will not be in order any longer. To handle this, just add the max movement distance to the test interval.

Something like this:

max_movement = 0;
for each obj in objectlist do

// execute collision detection
test_interval = obj.AABB.x + max_movement
collision_candidates = sweepAndPruneTest( test_interval)
... do collision testing, movement, whatever

// update max movement
max_movement += obj.movement


// sort
bubblesort( objectlist)


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!