Welche Technik sollte verwendet werden, um 2d Kollisionsprüfungen zu bereinigen?

Question

Von Anfang an fühlt sich die Kollisionserkennung an wie ein O (n^2) Problem.

Sie haben eine Reihe von Objekten und Sie müssen überprüfen, ob jedes Objekt mit einem der anderen Objekte kollidiert. Ich weiß jedoch, dass es sehr ineffektiv ist, jedes Objekt gegen alle anderen Objekte zu prüfen. Warum sollte eine relativ teure Kollisionsprüfung zwischen zwei Bällen stattfinden, wenn sie nicht einmal nahe beieinander sind?

Hier ist Beispiel meines einfachen Programms arbeite mich an:

Wenn Sie 1000 Kugeln haben dann, wenn Sie mit der naiven Kollisionserkennung gehen würden Sie 1000^2 Sammlung überprüft haben (a Million)! Diese Kollisionsprüfung wurde schnell zum Engpass in meiner Anwendung. I benötigen, um einige umfassende Phasenschnitt zu implementieren.

Welche Techniken sollten verwendet werden, um Kollisionskontrollen bei der Arbeit mit 2D - kreisförmigen Objekten zu reduzieren? Ich habe über QuadTrees, BSP, räumliches Hashing usw. gelesen, aber es ist schwierig herauszufinden, welche Methode für diesen Anwendungsfall am besten geeignet ist.

Weiß jemand, was am besten funktioniert?

Answer 1

räumliche Hashing.

Answer 2

Ich würde QuadTrees oder irgendetwas, das kompliziert ist, nicht verwenden, weil Sie ständig balancieren und Bäume ausgleichen werden, während sich Bälle zwischen ihnen bewegen. Es wäre wahrscheinlich effizienter, nur ein Gitter zu haben - jedes Mal, wenn Sie einen Ball bewegen, können Sie einfach berechnen, in welcher Gitterzelle er sich befindet, und ihn dort hineinwerfen, wenn er sich ändert. Und jedes Mal, wenn Sie eine Kollisionsprüfung durchführen müssen, können Sie einfach Bälle überprüfen, deren Mittelpunkt sich entweder in Ihrem Gitter befindet, oder in benachbarten, wenn Sie ausreichend nahe an der Kante sind.

Sie können mit der Gittergröße experimentieren, um das Optimum zu finden. Sie können feststellen, dass es davon abhängt, wie viele Bälle Sie haben.

Ich sagte dies in einem Kommentar unten, aber ich denke, es verdient, ein Teil der Antwort zu sein: Nur Kollisionserkennung, wenn etwas bewegt, so müssen Sie nur das bewegende Ding gegen Dinge in seinem Rasterfeld überprüfen (und (wie oben erwähnt). Auf diese Weise werden die Objekte, die sich nicht bewegen, auf keinen Fall auf Kollisionen überprüft, da sich in ihrem Raster nichts bewegt und auch nichts in ihr Gitter hinein oder hinaus bewegt wird.

Answer 3

Ich zweite die Grid-Methode. Eine 2D-Simulation von Bällen wird nicht von QuadTrees (die im Allgemeinen verwendet werden, wenn Sie komplexe Geometrie wie Charaktere und Gebäude haben) oder BSPs (die Sie wählen sollten, wenn Sie eine sehr ungleichmäßige Verteilung/Konzentration von Objekten haben, wie mit hoher Konzentration Bereiche und Bereiche mit geringer Konzentration, in einem Multiplayer oder Strategiespiel)