Sweep and prune
Author
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?
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
endfor
// sort
bubblesort( objectlist)
--
Ashaman
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
endfor
// sort
bubblesort( objectlist)
--
Ashaman
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
