5

So, after hours of Googling and reading, I've found that the basic process of detecting a collision using SAT is:

for each edge of poly A
    project A and B onto the normal for this edge
    if intervals do not overlap, return false
end for

for each edge of poly B
    project A and B onto the normal for this edge
    if intervals do not overlap, return false
end for

However, as many ways as I try to implement this in code, I just cannot get it to detect the collision. My current code is as follows:

for (unsigned int i = 0; i < asteroids.size(); i++) {
    if (asteroids.valid(i)) {
        asteroids[i]->Update();

        // Player-Asteroid collision detection
        bool collision = true;
        SDL_Rect asteroidBox = asteroids[i]->boundingBox;

        // Bullet-Asteroid collision detection
        for (unsigned int j = 0; j < player.bullets.size(); j++) {
            if (player.bullets.valid(j)) {
                Bullet b = player.bullets[j];

                collision = true;
                if (b.x + (b.w / 2.0f) < asteroidBox.x - (asteroidBox.w / 2.0f)) collision = false;
                if (b.x - (b.w / 2.0f) > asteroidBox.x + (asteroidBox.w / 2.0f)) collision = false;
                if (b.y - (b.h / 2.0f) > asteroidBox.y + (asteroidBox.h / 2.0f)) collision = false;
                if (b.y + (b.h / 2.0f) < asteroidBox.y - (asteroidBox.h / 2.0f)) collision = false;

                if (collision) {
                    bool realCollision = false;

                    float min1, max1, min2, max2;

                    // Create a list of vertices for the bullet
                    CrissCross::Data::LList<Vector2D *> bullVerts;
                    bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y + b.h / 2.0f));
                    bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y - b.h / 2.0f));
                    bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y - b.h / 2.0f));
                    bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y + b.h / 2.0f));
                    // Create a list of vectors of the edges of the bullet and the asteroid
                    CrissCross::Data::LList<Vector2D *> bullEdges;
                    CrissCross::Data::LList<Vector2D *> asteroidEdges;
                    for (int k = 0; k < 4; k++) {
                        int n = (k == 3) ? 0 : k + 1;
                        bullEdges.insert(new Vector2D(bullVerts[k]->x - bullVerts[n]->x,
                                                bullVerts[k]->y - bullVerts[n]->y));
                        asteroidEdges.insert(new Vector2D(asteroids[i]->vertices[k]->x - asteroids[i]->vertices[n]->x,
                                                    asteroids[i]->vertices[k]->y - asteroids[i]->vertices[n]->y));
                    }

                    Vector2D *vectOffset = new Vector2D(asteroids[i]->center.x - b.x, asteroids[i]->center.y - b.y);

                    for (unsigned int k = 0; k < asteroidEdges.size(); k++) {
                        Vector2D *axis = asteroidEdges[k]->getPerpendicular();
                        axis->normalize();
                        min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]);
                        for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) {
                            float test = axis->dotProduct(asteroids[i]->vertices[l]);
                            min1 = (test < min1) ? test : min1;
                            max1 = (test > max1) ? test : max1;
                        }
                        min2 = max2 = axis->dotProduct(bullVerts[0]);
                        for (unsigned int l = 1; l < bullVerts.size(); l++) {
                            float test = axis->dotProduct(bullVerts[l]);
                            min2 = (test < min2) ? test : min2;
                            max2 = (test > max2) ? test : max2;
                        }
                        float offset = axis->dotProduct(vectOffset);
                        min1 += offset;
                        max1 += offset;
                        delete axis; axis = NULL;
                        float d0 = min1 - max2;
                        float d1 = min2 - max1;
                        if ( d0 > 0 || d1 > 0 ) {
                            realCollision = false;
                            break;
                        } else {
                            realCollision = true;
                        }
                    }

                    if (realCollision) {
                        for (unsigned int k = 0; k < bullEdges.size(); k++) {
                            Vector2D *axis = bullEdges[k]->getPerpendicular();
                            axis->normalize();
                            min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]);
                            for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) {
                                float test = axis->dotProduct(asteroids[i]->vertices[l]);
                                min1 = (test < min1) ? test : min1;
                                max1 = (test > max1) ? test : max1;
                            }
                            min2 = max2 = axis->dotProduct(bullVerts[0]);
                            for (unsigned int l = 1; l < bullVerts.size(); l++) {
                                float test = axis->dotProduct(bullVerts[l]);
                                min2 = (test < min2) ? test : min2;
                                max2 = (test > max2) ? test : max2;
                            }
                            float offset = axis->dotProduct(vectOffset);
                            min1 += offset;
                            max1 += offset;
                            delete axis; axis = NULL;
                            float d0 = min1 - max2;
                            float d1 = min2 - max1;
                            if ( d0 > 0 || d1 > 0 ) {
                                realCollision = false;
                                break;
                            } else {
                                realCollision = true;
                            }
                        }
                    }
                    if (realCollision) {
                        player.bullets.remove(j);

                        int numAsteroids;
                        float newDegree;
                        srand ( j + asteroidBox.x );
                        if ( asteroids[i]->degree == 90.0f ) {
                            if ( rand() % 2 == 1 ) {
                                numAsteroids = 3;
                                newDegree = 30.0f;
                            } else {
                                numAsteroids = 2;
                                newDegree = 45.0f;
                            }
                            for ( int k = 0; k < numAsteroids; k++)
                                asteroids.insert(new Asteroid(asteroidBox.x + (10 * k), asteroidBox.y + (10 * k), newDegree));
                        }
                        delete asteroids[i];
                        asteroids.remove(i);
                    }
                    while (bullVerts.size()) {
                        delete bullVerts[0];
                        bullVerts.remove(0);
                    }
                    while (bullEdges.size()) {
                        delete bullEdges[0];
                        bullEdges.remove(0);
                    }
                    while (asteroidEdges.size()) {
                        delete asteroidEdges[0];
                        asteroidEdges.remove(0);
                    }

                    delete vectOffset; vectOffset = NULL;
                }
            }
        }
    }
}

bullEdges is a list of vectors of the edges of a bullet, asteroidEdges is similar, and bullVerts and asteroids[i].vertices are, obviously, lists of vectors of each vertex for the respective bullet or asteroid.

Honestly, I'm not looking for code corrections, just a fresh set of eyes.

3
  • What exactly is the problem? Is realCollision always coming out false? Is your bounding box test working? I don't see anything obvious, you should separate the collision detection out into a separate method so you can unit test it. Commented Jun 1, 2010 at 2:31
  • Bounding box collision works, but realCollision almost always ends up false.
    – Eddie
    Commented Jun 1, 2010 at 2:34
  • Updated with the latest code, read yet another article and followed it to the point.
    – Eddie
    Commented Jun 1, 2010 at 2:38

5 Answers 5

2

Turns out my mathematical understanding of the theorem was perfectly fine. Instead, the problem lay in the fact that I was not including the center points of the polygons in the vertice vectors.

Thank you everyone for their time.

0

You've added this vectOffset part which is wrong - both your asteroids' and bullets' coordinate systems are the same, right? (It must be, if the bounding box test is working.)

Are your asteroids squares? If so, then the bounding box test will always be exact, and realCollision and collision should always be identical. If not, then you're not building asteroidEdges properly - you need to iterate over the number of vertices, not 4.

But seriously, make this code a separate method and write a unit test for it, it's the only way I can run your code to see what is going on.

1
  • The asteroids are all 4 vertices, but not squares.
    – Eddie
    Commented Jun 1, 2010 at 3:30
0

bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y + b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x - b.w / 2.0f, b.y - b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y - b.h / 2.0f)); bullVerts.insert(new Vector2D(b.x + b.w / 2.0f, b.y + b.h / 2.0f));

It looks like you're creating an asteroids clone, in which case you'd expect the bullet to be rotated, but this code always treats the bullet as though it is fully upright. Could that be your problem?

4
  • I hadn't thought of that, I'll see what I can do.
    – Eddie
    Commented Jun 1, 2010 at 3:30
  • Scratch that, the bullets are never rotated.
    – Eddie
    Commented Jun 1, 2010 at 3:33
  • hmm, in that case I can't find anything wrong with your code, other than that I (like Keith) don't understand what vectOffset is supposed to do. Have you tried commenting out the float offset = ... line and the two lines after that? Commented Jun 1, 2010 at 4:41
  • I've since removed the offset, and it does nothing. This is a project due today, so there really isn't much else I can do from this point. Luckily it's a 10th grade trig class and not a class of programmers who will notice the difference in collision detection (really, I just need to explain the theorem, but showing it would have been nice too).
    – Eddie
    Commented Jun 1, 2010 at 9:54
0

Something that may help find the problem is to make the bullet a point. It might illuminate problems with other parts of your code. Plus, then if your point makes a collision but the bullet does not you will get something concrete to look at.

In other words, simplify your problem until a solution emerges. ;)

0
0

Besides the whole offset thing, which is buggy, the rest of the algorithm seems OK. Have you tried tracing through it to spot the problem?

BTW, there are several stylistic quirks that make the code hard to read at a glance:

  • Why the pointers everywhere, instead of allocating all of those temporary Vector2Ds on the stack?
  • Why CrissCross::Data::LList instead of "good old" std::vector?
  • Surely Vector2D has an overloaded operator-?

Here's a quick-and-dirty self-contained implementation of the algorithm. I've somewhat tested it, but make no guarantees:

#include <vector>
#include <limits>

using namespace std;

class Vector2D
{
public:
  Vector2D() : x(0), y(0) {}
  Vector2D(double x, double y) : x(x), y(y) {}

  Vector2D operator-(const Vector2D &other) const
  {
    return Vector2D(x - other.x, y - other.y);
  }

  double dot(const Vector2D &other) const
  {
    return x * other.x + y*other.y;
  }

  Vector2D perp() const
  {
    return Vector2D(-y, x);
  }

  double x,y;
};

bool checkCollisionOneSided(vector<Vector2D> &object1, vector<Vector2D> &object2)
{
  int nume = object1.size();
  for(int i=0; i<nume; i++)
    {
      Vector2D edge = object1[(i+1)%nume] - object1[i];
      Vector2D normal = edge.perp();

      double min1 = numeric_limits<double>::infinity();
      double min2 = min1;
      double max1 = -numeric_limits<double>::infinity();
      double max2 = max1;

      for(int j=0; j<object1.size(); j++)
    {
      double dot = normal.dot(object1[j]);
      min1 = std::min(min1, dot);
      max1 = std::max(max1, dot);
    }
      for(int j=0; j<object2.size(); j++)
    {
      double dot = normal.dot(object2[j]);
      min2 = std::min(min2, dot);
      max2 = std::max(max2, dot);
    }

      if(min2 > max1 || min1 > max2)
    return false;
    }
  return true;
}

bool isColliding(vector<Vector2D> &object1, vector<Vector2D> &object2)
{
  return checkCollisionOneSided(object1, object2) && checkCollisionOneSided(object2, object1);
}
6
  • Is object1 a vector of vertices or edges?
    – Eddie
    Commented Jun 1, 2010 at 22:03
  • Vertices. From it the edges are constructed by subtracting consecutive vertices (Vector2D edge = object1[(i+1)%nume] - object1[i];)
    – user168715
    Commented Jun 1, 2010 at 22:05
  • Also, in case it wasn't clear, the final method to use is isColliding, by passing it two lists of vertices (in your case, four vertices each). checkCollisionOneSided is just a helper method.
    – user168715
    Commented Jun 1, 2010 at 22:06
  • Yep, looks like it. I basically reimplemented youe code, but in a way that is self-contained so that I could compile & test it. You could try calling both my code and your code from within your game, and comparing answers; if they disagree for a certain input, you have a concrete test case you can check by hand. If they both agree and the game is still buggy, you might look into the bug being in other code (e.g. the bounding boxes or centers are not being computed correctly.)
    – user168715
    Commented Jun 1, 2010 at 22:13
  • Yeah, I'm in the process of adding your functions now.
    – Eddie
    Commented Jun 1, 2010 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.