spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Also bei Galactineers habe ich das so gemacht, dass es nicht einen Speicherort für alle Blöcke gibt, sondern es (wie ja bei Minecraft auch) Chunks gibt, die jeweils ihre eigene Blockliste enthalten. Bei Minecraft sind die 16x16 groß, bei mir 32x32. Chunks brauchte ich sowieso, aufgrund des Nachladens über das Netzwerk und der "unendlich" großen Karte. Die Tatsache, dass sich die Blöcke in den Chunks befinden, habe ich mir aber auch bei dem Anklick-Problem zunutze gemacht:
Als erstes prüfe ich, welche Chunks mein Ray schneidet und dann brauche ich nur noch die Blocklisten der getroffenen Chunks durchgehen. Am Ende bekomme ich eine Liste aller getroffenen Blöcke und da schaue ich dann nur noch nach, welcher der am nächsten zur Kamera ist und habe meinen getroffenen Block. Und für den einzelnen Block prüfe ich dann nochmal die 6 Seiten ab (gleiche Methode), welche da getroffen wurde.
Auf diese Weise, indem du die gesamte Menge auf immer kleiner werdende Segmente zusammenstauchst, kannst du den Rechenaufwand logarithmisch herunterbrechen im Vergleich dazu, alle Blöcke zu prüfen.

Zitat von »Fatov«

Aber das

	C-/C++-Quelltext
1	sinf(ry), cosf(ry - M_PI), sinf(rx)

kann nicht falsch sein.
Das zeigt genau in die Richtung, in die ich mit der Kamera gucke.

Du hast x=sin(ry), z=-cos(ry) und y = sin(rx). Damit ist bei einer Rotation von rx = 90° und ry= 0° die Richtung (0,-1,-1), also nicht direkt nach oben, sondern nach oben in einem 45° Winkel. Also ist das definitiv falsch.

Wieso muss man irgendwelche Listen durchgehen? Man kann anhand der x/y/z-Position ganz prima direkt den Index des jeweiligen Blocks ausrechnen.

Wahrscheinlich benutzt er pro Chunk eine Liste, weil der größte Teil des Raums leer ist, und er dadurch Speicher spart.
Man könnte aber auch ein assoziatives Array (Hash-Array) mit einem Integer-Tripel als Index nehmen.

Im Übrigen ist es schon sinnvoll, eine andere Datenstruktur zu benutzen als das Grid - nämlich eine, die große leere Räume zusammenfassen kann, so dass diese schnell übersprungen werden können. Ansonsten läuft man für einen Strahl, der nichts trifft oder erst in großer Entfernung, unnötigerweise durch ziemlich viele leere Grid-Zellen. Das ist schon bei einem dichten 3D-Array langsam, und bei einem Hash-Array mit Sicherheit noch bedeutend langsamer, da die Speicherzugriffe weit gestreut sind (eine gute Hash-Funktion gibt für leicht unterschiedliche Eingaben stark unterschiedliche Ausgaben), was katastrophal für den Cache ist.

Bei einem einzelnen Klick, um einen Block auszuwählen, wird das nicht viel ausmachen. Wenn aber das Raycasting auch zum Rendern benutzt wird (z. B. um eine Liste aller sichtbaren Blöcke zu erhalten), dann muss man sich darüber Gedanken machen.

Zitat von »David Scherfgen«

Wahrscheinlich benutzt er pro Chunk eine Liste, weil der größte Teil des Raums leer ist, und er dadurch Speicher spart.

Richtig, zudem ist ein Block mehr als nur Koordinaten. Der hat eine BoundingBox, über die Anklicken und Kollision gemacht wird, sowie ein Material, welches wiederum weitere Informationen über Stabilität, Kosten, Baubarkeit und andere spielrelevante Eigenschaften (z.B. ob beim Abreißen des Blocks ein collectable Item entsteht, oder nicht) hat. Die BoundingBoxen brauche ich auch nicht nur beim Klicken, sondern permanent, von daher lege ich die natürlich auch in den Speicher und erzeuge die nicht immer neu. Die Materialinformationen werden ebenfalls häufiger gebraucht, als nur bei der Interaktion durch den Spieler, z.B. wenn Projektile das Schiff beschädigen, oder für die Kollisionsabfrage beim Platzieren von Gebäuden (da wird ein Dummygebäude über die Map bewegt).
Aus dem Grund habe ich eine List<Block> (bzw. eine Ableitung davon mit ein paar Extrafunktionen) pro Chunk und die Block-Klasse enthält alles, was ich regelmäßig brauche.
Lediglich das Bauen der Vertex-/Indexlisten zum Rendern wird einmalig pro Änderung im Chunk und dann über die gesamte Blockliste (gruppiert nach Material, um den Texturparameter im Shader nicht unnötig oft neu setzen zu müssen) gemacht und nicht pro Block.

Warum hast du für jeden Block eine eigene BoundingBox wenn alle Blöck eh gleich groß sind?