Ich arbeite an einer rein kontinuierlichen Physik-Engine und muss Algorithmen für die Erkennung von Kollisionen in breiten und engen Phasen auswählen. "Rein kontinuierlich" bedeutet, dass ich niemals Kreuzungstests durchführe, sondern Wege finden möchte, um jede Kollision zu erfassen, bevor sie auftritt, und sie in den von TOI geordneten Stapel "Geplante Kollisionen" zu legen.

Breite Phase Die einzige kontinuierliche Breitphasenmethode, die ich mir vorstellen kann, besteht darin, jeden Körper in einen Kreis einzuschließen und zu testen, ob sich jeder Kreis jemals mit einem anderen überlappt. Dies scheint jedoch schrecklich ineffizient zu sein und es fehlt jegliches Keulen.

Ich habe keine Ahnung, welche kontinuierlichen Analoga für die heutigen diskreten Kollisions-Keulungsmethoden wie Quad-Bäume existieren könnten. Wie kann ich unangemessene und sinnlose Tests verhindern, wie dies bei einem diskreten Motor der Fall ist? Ich möchte auch Kollisionen sehen können, die mehr als einen Frame vor mir liegen.

Enge Phase
Ich habe es geschafft, den engen SAT eher an eine kontinuierliche als an eine diskrete Überprüfung anzupassen, aber ich bin sicher, dass es andere bessere Algorithmen in Zeitungen oder Websites gibt, auf die ihr vielleicht gestoßen seid.
Welche verschiedenen schnellen oder genauen Algorithmen schlagen Sie vor, die ich verwende, und welche Vor- / Nachteile hat jeder?

Schlussbemerkung:
Ich sage Techniken und keine Algorithmen, weil ich noch nicht entschieden habe, wie ich verschiedene Polygone speichern soll, die konkav, konvex, rund oder sogar löchrig sein können. Ich habe vor, eine Entscheidung darüber zu treffen, basierend auf den Anforderungen des Algorithmus (wenn ich beispielsweise einen Algorithmus wähle, der ein Polygon in Dreiecke oder konvexe Formen zerlegt, speichere ich die Polygondaten einfach in dieser Form).

Ich werfe hier wirklich nur Ideen herum. Angenommen, Sie haben (zumindest) die currentPosition und nextPosition; für jeden Rahmen.

Sie würden zwei separate breite Phasen benötigen, gefolgt von Ihrer engen Phase:

• Eine, die herausfindet, dass eine Kollision auftreten wird.
• Eine, die ungefähr herausfindet, wo die Kollision tatsächlich auftritt (z. B. eine breite Phase / ungenauer SAT)
• Schließlich würde Ihre enge Phase das Ergebnis der zweiten breiten Phase verbessern.

Anfängliche breite Phase

Sie könnten räumliches Hashing (unter Verwendung der nextPosition, nicht current) für die anfängliche breite Phase untersuchen. Dies würde Ihren Problembereich gut in Gruppen von Kollisionskandidaten aufteilen.

Zweite breite Phase

Führen Sie eine binäre Mehrfachabtastung mit der von Ihnen beschriebenen Kreisschnittmethode durch. Mit anderen Worten:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Diese Genauigkeitsoptimierung könnte auch die Entfernung berücksichtigen - ich denke , die Verwendung des "Längenquadrats" von next - currentwürde ein pixelgenaues Ergebnis erzielen.

Enge Phase

Machen Sie ein binäres Multi-Sample mit etwas wie PMask - die Logik ist genau die gleiche wie oben; nur mit einer anderen Kollisionsroutine.

Schließlich

Sie können aus dem Time-of-Kreuzung arbeiten pointOfCollision, currentund Ihre aktuellen speedund acceleration(vorausgesetzt , Sie einen angemessenen Integrator haben).

Okay, ich habe gesehen, dass Sie Ihre Frage aktualisiert haben, um genauer zu sein. Ich werde versuchen, dir noch mehr zu helfen.

Für Ihre erste Breitphasenprüfung würde ich räumliches Hashing dringend empfehlen .

Im Wesentlichen teilen Sie Ihren Bildschirm in gleich große Raster. Wenn ein Objekt in einem Raster liegt, fügen Sie es einem "Bucket" in einer 1D-Hash-Tabelle hinzu.

Das ist deine erste Überprüfung. Wenn sich Objekte nicht im selben Bucket befinden, können sie sich nicht schneiden.

Wenn Sie damit fortfahren, haben Sie jetzt eine Liste von Buckets mit Objekten (möglicherweise) darin. Sie können hier eine weitere umfassende Prüfung durchführen, indem Sie entweder:

A.) Teilen Sie diesen Bucket in 4 andere Buckets und überprüfen Sie die resultierende 1D-Hash-Tabelle. Wenn sie nicht im selben Eimer sind, keine Kollision.

Oder:

B.) Führen Sie eine einfache Abstandsprüfung durch und berücksichtigen Sie dabei die Breite und / oder Höhe des Objekts, um die Genauigkeit sicherzustellen.

Aber was ist, wenn Sie möglicherweise eine Kollision haben?

Dann würde ich etwas entlang der Linien von empfehlen diese . Es ist im Wesentlichen eine Art Mischung zwischen polygonaler Kollision (für komplexe Formen) oder Rechteck / Kreis für weniger komplexe Formen.

Wenn Sie wirklich "Kollisionen abfangen möchten, bevor sie auftreten, und sie speichern" möchten, können Sie immer Folgendes tun:

Wenn sich zwei Objekte im selben Bucket befinden, können sie kollidieren.

Sind die Objekte außerdem nahe genug, dass sie bald kollidieren können? (Unter Berücksichtigung von Geschwindigkeit, Objektgröße und Entfernung)

Wenn die Antwort auf beide Fragen Ja lautet, speichern Sie sie, um später einen Kreuzungstest durchzuführen.

" Alte Antwort

Nun, leider habe ich den Überblick über mein Handbuch "Alle Kollisionstypen und wofür sie verwendet werden" verloren. :) :)

Obwohl dies eine äußerst umfassende Aufgabe ist, werde ich Ihnen den Einstieg erleichtern.

Es gibt eine gute (beantwortet) Frage wie diese auf etwas Bezug hier .

Sowie einen Artikel von den Leuten, die hier N und N + gemacht haben .

Ganz zu schweigen davon, dass Sie den guten alten Fallback Per-Pixel Collision haben .

Ich bezweifle aufrichtig, dass irgendjemand eine Liste mit jeder Art von Kollision zur Hand hat, aber dies sollte Ihnen den Einstieg erleichtern.

Ich sollte jedoch erwähnen, dass die Art der Kollision, die Sie benötigen (und letztendlich verwenden werden), weitgehend von der Art des Spiels abhängt, das Sie erstellen. Aus diesem Grund finden Sie Tutorials - die meisten Leute gehen davon aus, dass Sie eine Vorstellung davon haben, was Sie wollen, und helfen Ihnen in diesem speziellen Bereich. Mir ist klar, dass die meisten meiner Links Tutorials zu einem bestimmten Thema sind, aber ich denke, ein Tutorial wird Ihnen ehrlich mehr helfen. Eine Liste ist eine Sache, aber wenn Sie selbst über jeden Aufzählungspunkt lesen, können Sie eine fundiertere Entscheidung treffen, die wahrscheinlich Ihren Anforderungen genauer entspricht.