2009-10-26 11 views
5

OK, also versuche ich einen einfachen Asteroiden-Klon zu machen. Alles funktioniert gut, bis auf die Kollisionserkennung.Polygon Intersection fehlschlägt, Kollision "Größe" zu groß

Ich habe zwei verschiedene Versionen, die erste verwendet java.awt.geom.Area:

// polygon is a java.awt.Polygon and p is the other one 
final Area intersect = new Area(); 
intersect.add(new Area(polygon)); 
intersect.intersect(new Area(p.polygon)); 
return !intersect.isEmpty(); 

Dies funktioniert wie ein Charme ..., wenn Sie nicht nur für etwa 40% CPU egal 120 Asteroiden :(

Also suchte ich im Internet nach dem berühmten Achse Satz zu trennen, da ich mir die Implementierung von here und konvertierte es dauerte nicht thaaaaaat gut ein Mathe bin mein Java passen muss:

public double dotProduct(double x, double y, double dx, double dy) { 
     return x * dx + y * dy; 
    } 

    public double IntervalDistance(double minA, double maxA, double minB, 
      double maxB) { 
     if (minA < minB) { 
      return minB - maxA; 
     } else { 
      return minA - maxB; 
     } 
    } 

    public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) { 
     double dotProduct = dotProduct(ax, ay, x[0], y[0]); 
     double min = dotProduct; 
     double max = dotProduct; 
     for (int i = 0; i < p; i++) { 
      dotProduct = dotProduct(x[i], y[i], ax, ay); 
      if (dotProduct < min) { 
       min = dotProduct; 
      } else if (dotProduct > max) { 
       max = dotProduct; 
      } 
     } 
     return new double[] { min, max }; 
    } 

    public boolean PolygonCollision(Asteroid ast) { 
     int edgeCountA = points; 
     int edgeCountB = ast.points; 
     double edgeX; 
     double edgeY; 

     for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) { 
      if (edgeIndex < edgeCountA) { 
       edgeX = xp[edgeIndex] * 0.9; 
       edgeY = yp[edgeIndex] * 0.9; 
      } else { 
       edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9; 
       edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9; 
      } 

      final double x = -edgeY; 
      final double y = edgeX; 
      final double len = Math.sqrt(x * x + y * y); 
      final double axisX = x/len; 
      final double axisY = y/len; 

      final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp, 
        yp); 
      final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points, 
        ast.xp, ast.yp); 

      if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

Es funktioniert ... irgendwie. Eigentlich scheint es so, als wäre die "Kollisionshülle" der Asteroiden zu groß, wenn man diesen Code benutzt, es ist 1,2 mal so groß wie der Asteroid. Und ich habe keine Ahnung warum.

Hier sind zwei Bilder zum Vergleich:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

Wie Sie hoffentlich sehen können, die Asteroiden in Bild eines viel dichter als die in Bild 2, wo Sie den Code SAT verwenden.

Also irgendwelche Ideen? Oder kennt jemand eine Polygon-Implementierung für Java mit Schnittstellentests, die ich verwenden könnte?

Antwort

4

Es sieht so aus, als ob Ihr zweites Ergebnis eine Kollisionserkennung durchführt, als ob die Polygone Kreise wären, deren Radius auf den entferntesten Punkt des Polygons von der Mitte aus eingestellt ist. Die meisten Kollisionserkennungselemente, die ich gesehen habe, erzeugen eine einfache Begrenzungsbox (entweder einen Kreis oder ein Rechteck), in die das Polygon passen kann. Nur wenn sich zwei Bounding Boxes schneiden (eine weitaus einfachere Berechnung), geht es weiter zur detaillierteren Erkennung. Vielleicht ist der verwendete Algorithmus nur als Bounding-Box-Rechner gedacht?

EDIT: Auch aus wikipedia

Der Satz gilt nicht, wenn einer des Körpers nicht konvex ist.

Viele der Asteroiden in Ihrem Bild haben konkave Oberflächen.