Institut für Informatik
Markus Blumenstock
Sommersemester 2024Angewandte Mathematik am Rechner
Übungsblatt 6: Abschlussprojekt — angewandte Differentialgleichungen
Letzte Änderung : 09:12 Uhr, 04 July 2024Abnahmetermin : 18. Juli 2024
Auf diesem Aufgabenblatt wollen wir das, was wir auf Blatt 05 über Differentialgleichungen gelernt haben, praktisch anwenden. Wie versprochen entwickeln wir ein kleines Computerspiel, in dem wie die DGLs für Simulationen und Spezialeffekte anwenden.
Diesmal ist die Aufgabe sehr frei gestellt — es geht hier viel mehr darum, die mathematischen Methoden kreativ einzusetzen, als darum, systematisch Wissen zu erarbeiten (das haben wir auf den anderne Blättern ja schon ausgiebig getan).
Dieses Blatt ist das Abschlussprojekt des Praktikums: Wir werden uns die Ergebnisse alle zusammen in der letzten Vorlesungswoche ansehen (jede Gruppe erhält hier 5min Zeit für eine kurze Präsentation). Eine schöne Gestaltung lohnt sich also! Mehr Informationen zur organisation folgen in Kürze via Reader-Mail. Viel Erfolg & viel Spaß!
„Artillery“ (aka. Gorillas, Worms, etc.)
Spielablauf:
Beim „Artillery“-Spiel steuern die Mitspieler je eine Kanone in einer Landschaft und versuchen durch ballistische Schätzungen die Einheiten der anderen Spieler zu treffen und diesem dadurch Lebenspunkte abzuziehen. Dabei können die Spieler lediglich den Winkel des Schusses sowie die eingesetzte Feuerkraft des Schusses angeben. Um das Spiel zu erschweren, ist oftmals der Stärkefaktor an einen Geschicklichkeitsmechanismus (halten zum Aufladen und loslassen zum Abfeuern) geknüpft oder ein zufällig wechselnder Wind geht in die ballistische Simulation ein, um eine wiederholte optimale Einstellung zu verhindern. Es gewinnt der Spieler, der am längsten überlebt.
Historischer Hintergrund
Das Spielprinzip ist ein alter Klassiker — erste Varianten erschienen schon Mitte der siebziger Jahre (wenige Jahre nach Pong). Es gab danach unzählige Variationen. Besonders bekannt ist wohl das zu MSDOS 5.0 gehörende „Gorillas.bas )“, mit wütenden Gorillas, oder die Worms)-Reihe (besonders bekannt ist die legendäre Episode „Worms Armageddon“).
Hinweis: Der Übersichtlichkeit halber haben wir diesmal Aufgabentext und Erklärungen getrennt. Tipps und Erläuterungen finden sich in einem gesonderten Abschnitt, nach den Aufgabenstellungen. Beachten Sie auch, dass in Aufgabe 6.2 viel Wahlfreiheit besteht (man muss nicht alles implementieren).
Aufgabe 6.1: Implementieren Sie das Grundgerüst des Spiels.
[55 Punkte]
Implementieren Sie ein Spiel nach dem „Artillery“-Spielprinzip, bei dem zwei (oder mehr) Spieler versuchen, den/die Gegenspieler mit einem Projektil zu treffen.
- Ihre Implementierung sollte über die folgenden Features verfügen:
- Das Spiel soll wie oben beschrieben von mindestens zwei Spielern gespielt werden können. (Nacheinander/rundenbasiert oder gleichzeitig/in Echtzeit).
- Wichtig ist die physikalische Simulation der Ballistik. Schreiben Sie hierzu Code, der gegeben einen Startpunkt und eine Startgeschwindigkeit die Differentialgleichung \(F = mg\) löst, wobei \(g\) die Gravitationsbeschleunigung (in \(y\)-Richtung) beschreibt.
- Vergessen Sie auch nicht, sich ein Schadensmodell an den Spielern zu überlegen; zum Beispiel sollte der Schaden höher sein, wenn das Geschoss näher am Spieler auftrifft. Beachten Sie auch, dass das Geschoss den Spieler aber nicht die Karte treffen kann.
- Beim Auftreffen eines Geschosses in die Landschaft soll die Flugbahn enden. Die Zerstörung soll durch einen Krater visualisiert werden.
- Um das Spiel etwas schwieriger zu gestalten, soll ein sich ändernder Wind die Flugbahn der Geschosse beeinflussen. Hierzu müssen Sie die Differentialgleichung entsprechend erweitern. Visualisieren Sie auch die Windrichtung, damit Spieler diese berücksichtigen können.
Aufgabe 6.2: Erweiterungen
[45 Punkte]
Wählen Sie drei der nachfolgend vorgeschlagenen Erweiterungen aus und bauen Sie dies in Ihre Implementierung ein. Jede Ergänzung gibt (unabhängig vom Schwierigkeitsgrad) 15 Punkte; maximal sind 45 Punkte erreichbar. Es dürfen beliebig viele Ergänzungen implementiert werden.
- Ermöglichen Sie den Spielern vor und nach dem Abschuss des Geschosses sich eine eine begrenzte Zeit lang über die Karte zu bewegen. (Dieses Feature ist nur bei einem rundenbasierten Spiel sinnvoll). Visualisieren Sie auch den Countdown für die Zeit, in der man sich bewegen kann.
- Erweitern Sie die Kanonensteuerung wie unten beschrieben durch ein graphisch Einstellbare Ausrichtung und durch eine geschicklichkeitsbasierten Justierung der Abschussstärke (z.B.: Taste länger drücken für mehr Geschwindigkeit).
- Implementieren Sie einen einfachen KI-Gegner: Wählen Sie zuerst einen Punkt in der weiteren Umgebung des menschlichen Spielers und bestimmen Sie dann die Abschussgeschwindigkeit (und daraus den Abschusswinkel und die Stärke des Schusses) so, dass das Geschoss der KI der Simulation folgend in genau diesen Punkt einschlägt.
- Die Landschaft, die Sie auf den Screenshots der Musterlösung sehen können wurden zufällig generiert. Implementieren Sie die zufällige Generierung der Landschaft wie in den Tipps beschrieben.
- Was wir mit der Landschaft gemacht haben können wir auch (diesmal in 2D) auf den Wind anwenden. Statt einer global konstanten Windrichtung sollen grobe Fluktuationen im Wind simuliert werden.
- Einfach verschwindende Geschosse und sich schlagartig ändernde Landschaften sind visuell wenig ansprechend. Damit es richtig kracht sollen Partikeleffekte der Explosion wie Rauch oder Splitter in die Simulation eingebaut werden. Hier brauchen wir wieder Differentialgleichungen (Stichwort: „Particle-Systems“). Mehr dazu auch in der nächsten (und letzten) Vorlesung!
Für die Abschlußpräsentation sind natürlich auch weiterführende Erweiterungen (Sound/Graphik/Spielerweiterungen) gerne gesehen; formale Punkte gibt es aber keine.
Tipps zur Implementierung (mit PyQt)
Zeichnen auf Bildern
An sich können Sie ähnlich wie beim ersten Übungsblatt („Snake“) auch erst ein Bild erstellen und dann die einzelnen Pixel manipulieren. Dies hat einige Nachteile: Zum einen müssen Sie so zu jedem Zeitschritt das komplette Bild neu zeichnen lassen. (z.B. ändert sich der Hintergrund sehr selten). Zum anderen ist es so schwieriger komplexere Strukturen wie Kreise zu zeichnen oder bestehende Grafiken einzubinden. Unsere Empfehlung ist es, mit der Klasse QPainter zu arbeiten. Wir haben dazu das Skript um einige Grundfunktionen wie das Zeichnen von Ellipsen/Kreisen, Rechtecken und Text erweitert (Kapitel 1.4.9 „PyQt — Arbeiten mit Bildern“). Für alles Weitere empfehlen wir Ihnen einen Blick in die Dokumentation (Der dortige Code ist zwar C++, das Python-Äquivalent sieht jedoch bis auf etwas anderen „syntaktischen Zucker“ genauso aus).
Krater & Kollision mit der Landschaft
Generieren Sie die Landschaft als Hintergrundbild in einem QImage und radieren Sie das Hintergrundbild nach und nach aus. (In Wirklichkeit setzen wir den Alpha-Kanal auf volle Transparenz).
# Dies muss nur einmalig ausgeführt werden:
# numpy-Darstellung des Bildes (wie bei Snake, siehe Skript)
world = ...
# Darstellung als Bild
world_img = QImage(world.data, width, height, QImage.Format_RGBA8888)
# Raddiergummi auf dem Bild
mappainter = QPainter(world_img)
mappainter.setCompositionMode(QPainter.CompositionMode_Clear)
mappainter.setPen(Qt.black)
mappainter.setBrush(Qt.black)
# später im Code ...
# Krater zeichnen in Position (12,34) mit dem Radius 50
mappainter.drawEllipse(QPoint(12,34),50,50)
Mithilfe der QImage-Klasse (dem Objekt auf dem der QPainter zeichnet) können Sie auch stets prüfen, ob die Karte an einer gegebenen Position durchsichtig ist.
# alpha-Wert in der Position (25,25) prüfen
world_img.pixel(25,25).alpha()
Abstand zur Oberfläche (wie auf dem Screenshot)
Auf dem Screenshot sind Punkte, die näher an der Oberfläche sind heller. Wir haben dies mithilfe des Pakets scikit-fmm gelöst. Dieses berechnet den Abstand von einem Wert zur nächsten 0.
import skfmm
# Karte ist ein Boolsches Array mit True = Pixel ist Land, False = Pixel ist kein Land
map = np.zeros([width,height], dtype=np.bool)
# Distanzen zur 0 (also False)
map_dist = skfmm.distance(map)
# Normieren auf 0,1
map_dist = map_dist / np.max(map_dist)
# Mit Matplotlib in Farben Konvertieren
world = plt.cm.copper_r(map_dist)
# Nicht-Land auf Transparent setzen (True = 1, False = 0)
world[:,:,3] = map
# Konvertierung in ein 8-Bit Array, das in ein QImage konvertiert werden kann
world = np.asarray(world*255,np.uint8)
Zufällige Karte und Windvektorfeld
Eine weit verbreitete Möglichkeit zufällige Gebirgslandschaften zu generieren verwendet die Sinus-Funktion:
Wir summieren eine feste Anzahl von zufällig verschobenen und gestreckten/gestauchten Sinusfunktionen und gewichten die Sinusfunktionen, die stark gestaucht worden stärker. \[\sum_{w\in W} \frac{1}{\sqrt{w}} \cdot sin\left(w\cdot x + \text{rand}[0..2\pi] \right)\cdot \text{rand}[-1..1]\]
Beispielsweise hat in unserer Musterlösung \(W = \,\) np.linspace(0.001,0.05,20) gut funktioniert.
Mithilfe dieser Kurve können Sie nun ein Boolsches-Array erstellen, das wie in der Erklärung der Krater die Karte definiert.
Hinweis: Diese Kurve bewegt sich nun in welchem Intervall? Womit müssen Sie die Kurve multiplizieren, damit Sie sich stets in Ihrem Bildausschnitt bewegt?
Ganz ähnlich können Sie nun ein Windvektorfeld erstellen. Verwenden Sie dazu zwei Mengen \(W_x\) und \(W_y\) für die x- bzw. die y-Koordinate und Summieren Sie die beiden Ergebnisse für das Ergebnis \(\alpha_{x,y}\). Der daraus resultierende Wert kann den Winkel der Windrichtung beschreiben. Führen Sie dies ein zweites mal aus, um die Stärke \(s_{x,y}\) der jeweiligen Windvektoren zu definieren. Die Beschleunigung durch den Wind ist dann am Punkt \(\begin{pmatrix}x\\y\end{pmatrix}\) durch \(s_{x,y}\cdot \begin{pmatrix}\cos \alpha_{x,y}\\\sin \alpha_{x,y}\end{pmatrix}\) gegeben.
Alternativ: Statt die beiden Werte als Richtung und Stärke zu interpretieren können sie die Werte auch \(x_{x,y}\) und \(y_{x,y}\) nennen und damit die Gesamtbeschleunigung durch \(\begin{pmatrix}x\\y\end{pmatrix}\) durch \(\begin{pmatrix}x_{x,y}\\y_{x,y}\end{pmatrix}\). Tatsächlich kann man die beiden Darstellungen in einander überführen. Die erste nennt sich kartesische Koordinatendarstellung, die zweite nennt sich Polarkoordinatendarstellung. Das Umrechnen zwischen diesen beiden ist beim Rechnen mit komplexen Zahlen üblich. Beispielsweise haben wir Ihnen bereits die Umrechnung aus Polakoordinaten \(\alpha,r\) in kartesische Koordinaten bereits genannt.
Die Theorie hinter diesem Trick ist die des „farbigen“ Rauschens: Man kann (alle physikalisch realistischen) 1D Funktionen \(f: [0,2\pi] \rightarrow \mathbb{R}\) durch eine Fourierreihe wie folgt darstellen:
\[f = \sum_{w=0,1,2,3,...} a_w \cdot \sin(w\cdot x + b_w), \quad a_w \in \mathbb{R}, \quad b_w \in [0,2\pi]\] Tatsächlich handelt es sich hierbei um eine orthogonale Basis des Funktionenraums. Die Koeffizienten \(a_w\) geben dabei an, wie stark verschiedene Frequenzen in der Funktion erhalten sind, die \(b_w\) sind die sogenannte „Phaseninformation“. Grob vereinfacht steuern die \(a_w\) die Textur des Signals (hohe Frequenzen = rauer) und die \(b_w\) enthalten den größten Teil der Form des Signals (wo Kanten im Bild auftauchen). Nimmt man nun zufällige Werte für alle \(a_w\) und \(b_w\), so erhält man schlicht gleichmäßiges Rauschen, ohne Struktur. Dampft man aber die Koeffizienten \(b_w\) mit steigender Frequenz, so erscheinen grobe Strukturen (weil weniger gedämpft) aber das feine Rauschen verschwindet (stärker gedampft). Die Graphen solcher Funktionen sehen aus wie Silhouetten einer Berglandschaft. Meistens dämpft man mit \(a_i \sim 1/w^h\), wobei die reelle Zahl \(h > 0\) der „fraktale Exponent“ ist. Gute Werte liegen ca. zwischen 0,5 und 2. Je höher dieser Wert, desto glatter wird die Funktion.
Diese Technik ist in der Computergraphik als Fractal Brownian Motion bekannt (warum das so heißt — lange Geschichte). Optional, für alle die es interessiert, mehr dazu im Web: Fractal Brownian Motion (Theorie), Fractal Brownian Motion (Praxisbeispiele), Perlin Noise (beliebte alternative Implementation des Prinzips).
2D Version
Für 2D Skalarfelder würde man eine 2D Fourierbasis (konstruiert als sogenannte „Tensorproduktbasis“, aka: alle Kombinationen multipliziert, verwenden:
\[f = \sum_{x=0,1,2,3,...} \sum_{y=0,1,2,3,...} a_xy \cdot \sin(w\cdot x + b_x) \cdot \sin(w\cdot y + c_y), \quad a_xy \in \mathbb{R}, \quad b_x,c_y \in [0,2\pi]\] Um ein Vektorfeld zu konstruieren, baut man zwei solche Reihen, eine für die Ausgabe in x-Richtung und eine zweite, unabhängige, für die Ausgabe in y-Richtung. Man würde hier typischerweise nur sehr niederfrequente Moden („Windböen“) benutzen, und diese durch einzelne Partikel visualisieren, die durch die Luft wehen (siehe z.B. das Spiel „Worms-Armageddon“). Die Amplitude des Rauschens darf nicht zu groß werden, sonst ist das Spiel zu zufällig.
Der Tipp oben in der Aufgabe vereinfacht dies etwas, indem Rauschen in Polarkoordinaten erzeugt wird.
Mehr zu alle dem in der letzten Vorlesung!
Flüssigere Steuerung des Kanonenrohrs
Da die Simulation der Partikel häufig und lange laufen muss bietet es sich an sie die ganze Zeit laufen zu lassen (ganz ähnlich wie in der Event-basierten Programmierung). Beim Tastendruck setzen wir die Beschleunigung, die auf den Winkel des Kanonenrohrs wirkt auf einen festen Wert und lösen die Differentialgleichung \(F=ma\) wie gewohnt.
Partikeleffekte
Erweitern Sie Ihre Simulation, indem sie (theoretisch) eine beliebige Anzahl von Partikeln simulieren können; Kanonenkugel, Splitter und Rauch sind dann nur noch Spezialfälle des abstrakten Partikelobjektes, die sich lediglich durch die Art der Visualisierung und der internen Parameter (wie das Gewicht, die Beschleunigung oder die Stärke der Dämpfung) unterscheiden.
Implementieren Sie nun Splitter-Partikel: Sobald eine Kollision beobachtet wurde sollen einige Splitterpartikel mit randomisierten Anfangsgeschwindigkeiten und Richtungen an den aktuellen Kollisionspunkt gesetzt werden. Färben Sie die Splitter-Partikel abhängig von der Länge des Geschwindigkeitsvektors. Dazu eignet sich zum Beispiel eines der vielen Farbschemata von Matplotlib (siehe letztes Blatt). Dieses Vorgehen kann bei der richtigen Wahl dazu führen, dass die Explosion im Zentrum „heißer“ aussieht und nach außen hin abzukühlen scheint.
Implementieren Sie nun Rauchpartikel, die eine leichte Beschleunigung nach oben aufweisen und eine starke Dämpfung der Geschwindigkeit. Sobald die Geschwindigkeit eines Splitterpartikels einen bestimmen Wert überschreitet soll an dessen Stelle zusätzlich ein Rauchpartikel (Startgeschwindigkeit 0) erscheinen.
Hinweis: Achten Sie darauf. die Partikel wieder zu entfernen, wenn sie den Bildschirmrand verlassen oder kollidieren. Ansonsten wird Ihr Code sehr schnell darunter leiden, dass es nur in Python geschrieben wurde. Sie können dies um ein vielfaches herauszögern, wenn sie die Differentialgleichungen vektorisiert lösen. Mehr Details sowie Tipps & Tricks zu diesen Partikelsystemen gibt es in der letzten Vorlesung!
Partikeleffekte 2
Zeichnen Sie die Rauchpartikel als Kreise mit dunkelgrauer halbtransparenter Mitte und gänzlich Transparentem Rand. Sind genug Rauchpartikel in der Nähe und haben Sie Windfluktuationen eingeführt, führt dies zu einem realistischer Rauch-Effekt.
Zeichnen Sie die Splitter-Partikel auf eine separate Ebene. Übermalen Sie diese Ebene im nächsten Simulationsschritt mit einer leichten Transparenz-Maske (wie der Radiergummi-Effekt beim Visualisieren der Krater) — verwenden Sie zum Übermalen der Ebene statt Schwarz einen Grauton. Dies bewirkt, dass die letzten Simulationsschritte noch leicht sichtbar sind. Visuell bewirkt dies, dass die Explosion mehr Partikel zu haben scheint.