Schnelle, genaue 2D-Kollision

17

Ich arbeite an einem 2D-Topdown-Shooter und muss jetzt über mein grundlegendes Kollisionssystem für rechteckige Bounding-Boxen hinausgehen.

Ich habe große Levels mit vielen verschiedenen Sprites, die alle unterschiedliche Formen und Größen haben. Die Texturen für die Sprites sind alle quadratische PNG-Dateien mit transparentem Hintergrund. Daher brauche ich auch eine Möglichkeit, um nur eine Kollision zu haben, wenn der Spieler in den farbigen Teil der Textur und nicht in den transparenten Hintergrund läuft.

Ich plane, wie folgt mit Kollisionen umzugehen:

  1. Überprüfen Sie, ob sich Sprites in Reichweite des Players befinden
  2. Führen Sie einen Kollisionstest mit einem geraden Begrenzungsrahmen durch
  3. Mach eine genaue Kollision (Wo ich Hilfe brauche)

Ich habe nichts gegen fortgeschrittene Techniken, da ich dies in Anbetracht all meiner Anforderungen richtig machen möchte, aber ich bin nicht sicher, wie ich das angehen soll. Welche Techniken oder sogar Bibliotheken zu versuchen. Ich weiß, dass ich wahrscheinlich eine Form erstellen und speichern muss, die genau jedes Sprite abzüglich des transparenten Hintergrunds darstellt.

Ich habe gelesen, dass pro Pixel langsam ist, daher halte ich das angesichts meiner großen Anzahl von Objekten nicht für geeignet. Ich habe mich auch mit Box2d befasst, konnte aber nicht viel Dokumentation oder Beispiele dafür finden, wie man es mit SFML zum Laufen bringt.

Neophyt
quelle

Antworten:

18
  1. Schritt eins, erstelle ein Raster und aktualisiere es für jedes Objekt, das sich bewegt.
  2. Prüfen Sie nur auf Kollisionen zwischen Objekten auf denselben Feldern.
  3. Überprüfen Sie, ob sich der Begrenzungsrahmen der Objekte schneidet (ihr umschließendes Rechteck).
  4. Prüfen Sie anhand einer niedrig aufgelösten Version der Kontur, ob eine pixelgenaue Kollision vorliegt (siehe Spielphysik).
  5. Führen Sie eine normale Überprüfung der Gliederungsverfolgung durch, wie in Game Physics (Q 2) beschrieben.

Schritt 1:

Erstellen Sie ein Gitter-2D-Array. Jedes Objekt weiß anhand seiner x-, y-Position und seiner Breite und Höhe, welche Quadrate es einnimmt. Wenn ein Objekt wegbewegt wird, löscht es sich von dem alten Feld und aktualisiert das neue Feld, das es belegt.

Dies nimmt nur O (n) insgesamt für n Objekte. Für ein bestimmtes Objekt O (1).

Schritt 2:

Führen Sie alle Überprüfungen auf Kollisionen zwischen Objekten in denselben Quadraten durch. Es müssen keine Tests für Kollisionen zwischen Objekten in verschiedenen Quadraten durchgeführt werden. Ein Objekt kann bis zu vier Felder einnehmen, wenn es eine durchschnittliche Größe hat. Dies bedeutet sehr wenige Kontrollen.

Schritt 3:

Prüfen Sie, ob sich die Rechtecke der Objekte überschneiden. Wenn keine Kreuzung vorhanden ist, halten Sie an.

Schritt 4:

Prüfen Sie, ob die Konturen der Objekte nur innerhalb des Schnittbereichs pixelgenau kollidieren. Es sollte schnell genug sein. Wenn nicht, erstellen Sie ein 2d-boolesches Array mit niedriger Auflösung und überprüfen Sie es zuerst. Wenn Sie dort Kollisionen finden, müssen Sie nur ein kleines Segment im 2d-Array mit hoher Auflösung überprüfen, um wertvolle Zeit zu sparen.

Bitte lesen Sie dieses Konzept, um herauszufinden, wie Sie Ihre Spielwelt in ein Gitter aus Quadraten aufteilen können :

Erstellen eines effizienten Kollisionserkennungssystems

Bitte lesen Sie diese Informationen, um zu erfahren, wie Sie pixelgenaue Kollisionen erkennen können.

Spielphysik / 2D-Kollisionserkennung AS3

Sie können die Leistung erheblich verbessern:

  1. Speichern Sie eine niedrigauflösende (1/16) Version der Gliederung, um sie zuerst zu überprüfen.

  2. Nur in dem Bereich prüfen, in dem sich die beiden Rechtecke kreuzen.

  3. indem Sie den Umriss grob in Segmente unterteilen und erst auf Kollisionen zwischen Segmenten prüfen.

Bitte fühlen Sie sich willkommen zu kommentieren und ich werde näher darauf eingehen.

Überprüfen Sie im Bereich der Kreuzung

wolfdawn
quelle
1
Ersetzen Sie, wie Arthur sagte, Ihre Schritte 1. und 2. durch ein Raster, und für eine genaue Kollisionserkennung können Sie eine Version Ihrer Bilder mit niedriger Auflösung verwenden.
Markus von Broady
1
Und wenn Sie wirklich brauchen, können Sie auch eine ähnliche Technik wie hier verwenden: gamedev.stackexchange.com/questions/38481/…
Markus von Broady
Markus weist auf eine gute Idee hin. Sie sollten ein 2d-boolesches Array oder ein 1d-Array verwenden, das als 2d behandelt wird, und Sie könnten 1/2 1/4 1/8 niedrig aufgelöste Versionen dieses Arrays speichern, um die Dinge zu beschleunigen. Dies ist wahrscheinlich nicht erforderlich, da die Berechnung für 2d-boolesche Arrays sehr schnell ist. Es ist immer noch ein nützliches Werkzeug.
Wolfdawn
Befindet sich der Spieler vollständig in einem Feld des Gitters, können Sie nur Objekte in diesem Feld prüfen. Der Spieler darf sich auf vier benachbarten Feldern gleichzeitig aufhalten. Meinst Du das? Wenn Sie den Schnittpunkt zwischen Rechtecken meinen, müssen Sie nur prüfen, ob sich Kollisionen ergeben.
Wolfdawn
1
Ich hoffe, das Update hilft bei der Aufklärung. Sobald Sie einen Code geschrieben haben, können Sie ihn in der Codeüberprüfung veröffentlichen und uns für Kommentare verlinken. codereview.stackexchange.com
wolfdawn