2D-Kollisionserkennung

11

Nehmen wir an, ich benutze diesen Charakter.

Vogel
(Quelle: iconbug.com )

Wie würden Sie die Kollisionserkennung dafür implementieren? Die Verwendung eines Begrenzungsrahmens scheint keine gute Annäherung zu sein, da die Form des Vogels bei weitem nicht in der Nähe eines Quadrats liegt.

Ich dachte daran, eine Art Quad-Tree-Datenstruktur innerhalb des Objekts zu haben, die Teile des Bildes darstellt. Jedes Blatt kann entweder false(falls es den weißen / transparenten Raum außerhalb des Vogels bedeckt) oder seintrue (falls es einen Bereich des Vogels darstellt, dh Schnabel, Auge usw.) sein. Dann testen Sie irgendwie das einzige Hindernis in der Szene auf Kollision mit dem Vogel.

Aber meine Probleme in meinem Ansatz sind:

  1. Ich weiß nicht, wie ich den Quad-Baum initialisieren soll.
  2. Sobald der Quad-Baum initialisiert ist, bin ich mir nicht sicher, wie ich ihn durchlaufen und verwenden soll, wenn sich das Hindernis innerhalb der Koordinaten des Bildes befindet.

Wie würden Sie die Kollisionserkennung mit nicht quadratischen Zeichen durchführen?

LE: Der andere Ansatz, den ich gesehen habe, war die Verwendung mehrerer Begrenzungsrahmen. Zum Beispiel hätte ich einen oder mehrere Begrenzungsrahmen für den Schnabel, dann einige für die Haare oder den Schwanz. Aber es kann langweilig werden. Wenn dies in meinem Fall ein gültiger Ansatz ist, wie würde ich diese Begrenzungsrahmen generieren? Ich bezweifle, dass ich sie in meinem Programm fest codieren muss.

LE2: Ich kümmere mich um ziemlich genaue Kollisionen. Ich kann mir nicht vorstellen, wie ein einzelner Begrenzungsrahmen oder Kreis diese Form zumindest annähernd annähern kann, daher funktioniert dieser Ansatz nicht.

asynchron
quelle
2
Ein allgemeiner Hinweis: Ich würde sowohl einen Begrenzungsrahmen als auch eine detailliertere Prüfung verwenden: Die granulare Prüfung hat einen höheren Leistungsverlust, sodass Sie möchten, dass sie so selten wie möglich ausgeführt wird. Aktivieren Sie daher zuerst den Begrenzungsrahmen und gehen Sie nur dann tiefer, wenn dies getroffen wird, und testen Sie Ihren detaillierteren Ansatz (was auch immer das sein wird).
Philip Allgaier
Danke, ich hatte sowieso vor, das zu tun, aber ich bin mir nicht ganz sicher, wie der "granulare Check" aussehen soll. :)
async
1
Das einzige wichtige Detail fehlt: Was möchten Sie damit machen? Interessieren Sie sich für genaue Kollisionen? Sind Sie glücklich, den Charakter mit einem Kreis zu approximieren? Möchten Sie, dass Staubpartikel getrennt von den anderen mit den Augen des Charakters kollidieren?
Anko
@Anko Wie können Sie diese Form mit einem Kreis approximieren? Ich interessiere mich für ziemlich präzise Kollisionen - nicht wirklich pixelgenau, aber etwas, das gut / natürlich aussehen wird -.
Async
1
Wie dies . Was bedeuten "gut" und "natürlich" überhaupt? Ist das eine philosophische Frage?
Anko

Antworten:

12

Kreiscollider. Gut genug dafür würde ich sagen, es sei denn, Sie tun etwas Besonderes, wenn bestimmte Teile von der Physik betroffen sind oder wenn die Kollision unnatürlich aussieht, und selbst wenn Sie sie in mehrere Teile aufteilen müssen, muss ich Ihnen eines sagen:

Überkomplizieren Sie es nicht.

Sie benötigen hierfür keine vollständige Quad-Baum-Struktur. Haben Sie einfach mehrere Kästchen oder Kreise in einer geraden Anordnung und schneiden Sie sie dann mit allen. Dies kann unmöglich leistungskritisch genug sein und Sie werden nicht so viel von der Verwendung eines Quad-Baums profitieren.

Jonkel
quelle
3
Ja, machen Sie einfach eine kleine Reihe von mehreren Formen, wenn eine einzelne Form sie nicht bedeckt. Zum Beispiel: i.imgur.com/Dd4yyGN.png
MichaelHouse
Danke Jonkel & @ Byte56. Die Verwendung einiger Formen scheint in meiner Situation die richtige Lösung zu sein. Einfache Implementierung, genau und schnell. Ich kann nicht glauben, dass ich direkt zu Quad-Bäumen gesprungen bin, ohne dies zu berücksichtigen! Äh.
Async
Ein Kreiscollider für den Körper und ein Rechteck für den Schnabel für zusätzliche Genauigkeit.
Kroltan
14

Ein zweistufiger Überprüfungsprozess

Im ersten Schritt aktivieren Sie den Begrenzungsrahmen Wenn dort keine Kollision vorliegt, ist der Test beendet. Bei einer Kollision wechseln Sie zum zweiten Durchgang

Wenn Sie beim zweiten Durchgang mehr Präzision und eine echte pixelgenaue Lösung wünschen, können Sie genau das tun, einen pixelgenauen Prüfdurchgang

Da es sich bei Ihrem Bild um ein PNG (oder ein anderes Dateiformat, das einen Alphakanal enthält) handelt, ist dies recht einfach

  1. Berechnen Sie die Schnittfläche zwischen diesem einen Objekt in der Szene und dem Vogel und erzeugen Sie auf beiden Bildern ein einfaches Schnittrechteck
  2. Überprüfen Sie innerhalb dieses Schnittpunkts, ob jedes Pixel in BEIDEN Bildern einen Alpha-Wert> 0 hat
  3. Wenn solche Pixel existieren, haben Sie Ihre Kollision. Sonst nein

Wenn Sie sich den Alpha-Kanal Ihrer Bilder ansehen, können Sie sehen, dass er bereits alle Informationen enthält, die Sie für eine pixelgenaue Kollision benötigen

Alphakanal vom Bild

Pixel-perfekte Kollisionen sind normalerweise teuer. Wenn Sie also zunächst eine grobe Schätzung mit einem Begrenzungsrahmen oder einer detaillierteren Kollisionszahl (wie von Anko vorgeschlagen) vornehmen, können Sie wertvolle Zeit sparen

Der "feinere" detaillierte Kollisionsbegrenzungsrahmen, den Anko vorschlug:

detaillierterer Begrenzungsrahmen

PS: Wenn Ihr Bild einen Heiligenschein, einen Effekt oder einen anderen Nicht-0-Alphakanal aufweist, mit dem Sie nicht kollidieren möchten, kann der Algorithmusschwellenwert leicht angepasst werden, um dies zu berücksichtigen

codemonkey
quelle
1
Vielen Dank! Aber ich brauche doch keine pixelgenaue Präzision. Eine ausgezeichnete Antwort wird jedoch zu einem späteren Zeitpunkt hilfreich sein.
Async
Natürlich Kumpel, ja, eine pixelgenaue Kollision ist fast immer ein Overkill, außer in Spielen, die es wirklich brauchen (wie 2D-Kämpfer)
codemonkey
3

Ich würde einen Kreis für den Körper und ein einzelnes Rechteck für den Schnabel verwenden, aber das ist nur meine Meinung. Eine Überkomplizierung Ihrer Kollisionsgeometrie kann Ihre App jedoch verlangsamen. Sie verdoppeln praktisch (oder mehr) die Anzahl der Zeichen auf dem Bildschirm.

igrad
quelle
0

Vielleicht könnten Sie eine Art wackeligen Polygon / Kanten-Collider verwenden.

Ich weiß nicht genau, wie das funktionieren würde, aber:

zwei Objekte: Objekt 1: der Vogel (o1), Objekt 2: das Ding, das den Vogel treffen könnte (o2)

1) Definieren Sie eine Begrenzungsform, die ein Polygon ist, das eng an das erste betreffende Objekt (o1) passt.

2) Holen Sie sich die Kanten von o1, o2, die möglicherweise kollidieren könnten, ohne dass sie möglicherweise kollidieren könnten, ohne dass o2 durch o1 geht oder umgekehrt.

Mit der Position und Größe der Form (o2) könnten Sie wahrscheinlich Kanten (von o1) isolieren, die möglicherweise nicht getroffen werden können, unabhängig davon, ob sie sich "hinter" einer anderen Kante (von o1) befinden, die näher an o2 liegt. Wenn Sie ein rechtwinkliges Dreieck hatten, dessen Hypotenuse nach oben und rechts zeigt, und ein Rechteck, das sich ihm gerade nähert (mit der langen Seite entlang der x-Achse), können Sie erkennen, welche Kanten weggelassen werden sollen, da beide Werte für Anfang und Ende y sind über oder unter dem Rechteck.

3) Stellen Sie fest, ob einer der Punkte an einer Kante von o2 mit einem Punkt an einer der Kanten von o1 übereinstimmt, die Sie in Schritt 2 ausgewählt haben.

Dieses Konzept funktioniert wahrscheinlich am besten für kollidierende Polygone (dh Dinge mit klaren Kanten), aber vielleicht können Sie einen Kreis als eine lange Kante behandeln (z. B. wenn o2 ein Kreis war).

Jeremy Harton
quelle