bei der Implementierung Kollisionserkennung mit Hilfe der Vereinzeler Achse Satz

Question

So Brauchen Sie Hilfe, nach Stunden Googeln und Lesen, ich habe festgestellt, dass der grundlegende Prozess eine Kollision des Erfassens SAT verwendet, ist:

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 

Da jedoch viele Wenn ich versuche, dies im Code zu implementieren, kann ich die Kollision nicht erkennen. Mein aktueller Code ist wie folgt:

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 eine Liste von Vektoren der Ränder einer Kugel ist, asteroidEdges ist ähnlich, und bullVerts und Asteroiden [i] .vertices sind, offensichtlich, Listen von Vektoren jeden Scheitel für die jeweilige Kugel oder den Asteroiden.

Ehrlich, ich bin nicht auf der Suche nach Code-Korrekturen, nur ein frischer Satz von Augen.

Answer 1

Stellt sich heraus mein mathematisches Verständnis des Theorems war völlig in Ordnung.Das Problem lag vielmehr darin, dass ich die Mittelpunkte der Polygone in den Verticevektoren nicht einbezog.

Vielen Dank für ihre Zeit.

Answer 2

Sie haben diesen vectOffset Teil hinzugefügt, der falsch ist - sowohl die Koordinatensysteme Ihrer Asteroiden als auch Ihre Kugeln sind gleich, oder? (Es muss sein, wenn der Bounding-Box-Test funktioniert.)

Sind Ihre Asteroiden Quadrate? Wenn ja, dann ist der Bounding-Box-Test immer genau und realCollision und collision sollten immer identisch sein. Wenn nicht, dann erstellen Sie asteroidEdges nicht richtig - Sie müssen über die Anzahl der Scheitelpunkte iterieren, nicht 4.

Aber im Ernst, machen Sie diesen Code eine separate Methode und schreiben Sie einen Komponententest dafür, es ist der einzige Weg Ich kann deinen Code ausführen, um zu sehen, was passiert.

Answer 3

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));

Es sieht aus wie Sie einen Asteroiden Klon erstellen, in dem Fall, dass Sie die Kugel gedreht werden erwarten würde, aber dieser Code immer behandelt die Kugel, als ob es gerade steht. Könnte das dein Problem sein?

Answer 4

Etwas, das helfen könnte, das Problem zu finden, ist, die Kugel einen Punkt zu machen. Es könnte Probleme mit anderen Teilen Ihres Codes beleuchten. Plus, dann, wenn dein Punkt eine Kollision macht, aber die Kugel nicht, wirst du etwas Konkretes zu sehen bekommen.

Mit anderen Worten, vereinfachen Sie Ihr Problem, bis eine Lösung entsteht. ;)

Answer 5

Neben der ganzen Offset-Sache, die fehlerhaft ist, scheint der Rest des Algorithmus OK. Haben Sie versucht, das Problem zu erkennen?

BTW, gibt es mehrere stilistische Macken, dass der Code schwer machen, auf einen Blick zu lesen:

• Warum die überall Zeiger, anstatt auf dem Stapel alle diese temporären Vector2Ds Zuteilung?
• Warum CrissCross::Data::LList anstelle von "gut alt" std::vector?
• Sicher hat Vector2D einen überladenen Operator-?

Hier ist eine schnelle und in sich geschlossene Implementierung des Algorithmus. Ich habe es etwas getestet, aber mache keine Garantien:

#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); 
}