Richtig Große Welten und Landschaften

Hallo alle miteinander!
Ich habe mich einmal gefragt wie, insbesondere in Rollenspielen (z.B. World Of Warcraft), diese riesigen Welten ohne ständiges "Spielen - Ladepause - Spielen - Ladepause" möglich ist.
Bei meinen Recherchen bin ich da nicht gerade auf viel konkretes zum Thema gestossen, aber es hat gereicht, um mir einen Algorithmus zusammenzureimen 🙂
Habe mein "Paper" hier mal als PDF angehängt. Lest es euch doch bitte mal durch. Es stellt meinen Lernerfolg auf diesem Gebiet dar. Daher bin ich für jeden Verbesserungsvorschlag, bzw. jede Korrektur, offen und sogar dankbar 😉
Vielleicht ist das ja die Basis zu einem neuen Tutorial in dieser Sektion.

Liebe Grüße
Oliver

Sehr schoen, nur gibt es dergleichen wie Sand am Meer

Hab sowas hier noch nicht gesehen. Und da ich mir bei solchen Sachen immer Notizen mache, habe ich gedacht ich könnte es ja gleich hier öffentlich machen. Gerade auch wegen den Illustrationen.

Riesige Welten werden aus einem Set zusammengesetzt, dh. alles wiederholt sich irgendwie(Nur Nachbarelemente sind andere Wiederholungen(Drehungen der selben Elemente inkl., um höhere Vielfalt vorzutäuschen)). Diese Makroelemente bestehen wiederum aus kleineren Elementen. Im wirklichen Leben ist ein Baum, ein Haus oder ein Baumhaus einzigartig - bei solchen Sachen nicht.
Damit passt diese grosse Welt super in einen kleinen Speicher. Die Matrix die die Welt beschreibt kann damit klein bleiben. Der Rest verwaltet die "lebenden" Elemente, die sich auch kaum unterscheiden(Typ, Verwendete Bodyteile, Skins der Bodyteile - siehe NWN - AuroraToolkit).
Organisation ist alles. Also zum einen die Kunst der Verwaltung, Speed(Modellstufen), scheinbare Intelligenz und Lebendigkeit des Szenarios. Letzteres ist dann nicht an die Grafikkarte gebunden, wie das Management auch.

@ikaros

Also ich habe ja WOW noch nie gespielt, aber Gothic 2 benutzt ganz bestimmt kein Set. Dort wurde alles individuell modelliert und die Welt dort ist ja auch nicht gerade klein. Auch Elder Scrolls 4 - Oblivion (habe ich gestern gekauft und angespielt) macht nicht den Eindruck, als ob sich das Terrain wiederholt. Und die Landschaft ist dort noch um einiges grösser als bei Gothic 2.

Bei den anderen Levelobjekten wie Bäumen, Felsen etc. stimme ich mit dir überein.

@Bix

Hast du das ganze auch schon programmiert? Würde mich interessieren. Vor allem auch, wie du die Sektoren nachladen willst, ohne das der Spielfluss ins Ruckeln kommt (ein .x-File bekommst du ja immer nur als ganzes in den Speicher, es sei denn, du benutzt nicht die Direct3D-Methode).

mfg Hitman

Also für große Welten, wird Occlusion Culling auf der Grafikhardware immer populärer. Heutige Grafikkarten unterstützen Occulusion Queries nativ. Damit kann man recht einfach und hardwarebeschleunigt testen, welche Geometrie man sehen kann und welche nicht. Das ganze funktioniert grob so:
Du erzeugst zuerst eine sehr einfache geometrische Repräsentation deiner Welt (Bäume, Häuser, Felsen, usw. ... werden als Bounding Boxes angenähert).
Jetzt aktivierst die Occulusion Queries und renderst diese Bounding Boxes in eine nicht sichtbare Surface. Natürlich stark verkleinert (320*200) und mit deaktiviertem Shading, also keine Lichter, Texturen, Blending oder sonst was.
Dann zeichnest du alle "richtigen" Objekte, die in deinem Occulusion Querie stehen in das VRAM, fertig. Natürlich lässt sich die Sache noch stark erweitern: LOD Meshes usw...

Das Problem sehe ich nicht unbedingt in der Darstellungsgeschwindigkeit, sondern in der Speicherbelastung durch die nicht gerenderten Objekte, welche ja trotzdem im Grafikkartenspeicher untergebracht werden müssen. Bei grossen Landschaften können das einige 10 MByte sein.

mfg Hitman

@maxE und HitmanII: Genau wegen der Speicherbelastung habe ich auch darüber nachgedacht. Selbst wenn die Grafikkarte die Aufgabe des Cullings übernimmt, muss die gesamt Welt ja trotzdem in irgendeiner Form in flüchtigem Speicher (VRAM oder RAM) vorliegen. Aber ab einer bestimmten größe funktioniert das einfach nicht mehr.

@Ikaros: GTA San Andreas und WoW verwenden z.B. eine Technologie bei der die Daten der Welt kontinuierlich gestreamt werden. Was ja auch im Grunde genommen mein Ansatz ist. Das die Welt aus bestimmten Sets "zusammengeklebt" wird, ist zumindest bei diesen Spielen nicht der Fall.

@HitmanII
Zur Implementierung bin ich noch nicht so wirklich gekommen. Allerdings könnte man es zum Beispiel mit verschiedenen Threads machen. Ein Thread ist nur für das nachladen von Daten zuständig. Darunter dürfte der Spielfluss an sich denke ich nicht leiden. Wenn man allerdings alles in einem Thread erledigt, dann könnte man Probleme bekommen, da das gesamte Programm auf die Festplattenzugriffe warten müsste.

Gruß!
Oliver

@Bix: Wär es nicht schöner ein Wabenraster zu machen? Ich denk mal das wäre auch effizienter als lauter Quadrate.

Hi Progger!
Ich habe mir Deine Idee mit dem Wabenmuster eben mal schnell aufgemalt. Wenn ich mir das so anschaue, dann komme ich auf maximal 3 Waben, die gleichzeitig im Speicher wären, wenn man statt mit 4 Quadraten mit 1 Wabe startet. Netter Einfall 🙂 Das wäre denke ich zwar komplizierter zu implementieren, aber bestimmt besser als meine Idee mit Quadraten.

Streaming widerspricht nicht der Idee des Sets.
Streaming funktioniert nicht ohne Sets("NWN "spiegelt das Paradebeispiel von Sets wieder(einfache Form), "Dungeon Siege" ist wie Oblivion relativ frei). Ich habs ja eigentlich schon erwähnt aber: einzelne Objekte können leicht beschrieben werden(Grösse,Drehung + Position) das sind wenig Daten(die leicht nachgeladen werden können, während sich die "Prototypen" schon im Speicher befinden). Für "Akteure" verweise ich nochmals auf das AuroraToolkit(die sind auch nach dem Legoprinzip aufgebaut). Streaming KANN stattfinden(Grafikkram) ist aber auch "Setabhängig" oder unbrauchbar(geht auch bei falschen Sets ganz leicht).
Ich geh auch einfach mal davon aus das du soviel Grafiken nicht hast, oder wenn doch die Vielfalt nicht bringt. Moderne Spiele leben auch eher von Details und Kombinationen...

Zu den Waben:
Waben vs. Quadrate: es gibt keinen echten Unterschied bei dieser Art von Weltmodellierung. Waben stellen nur vertikal oder horizontal(seltener) verschobene Quadratreihen dar. Waben spielen ihren Vorteil in 2D-Strategiespielen aus(6 statt 4 Bewegungsrichtungen).

Ich fände es schade, wenn dieses interessante Thema hier nicht mehr weiter diskutiert würde. Deshalb an dieser Stelle mal ein konkreteres Beispiel:

Mein Programm erstellt aus einer 1025x1025 Pixel grossen Heightmap 32x32 Patches von der Kantenlänge 32, welche anschliessend als .X-Dateien abgespeichert werden. Die Geometrie wird so optimiert, dass Punkte, welche auf derselben Ebene liegen, nach Möglichkeit zusammengefasst werden (siehe Bild). So gehen auf der einen Seite keine Details verloren, auf der anderen Seite kann jedoch abhängig von der Geometrie ziemlich viel Speicherplatz gespart werden. Da das Renderprogramm mit Shadern arbeitet, wird zusätzlich auch noch eine Normalmap generiert. Somit kann man sich das Abspeichern der Normalen in der .X-Datei sparen, was deren Grösse fast auf die Hälfte reduziert.

Damit haben wir jetzt 1024 .X-Dateien und eine Normalmap (ca. 1 MByte) was eine Speicherbelastung von zwischen 50 bis knapp 100 MByte (abhängig von der Geometrie) ergibt. Da die .X-Dateien als Textdateien abgespeichert werden, kann man die Daten mit einer Huffman-Verschlüsselung (WinZip) ziemlich stark komprimieren, was schlussendlich noch einen Speicherbedarf auf der Festplatte von 10 bis maximal 20 MByte pro Sektor ergibt, was meiner Meinung nach völlig in Ordnung geht. Allerdings wandern ja die Daten zur Laufzeit in den Grafikkartenspeicher, wo sie natürlich wieder dekomprimiert vorliegen. Wenn man bedenkt, dass eine 6-Stellige Fliesskommazahl in einer Textdatei 7 Byte (6 Zahlen und der Punkt, 1 Byte pro ASCII-Zeichen) verschlingt, ein float allerdings nur 4 kommen wir grob geschätzt auf maximal 60 MByte im Grafikkartenspeicher. Hoffe die Rechnung ist einigermassen in Ordnung 🙂

60 MByte… Aktuelle Grafikkarten haben 256 MByte oder sogar noch mehr, wo soll jetzt da das Problem sein? Folgendes: Ich setzte einfach mal voraus, dass die Sichtweite mindestens ein Kilometer beträgt. Wie hoch soll der maximale Detailgrad des Terrains sein? Angenommen ich rechne mit einem Meter pro Einheit womit ein Sektor ca. ein Quadratkilometer (1025x1025m) gross wäre. Um die Sichtweite von einem Kilometer zu garantieren müssten die 8 angrenzenden Sektoren ebenfalls geladen werden, was nach meiner Rechnung 60 x 8 = 480 MByte Speicher kosten würde!!! Wenn ich allerdings mit 3 Meter pro Einheit rechne, wäre ein Sektor 9 Quadratkilometer gross, 60 MByte würden demnach reichen, um die Sichtweite zu garantieren. Die Frage stellt sich meiner Meinung also, was als Verhältnis Länge pro Einheit vernünftig ist. Wie sieht das bei aktuellen Spielen aus?

Eure Meinungen zu der Rechnung und / oder der Realisierung sind gefragt.

mfg Hitman