Collision detection in class Turtle

[weichm]

Ich habe versucht, ein einfaches Snake-Game mit der Klasse Turtle zu programmieren, s.u.
Dabei habe ich es nicht geschafft zu erkennen, wann die Schlange sich in den eigenen Schwanz beißt.
Evtl. ist die Methode collidesWithFillColor(color) fehlerhaft.

Demonstration des Problems:

/*
 * einfaches Snake Game
 * 
 * der Spieler steuert mit den Tasten "a" und "d"
 * BUG: kreuzt die Schlange (rotes Dreieck) den eigenen Schwanz (weiße Linie)
 *       dann wird nicht "Aua" gedruckt
 * gewünschtes Verhalten: collidesWithFillColor(color) liefert true, wenn das Zentrum der
 *       Schildkröte (rotes Dreieck) einen Punkt der Farbe color berührt
 * Sonstiges: Funktionalität der anderen Kollisionsmethoden wurde nicht überprüft:
 *    boolean collidesWithAnyShape()
 *    boolean collidesWithFillColor(int color)
 *    boolean collidesWithShape(Shape s)
 */

class Snake extends Turtle {
   Snake(int x, int y) {
      super(x, y);
      this.setBorderColor(Color.white);
   }
   void act() {
      this.forward(3);
      if(this.collidesWithFillColor(Color.white)) {
         println("Aua");  // never gets there, even if Turtle crosses itself
      }
   }
   // Wird aufgerufen, nachdem der Benutzer eine Taste gedrückt hat.
   void onKeyDown(String key) {
      if(key == "a") {
         this.turn(90); 
      }
      if(key == "d") {
         this.turn(90); 
      }
   }
}

Snake p1 = new Snake(50, 300);

[martin-pabst]

Die Methode collidesWithFillColor(color) funktioniert nur bei gefüllten Turtle-Objekten, d.h. solchen, deren filled-Eigenschaft den Wert true hat. Man kann dies mit dem Methodenaufruf closeAndFill(true) erreichen, es ist beim Spiel Snake aber natürlich nicht zielführend. Wenn ich es richtig verstehe geht es darum, herauszufinden, ob der Streckenzug des Turtle-Objektes Überschneidungen hat. Würde es helfen, wenn ich der Turtle-Klasse eine entsprechende Methode boolean hasCrossings() hinzufüge?

[weichm]

Okay, mit Deiner Erklärung macht die vorhandene Implementierung von collidesWithFillColor(color) am meisten Sinn.

Die von dir vorgeschlagene Implementierung von hasCrossings() würde das Problem "1 Spieler spielt gegen sich selbst" lösen und wäre für mein Vorhaben nur bedingt von Nutzen (aber sicherlich auch interessant).

Ziel der Unterrichtseinheit ist nämlich das vollständige Snake-Spiel selbst, bei dem 2 Spieler gegeneinander spielen: der eine steuert seine (rote) Schlange snake1 mit "a" und "d", der andere seine (weiße) Schlange snake2 mit "Cursor up" und "Cursor down". Dieses Problem würde die vorgeschlagene Methode hasCrossings() nicht lösen. Ein zwei Spieler-Spiel könnte ungefähr so aussehen:

class Snake extends Turtle {
   String left;
   String right;
   String name;
   Snake(int x, int y, int startDirection, String name, String left, String right, Color color) {
      super(x, y);
      this.left = left;
      this.right = right;
      this.name = name;
      this.setAngle(startDirection);
      this.setBorderColor(color);
   }
   void act() {
      this.forward(3);
   }
   void onKeyDown(String key) {
      if(key == this.left) {
         this.turn(90); 
      }
      if(key == this.right) {
         this.turn(90); 
      }
   }
}

class Game extends Group {
   Snake p1;
   Snake p2;
   Line r;
   Game() {
      p1 = new Snake(50, 300, 0, "Hans", "a", "d", Color.red);
      p2 = new Snake(550, 300, 180, "Susi", "CursorUp", "CursorDown", Color.white);
      r = new Line(200, 10, 200, 500);
   }
   void act() {
      if(p1.collidesWith(p2)) {  // Kollisionserkennung funktioniert nicht
         println("Aua1");        // funktioniert wohl nur für geschlossene Turtle-Figuren (closeAndFill(true))
      }
       if(p1.collidesWith(r)) {  // zum Test: Kollision mit Linie wird erkannt
         println("AuaLinie");
      }
   }
}
new Game();

Bemerkungen zum Code:

• die Kollisionserkennung mit collidesWith(Shape s) funktioniert nicht; selbst wenn: es ist nicht klar, ob Spieler1 oder Spieler2 verloren hat
• Kollisionserkennung über collidesWith(Shape s) benötigt Referenzen und ist nicht niederschwellig für den Einstiegsunterricht (9.Klasse im Lehrplan G9 Bayern). Referenzen kommen erst in 10.Klasse. (Wenn man auf Farbe prüfen könnte, könnte die Game-Klasse auch wegfallen und somit die Verwendung von Referenzen in obigem Code)

Für meine Zwecke würde man eine Methode benötigen, mit der man prüfen kann, ob der Kopf von z.B. snake2 auf eine rote Farbe trifft.
Da man die Linienfarbe der Schlange mit setBorderColor(color) setzt, würde dem gewünschten Verhalten am ehesten eine Methode collidesWithBORDERColor(color) entsprechen. Aber wahrscheinlich ist das aufwändig umzusetzen.

[martin-pabst]

An die zweite Snake habe ich bei meiner Antwort nicht gedacht - das ist mir peinlich!
Die Online-IDE nutzt zur Ausgabe der Graphik die Bibliothek pixi.js, die WebGL nutzt, das wiederum auf OpenGL basiert. Die grafischen Objekte werden daher nicht in eine Bitmap gerendert, sondern direkt in Form von Vektoren zur Grafikkarte geschickt. Das hat den Vorteil, dass die Grafik schnell und von recht hoher Qualität ist, gleichzeitig habe ich aber keine Möglichkeit, auf einfache Art herauszufinden, ob ein Punkt der Grafikausgabe eine bestimmte Farbe besitzt.
Alle graphischen Objekte, die Unterklassen von Shape sind, führen eine BoundingBox (kleinstes umfassendes achsenparalleles Rechteck) und ein HitPolygon (im Idealfall kleinstes umfassendes Polygon) mit. Beide basieren auf den Eckpunkten der Grafikobjekte ohne Berücksichtigung des Borders und umschließen genau den ausgefüllten Bereich.
Um herauszufinden, ob ein Punkt im ausgefüllten Bereich einer Figur liegt, prüft die Online-IDE zuerst, ob er in der BoundingBox der Figur liegt. Falls "ja", erfolgt die genauere (aber aufwändigere) Prüfung anhand des HitPolygons. Entsprechend wird verfahren um herauszufinden, ob sich zwei Figuren überlappen.

Den Border zu berücksichtigen ist recht aufwändig, weil seine Gestalt sich bei einigen Figuren nicht einfach einheitlich aus dem HitPolygon berechnen lässt (z.B. RoundedRectangle oder Ellipse). Bei der Turtle ergibt sich zusätzlich die Schwierigkeit, dass jede Teilstrecke eine eigene Farbe und Strichdicke haben kann.

Relativ einfach wäre noch eine auf die Turtle beschränkte Lösung zu schaffen, etwa durch eine Methode borderContainsPoint(x, y). Dazu bräuchte man aber eine Referenz auf die Turtle. Die Herausforderung der Methode collidesWithBORDERColor(Color.white) besteht darin, dass ihre Semantik nahelegt, dass nicht nur die Kollision mit einem weißen Border einer Turtle erkannt wird, sondern auch die Kollision mit dem weißen Border eines RoundedRectangle, einer Ellipse, eines Text-Objekts usw.
Ich werde recherchieren, wie hoch die Aufwände tatsächlich sind und nachdenken, ob es nicht eine einfachere, nicht ganz exakte Möglichkeit gibt, bei allen Klassen außer Turtle die Kollisionen mit den Borders basierend auf dem HitPolygon und der BorderWidth auszuwerten.
Die Idee, Snake mit Turtles zu programmieren, finde ich auf jeden Fall genial. Es wäre eine richtig schöne Anwendung ohne Objektreferenzen, wenn sich die Methode collidesWithBORDERColor(color) nur irgendwie umsetzen ließe...

[martin-pabst]

Ich habe die Methode collidesWithBorderColor jetzt implementiert. Es gab noch ein Problem beim Erkennen, ob sich eine Snake selbst beißt: Unmittelbar nach einer 90°-Wende befindet sich der Kopfpunkt der Turtle noch innerhalb des letzten Liniensegments. Ich habe daher zusätzlich die Methode getLastSegmentLength zur Turtle hinzugefügt und die forward-Methode so abgeändert, dass sie unmittelbar aufeinanderfolgende Liniensegmente gleicher Farbe und Breite zu einem einzigen Segment zusammenfasst. Anhand der Länge des letzten Segments lässt sich jetzt unterscheiden, ob sich die Snake selbst beißt oder ob sie nur ihre Richtung geändert hat.

Unten anliegend das Testprogramm von Dir, etwas erweitert.

Im Konstruktor von Snake empfiehlt es sich übrigens, die Methode turn statt setAngle zu verwenden, da letztere (ebenso wie rotate) die Transformationsmatrix der Snake ändert und bewirkt, dass alles bisher gezeichnete einfach gedreht wird (was sich negativ auf die Performance bei der Kollisionserkennung auswirkt), während turn nur die Laufrichtung der Turtle ändert.

Ich hoffe, dass sich das Snake-Spiel mithilfe der neuen Methoden realisieren lässt. Fall etwas nicht passt oder noch fehlt, schreib' bitte gerne!

   String left;
   String right;
   String name;
   Snake(int x, int y, int startDirection, String name, String left, String right, Color color) {
      super(x, y);
      this.left = left;
      this.right = right;
      this.name = name;
      this.turn(startDirection);
      this.setBorderColor(color);
   }
   void act() {
      this.forward(3);
   }
   void onKeyDown(String key) {
      if(key == this.left) {
         this.turn(90); 
      }
      if(key == this.right) {
         this.turn(90); 
      }
   }
}

class Game extends Group {
   Snake p1;
   Snake p2;
   Line r;
   Game() {
      p1 = new Snake(50, 300, 0, "Hans", "a", "d", Color.red);
      p2 = new Snake(550, 300, 180, "Susi", Key.ArrowUp, Key.ArrowDown, Color.white);
      r = new Line(200, 10, 200, 500);
      r.setBorderColor(Color.blue);
   }
   void act() {
      if(p1.collidesWithBorderColor(Color.white)) {  // Kollision mit anderer Snake
         println("Aua1");        // funktioniert wohl nur für geschlossene Turtle-Figuren (closeAndFill(true))
      }
      if(p1.collidesWithBorderColor(Color.red) && p1.getLastSegmentLength() > 6) {  // Snake beißt sich selbst
         println("AuaLinie");
      }
      if(p1.collidesWithBorderColor(Color.blue)) {  // zum Test: Kollision mit Linie wird erkannt
         println("Blau!");
      }
   }
}
new Game();

[weichm]

Danke Dir für die schnelle Lösung - auch wenn es wohl nicht ganz einfach war.
Die Lösung passt genau!
Danke auch für die umfangreichen Erklärung, da hab ich auch was dazu gelernt!