Kreis-Rechteck-Kollisionsseitenerkennung in libgdx

Unten finden Sie eine Erklärung für Kreis- / Rechteckkollisionen. Beachten Sie jedoch, dass diese Art der Kollision für Ihre Anforderungen möglicherweise nicht erforderlich ist. Wenn Sie zum Beispiel eine rechteckige Begrenzungsbox für Ihr Zeichen hätten, wäre der Algorithmus einfacher und schneller. Selbst wenn Sie einen Kreis verwenden, ist es wahrscheinlich, dass es einen einfacheren Ansatz gibt, der für Ihre Zwecke gut genug ist.

Ich habe zwar den Code dafür geschrieben, aber es würde zu lange dauern, deshalb hier nur eine Erklärung:

Hier ist eine Beispielbewegung Ihres Charakterkreises mit seinen letzten (vorherigen) und aktuellen Positionen. Das Wandrechteck wird darüber angezeigt.





Hier ist die gleiche Bewegung, gepunktete Linien stellen den Bereich dar, den der Kreis in dieser Bewegung überstreicht. Der Sweep-Bereich ist kapselförmig.




Es wäre schwierig, die Kollision dieser beiden Objekte zu berechnen, also müssen wir das anders machen. Wenn Sie die Kapsel auf dem vorherigen Bild betrachten, werden Sie sehen, dass es sich einfach um die Bewegungslinie handelt, die in jeder Richtung um den Radius des Kreises erweitert wird. Wir können diese "Erweiterung" von der Bewegungslinie zum Wandrechteck verschieben. Auf diese Weise erhalten wir ein abgerundetes Rechteck wie auf dem Bild unten.




Die Bewegungslinie kollidiert genau dann mit diesem erweiterten (abgerundeten) Rechteck, wenn die Kapsel mit dem Wandrechteck kollidiert, so dass sie irgendwie äquivalent und austauschbar sind.

Da diese Kollisionsberechnung immer noch nicht trivial und relativ teuer ist, können Sie zuerst eine schnelle Kollisionsprüfung zwischen dem verlängerten Wandrechteck (dieses Mal nicht abgerundet) und dem Begrenzungsrechteck der Bewegungslinie durchführen. Sie können diese Rechtecke auf dem Bild unten sehen - sie sind beide punktiert. Dies ist eine schnelle und einfache Berechnung, und während Sie das Spiel spielen, wird es wahrscheinlich KEINE Überschneidung mit einem bestimmten Mauerrechteck geben & 99% der Zeit und die Kollisionsberechnung wird hier aufhören.




Wenn es jedoch eine Überlappung gibt, besteht wahrscheinlich eine Kollision des Zeichenkreises mit dem Wandrechteck, aber es ist nicht sicher, wie später gezeigt wird.

Nun müssen Sie den Schnittpunkt zwischen der Bewegungslinie selbst (nicht der Begrenzungsbox) und dem erweiterten Wandrechteck berechnen. Sie können wahrscheinlich einen Algorithmus finden, wie Sie dies online tun, nach einer Linie / Rechteck-Kreuzung oder einer Linie / Aabb-Kreuzung suchen (aabb = Axis Aligned Bounding Box). Das Rechteck ist achsausgerichtet und dies macht die Berechnung einfacher. Der Algorithmus kann Ihnen einen Schnittpunkt oder Punkte geben, da es möglich ist, dass es zwei gibt - in diesem Fall wählen Sie den nächsten zum Startpunkt der Linie. Unten ist ein Beispiel für diese Kreuzung / Kollision.




Wenn Sie einen Schnittpunkt erhalten, sollte es einfach sein zu berechnen, auf welchem ​​Teil des erweiterten Rechtecks ​​dieser Schnittpunkt liegt. Sie können diese Teile auf dem Bild oben sehen, getrennt durch rote Linien und markiert mit einem oder zwei Buchstaben (l - links, r - rechts, b - unten, t - oben, tl - oben und links usw.) Wenn der Schnittpunkt auf den Teilen l, r, b oder t liegt (die einzelnen Buchstaben, in der Mitte), dann sind Sie fertig. Es gibt definitiv eine Kollision zwischen Charakterkreis und Wandrechteck, und Sie wissen auf welcher Seite. Im obigen Beispiel ist es auf der Unterseite. Sie sollten wahrscheinlich 4 Variablen namens isLeftCollision , isRightCollision , isBottomCollsion und isTopCollision verwenden. In diesem Fall würden Sie isBottomCollision auf True setzen, während die anderen 3 auf false bleiben würden.

Wenn sich der Schnittpunkt jedoch an der Ecke befindet, sind in den aus zwei Buchstaben bestehenden Abschnitten zusätzliche Berechnungen erforderlich, um festzustellen, ob eine tatsächliche Kollision zwischen dem Zeichenkreis und dem Wandrechteck besteht. Das Bild unten zeigt 3 solcher Schnittpunkte an den Ecken, aber es gibt eine tatsächliche Kreis-Rechteck-Kollision bei nur 2 von ihnen.




Um festzustellen, ob eine Kollision vorliegt, müssen Sie einen Schnittpunkt zwischen der Bewegungslinie und dem Kreis finden, der in der nächstgelegenen Ecke des ursprünglichen Rechtecks ​​der nicht erweiterten Wand zentriert ist. Der Radius dieses Kreises ist gleich dem Radius des Zeichenkreises. Auch hier können Sie nach einem Linien / Kreis-Schnittalgorithmus googlen (vielleicht sogar libgdx), es ist nicht komplex und sollte nicht schwer zu finden sein.
Es gibt keine Linie / Kreis-Schnittpunkt (und keine Kreis / Rechteck-Kollision) auf Bl-Teil, und es gibt Kreuzungen / Kollisionen auf Br und Tr-Teile.
Im Fall br setzen Sie isRightCollision , isBottomCollsion auf true und im Fall tr ​​setzen Sie isRightCollision und isTopCollision auf true.

Es gibt auch einen Randfall, auf den Sie achten müssen, und Sie können es auf dem Bild unten sehen.




Dies kann passieren, wenn die Bewegung des vorherigen Schritts in der Ecke des erweiterten Rechtecks ​​endet, aber außerhalb des Radius der inneren Rechteckecke (es gab keine Kollision).
Um festzustellen, ob dies der Fall ist, überprüfen Sie einfach, ob sich der Bewegungspunkt innerhalb des erweiterten Rechtecks ​​befindet.
Wenn dies der Fall ist, sollten Sie nach dem anfänglichen Rechtecküberlappungstest (zwischen dem erweiterten Wandrechteck und dem Begrenzungsrechteck der Bewegungslinie) den Linien / Rechteck-Schnitttest überspringen (da in diesem Fall möglicherweise kein Schnittpunkt UND immer noch eine Kreis- / Rechteckkollision ist) ), und auch einfach basierend auf der Bewegung, indem Sie den Punkt bestimmen, in welcher Ecke Sie sich befinden, und dann nur nach einer Linie / Kreis-Kreuzung mit dem Kreis dieser Ecke suchen. Wenn es eine Kreuzung gibt, gibt es eine Kollision des Zeichenkreises / Wandrechtecks, andernfalls nicht.

Nach all dem sollte der Kollisionscode einfach sein:

[Update]

Hier ist eine einfache und ich glaube effiziente Umsetzung der Segment-AABB-Kreuzung, die für Ihre Zwecke gut genug sein sollte. Es ist ein leicht modifizierter Cohen-Sutherland-Algorithmus . Sie können auch den zweiten Teil von diese Antwort lesen.

Hier ist eine Codebeispielverwendung:

Dies ist das Ergebnis, das ich beim Ausführen dieses Befehls erhalte:

Bitte beachten Sie, dass dies Desktopleistung auf einer i5-2400 CPU ist. Es wird wahrscheinlich viel langsamer auf Android-Geräten, aber ich glaube, immer noch mehr als ausreichend.
Ich habe das nur oberflächlich getestet. Wenn Sie Fehler finden, lassen Sie es mich wissen.

Wenn Sie diesen Algorithmus verwenden, brauchen Sie meines Erachtens keine besondere Behandlung für den Fall, in dem sich der Anfangspunkt in der Ecke des erweiterten Wandrechtecks ​​befindet, da Sie in diesem Fall den Schnittpunkt beim Zeilenanfang erhalten Kollisionserkennungsprozedur wird mit dem nächsten Schritt fortgesetzt (Line-Circle-Kollision).

Ich nehme an, Sie bestimmen die Kollision, indem Sie den Abstand des Mittelpunkts der Kreise mit den Linien berechnen. Wir können den Fall vereinfachen und sagen, dass der Kreis mit der Ecke kollidiert, wenn beide Abstände gleich und kleiner als der Radius sind. Die Gleichheit sollte natürlich eine Toleranz haben.

Mehr - möglicherweise nicht notwendig - Ein realistischer Ansatz wäre, x, y-Geschwindigkeit zu berücksichtigen und bei der Gleichheitsüberprüfung zu berücksichtigen.