Raumaufteilung, wenn sich alles bewegt

Hintergrund

Zusammen mit einem Freund arbeite ich an einem 2D-Spiel, das im Weltraum spielt. Um es so immersiv und interaktiv wie möglich zu gestalten, möchten wir, dass Tausende von Objekten frei herumschweben, einige zusammen gruppiert, andere im leeren Raum treiben.

Herausforderung

Um die Rendering- und Physik-Engine zu entlasten, müssen wir eine Art räumliche Partitionierung implementieren. Wir müssen zwei Herausforderungen bewältigen. Die erste Herausforderung besteht darin, dass sich alles bewegt, sodass die Rekonstruktion / Aktualisierung der Datenstruktur extrem kostengünstig sein muss, da sie in jedem Frame durchgeführt werden muss. Die zweite Herausforderung ist die Verteilung von Objekten, wie bereits erwähnt, dass es möglicherweise Cluster von Objekten und riesige Teile des leeren Raums gibt, und um es noch schlimmer zu machen, gibt es keine Grenze zum Raum.

Bestehende Technologien

Ich habe mir vorhandene Techniken wie BSP-Bäume, QuadTrees, kd-Bäume und sogar R-Bäume angesehen, aber soweit ich das beurteilen kann, passen diese Datenstrukturen nicht perfekt zusammen, da viele Objekte aktualisiert wurden, die in andere Zellen verschoben wurden ist relativ teuer.

Was ich versucht habe

Ich habe die Entscheidung getroffen, dass ich eine Datenstruktur benötige, die mehr auf schnelles Einfügen / Aktualisieren ausgerichtet ist als auf die Rückgabe der geringstmöglichen Anzahl von Treffern bei einer Abfrage. Zu diesem Zweck habe ich die Zellen implizit gemacht, damit jedes Objekt anhand seiner Position berechnen kann, in welcher Zelle (n) es sich befinden soll. Dann verwende ich eine HashMap, die Zellkoordinaten auf eine ArrayList(den Inhalt der Zelle) abbildet . Dies funktioniert ziemlich gut, da bei "leeren" Zellen kein Speicher verloren geht und es einfach ist zu berechnen, welche Zellen untersucht werden sollen. Das Erstellen all dieser ArrayLists (Worst Case N) ist jedoch teuer und wächst häufig HashMap(obwohl dies durch eine große Anfangskapazität leicht gemildert wird).

Problem

OK, das funktioniert, ist aber immer noch nicht sehr schnell. Jetzt kann ich versuchen, den JAVA-Code zu optimieren. Ich erwarte jedoch nicht zu viel davon, da der Profiler mir sagt, dass die meiste Zeit für die Erstellung all der Objekte aufgewendet wird, die ich zum Speichern der Zellen verwende. Ich hoffe, dass es einige andere Tricks / Algorithmen gibt, die dies viel schneller machen. So sieht meine ideale Datenstruktur aus:

• Die Priorität Nummer eins ist die schnelle Aktualisierung / Rekonstruktion der gesamten Datenstruktur
• Es ist weniger wichtig, die Objekte fein in gleich große Bins zu unterteilen. Wir können ein paar zusätzliche Objekte zeichnen und ein paar zusätzliche Kollisionsprüfungen durchführen, wenn dies bedeutet, dass die Aktualisierung etwas schneller ist
• Speicher ist nicht wirklich wichtig (PC-Spiel)

Die von Ihnen verwendete Technik ist einer rechnerphysikalischen Technik namens Molekulardynamik sehr ähnlich, bei der die Trajektorien von Atomen (normalerweise jetzt im Bereich von 100k bis 10M Teilchen) mit sehr kleinen Zeitschritten verfolgt werden. Das Hauptproblem besteht darin, dass Sie zur Ermittlung der Kraft auf ein Partikel seine Position mit der Position jedes anderen Partikels vergleichen müssen, das sehr schlecht skaliert (n Quadrat).

Ich kann einen Trick vorschlagen, bei dem Sie eine maximale Entfernung auswählen müssen, über die die Dinge interagieren können. Als Ausgangspunkt würde ich mit etwa 1/10 der langen Dimension Ihres Raums beginnen und mich an den Geschmack anpassen (längerer Cutoff bedeutet genauere, aber mehr Berechnungen).

Die Methode besteht darin, jedes Teilchen (i) zu durchlaufen. (I) erhält ein Array, in dem alle Partikel im Bereich von i zum Array hinzugefügt werden. Was Sie am Ende erhalten, ist ein 2d-Array, wobei der i-te Eintrag ein Array des Partikels im Bereich von i ist. Um die Kräfte für i zu berechnen, müssen Sie nur die Einträge im Array von i überprüfen.

Die Kunst dieser Methode besteht darin, den Grenzabstand und die zusätzliche Polsterung (z. B. 20%) auszuwählen. Der Geschwindigkeitsgewinn besteht darin, dass Sie nur einige Wechselwirkungen für jedes Partikel überprüfen müssen und die Nachbarn nur alle paar Schritte neu berechnen. Ich würde vorschlagen, eine etwas schnelle Geschwindigkeit zu wählen und herauszufinden, wie viele Zeitschritte erforderlich wären, um die "Polster" -Region zu durchqueren. Wenn Sie die Polsterung vergrößern (50% oder sogar 100% des Grenzwerts), erhalten Sie mehr Schritte zwischen der Neuberechnung der Nachbarn, aber jeder Schritt wird etwas langsamer. Der Ausgleich ist ein Kompromiss.

Ein weiterer Trick bei der Berechnung der Entfernungen besteht darin, mit d ^ 2 anstelle von d zu arbeiten und eine Reihe von Aufrufen von pow () und sqrt () zu entfernen.

Bearbeiten: Es ist schwer, einen Ref-Link zu finden, der nicht besonders technisch ist. Dies ist der einzige, den ich finden konnte.

Ihre eigene Lösung klingt ziemlich gut, wenn Sie die Datenstruktur in o (n) erstellen können, dann würde ich sagen, dass die Optimierung eher über die Wahl der Datenstruktur als über den Algorithmus erfolgen muss.

Ich habe eine ähnliche Implementierung mit einigen Unterschieden: Die Hauptdatenstruktur ist ein Array mit fester Größe (wie ArrayList), das am besten für den direkten Zugriff auf ein Element geeignet ist. Jede Zelle des Arrays enthält eine verknüpfte Liste, die sich am besten für Einfügungen eignet und so gut wie eine Array-Liste ist, in die Sie eine Schleife einfügen können. Wir müssen später Elemente aus der verknüpften Liste löschen. Um diesen Vorgang sehr schnell zu machen, sollten Sie in jedem Element der Liste einen Iterator speichern, der auf sich selbst verweist (Sie sagten, der Speicher sei kein Problem, oder?).

Zur Initialisierung wird jedes "Partikel" am Ende der verknüpften Liste eingefügt, die der Zelle im Array entspricht, die ihrer Position im Raum entspricht, vorausgesetzt, der Raum ist in Kacheln fester Größe unterteilt. Wir sind also immer noch mit o (n) Komplexität, aber wir optimieren das Ganze, indem wir Container verwenden, die besser auf die Verwendung abgestimmt sind.

Jedes "Partikel" hat einen Verweis auf seine verknüpfte Liste, um einen schnellen Zugriff auf seine Nachbarn zu ermöglichen.

Bei jedem Frame können wir die Interaktion zwischen jedem Partikel mit seiner Liste von Nachbarn durchführen, und ich würde auch mit den 8 umgebenden Kacheln sagen, um Schwelleneffekte in der Nähe von Kachelrändern zu vermeiden.

Es ist nicht erforderlich, die gesamte Partitionierung bei jedem Frame neu zu berechnen. Wir müssen ein Objekt nur entfernen und erneut platzieren, wenn es sich mehr als eine bestimmte Strecke bewegt oder aus Sicherheitsgründen alle X Frames. Eine Idee könnte sein, die Position jedes Elements zu dem Zeitpunkt zu speichern, zu dem es in eine verknüpfte Liste eingefügt wurde, und an jedem Frame die aktuelle Position mit der alten zu vergleichen.