Gestalten Sie Ihre Anzeigeliste mit räumlichen Hashes neu

In jedem 2D-Spiel müssen Sie wissen, in welcher Reihenfolge Sie Ihre Sprites zeichnen müssen. Sie zeichnen normalerweise von der Rückseite der Szene nach vorne, wobei die früheren Objekte durch die späteren Objekte verdeckt werden. Dies ist der Standard-Painter-Algorithmus, der verwendet wird, um die Tiefe auf einer Leinwand darzustellen (digital oder anderweitig)..

Von Zapyon - Eigene Arbeit, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Die einfachste Möglichkeit, dies nachzuverfolgen, besteht darin, alle Ihre Objekte in einem großen Array anzuordnen, sortiert nach ihrer Tiefe. In der obigen Szene würde Ihr Array also ungefähr so ​​aussehen: [Berg, Boden, Baum1, Baum2, Baum3,…]

Das Problem mit einem einzelnen großen Array

Das Problem bei einer zentralen Anzeigeliste besteht darin, dass es nicht einfach ist, zu einem bestimmten Zeitpunkt herauszufinden, welche Objekte auf dem Bildschirm angezeigt werden. Dazu müssen Sie das gesamte Array durchlaufen und jedes einzelne Objekt überprüfen. Dies wird meistens zu einem Problem, wenn Sie eine große Spielwelt haben, in der sich viele Objekte außerhalb des Bildschirms befinden und nicht gerendert oder aktualisiert werden sollten.

Ein räumlicher Hash ist eine Methode zum Speichern Ihrer Objekte, um dieses Problem zu vermeiden. Das Schöne an der Verwendung eines Hash ist, dass es immer eine konstante Zeit dauert, um herauszufinden, welche Objekte auf dem Bildschirm angezeigt werden, unabhängig davon, wie groß die Spielwelt ist!

Die meisten Game-Engines lassen Sie nicht mehr damit zu, wie sie ihre Objekte intern strukturieren, aber wenn Sie in einer Umgebung programmieren, in der Sie die Kontrolle über die Draw-Aufrufe haben (z. B. Ihre eigene OpenGL-Engine, ein reines JavaScript) Spiel, oder mehr offene Frameworks wie LÖVE), könnte dies eine Implementierung wert sein.

Die Alternative: räumliche Hashes

Ein räumlicher Hash ist nur ein Hash-Tabelle, wobei jeder Schlüssel eine 2D-Koordinate ist und der Wert ist eine Liste von Spielobjekten in diesem Bereich.

Stellen Sie sich vor, dass Ihre Welt in ein Raster aufgeteilt ist, sodass jedes Objekt zu mindestens einer Zelle gehört. So würden Sie etwas an Position (420.600) nachschlagen, wenn Sie dies in JavaScript implementiert hätten:

var X, Y = 420 600; // X und Y am Raster ausrichten X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Prüfen Sie nun, welche Elemente sich in dieser Position befinden. SpatelHash [X + "," + Y] // Dies ist eine Liste von Objekten in dieser Zelle

So einfach ist das! Sie können sofort wissen, was in dieser Position ist. Der Schlüssel ist eine Zeichenkettenverkettung der X- und Y-Koordinaten, dies ist jedoch nicht der Fall haben um eine Zeichenfolge zu sein, braucht es auch kein Komma in der Mitte; es muss nur für jedes Paar von X und Y eindeutig sein.

Um herauszufinden, warum das so praktisch ist, überlegen Sie, wie Sie die Objekte an dieser Position mit einem großen Array erhalten:

var X = 420; var Y = 600; für (var i = 0; i
Wir prüfen jedes einzelne Objekt, auch wenn die meisten davon sehr weit entfernt sind! Dies kann Ihre Leistung stark beeinträchtigen, wenn Sie viele Suchvorgänge wie diese und Ihre durchführen gameObjects Array ist riesig.
Ein konkretes Beispiel
Wenn Sie noch nicht überzeugt sind, wie nützlich dies sein kann, haben wir eine Demo in reinem JavaScript geschrieben, in der ich versuche, eine Million Objekte in der Spielwelt zu rendern. In beiden Fällen werden nur die Objekte auf dem Bildschirm tatsächlich gerendert.
Klicken Sie hier, um die Live-Demo zu sehen!
Und die Live-Version des räumlichen Hashs.
Die Version mit einem Array ist schmerzhaft langsam. Selbst wenn Sie speichern, welche Elemente auf dem Bildschirm angezeigt werden, sodass Sie nicht jedes Bild überprüfen müssen, müssen Sie das gesamte Array noch einmal überprüfen, wenn sich die Kamera bewegt, was zu starkem Abplatzen führt.
Eine Änderung der Art und Weise, wie wir unsere Spielobjekte speichern, kann den Unterschied zwischen einem reibungslosen Spiel und einem unspielbaren Spiel ausmachen.
Ein räumliches Hash implementieren
Ein räumlicher Hash sollte in jeder Sprache sehr einfach zu implementieren sein (vom ersten Beispiel zum zweiten Beispiel wurden nur 30 zusätzliche Codezeilen benötigt!)
Es gibt vier Schritte, um dies als Ihr Renderingsystem zu implementieren:
 
Richten Sie die Hashtabelle ein.
 
Objekte im Hash hinzufügen und entfernen.
 
Sammeln Sie Objekte in einem bestimmten Bereich.
 
Sortieren Sie Objekte nach Tiefe, bevor Sie sie rendern.
 
Sie können eine funktionale Implementierung in JavaScript auf GitHub als Referenz sehen.
1. Richten Sie die Hash-Tabelle ein
Die meisten Sprachen haben eine Art eingebaute Hashtabelle / Karte. Unser räumlicher Hash ist nur eine Standard-Hashtabelle. In JavaScript können Sie einfach eines deklarieren mit:
var spaticalHash = ; var CELL_SIZE = 60;
Die einzige andere Sache, die Sie hier erwähnen müssen, ist, dass Sie bei der Auswahl der Zellengröße einen gewissen Spielraum haben. Im Allgemeinen scheint es gut zu funktionieren, wenn Ihre Zellen doppelt so groß sind wie Ihr durchschnittliches Objekt. Wenn Ihre Zellen zu groß sind, ziehen Sie bei jeder Suche zu viele Objekte ein. Wenn sie zu klein sind, müssen Sie mehr Zellen markieren, um den gewünschten Bereich abzudecken. 
2. Hinzufügen und Entfernen von Objekten im Hash
Das Hinzufügen eines Objekts zum Hash ist nur eine Angelegenheit, die es an einer Zelle ausrichtet, das Zellenarray erstellt, falls es nicht existiert, und es zu diesem Array hinzufügen. Hier ist meine JavaScript-Version:
spaciousHash.add = Funktion (Objekt) var X = Math.round (Objekt.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (obj.y / CELL_SIZE) * CELL_SIZE; var-Taste = X + "," + Y; if (spaticalHash [key] == undefined )oodthash [key] = []oodhash [key] .push (obj)
Es gibt jedoch eine Einschränkung: Was ist, wenn Ihr Objekt mehrere Zellen umfasst oder zu groß ist, um in eine Zelle zu passen?
Die Lösung ist, es einfach hinzuzufügen alles die Zellen, die es berührt. Dies garantiert, dass das Objekt gerendert wird, wenn ein Teil des Objekts sichtbar ist. (Natürlich müssen Sie auch sicherstellen, dass Sie diese Objekte nicht mehrmals rendern.)
Ich habe in meinem Beispiel keine Remove-Funktion implementiert, aber das Entfernen eines Objekts ist nur eine Frage des Entfernens des Arrays (der Arrays), zu dem es gehört. Um dies zu vereinfachen, kann jedes Objekt einen Verweis darauf enthalten, zu welchen Zellen es gehört.
3. Sammeln Sie Objekte in einem bestimmten Bereich
Hier ist der Kern dieser Technik: Wenn Sie einen Bereich auf dem Bildschirm haben, möchten Sie alle Objekte darin aufnehmen können.
Hier müssen Sie nur alle Zellen durchgehen, die sich auf die Position Ihrer Kamera in der Spielwelt beziehen, und alle Unterlisten in einem Array zusammenfassen, um sie zu rendern. Hier ist das relevante JavaScript-Snippet:
var padding = 100; // Padding, um zusätzliche Zellen an den Rändern zu packen, damit der Spieler Objekte nicht als "Pop" -Oberflächen wahrnimmt. var startX = -camX - Auffüllen; var startY = -camY - Auffüllen; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.height + padding; var onScreen = [] für (var X = startX; X < endX; X += CELL_SIZE) for(var Y = startY; Y < endY; Y += CELL_SIZE) var sublist = spatialHash.getList(X,Y) if(sublist != undefined)  onScreen = onScreen.concat(sublist)   
4. Sortieren Sie die Objekte vor dem Rendern nach Tiefe
Möglicherweise haben Sie inzwischen erkannt, dass das Aufgeben der großen Anzeigelistenidee auch bedeutet, dass Sie die bequeme Tiefensortierung aufgeben. Wir holen Objekte aus unserem Raster nach ihrem Standort, aber das Array, das wir erhalten, ist in keiner Weise sortiert. 
Als letzten Schritt vor dem Rendern müssen wir unser Array nach Schlüssel sortieren. Ich habe jedem Objekt einen Tiefenwert gegeben, und so kann ich Folgendes tun:
onScreen.sort (Funktion (a, b) return a.depth> b.depth) 
Vor dem endgültigen Rendern alles:
für (var i = 0; i
Dies ist einer der Nachteile dieser Methode. Sie müssen sortieren, was auf jedem Bildschirm angezeigt wird. Sie können dies immer beschleunigen, indem Sie sicherstellen, dass alle Unterlisten sortiert sind. Sie können sie während der Verkettung zusammenführen, um die Reihenfolge aufrechtzuerhalten.
Das ist es! Sie sollten jetzt ein (hoffentlich viel schnelleres) funktionierendes Wiedergabesystem haben!
Andere Verwendungen und Tipps
Dies kann eine wirklich nützliche Technik sein, aber wie ich in der Einführung sagte, können Sie dies nur in einer Spiel-Engine oder einem Framework tun, das Ihnen die Kontrolle über die Draw-Aufrufe gibt. Neben dem Rendern können Sie jedoch auch räumliche Hashes verwenden. Tatsächlich werden sie häufig verwendet, um die Kollisionserkennung zu beschleunigen (Sie können Kollisionsprüfungen für Objekte, von denen Sie wissen, dass sie weit entfernt sind oder sich nicht in derselben Zelle befinden, überspringen)..
Eine andere Technik, die räumlichen Hashes ähnelt, aber etwas komplizierter ist, ist die Verwendung eines Quadtrees. Während ein räumlicher Hash nur ein flaches Gitter ist, ist ein Quadtree eher eine hierarchische Struktur, so dass Sie sich keine Gedanken über die Zellengröße machen müssen und Sie können schneller alle Objekte in einem bestimmten Bereich erhalten, ohne dass Sie ein wenig nachprüfen müssen Zelle.
Im Allgemeinen sollten Sie bedenken, dass eine räumliche Struktur nicht immer die beste Lösung ist. Es ist ideal für ein Spiel mit:
 
eine große Welt mit vielen Objekten
 
im Vergleich zur Weltgröße relativ wenige Objekte auf dem Bildschirm
 
meist statische Objekte
 
Wenn sich alle Ihre Objekte ständig bewegen, müssen Sie sie ständig entfernen und zu verschiedenen Zellen hinzufügen, was einen erheblichen Leistungsabfall nach sich ziehen kann. Es war ein ideales Wiedergabesystem für ein Spiel wie Move oder Die (fast verdoppelt die fps), da die Levels aus vielen statischen Objekten bestanden und die Charaktere die einzigen waren, die sich bewegten.
Wir hoffen, dass Ihnen dieses Tutorial vermittelt, wie die räumliche Strukturierung von Daten eine einfache Möglichkeit ist, die Leistung zu steigern, und wie Ihr Rendingsystem nicht immer eine einzige lineare Liste sein muss!



		
			
	   
	




Spielentwicklung