© StonePictures/Shutterstock.com
Neuronale Netzwerke im Bann der Gravitation

Classic Games Reloaded


Die Durchführung von ballistischen Berechnungen, orbitalen Flugmanövern und die Handhabung der Flugkontrolle von autonom landenden Raumfahrzeugen sind Herausforderungen, die uns mitnichten nur im Rahmen von Computerspielen begegnen. Im heutigen Artikel werden wir uns anschauen, wie sich verhältnismäßig einfach aufgebaute neuronale Netzwerke bei der Bewältigung der besagten Probleme schlagen, was in Anbetracht ihres Stellenwerts gleich doppelt interessant sein dürfte.

Die Firma SpaceX konnte sich in der jüngsten Zeit unter anderem wegen ihrer eigenständig landenden und wiederverwendbaren Raketenstufen, ihrem im Aufbau befindlichen globalen Weltrauminternet (Starlink), ihren bemannten Weltraumflügen sowie wegen ihrer geplanten Marsmissionen eines immer größeren Medieninteresses erfreuen. Man denke da nur an den Werbespot für den neuen Audi A3 mit den Aussagen „Wir fliegen zum Mars“ und „Raketen können landen“ oder an die US-Sitcom „Young Sheldon“ (Staffel 1, Episode 6), in der Elon Musk das Notizbuch des neunjährigen Sheldon Cooper mit den theoretischen Grundlagen der vertikalen Raketenlandung in Händen hält. Aber Spaß beiseite: Dass ich an dieser Stelle auf autonom landende Raketen zu sprechen komme, hat natürlich seinen Grund.

Im Jahr 1979 brachte die Firma Atari eine Arcade-Version des Spiels „Lunar Lander“ auf den Markt, in dem sich die Spieler daran versuchen durften, eine Raumfähre sanft und ohne Kratzer auf der Mondoberfläche zu landen. Heutzutage erfreut sich dieser Spieleklassiker zumindest bei KI-Programmierern durchaus noch einer gewissen Beliebtheit, da die Spielewelt eine ideale Testumgebung für genetische Algorithmen und/oder neuronale Netzwerke darstellt, in der diese ihre Qualitäten bei der Flugsteuerung unter Beweis stellen können.

Im Rahmen dieses Artikels werden wir uns allerdings nicht nur mit autonom landenden Raumfahrzeugen auseinandersetzen, sondern auch mit orbitalen Flugmanövern sowie ballistischen Berechnungen mit und ohne Reibungseinflüssen. Anzumerken ist, dass die Durchführung von ballistischen Berechnungen nicht nur für eine Vielzahl von Computerspielen unverzichtbar ist, sie stellt darüber hinaus auch das zentrale Gameplay-Element des Artillerie-Videospiel-Genres dar, zu dem übrigens auch die weithin bekannten Angry-Birds-Titel zählen.

Ein wenig Physik zum Warmwerden

Eins gleich vorweg: Wir werden uns im weiteren Verlauf dieses Artikels mit keinerlei komplizierten physikalischen Berechnungen herumschlagen müssen, die über das schulische Niveau hinausgehen. Wurfparabeln und dergleichen werden wir demzufolge heute nicht berechnen, denn unser Ziel besteht ja darin, verhältnismäßig einfach aufgebaute neuronale Netzwerke dahingehend zu trainieren, dass sie uns diese Arbeit abnehmen. Genau genommen müssen wir uns lediglich eine einzige simple Gleichung in Erinnerung rufen, auf der letzten Endes die komplette klassische Physik basiert. Gemeint ist natürlich das berühmte zweite Newtonsche Axiom:

  • Kraft = Masse mal Beschleunigung: F = m * a

Zur Erklärung: Die fettgedruckten Wörter und Buchstaben weisen auf den vektoriellen (richtungsabhängigen) Charakter der zugehörigen physikalischen Größen hin. Skalare Größen wie Masse und Zeit sind richtungsunabhängig (einfache Zahlenwerte) und werden dementsprechend nicht im Fettdruck dargestellt. Das erste Newtonsche Axiom, das sogenannte Trägheitsprinzip bzw. Inertialgesetz, stellt genaugenommen lediglich einen Spezialfall des zweiten Gesetzes dar: Wirken keinerlei Kräfte auf einen Körper ein, dann bewegt er sich mit geradlinig konstanter Geschwindigkeit (engl. Velocity) oder verharrt in Ruhe (der jeweils gemessene Geschwindigkeitsbetrag ist abhängig von der Geschwindigkeit, mit der sich der jeweilige Beobachter bewegt). Die Geschwindigkeitsänderung (Beschleunigung, engl. Acceleration) ist demzufolge gleich null. Formt man die zuvor betrachtete Gleichung ein wenig um und ermittelt alle auf einen Körper einwirkenden Kräfte, dann können wir die daraus resultierende Geschwindigkeitsänderung auf folgende Weise berechnen:

  • Beschleunigung = Summe aller Kräfte durch Masse: a = FSumme / m

Unter Berücksichtigung der Beschleunigung lässt sich nun für jeden Zeitpunkt die aktuelle Geschwindigkeit und Position eines Körpers mit Hilfe eines geeigneten numerischen Integrationsverfahrens ermitteln. Vereinfacht ausgedrückt handelt es sich bei einer numerischen Bewegungssimulation um eine Schritt-für-Schritt-Berechnung, in deren Verlauf die Bahnkurve eines Körpers schrittweise ermittelt wird. Für unsere Zwecke greifen wir in diesem Zusammenhang auf die denkbar einfachste Methode, das sogenannte Eulersche Polygonzugverfahren, zurück:

  • Geschwindigkeit (neu) = Geschwindigkeit (alt) + momentane Beschleunigung mal Zeitspanne (bzw. Simulationsschritt): v(t+dt) = v(t) + a(t) * dt

    velocityX += accelerationX * timeStep; velocityY += accelerationY * timeStep; velocityZ += accelerationZ * timeStep;
  • Position (neu) = Position (alt) + momentane Geschwindigkeit mal Zeitspanne: s(t+dt) = s(t) + v(t+dt) * dt

    positionX += velocityX * timeStep; positionY += velocityY * timeStep; positionZ += velocityZ * timeStep;

Für die Handhabung von sämtlichen physikalischen Objekten greifen wir in unseren Programmbeispielen auf Instanzen der in Listing 1 skizzierten CSimplePhysicsObject-Klasse zurück. Für die Aktualisierung der jeweiligen Objektpositionen und -geschwindigkeiten gemäß dem Eulerschen Integrationsverfahren ist darüber hinaus die in Listing 2 gezeigte Update()-Methode der CSimplePhysicsObject-Klasse verantwortlich.

Codebeispiel und Listings zum Download

Achtung: Das Beispielprojekt und die Listings zu diesem Artikel finden Sie in unserem GitHub Repository: https://github.com/EntwicklerMagazin/Entwickler-Magazin. Dort stehen auch die Codes zu den vorherigen Teilen der Serie bereit.

Der Autor stellt die Programmbeispiele außerdem unter www.graphics-and-physics-framework.spieleprogrammierung.net bereit.

Parallelisierung leicht gemacht dank OpenMP

Die Vorgehensweise, mit der wir unsere neuronalen Netzwerke trainieren werden, haben wir bereits im vorangegangenen Artikel ausführlich erörtert. Auch heute werden wir wieder auf das Konzept der Neuroevolution zurückgreifen. In diesem Zusammenhang gilt es, bis zu 200 (durch neuronale Netzwerke kontrollierte) KI-Spieler handzuhaben, die zum Zwecke ihrer Evaluierung (Fitnesswertberechnung) jeweils die gleichen Trainingsspiele bis zu einem bestimmten Punkt (einer vorgegebenen Anzahl von Frames) durchspielen müssen. Dass es sich hierbei um eine extrem zeitaufwendige und rechenintensive Angelegenheit handelt, muss wohl nicht extra betont werden. Die einzige Möglichkeit, mit der wir verhindern können, dass die zu veranschlagende Trainingszeit aus dem Ruder läuft, besteht nun darin, die Trainingsspiele auf mehrere nebenläufige Threads zu verteilen (engl. Concurrency). Somit könnten auf einer 8-Kern-CPU beispielsweise acht Individuen mehr oder weniger gleichzeitig ein Trainingsspiel absolvieren. Die einfachste Vorgehensweise, um die betreffenden Teile des Programmablaufs zu parallelisieren, besteht in der Verwendung des OpenMP (Open Multi-Processing) API, da wir uns in diesem Fall eine aufwendige Überarbeitung unseres Source Codes ersparen können. Für unsere Zwecke benötigen wir lediglich einige wenige OpenMP-Compilerdirektiven und -Bibliotheksfunktionen, die sich problemlos auch nachträglich in den Programmcode integrieren lassen. Schauen wir uns in diesem Zusammenhang zunächst einmal an, wie wir die Multi-Threading-Fähigkeiten der verbauten CPU ermitteln können.

  • Anzahl der Prozessoren bzw. CPU-Kerne (nebenläufige Hardwarethreads) ermitteln:

int32_t numCpuCores = omp_get_num_procs();

Sofern eine Anwendung nicht auf sämtliche zur Verfügung stehende nebenläufige Hardwarethreads bzw. CPU-Kerne zurückgreifen soll, können wir die Anzahl der verfügbaren Threads mit Hilfe der omp_set_num_threads()-Funktion selbstverständlich auch begrenzen:

// maximal vier Threads verwenden: omp_set_num_threads(4);

Mit Hilfe der omp_get_max_threads()-Funktion können wir die Anzahl der maximal verfügbaren Threads abfragen. Ohne einen vorangegangenen Aufruf der omp_set_num_threads()-Funktion entspricht der zurückgelieferte Wert der Anzahl an CPU-Kernen bzw. Hardwarethreads:

int32_t maxThreads = omp_get_max_threads();

Möchte man nun einen Source-Code-Abschnitt (einen mit geschweiften Klammern gekennzeichneten lokalen Gültigkeitsbereich) parallelisieren, müssen wir den betreffenden Bereich für den Compiler (#pragma) mit der OpenMP-Direktive (omp) parallel kennzeichnen.

  • Beispiel 1 – Im Zuge der Parallelisierung sollen alle verfügbaren Threads genutzt werden:

    #pragma omp parallel { //[do something] }
  • Beispiel 2 – Im Zuge der Parallelisierung sollen vier Threads genutzt werden (Variante 1):

    #pragma omp parallel num_threads(4) {  //[do something] }
  • Beispiel 3 – Im Zuge der Parallelisierung sollen vier Thread genutzt werden (Variante 2):

    omp_set_num_threads(4); #pragma omp parallel {  //[do something] }

Würde man beispielsweise versuchen, aus mehreren nebenläufigen Threads heraus Nachrichten auf dem Bildschirm auszugeben, würde das mit ziemlicher Sicherheit zu einem üblen Kauderwelsch führen. Der Grund dafür ist, dass es nur einen Output-Stream gibt und demzufolge auch immer nur ein Thread zu einem bestimmten Zeitpunkt auf diesen Stream zugreifen sollte. Eine solche Vorgehensweise ist demzufolge nicht zu empfehlen:

#pragma omp parallel { cout << "Message1 "; cout << " Message2 "; cout << " Message3 " << endl; }

Um sicherzustellen, dass die Threads ihre Nachrichten nacheinander auf dem Bildschirm ...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang