Wie kann ich eine schnelle und genaue 2D-Kollisionserkennung implementieren?

11

Ich weiß genau, wie man erkennt, ob zwei oder mehr 2D-Objekte kollidieren, aber ich bin daran interessiert, wie man entscheidet, ob nach einer Kollision gesucht wird. In früheren Projekten ließ ich einfach jedes Objekt mit jedem anderen Objekt vergleichen (ich weiß, O (n ^ 2) Dummheitsgrad) und es entstand ein weniger flüssiges Gameplay.

Verschiedene Foren begrüßen die Größe von Quadtrees, B-Trees und jeder anderen Art von Baum oder Struktur, die Sie sich vorstellen können.

Was ist die effizienteste Struktur, um zu bestimmen, ob eine Kollision überprüft werden soll?

2d collision-detection data-structure Mike Cluck
quelle
1
Eine Sache, die Sie in Betracht ziehen sollten, ist, nur Kollisionen auf Objekte zu überprüfen, die sich bewegt haben, und nur die Objekte, die sich in Ihrer Nähe befinden. Mein aktuelles System funktioniert gut (Hunderttausende von Objekten) - und das ist alles, was ich tue.
Ultifinitus
Ich denke, gamedev.stackexchange.com/questions/14369/… könnte Ihnen sehr helfen. Es war ursprünglich für und Algorithmus für die Parallelverarbeitung gedacht, aber ich denke, der gleiche Algorithmus könnte auch Single-Threaded-Anwendungen verbessern.
Ali1S232
1
@ultifinitus Das ist im Wesentlichen das, worüber ich frage. Wie bestimme ich, welche Objekte sich in der Nähe befinden, ohne jedes Objekt zu durchlaufen und seine Position zu überprüfen?
Mike Cluck
Mike, du kannst mir eine E-Mail mit einem bestimmten Code senden, den ich verwendet habe. Er ist in C ++ - oder ich kann dir die Grundstruktur geben, obwohl er dadurch möglicherweise mehrdeutig und kompliziert wird.
Ultifinitus
1
Es ist kein Duplikat, weil ich gefragt habe, welche Art von Struktur am besten geeignet ist, um festzustellen, ob wir uns die Mühe machen sollten, nach einer Kollision zu suchen. Bei dieser anderen Frage ging es um transparente und nicht transparente Kollisionen. Ganz zu schweigen davon, dass diese Frage etwa ein Jahr vor der von Ihnen verlinkten gestellt wurde.
Mike Cluck

Antworten:

12

Bei einem 2D-Spiel ist ein einheitliches Raster fast immer der richtige Weg, es sei denn, die 2D-Objekte sind auf einer Seite Ihrer Karte sehr stark verteilt. Die Speicherkomplexität ist unkompliziert (proportional zu den Abmessungen Ihrer Karte) und weist bei einer angemessenen Verteilung eine Nachschlagzeit von O (1) und einen Durchschnitt von log (numberOfObjects / (Zeilen * Spalten)) ^ 2 Schnittpunkttests auf pro Zelle gemacht. Möglicherweise möchten Sie nur Zellen überprüfen, in denen sich ein Objekt bewegt hat, wodurch die statische Geometrie wesentlich effizienter wird. Es ist einfach, ein einheitliches Raster im laufenden Betrieb zu ändern (viel weniger schmerzhaft als bei baumbasierten Lösungen), und es ist einfacher zu implementieren. Das einzige Mal, wenn ich sagen würde, dass es nicht in einem 2D-Spiel verwendet werden soll, ist, wenn der Speicherbedarf eines einheitlichen Gitters zu groß wird (z. B. eine Raumsimulation, bei der die Ebenen spärlich, aber enorm sind).

Darcy Rayner
quelle
Wie geht diese Lösung mit Objekten um, die an 2 oder 4 Gitterzellen grenzen?
Asche999
1
Jede Zelle, in der sich das Objekt überlappt, wird als solche betrachtet, sodass sich ein Objekt in mehreren Zellen befinden kann. Die meisten Geodatenstrukturen werden das Problem der Überlappungen auf ähnliche Weise behandeln.
Darcy Rayner
Wow, das ist ziemlich klug. +1 Prost, Alter.
Asche999
1

Wenn Ihre Welt im Vergleich zu anderen eine sehr "lange" Dimension hat (nennen Sie sie X), können Sie die Objekte in einer geordneten Liste behalten, die Sie während der Bewegung neu sortieren können. Kollisionserkennung bedeutet dann, nur nach Objekten zu suchen, die Überlappung in der X-Achse.

Eine andere Möglichkeit besteht darin, aktive / passive Listen von Objekten zu führen und sich nicht um die passiven Objekte zu kümmern (die sich überhaupt nicht bewegen).

Wenn es sich um mittelgroße Objekte handelt, die für den Spieler auf dem Bildschirm sichtbar sind, ist wahrscheinlich alles gegen alles nicht schlecht.

Davon abgesehen bin ich bei Darcy, ein einheitliches Gitter ist gut.

MarkR
quelle