Mit vielen Würfeln arbeiten. Verbessernde Leistung?

12

Bearbeiten: Um die Frage zusammenzufassen, ich habe eine Voxel-basierte Welt (Minecraft-Stil (Dank kommunistische Ente)), die unter schlechter Leistung leidet. Ich bin mir der Quelle nicht sicher, hätte aber gerne einen möglichen Rat, wie ich sie loswerden kann.

Ich arbeite an einem Projekt, in dem eine Welt aus einer großen Menge von Würfeln besteht (ich würde Ihnen eine Nummer geben, aber es sind benutzerdefinierte Welten). Mein Test ist um (48 x 32 x 48) Blöcke.

Grundsätzlich machen diese Blöcke nichts für sich. Sie sitzen einfach da.

Sie werden verwendet, wenn es um die Interaktion der Spieler geht.

Ich muss überprüfen, mit welchen Cubes die Maus des Benutzers interagiert (Mouseover, Clicking, etc.) und Kollisionserkennung, wenn sich der Spieler bewegt.

Jetzt hatte ich zuerst eine massive Verzögerung und durchlief jeden Block.

Ich habe es geschafft, diese Verzögerung zu verringern, indem ich alle Blöcke durchlaufen habe und herausgefunden habe, welche Blöcke in einem bestimmten Bereich des Zeichens liegen, und dann nur diese Blöcke für die Kollisionserkennung durchlaufen habe usw.

Ich gehe jedoch immer noch mit einem deprimierenden 2fps.

Hat jemand andere Ideen, wie ich diese Verzögerung verringern könnte?

Übrigens benutze ich XNA (C #) und ja, es ist 3d.

Joel
quelle
Meinen Sie Minecraft-like? Das heißt, Voxel?
Die kommunistische Ente
4
Hast du schon in die Achte geschaut? en.wikipedia.org/wiki/Octree
bummzack
1
Haben Sie versucht, Ihr Spiel zu profilieren? Es werden möglicherweise einige Schlüsselbereiche angezeigt, in denen die meiste Zeit verbracht wird. Möglicherweise ist es nicht das, was Sie denken.
verzögerte
2
Anstatt alle 6 Flächen eines Würfels zu zeichnen, können Sie nur die Flächen zeichnen, die mit nichts in Kontakt stehen
David Ashmore,
1
@David: Ja, oder er könnte aufhören, einen einzelnen Draw-Aufruf pro Würfel auszuführen und sich später um einzelne Polygone kümmern.
Olhovsky

Antworten:

20

Klingt so, als wollten Sie etwas über Bäume lernen!

Und ich meine es ernst, wenn Sie derzeit eine Schleife über ein Array all Ihrer Cubes erstellen, sollten Sie sich wirklich mit verschiedenen räumlichen Datenstrukturen befassen. In diesem Fall können Sie sich Ihre Würfelwelt am besten als Baum vorstellen.

Bevor wir auf die Gründe eingehen, warum, lassen Sie uns über unser Problem nachdenken. Wir suchen nach einer Lösung, mit der wir zu möglichst geringen Kosten eine Liste von Würfeln in der Nähe abrufen können, mit denen der Spieler möglicherweise kollidiert. Diese Liste sollte so klein und genau wie möglich sein.

Um diese Zone zu bestimmen, müssen wir den Koordinatenraum unseres Spielers auf den Koordinatenraum der Würfelkarte abbilden. Das heißt, wir müssen die Gleitkommaposition des Players auf einen diskreten Index des mehrdimensionalen Arrays von Cubes abbilden (Beispielnotation könnte zB world[31][31][31]genau die Mitte für ein mehrdimensionales 64 * 64 * 64-Array sein).

Wir könnten einfach die umgebenden Blöcke mit derselben diskreten Indizierung berechnen, vielleicht nur die nahe gelegenen Würfel abtasten, aber dies erfordert immer noch eine ständige Neuberechnung und lässt keine Objekte zu, die nicht diskret platziert sind (dh möglicherweise nicht dem Würfel zugeordnet sind Karte).

Die ideale Situation ist ein Satz von Eimern, die unsere Würfelsätze für bestimmte Abschnitte unserer Würfelkarte enthalten, die gleichmäßig aufgeteilt sind. Statt die Umgebung neu zu berechnen, bewegen wir uns einfach in diese Zonen hinein und aus diesen heraus . Bei einer nicht trivialen Berechnung kann das Speichern dieser Daten dazu führen, dass nicht alle Cubes wiederholt werden, sondern nur die einzelnen Sets in der Nähe.

Die Frage ist: Wie setzen wir das um?

Stellen Sie sich für die 64 * 64 * 64-Welt vor, dass sie in 8 * 8 * 8- Zonen unterteilt ist . Dies bedeutet, dass Sie in Ihrer Welt 8 Zonen pro Achse haben (X, Y, Z). Jede dieser Zonen enthält 8 Würfel, die mit diesem neuen vereinfachten Index leicht abgerufen werden können.

Wenn Sie eine Operation für eine Gruppe benachbarter Cubes ausführen müssen, anstatt jeden Cube in Ihrer Welt zu durchlaufen, können Sie diese Zonen einfach durchlaufen und dabei die maximale Anzahl von Iterationen von 64 * 64 * 64 (262144) bis auf aufschlüsseln nur 520 (8 * 8 * 8 + 8).

Zoomen Sie nun aus dieser Zonenwelt heraus und ordnen Sie die Zonen in größere Superzonen ein . wobei jede Superzone 2 · 2 · 2 reguläre Zonen enthält . Da Ihre Welt derzeit 512 (8 * 8 * 8) Zonen enthält , können wir die 8 * 8 * 8- Zonen in 64 (4 * 4 * 4) Superzonen aufteilen, indem wir 8 Zonen durch 2 Zonen pro Superzone teilen . Wendet man dieselbe Logik von oben an, würde dies die maximalen Iterationen von 512 auf 8 unterbrechen, um die Superzone zu finden . und dann maximal 64, um die vorgehende Zone zu finden(insgesamt max 72)! Sie können sehen, wie viele Iterationen dadurch bereits gespart werden (262144: 72).

Ich bin sicher, Sie können jetzt sehen, wie nützlich Bäume sind. Jede Zone ist eine Verzweigung im Baum, wobei jede Superzone eine vorangehende Verzweigung ist. Sie durchqueren einfach den Baum, um das zu finden, was Sie brauchen. Verwendung kleinerer Datensätze zur Minimierung der Gesamtkosten.

Das folgende Diagramm soll Ihnen helfen, das Konzept zu visualisieren. (Bild von Wikipedia: Octrees ): Octree

Haftungsausschluss:

In einer idealen Konfiguration wie oben, in der Ihre Voxel-Welt bereits in einem mehrdimensionalen Array fester Größe angeordnet ist, können Sie einfach die Spielerposition abfragen und dann die umgebenden Blöcke mit einem O (1) -Kosten indexieren! (Siehe Olhovskys Erklärung) Dies wird jedoch schwieriger, wenn Sie bedenken, dass Ihre Welt in einem Voxel-Spiel selten eine feste Größe hat. und Sie benötigen möglicherweise Ihre Datenstruktur, um ganze Superzonen von der Festplatte in den Speicher laden zu können. Im Gegensatz zu einem mehrdimensionalen Array mit fester Größe ermöglichen Bäume dies ohne großen Zeitaufwand für kombinatorische Algorithmen.

gebremster Kaviar
quelle
Ich würde sagen, ich verstehe es, aber leider nicht. Die Kollisionsboxen der Blöcke bewegen sich nicht, nur die Kollisionsbox des Spielers. Und ich habe jetzt eine Methode, die (ohne alle Blöcke durchlaufen zu haben) alle Blöcke zurückgibt, die sich innerhalb eines Radius von 5 Blöcken vom Spieler befinden. Entschuldigung für die Mühe, aber keine Klarstellung? Übrigens, um es einfacher zu machen, könnten Sie annehmen, dass die Welt 64 x 64 x 64 ist?
Joel
Und ich bekomme immer noch um die 5fps :(
Joel
Ich habe meine Antwort umformuliert und mich informieren, ob es geholfen hat.
verzögerte
Also schränke ich die Blöcke ein, in denen der Spieler sein könnte, indem ich diese Octree-Technik verwende. Ich bin mir ziemlich sicher, dass ich das verstehe. Aber schlagen Sie vor, dass ich meine Kollisionserkennung verwende, wenn ich sie auf eine kleine Auswahl von Blöcken eingegrenzt habe, oder haben Sie eine andere Methode?
Joel
2
Wenn der Spieler im Verhältnis zur Größe der Würfel nicht sehr groß ist, ist die Überprüfung der Kollision um den Spieler wahrscheinlich der schnellste Weg. Wenn der Spieler beispielsweise nicht mehr als einen Würfel belegt, muss er höchstens 27 umgebende Würfel prüfen, um eine Kollision zu finden. Hierfür ist kein Baum erforderlich, da Sie direkt in diese Cube-Positionen indizieren können, vorausgesetzt, er speichert die Cubes in einem Array, in das er indizieren kann, wobei für jede mögliche Cube-Position ein Slot zugewiesen wird.
Olhovsky
13

Ich stimme Daniels Antwort darin zu, dass das Durchlaufen großer Mengen von Boxen die wahrscheinlichste Ursache ist und dass Sie durch die räumliche Unterteilung das Spiel erheblich beschleunigen könnten - aber das Problem könnte auch anderswo liegen und Sie könnten Ihre Zeit verschwenden .

Um die Geschwindigkeit Ihres Spiels signifikant zu erhöhen, müssen Sie Ihren Code profilieren. Ermitteln Sie, wo sich der Engpass befindet. Auf diese Weise können Sie die größten Verbesserungen vornehmen.

Es gibt viele Möglichkeiten, Ihren Code zu profilieren. Sie können eine eigene Leistungsanalyseklasse erstellen (die die Stopwatch-Klasse (MSDN) verwendet ) oder PIX verwenden, um einen allgemeinen Überblick über die Auslastung der CPU / GPU zu erhalten .

Sie können auch PIX-Ereignismarkierungen in Ihren Code einfügen, die in den PIX-Anzeigen als farbige Bereiche angezeigt werden. Es gibt keine offizielle C # -Schnittstelle für diese Funktionen, aber dieser Thread zeigt, wie Sie eine C # -Schnittstelle selbst erstellen können.

CiscoIPPhone
quelle
2
+1, stimme vollkommen zu. Sie sollten sich nicht mit Algorithmen befassen, sondern sich mit der Profilerstellung Ihres Codes befassen. Ich vermute, es hat nichts mit der Tatsache zu tun, dass Sie durch die Blöcke iterieren (es sind nicht so viele). Es ist das, was Sie mit jedem Block tun. Letztendlich brauchen Sie eine bessere Methode als Brute Force, aber wenn Sie eine einfache Iteration bei 48x32x48-Cubes nicht bewältigen können, müssen Sie überdenken, was Sie mit jedem Cube tun, und nicht, wie Sie eine Schleife erstellen.
Tim Holt
4
@Tim: Wenn sein Player nicht groß genug ist, um einen Bereich von 48 x 32 x 48 zu belegen, sollte er nicht durch so viele Würfel iterieren. Wenn er 73000 Cubes pro Frame durchläuft, kann ich Ihnen ohne Profilerstellung sagen, dass es sich für ihn lohnt, das zu beheben, wenn auch aus keinem anderen Grund, als zu lernen, wie man es vermeidet, zehntausende Male mehr Iterationen durchzuführen als sind notwendig. Dies würde ich nicht als Mikro- oder vorzeitige Optimierung bezeichnen.
Olhovsky
Mein Spieler ist kleiner als die Größe eines Würfels, kann aber irgendwann größer sein (aber nicht viel)
Joel
Randomman159: Dann musst du nur noch gegen seine umliegenden 27 Würfel testen, um eine Kollision zu finden. Siehe meine Antwort.
Olhovsky
6

Wenn Ihr Player im Verhältnis zur Größe der Cubes groß ist, möchten Sie wahrscheinlich eine Octree- oder eine andere räumliche Partitionierungsstruktur, wie von anderen vorgeschlagen.

Wenn Ihr Player jedoch im Verhältnis zur Größe der Würfel klein ist, besteht die wahrscheinlich schnellste Möglichkeit, eine Kollision mit den Würfeln zu erkennen, darin, den Bereich um den Player herum linear zu durchsuchen.

Da Ihr Spieler kleiner als 1 Würfel ist, müssen Sie höchstens 27 benachbarte Würfel auf Kollision testen.

Dies setzt voraus, dass Sie die Cubes in einem Array speichern, in das Sie einen Index einfügen können, wobei für jeden Cube ein Slot im Array vorhanden ist.

Wie bereits erwähnt, müssen Sie Ihren Code profilieren, um festzustellen, was Sie tatsächlich verlangsamt.

Wenn ich allerdings raten müsste, würde ich sagen, dass Sie wahrscheinlich für jeden Würfel einen Draw Call machen, was bei weitem Ihr Engpass wäre. Um dies zu beheben, sollten Sie sich mit der Geometrieinstanzierung befassen.

Olhovsky
quelle
Sie können auch einen Begrenzungsrahmen um den Player haben und dann einfach überprüfen, mit welchen Objekten der Player kollidieren soll. Eine gute Physik-Engine kann alle Optimierungen für Sie durchführen. Es ermöglicht auch, dass mehr als nur "Blöcke" kollidieren.
verzögerte
Persönlich möchte ich mich nicht auf die breite Phase einer Physik-Engine verlassen, um für mich 73000 Cubes zu testen, wenn ich nur etwa zwei Dutzend Codezeilen schreiben könnte, um für mich effizient auf Kollisionen zu testen. Außerdem hat er wahrscheinlich noch keine Physik-Engine, auf die er zugreifen kann.
Olhovsky
1

Noch ein Vorschlag, um die Dinge zu beschleunigen: Deine Blöcke sind ungefähr fixiert - das bedeutet, dass ein Spieler mit den meisten von ihnen nicht kollidieren kann. Fügen Sie Blöcken einen Booleschen Wert hinzu, der angibt, ob sie verfügbar sind oder nicht. (Dies kann durch Betrachten der Nachbarn neu berechnet werden.) Ein Block, der nicht freigelegt ist, muss nicht auf Kollisionen überprüft werden.

Es ist offensichtlich, dass Minecraft etwas Ähnliches tut - ich habe einmal einen nicht geladenen Block getroffen, der mir einen Blick in die Welt ermöglichte - ich konnte durch den festen Boden hindurch sehen, alles, was sich zeigte, waren die offenen Räume (die andere Seite von sie war eine exponierte Oberfläche und daher gerendert.)

Loren Pechtel
quelle
-1

Ich hatte dieses Problem mit meinem Voxel-Motor.

Lösung: (Viel einfacher als Octrees) Anstatt alle Blöcke zu durchlaufen, verwenden Sie einfach eine Gleichung, um die Position des Blocks im Blockarray zu bestimmen.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Dann, wenn Sie sehen möchten, ob ein Block existiert:

Blocks[BlockIndex].Type > -1;

Oder Sie bestimmen, ob der Block existiert.

BMW
quelle
Das Problem hier ist komplizierter, weil Sie nur 2 Koordinaten für Ihre Maus haben, um mit 3D-Welt zu testen. Wenn die Ansicht von oben nach unten war, konnten Sie 2 von 3 rechten Indizes für eine Mausposition finden und dann eine Schleife für die Höhe ausführen, beginnend von oben - näher an der Kamera, und das erste Auftreten eines Blocks feststellen.
Markus von Broady