# Why does this implementation of sweep and prune freeze, and how can I fix it?

When I try to implement sweep and prune the aabb and sphere collisions don't collide properly. I have debugged the code and traced the problem to these methods.

AABB and Sphere collisions(The code for both is slightly different)

@Override
public boolean collides(Sphere other) {
//AABB
float dist = sqDistance(other.getCenter(), this);

}

@Override
public boolean collides(AABB other) {
float dist = sqDistance(center, other);

}

public default float sqDistance(Vector3f point,AABB aabb) {
float sqDist = 0.0f;
for( int i = 0; i < 3; i++ ){
// for each axis count any excess distance outside box extents
sqDist += check(point,aabb,i);
}
return sqDist;
}

public default float check(Vector3f point,AABB aabb,float axis) {
float sqDist = 0;
if(axis == 0) {
float v = point.x;

if( v < aabb.getMin().x ) sqDist += (aabb.getMin().x - v) * (aabb.getMin().x - v);
if( v > aabb.getMax().x ) sqDist += (v - aabb.getMax().x) * (v - aabb.getMax().x);
}
if(axis == 1) {
float v = point.y;

if( v < aabb.getMin().y ) sqDist += (aabb.getMin().y - v) * (aabb.getMin().y - v);
if( v > aabb.getMax().y ) sqDist += (v - aabb.getMax().y) * (v - aabb.getMax().y);
}
if(axis == 2) {
float v = point.z;

if( v < aabb.getMin().z) sqDist += (aabb.getMin().z - v) * (aabb.getMin().z - v);
if( v > aabb.getMax().z) sqDist += (v - aabb.getMax().z) * (v - aabb.getMax().z);
}
return sqDist;
}


Could anyone please try and tell me what is wrong with these methods.

• 1. You should generally avoid editing a question in such a way that it's no longer talking about its original topic (ie. your AABB testing loop) - you can ask a new question in these situations. 2. If a question already has an Accepted answer, most users will assume it's solved, and won't click inside to learn that you've actually changed it to a new question. 3. Saying these methods "don't collide properly" doesn't tell us what they do instead. In what specific way is their behaviour "improper"? You've removed all description of the actual problem from the question, making it hard to glean. – DMGregory Apr 1 '18 at 12:10
• @DMGregory the code is hard to debug. The code is just going crazy with the player colliding with random things. – Macky ben Jonah Apr 1 '18 at 12:26
• If you're having a hard time debugging it with the live code in front of you, just imagine how much harder it is for users on the other side of the Internet, who have only your text to go on. Debugging is never easy, but you have to put in the legwork and clearly describe your problem if you want others to be able to help you. Try setting up one controlled test, with two bodies that obviously should collide, but fail to register as colliding (or obviously should not collide, but register as colliding anyway), and describe that scenario in detail. – DMGregory Apr 1 '18 at 12:30
• @DMGregory the strange thing is that my code seems not to care whether the objects are colliding or not. It just reports a collision with every object colliding or not. – Macky ben Jonah Apr 1 '18 at 12:45
• Great, that will make it really easy for you to show us a test case where it fails then! Make a scene with exactly two bodies. One AABB with corners at (0, 0)&(1, 1), and one AABB with corners at (100, 100)&(101, 101). Walk through your code acting on these two bodies, which obviously should not be colliding. If it reports a collision, what happens to lead to that result? Where does your code go wrong? – DMGregory Apr 1 '18 at 12:48

For starters, this doesn't look like sweep and prune. You're checking the whole bounding box in each comparison, rather than doing a series of sweeps filtering each axis. That's fine, comparing a whole bounding box is not a wrong way to do collision detection. Sweep and prune is a particular algorithm though, so for clarity it's best to use that term only when you're referring to that specific technique.

It looks like you're trying to do the following...

1. For each box in my original list

2. Check it against each preceding box in the list

3. If they collide, do something

4. Otherwise, do something else

But your 3. "do something" & 4. "do something else" don't make a lot of sense. You're either adding the next box to your active list (why? The next iteration of the loop will do that anyway) or removing the box you're checking from the list (why? It might still collide with the next box you check in your inner loop)

I think maybe you want something simpler:

for(int collider = 1; collider < axisList.size(); collider++) {

BoundingBox colliderBox = axisList.get(collider);

for(int collidee = 0; collidee < collider; collidee++) {

BoundingBox collideeBox = axisList.get(collidee);

if(colliderBox.collides(collideeBox)) {
System.out.println("COLLISION " + collideeBox + ":" + colliderBox);
// Record the collision here.
}
// No else. We have to keep checking the next collidee
// until there are no further possible collisions.
}
}

// Once we've detected all collisions, now we can act on them,
// by iterating over our collisionList for example.


There. Now we're not modifying a collection while we're traversing it, we just check each box against each box that precedes it in the same collection.

• Still doesn't work. Here is the declaration of the list: private static List<BoundingBox> axisList = new LinkedList<>(); The size of the axisList is 1803 – Macky ben Jonah Mar 30 '18 at 16:24
• "doesn't work" is never enough information to debug a problem. What are the patient's symptoms? – DMGregory Mar 30 '18 at 16:25
• The code still freezes and when I printed out the size of the axisList it was 1803. – Macky ben Jonah Mar 30 '18 at 16:27
• Then step one is to whip out your debugger and walk through the function to find where your infinite loop is. The code in the snippet above doesn't contain an infinite loop: the outer loop can only go through 1803 iterations, and the inner loop can only go through 1802 iterations at max, since we don't add to axisList anywhere. Together that's 1.6 million iterations in total. A big number, but not enough to lock your PC unless your collides method is a major time sink or has side effects. So the infinite loop has to be elsewhere - I'll need to see that info to be able to help. – DMGregory Mar 30 '18 at 16:36