Sporadic collision detection

Question

I worked on detecting a collision between an object in my game. Right now, everything is tabulating vertically, but I would like to leave the option for open movement. This is a classic 2nd vertical space shooter.

Right now I am looking at every object, checking for conflicts:

for(std::list<Object*>::iterator iter = mObjectList.begin(); iter != mObjectList.end();) { Object *m = (*iter); for(std::list<Object*>::iterator innerIter = ++iter; innerIter != mObjectList.end(); innerIter++ ) { Object *s = (*innerIter); if(m->getType() == s->getType()) { break; } if(m->checkCollision(s)) { m->onCollision(s); s->onCollision(m); } } } 

Here's how I check for a collision:

 bool checkCollision(Object *other) { float radius = mDiameter / 2.f; float theirRadius = other->getDiameter() / 2.f; Vector<float> ourMidPoint = getAbsoluteMidPoint(); Vector<float> theirMidPoint = other->getAbsoluteMidPoint(); // If the other object is in between our path on the y axis if(std::min(getAbsoluteMidPoint().y - radius, getPreviousAbsoluteMidPoint().y - radius) <= theirMidPoint.y && theirMidPoint.y <= std::max(getAbsoluteMidPoint().y + radius, getPreviousAbsoluteMidPoint().y + radius)) { // Get the distance between the midpoints on the x axis float xd = abs(ourMidPoint.x - theirMidPoint.x); // If the distance between the two midpoints // is greater than both of their radii together // then they are too far away to collide if(xd > radius+theirRadius) { return false; } else { return true; } } return false; } 

The problem is that it will randomly detect collisions correctly, but in other cases it will not detect it at all. This is not an if statement breaking away from the object loop because the objects are of different types. The closer the subject is to the top of the screen, the better the chance of collision detection. The closer to the bottom of the screen, the less likely it will be detected correctly or even at all. However, these situations do not always occur. The diameter for the objects is massive (10 and 20) to see if this was a problem, but it doesn’t help much.

EDIT - Updated Code

 bool checkCollision(Object *other) { float radius = mDiameter / 2.f; float theirRadius = other->getDiameter() / 2.f; Vector<float> ourMidPoint = getAbsoluteMidPoint(); Vector<float> theirMidPoint = other->getAbsoluteMidPoint(); // Find the distance between the two points from the center of the object float a = theirMidPoint.x - ourMidPoint.x; float b = theirMidPoint.y - ourMidPoint.y; // Find the hypotenues double c = (a*a)+(b*b); double radii = pow(radius+theirRadius, 2.f); // If the distance between the points is less than or equal to the radius // then the circles intersect if(c <= radii*radii) { return true; } else { return false; } } 

Answer 1

This logic is incorrect:

 if(std::min(getAbsoluteMidPoint().y - radius, getPreviousAbsoluteMidPoint().y - radius) <= theirMidPoint.y && theirMidPoint.y <= std::max(getAbsoluteMidPoint().y + radius, getPreviousAbsoluteMidPoint().y + radius)) { // then a collision is possible, check x } 

(The logic inside the curly braces is also incorrect, but this should lead to false positives and not false negatives.) Checking whether a collision occurred during the time interval can be difficult; Currently, I propose checking the collision and getting it to work in the first place. When you check for a collision (now), you cannot check x and y independently, you should look at the distance between the object centers.

EDIT:

The edited code is still not quite right.

 // Find the hypotenues double c = (a*a)+(b*b); // actual hypotenuse squared double radii = pow(radius+theirRadius, 2.f); // critical hypotenuse squared if(c <= radii*radii) { // now you compare a distance^2 to a distance^4 return true; // collision } 

It should be as follows:

 double c2 = (a*a)+(b*b); // actual hypotenuse squared double r2 = pow(radius+theirRadius, 2.f); // critical hypotenuse squared if(c2 <= r2) { return true; // collision } 

or that:

 double c2 = (a*a)+(b*b); // actual hypotenuse squared double c = pow(c2, 0.5); // actual hypotenuse double r = radius + theirRadius; // critical hypotenuse if(c <= r) { return true; // collision } 

Answer 2

Two circular objects collide when the distance between their centers is small enough. You can use the following code to check this:

 double distanceSquared = pow(ourMidPoint.x - theirMidPoint.x, 2.0) + pow(ourMidPoint.x - theirMidPoint.x, 2.0); bool haveCollided = (distanceSquared <= pow(radius + theirRadius, 2.0)); 

To check if a collision has occurred between two points in time, you can check for a collision at the beginning of the time interval and at the end of it; however, if objects move very fast, collision detection may fail (I think you ran into this problem for falling objects at the fastest speed at the bottom of the screen).

The following may make collision detection more reliable (although still not ideal). Suppose objects move at a constant speed; then their position is a linear function of time:

 our_x(t) = our_x0 + our_vx * t; our_y(t) = our_y0 + our_vy * t; their_x(t) = their_x0 + their_vx * t; their_y(t) = their_y0 + their_vy * t; 

Now you can define the (square) distance between them as a quadratic function of time. Find at what time it takes its minimum value (i.e., its derivative is 0); if this time belongs to the current time interval, calculate the minimum value and check it for a collision.

That should be enough to detect collisions almost perfectly; if your application works hard with freely falling objects, you may need to clarify the motion functions that will be quadratic:

 our_x(t) = our_x0 + our_v0x * t; our_y(t) = our_y0 + our_v0y * t + g/2 * t^2; 

Answer 3

Your inner loop should start with mObjectList.begin () instead of iter.

The inner loop should go through the whole list, otherwise you will miss the collision candidates, the further you advance in the outer loop.