Spielewelten mit Raycasting: Optimierungen

In diesem Kapitel geht es darum, Verbesserungen und Optimierungen für bisher dargestellten Funktionen zu aufzuzeigen. Wir stellen Möglichkeiten vor, wie man Quellcode wartungsfreundlich gestaltet und zeigen Möglichkeiten, wie man langsame Programme etwas beschleunigt. Nicht zuletzt ist Raycasting ein Verfahren, das auf alten - und wir meinen aus heutiger Sicht wirklich alten- Rechnern lief. Es gibt daher keinen Grund, warum eine Raycasting-Szene auf moderner Hardware langsam laufen muss.

Geldmodell

Aus rein methodischen Gründen führen wir in diesem Abschnitt das Geldmodell ein. In alter Zeit, als Computer noch so groß waren wie Kühlschränke, musste man für das Ausführen von Programmen Geld bezahlen. Je länger das Programm gerechnet hat, desto mehr Geld musste man bezahlen. Die Geldmenge geben wir in diesem Kapitel nur zum Teil nach Gefühl vor. Gründe dafür findet man, wenn man sich intensiver mit Prozessortechnik auseinandersetzt.

Aufräumen von Quelltext

Erstellt man ein Programm, dann schreibt man oft zu viel Quelltext hin. Solche Stellen findet man sehr leicht, denn es sind diejenigen Stellen, wo man Quelltext verdoppelt. Berechnet man an verschiedenen Stellen im Programm immer wieder die gleichen Dinge, dann ist man als Anwendungsentwickler darum bemüht, Funktionen einzuführen, die einem bei passender Wahl von Parametern diese Berechnungen etwas übersichtlicher gestalten. Man möchte schließlich nicht zu viel Quelltext haben, je weniger Text, desto wartungsfreundlicher ist das Programm. Außerdem können Änderungen im Programm an zentraler Stelle erfolgen, man muss nicht alle Stellen ändern, an denen man diese entsprechende Berechnung gemacht hat, sondern genau eine. Hier ein Beispiel aus findeWand() aus dem Kapitel Frei beweglich:

So haben wir es gemacht	So könnte man es machen
# ... dx1 = rx * dx1 dy1 = ry * dy1 dx2 = rx * dx2 dy2 = ry * dy2 # ...	def richtungsparameter(rx, ry, dx1, dy1, dx2, dy2): return (rx * dx1, ry * dy1, rx * dx2, ry * dy2)

An diesem Vorgehen ist absolut nichts falsch, Anwendungsprogrammierer würden genau so vorgehen. Als Spieleentwickler muss man unter Umständen darauf achten, dass Code schnell ausgeführt wird, und dem steht das Einführen von neuen Funktionen im Weg. Während im Vergleich eine einzelne Zuweisung vielleicht einen Euro kostet, kostet ein Funktionsaufruf 5 Euro. Der Grund dafür ist, dass im Hintergrund einige Dinge passieren, wenn Funktionen aufgerufen und wieder beendet werden.

Im Allgemeinen ist es aber immer eine gute Idee, Quelltext aufzuräumen und mit Funktionen und Methoden zu gliedern.

Wahl der Datenstruktur

Wie wir im Kapitel Mathematik ausgeführt haben, gibt es mehrere Möglichkeiten, Winkel zu bezeichnen. Die trigonometrischen Funktionen benutzen im Allgemeinen Radiant, wir hingegen benutzen in den Beispielen Dezimalgrad. Daher wird bei uns jede sehr teure trigonometrische Funktion durch eine Umrechnug mit der ebenfalls sehr teuren Fließkommadivision künstlich verteuert. Wir haben aus rein methodischen Gründen in den bisherigen Beispielen Dezimalgrad benutzt, aus Gründen der Optimierung sollten wir aber besser bei Radiant bleiben, wenn wir diese Art der Berechnung beibehalten wollen.

Manche Methoden funktionieren auch ganz gut mit ganzen Zahlen statt Fließkommazahlen. Schließlich braucht man im Allgemeinen nicht die dritte Nachkommastelle, wenn es um die Pixelgröße einer Wand geht. Rechnen mit ganzen Zahlen ist trotz der im Prozessor eingebauten Fließkommaeinheiten meistens billiger.

Wahl der Programmiersprache

In diesem Buch verwenden wir Python als Programmiersprache weil wir glauben, dass Programmieranfänger die Syntax leichter lesen können als zum Beispiel C. Alleine die Wahl einer Sprache, die Werkzeuge bereitstellt um optimiert compiliert zu werden würde den Code um einiges beschleunigen. Compilertechniken sind sehr stark ausgereift und können so zu einem deutlichen Geschwindigkeitsgewinn führen.

Früher rechnen, später profitieren

Verschiedene Funktionen sind sehr teuer. Dazu gehören trigonometrische Funktionen (Sinus, Kosinus und Tangens), die wir mit 150 Euro pro Aufruf ansetzen, aber auch die Division von Fließkommazahlen, die wir mit 30 Euro ansetzen.

Wenn unsere Spielfigur nach oben blickt, wird beim Gehen immer der Tangens der benachbarten Winkel berechnet. Viel besser wäre es doch, wenn alle Tangens-Werte schon früher mal berechnet worden wären, und man nur in einer Tabelle nachschauen müsste, wie groß denn der Tangens beim aktuell gewählten Winkel ist.

Bei einem Blickfeldwinkel von 60° und einer 600 Spalten breiten Projektionsebene sind das 3600 Tabelleneinträge bei einem Vollkreis, je zwei Winkel unterscheiden sich darin um 0,1°.

Die Tabellen kann man vor Spielbeginn erzeugen, dann lädt das Programm etwas langsamer, es spielt sich aber flüssiger weil die Berechnung während des Spieles entfällt.

Überhaupt ist es ein guter Trick der Spieleentwickler, alle Dinge, die man vor Spielbeginn berechnen kann auch vor Spielbeginn zu berechnen. Hierzu gehört auch eine Tabelle, die alle Spalten der Grafiken, die es als Wandtextur zu zeichnen gilt, bereitzustellen.

Bedingungen

Befehle werden nacheinander in den Prozessor geladen und von verschiedenen Verarbeitungsstufen bearbeitet. Viele Befehle werden dabei durchaus 20 Takte lang durch Ausführungsstufen gereicht, bis das Ergebnis des Befehls bereitsteht. Das bedeutet aber auch, das in diesem Beispiel 20 Befehle im Prozessor darauf warten, ausgeführt zu werden. Wenn nun ein bedingter Sprung (eine if-Anweisung) in den Verarbeitungsbereich geladen wird, dann wird das Sprungziel geprüft. Dieses Sprungziel ist unter Umständen nicht mit dem nachfolgenden Befehl, der sich schon in der Stufe befindet, identisch. Also müssen alle nach dem Sprungbefehl geladenen Befehle wieder gelöscht werden und die dem Sprungziel entsprechenden Befehle geladen werden. Durch das Löschen schon geladener Maschinenbefehle entsteht ein Performanceverlust.

Es ist hierbei schwer anzugeben, wieviel Geld eine einzelne if-Anweisung kostet. Das hängt nicht zuletzt davon ab, wie gut die im Prozessor integrierte Sprungvorhersage arbeitet.

Im Abschnitt Wand mit Textur, Kapitel "Frei beweglich" haben wir eine Möglichkeit genutzt, eine if-Anweisung einzusparen, in dem wir eine Formel gefunden haben, die bei einem beliebigen Wandschnittpunkt (mit horizontalen oder vertikalen Linien) die Texturspalte auswählt (Auszug aus Raum.raycasting()):

wandort = int((schnittpunktX + schnittpunktY) % spielfeld.feldgroesse)

Diese Zeile hätten wir auch mit einer if-Anweisung schreiben können, was näher lag als diese geschlossene Formel.

Weitere Berechnungen

Die Quadratwurzel, die wir benutzen, um den Abstand zu einer Wand zu bestimmen ist so teuer wie die Fließkommadivision. Wir benutzen die Quadratwurzel, um den Abstand der Spielfigur zu einer Wand zu berechnen. Die Rechnung sieht ungefähr so aus:

• $d={\sqrt {a^{2}+b^{2}}}$

Hier hat man zwei Fließkommaquadrate und eine Quadratwurzel. Eine solche Berechnung kann man nun auf zwei Weisen optimieren:

1. Man spart sich die Wurzel und tut so, als ob das Entfernungsquadrat gleich der Entfernung wäre - diese Lösung zieht unter Umständen weitere Änderungen nach sich
2. Man berechnet die Entfernung durch
   

• $d={\frac {\left|Px-Qx\right|}{\cos \ \alpha }}$,

wobei man die Kosinuswerte wie oben angegeben vorher berechnet hat.

Anregungen

• Probieren Sie, die hier genannten Anregungen umzusetzen
• Finden Sie heraus, was ein Profiler-Programm ist und wie man es einsetzt
• Schauen Sie in das Buch Das Performance-Handbuch hinein.

---