Mit vielen Würfeln arbeiten. Verbessernde Leistung?

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.

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 ):

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.

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.

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.

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.)

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.