Achsensatz mit mehreren Polygonen trennen?

9

Ich versuche, den Satz der Trennachse in C # zu implementieren. Ich habe eine Funktion, die den minimalen Translationsvektor zwischen zwei Polygonen berechnen kann. Ich kann jedoch scheinbar keine Funktion erstellen, die den minimalen Übersetzungsvektor zwischen einem Polygon und mehreren anderen Polygonen berechnet. Ehrlich gesagt, ich arbeite seit Monaten daran und bin einer Lösung nicht näher gekommen und konnte online keine Lösung finden. Es gibt immer einige Randfälle, die nicht das richtige Ergebnis liefern, was zu Fehlern mit hoher Priorität in meinem Spiel führt.

Hier sind häufige Randfälle, die nicht richtig funktionieren:

Randfälle

Gibt es eine bekannte Lösung für dieses Problem? Alles, was ich finden kann, sind Leute, die sagen "Führe einfach den SAT für jedes Polygon aus", aber dies erzeugt selten den minimalen Übersetzungsvektor.

Jede Hilfe wäre sehr dankbar.

collision-detection separating-axis-theorem user40698
quelle
Eine Idee, die ich eigentlich nie getestet habe, ist, dass einige Trennachsen - diejenigen, die Sie seitwärts in ein benachbartes Polygon bewegen würden - markiert werden könnten, um niemals als Minimum betrachtet zu werden. Dann würde eine Art wiederholter Test gute Ergebnisse liefern (möglicherweise mit einer Art FIFO- und / oder Iterationsbeschränkung, um zu verhindern, dass sie in einer Schleife stecken bleiben).
Andrew Russell
Eine noch schwieriger zu lösende Version davon ist, wenn eine Kante einer Form nur teilweise von einer anderen bedeckt wird. Zum Beispiel im Bild oben rechts, wenn sich das mittlere Quadrat nach rechts erstreckt, um ein größeres Rechteck zu sein. Dies ähnelt der Ausgabe eines von mir verwendeten Codes, der Zehntausende besetzter / nicht besetzter Zellen benötigt und diese auf unter hundert größere Kollisionsformen reduziert
Richard Tingle

Antworten:

2

Idealerweise bauen Sie Ihre Umgebung nicht aus Polygonen auf. Sie bauen es aus Kanten (die Sie vielleicht aus einer Reihe von Polygonen berechnen). In Ihrem ersten Beispiel gibt es beispielsweise eine einzelne diagonale Kante. Im letzten Beispiel ruht die Box auf einer einzelnen horizontalen Kante.

Die Tatsache, dass Ihr Editor oder Ihre Werkzeuge kleinere, individuelle Formen zum Erstellen einer Ebene verwenden, sollte sich nicht auf die Laufzeit auswirken.

Ein etwas einfacherer Ansatz würde einfach "innere" Kanten der Grundformen entfernen. In Ihrem letzten Beispiel gibt es zwei Kanten zwischen den "Boden" -Boxen. Ignorieren Sie diese während der Kollisionserkennung.

Weitere bessere Bilder und Implementierungsideen finden Sie in Abschnitt 4.5 (Kanten und Kantenketten) in der Box2D-Dokumentation .

Sean Middleditch
quelle
2
Die Verwendung von Kanten (insbesondere Kanten, bei Kantenketten ist dies etwas besser) hat den Hauptnachteil, dass es für Physikobjekte sehr einfach wird, innerhalb der Ebenengeometrie Störungen zu verursachen.
Andrew Russell
1
@ AndrewRussell: Diese Probleme werden mit den üblichen Tunnelkorrekturen vermieden. Stellen Sie sicher, dass Ihre sich bewegenden Objekte ein recht anständiges Volumen / eine anständige Fläche haben, halten Sie ihre maximale Geschwindigkeit pro Bild niedrig genug, damit sie sich nicht mehr als die Hälfte ihrer kürzesten Abmessung bewegen können (oder treten Sie mehrmals darauf, wenn Sie sie benötigen, um sich schneller zu bewegen). Vermeiden Sie dies Bei wirklich scharfen Spalten und dergleichen in Ihrer Ebenengeometrie wird die Auflösung mehrmals wiederholt, bis Sie an einem "sicheren" endgültigen Ort usw. konvergieren.
Sean Middleditch