Wenn man mit einer sehr großen Anzahl von Polygonen zu tun hat,tritt zwangsläufig irgendwann das Geschwindigkeitsproblemauf. Zuerst mussten wir uns überlegen, wie man ganz schnellden Teil der Welt herausfinden kann, der vom Spieler zu sehen ist.Denn einfach die ganze Welt von der Grafikkarte rendern zu lassenist vollkommen unsinnig, erst recht, wenn noch Spezialeffektehinzu kommen. Keine Grafikkarte der Welt würde das so schnelldarstellen können, dass man gut spielen kann.
Hierfür gibt es verschiedene Lösungen, die aber meist auf einemPrinzip basieren: Die Welt muss unterteilt werden. Bewährthaben sich dafür die so genannten QuadTrees,also 4-dimensionale Bäume. Und das geht so: Die ganze Weltwird von einer Box umschlossen, einer BoundingBox. Nun wird dieseBox in vier gleichgroße Teile „zerhackt“ undjede dieser vier Teile wird wieder geteilt. Das kann man solangedurchführen, bis eine gewisse Anzahl an Unterteilungenerreicht ist, oder die Boxen eine gewisse Größe haben.Die letzten Boxen enthalten nun Informationen über den Teilder Welt, den sie durch ihre Größe abdecken.
Wenn man nun wissen möchte, welche Teile der Spieler sehen kann,wird der Baum von oben an auf seine Sichtbarkeit geprüft. Isteine Box sichtbar und hat weitere Unterteilungen, so werden auchdiese geprüft und alle sichtbaren Teile der Welt werdenangezeigt.
Das war jetzt nur ein Schnelldurchlauf, denn die Sache ist natürlichein Stück komplexer. Dazu kommt, dass man die Anzahl derBoxen so wählen muss, dass zum einen die Prüfung derSichtbarkeit nicht zu lange dauert und zum anderen die Grafikkartenicht „unterfordert“ wird. Es macht nämlich auchkeinen Sinn jedes Polygon einzeln zu rendern.
An dieser Stelle möchte ich mich nochmal bei unserem ehemaligenProgrammierer jayjay bedanken, der eine sehr gute Arbeit geleistethat. Er war derjenige, der diese Lösung implementiert hatte.
Nachso viel Theorie muss auch mal etwas Sichtbares her. Auf diesemScreenshot sieht man eine kleine Landschaft mit einem Berg undeinem Haus. Was man allerdings nicht genau erkennen kann: Eshandelt sich hierbei um einen Octree, also einen 8-dimensionalenBaum. Dieser Octree wird jedoch nicht für dieSichtbarkeitsprüfung und das rendern der Welt benutzt. Dazuwäre er viel zu häufig unterteilt. Nein,wir benutzen ihn für die Kollisionsprüfung, wobei proBox nicht mehr als 15 Polygone enthalten sein dürfen. Damitkann man deutlich schneller auf Kollisionen prüfen, als wennman die Welt als Ganzes betrachten würde. Man kann sehr gutsehen, dass dort, wo wenige große Polygone auftreten nursehr wenig Unterteilungen vorgenommen werden mussten, um das Zielzu erreichen. Das Haus, und speziell der rechts oben herausragendeTurm hingegen haben viele „kleinere“ Polygone, darummusste hier häufiger Unterteilt werden.
Diese Figuren auf dem Dach sind nicht etwa eifrig arbeitende Dachdecker,sondern schlicht NPCs, die mit veralteten Positionsangaben geladenwurden. Das hat aber auch etwas Gutes an sich, es zeigt, dass dieKollisionsprüfung funktioniert.
Wer sich über die FPS Zahl links unten wundert, dem sei gesagt, dass es sich hier um den schlechtesten aller Fälle handelt. Denn das Programm war im so genannten „Debugmodus“ kompiliert und enthält somit zusätzliche Informationen, die in der endgültigen Fassung nicht mehr benötigt werden. Außerdem wurde die Anzeige der umschließenden Boxen nicht optimiert. Es werden hier noch restlos alle Boxen Frame für Frame neu abgeholt und zur Grafikkarte transportiert. Das habe ich nämlich nur schnell zur Anschauung zusammen geschustert.
Im „Releasemodus“ läuft diese Welt mit weit mehr als 100 FPS, dann aber ohne die Boxen.
Aber zurück zur Weltaufteilung. Einige unter euch werden sich vielleicht fragen, weshalb wir nicht auf freie Bibliotheken zurück gegriffen haben. Das hat mehrere Gründe. Zum einen wären die Informationen über die Welt doppelt vorhanden, einmal zum anzeigen und dann zur Kollisionsprüfung. Bei unseren Vorstellungen, was die Weltgröße anbelangt wären dies mit Sicherheit mehrere 50-100MB Zusatzbelastung für den RAM. Zum anderen sind viele Implementierungen viel mehr für kleinere dafür aber komplexere Objekte gedacht, nicht wie hier große und relativ einfache. Also haben wir unsere Eigenimplementation gemacht, wobei die Vorüberlegungen viel länger gedauert haben, als die Programmierung.
Die Objekte, wie Tische, Kisten, usw. werden je nach Größe und Komplexität durch einfachere Objekte ausgetauscht. Ein Tisch, der aus, sagen wir 500-700 Polygonen besteht kann so einfach mittels 5 Boxen dargestellt werden. Das erhöht die Geschwindigkeit der Kollisionsprüfung und nimmt weniger Speicher weg, als wenn wir ihn auch durch eine Octree-Struktur darstellen würden. Diese ist bei komplexeren Objekten notwendig, allerdings werden wir uns auch hier überlegen, ob wir dies nicht anders lösen können.
Tja, da wartet noch eine Menge Arbeit auf uns, aber ich bin zuversichtlich, dass wir auch solche Probleme gut und schnell in den Griff bekommen.
Der nächste Eintrag wird wohl etwas mehr Bildmaterial besitzen, dann geht es nämlich um, .... erm.... irgendetwas aus der aktuellen Entwicklung ;)