Breitphasige Kollisionserkennungsmethoden?
Ich Baue ein 2D-Physik-engine, und ich möchte hinzufügen, broad phase-Kollisionserkennung, aber ich weiß nur von 2 oder 3 Typen:
- Überprüfen, alles gegen alles andere (O(n^2) Komplexität)
- Fegen und Prune (sort and sweep)
- etwas über Binary Space Partition (nicht sicher, wie dies zu tun)
Aber sicherlich gibt es noch mehr Optionen? was sind Sie? Und kann entweder eine grundlegende Beschreibung der einzelnen zur Verfügung gestellt werden oder links zu Beschreibungen?
Ich habe gesehen, diese aber ich bin zu Fragen, für eine Liste von verfügbaren algorithmen, die nicht die beste für meine Bedürfnisse.
In diesem Fall, "Broad phase-Kollisionserkennung" ist eine Methode, die von Physik-engines, um zu bestimmen, welche Einrichtungen Sie bei Ihrer simulation sind in der Nähe genug, um weitere Untersuchungen und ggf. eine kollisionsauflösung.
InformationsquelleAutor der Frage RCIX | 2009-10-23
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist der beste Ansatz, hängt von der speziellen Verwendung, aber die Quintessenz ist, dass Sie möchten, unterteilen Sie Ihren Raum der Welt, so dass (a) jeder Körper ist in genau einer Unterteilung, (b) jede Unterteilung ist groß genug, dass ein Körper in einer bestimmten Unterteilung kann nur prallen Körper in der gleichen Gebietskörperschaft oder eines angrenzenden Gebiets, und (c) die Anzahl der stellen in einer bestimmten Unterteilung so klein wie möglich.
Wie Sie das tun, hängt davon ab, wie viele Körper, die Sie haben, wie Sie sich bewegen, was Ihre performance-Anforderungen sind, und wie viel Zeit Sie damit verbringen möchten an Ihrem Motor. Wenn Sie sprechen über Körper bewegen, in einem weitgehend offenen Raum, die einfachste Technik würde teilen die Welt in ein raster, wobei jede Zelle ist größer als Ihre größte Objekt, und verfolgen Sie die Liste der Objekte, die in jeder Zelle. Wenn Sie etwas auf der Skala des klassischen arcade-Spiel, kann diese Lösung auch genügen.
Wenn man sich mit dem Körper bewegen, in eine größere Welt, ein einfaches raster wird überwältigend werden ziemlich schnell, und Sie wahrscheinlich wollen, eine Art Baum-basierten Struktur wie quadtrees, wie Arriu schlägt.
Wenn du redest bewegten Körpern um innerhalb der begrenzten Räume statt offener Räume, dann können Sie erwägen, eine BSP-Baum; der Baum Partitionen, die Welt in "space können Sie zu Fuß in' und 'Mauern', und hängte ein Körper in den Baum legt fest, ob es sich in eine rechtliche position. Je nach Welt-geometrie, können Sie auch ein BSP für Ihre broad-phase Detektion von Kollisionen zwischen Körpern in der Welt.
Weitere option für die Einrichtungen bewegen sich im begrenzten Raum wäre ein portal-engine; wenn Ihre Welt besteht aus konvex-polygonalen Regionen, wobei jede Seite des Polygons ist entweder eine Feste Wand oder ein 'portal' zu einem weiteren konkaven Raum, können Sie leicht feststellen, ob ein Körper in einer region mit einem Punkt-in-polygon-test und Vereinfachung von Kollisionserkennung allein an Einrichtungen in der gleichen region oder Regionen verbunden.
InformationsquelleAutor der Antwort Skirwan
Alternative zu QuadTrees oder BSPTrees sind SphereTrees (CircleTrees in 2D, die Umsetzung wäre mehr oder weniger das gleiche). Den Vorteil, dass SphereTrees haben, dass Sie mit großen Lasten von dynamischen Objekten sehr gut. Wenn Sie Objekte sind ständig in Bewegung, BSPTrees und QuadTrees sind viel langsamer in die Aktualisierung als eine Kugel/Kreis Baum wäre.
Wenn Sie haben eine gute Mischung von statischen und dynamische Objekte, die eine einigermaßen gute Lösung ist die Verwendung eines QuadTree - /BSPTree für die Statik und eine Kugel/Turnus Baum für den dynamischen Objekten. Denken Sie daran, dass für jedes Objekt, müssen Sie überprüfen Sie es gegen beide Bäume.
InformationsquelleAutor der Antwort Russell Newquist
Empfehle ich quadtree partitionieren. Es ist ziemlich einfach und es funktioniert wirklich gut. Hier ist ein Flash - demo von brute-force Kollision-Erkennung vs. quadtree-Kollisionserkennung. (Sie können es sagen, zu zeigen, die quadtree-Struktur.) Haben Sie bemerkt, wie quadtree Kollisionserkennung ist nur 3% des brute-force in der demo?
Auch, wenn Sie ernsthaft über Ihre Maschine, dann empfehle ich Sie abholen Echtzeit-Kollisionserkennung. Es ist nicht teuer, und es ist ein wirklich tolles Buch, das deckt alles, was Sie jemals wissen wollen. (Einschließlich GPU basierte Kollisionserkennung.)
InformationsquelleAutor der Antwort zfedoran
Alle von der Beschleunigung von algorithmen abhängen, über einen preiswerten test an, um schnell auszuschließen Objekte (oder Gruppen von Objekten) und damit reduzieren auf die Anzahl von teuren tests, die Sie zu tun haben. Ich sehe die algorithmen in Kategorien, von denen jeder hat viele Variationen.
Räumliche Partitionierung. Schnitzen, Raum und günstig Ausschluss von Kandidaten, die sich in verschiedenen Regionen. Zum Beispiel, BSP, Gitter, octrees, etc.
Objekt partitionieren. Ähnlich wie #1, aber der clustering-konzentriert sich auf die Objekte selbst mehr als den Raum Sie sich befinden. Zum Beispiel, bounding volume Hierarchien.
Art und sweep-Methoden. Legen Sie die Objekte in der Reihenfolge räumlich und ausschließen von Kollisionen unter diejenigen, die nicht aneinander angrenzen.
1 und 2 sind oft hierarchisch, recursing in jede partition als erforderlich. Mit 3 können Sie Optional die Iteration entlang unterschiedlicher Dimensionen.
Trade-offs hängt viel von Szene-geometrie. Objekte von cluster-oder sind Sie gleichmäßig oder Dünn verteilt? Sind Sie alle etwa die gleiche Größe oder gibt es große Unterschiede in der Größe? Ist die Szene dynamisch? Können Sie es sich leisten, eine Menge von preprocessing-Zeit?
Die "Billigen" tests sind eigentlich entlang ein Spektrum von wirklich Billig bis ziemlich-teuer. Die Wahl des besten Algorithmus minimiert das Verhältnis der Kosten für die kostengünstige Prüfung der Reduzierung der Anzahl von teuren tests. Jenseits der algorithmischen Bedenken, dass man in tuning, wie sich Gedanken über die cache-Lokalität.
InformationsquelleAutor der Antwort Adrian McCarthy
Alternative plain-raster, sagen 20x20 oder 100x100 (hängt davon ab, Ihre Welt-und Speicher-Größe). Die Umsetzung ist einfacher als eine rekursive Struktur, wie quad/bsp-Bäume (oder Bereich Bäume für diese Angelegenheit).
Objekte der Kreuzung Zell-Grenzen sind etwas einfacher in diesem Fall, und nicht ausarten, so viel wie eine naive Implementierung einer bsp - /quad - /oct-tree machen könnte.
Mit dieser (oder einer anderen techinques), Sie sollten in der Lage sein, schnell zu pflücken viele Paare und eine Reihe von möglichen Kollisionen, die weitere Untersuchungen erforderlich machen.
InformationsquelleAutor der Antwort Macke
Ich kam mit einer Lösung, die nicht davon abhängig, grid-Größe und ist wahrscheinlich O(nlogn) (das ist das optimum, wenn es gibt keine Kollisionen), aber am schlimmsten O(nnlogn) (wenn alles kollidiert).
Ich auch implementiert und getestet, hier der link zu den Quelle. Aber ich habe nicht den Vergleich zum brute-force-Lösung.
Einer Beschreibung, wie es funktioniert:
(Ich bin auf der Suche nach Kollisionen von Rechtecken)
auf der x-Achse habe ich sozusagen die Rechtecke nach Ihrer rechten Kante ( O(nlogn) )
für jeden rect in die sortierte Liste nehme ich den linken Rand und eine binäre Suche, bis ich finde ist der Rechte Rand am linken Rand am linken Rand und legen Sie diese Rechtecke zwischen diesen Indizes in einer possible_Collision_On_X_Axis set ( das sind n Rechtecke, logn für die binäre Suche, n-fügt int set in O(log n)pro insert)
y-Achse ich habe das gleiche
in jedem der sets habe ich nun mögliche Kollisionen auf x (in einem Satz) und y(int), die ich schneiden diese Sätze, und jetzt habe ich die Kollisionen auf der x-Achse und y-Achse (das heißt, ich nehme die gemeinsamen Elemente) (O(n))
sorry für die schlechte Beschreibung, ich hoffe, Sie verstehen besser, aus der Quelle, auch ein Beispiel hier abgebildet: Bild
InformationsquelleAutor der Antwort csiz
Möchten Sie vielleicht zu prüfen, was Scott Tat, in Streifenhörnchen mit räumlichen Vermischung. Der source ist frei verfügbar. Ich denke, er verwendet eine ähnliche Technik, um Box-2Dwenn nicht die Kollision, auf jeden Fall für den Kontakt Persistenz.
InformationsquelleAutor der Antwort Nick Van Brunt
Wenn der Raum, die Objekte bewegen sich innerhalb begrenzt ist, dann können Sie mit einem Gitter zu unterteilen Ihre Objekte. Legen Sie jedes Objekt in jeder grid-Zelle, die das Objekt umfasst (vollständig oder teilweise). Um zu überprüfen, ob Ein Objekt kollidiert mit einem anderen Objekt, zu bestimmen, welche raster-Zellen-Objekt A deckt, dann bekommen Sie die Liste der einzigartigen Gegenstände in den Zellen, und schließlich test-Objekt Eine gegen jede eindeutige Objekt. Dieser Ansatz funktioniert am besten, wenn die meisten Objekte sind in der Regel in einer einzigen Rasterzelle.
Wenn Ihr Speicherplatz nicht begrenzt wird, dann werden Sie brauchen, um zu implementieren eine Art von dynamischen grid, die wachsen können auf Nachfrage in jeder der vier Richtungen (in 2D).
Der Vorteil dieses Ansatzes über mehrere adaptive algorithsm (also BSP, Quadtree, Circletree) ist, dass die Zellen zugegriffen werden kann, in O(1) Zeit (d.h. in konstanter Zeit) anstatt O(log N) Zeit (D. H. logarithmisch, Zeit). Aber diese algorithmen sind in der Lage, passen selbst für große Variabilität in der Dichte der Objekte. Der grid-Ansatz funktioniert am besten, wenn Objekt-Dichte ist ziemlich konstant über den Raum.
InformationsquelleAutor der Antwort voidstar69
Möchte ich empfehlen, dem einleitenden Verweis auf Spiel-Physik von Ian Millington, Spiel-Physik-Engine-Entwicklung. Es hat einen großen Abschnitt auf der broad phase-Kollisionserkennung mit Beispiel-code.
InformationsquelleAutor der Antwort wojakzek
Ich habe eine quad-tree in einem größeren Projekt, welches gut für Spiel-Objekte, die bewegen sich nicht viel (weniger Umzüge & re-Insertionen). Das gleiche Prinzip gilt für octrees.
Die grundlegende Idee Ist, erstellen Sie eine rekursive Struktur, die speichert 4(quad), oder 8(Okt) child-Objekte des gleichen Typs wie die Baumwurzel. Jeder Knoten im Baum repräsentiert einen Abschnitt des kartesischen Raum, zum Beispiel, -100 -> +100 auf dem jeweiligen Achse. jedes Kind vertritt, die gleichen Raum, sondern unterteilt die Hälfte, ein unmittelbares Kind des Beispiels darstellen würde, zum Beispiel, -100->0 auf der X-Achse, und -100->0 auf der Y-Achse).
Stellen Sie sich ein Quadrat, oder Flugzeug, mit einer Reihe von vorgegebenen Dimensionen. Nun ziehen Sie eine Linie durch die Mitte auf jeder Achse, teilt sich das Flugzeug in 4 kleinere Flugzeuge. Nehmen Sie jetzt einer von Ihnen, Es wieder tun, und wieder, bis Sie einen Punkt erreichen, wenn die Größe der Flugzeug-segment Ist etwa so groß wie ein Spiel-Objekt. Jetzt haben Sie Ihren Baum. Nur Objekte besetzen der gleichen Ebene, können möglicherweise kollidieren. Wenn Sie bestimmt haben, welche Objekte kann kollidieren, erzeugen Sie Paare von möglichen Kollisionen von Ihnen. In dieser Phase, die broadphase abgeschlossen Ist, können Sie sich auf narrow phase-Kollisionserkennung, die Ist, wo Ihr mehr präzise und teure Berechnungen sind.
Zweck der Broadphase, Ist die Verwendung von kostengünstigen Berechnungen zu generieren, die mögliche Kollisionen, und cull aus Kontakte nicht auftreten, wodurch die Arbeit Ihre engen phase-Algorithmus hat zu führen, die wiederum, so dass Ihre gesamte collision detection Algorithmus effizienter.
Also, bevor Sie voran gehen und den Versuch der Umsetzung eines solchen Algorithmus, wie dich selbst:
Wie viele Objekte in mein Spiel?
Wenn es gibt eine Menge, muss ich wohl ein broadphase. Wenn nicht, dann ist die Nnarrowphase sollte ausreichen.
Außerdem bin ich den Umgang mit vielen beweglichen Objekten?
Baum-Strukturen werden allgemein verlangsamt, die von fahrenden Objekten, wie Sie ändern Ihre position in der Struktur im Laufe der Zeit, einfach durch Bewegung. Dies erfordert, dass Gegenstände entfernt werden und wieder eingesetzt werden in jedem frame (potenziell), die weniger als Ideal ist.
Wenn dies der Fall ist, Sie wären besser dran mit Fegen und streichen, hält der min - /max-heaps der extents des shapes in Ihre Welt. Objekte müssen nicht erneut eingefügt werden, aber die Haufen müssen neu sortiert werden jeden frame, dachte, dies ist in der Regel schneller als ein Baum breit, traversal mit Umzug und reinsertions.
Je nach Codierung, kann komplizierter sein, um code über das andere. Persönlich finde ich die Bäume werden mehr intuitiv-code, aber weniger effizient und anfälliger für Fehler, da Sie andere Fragen, wie was zu tun ist, wenn Sie ein Objekt, die direkt sitzt oben auf der Achse oder dem Zentrum des root-Knotens. Dieses Problem kann gelöst werden, indem Sie lose Bäume, die durchaus räumlich überlappen, so dass ein Kind-Knoten ist immer Vorrang über andere, wenn solch ein Fall Auftritt.
InformationsquelleAutor der Antwort Ian Young