Thread-basierte (Kollisions)berechnungen – Worker-Threads, Events und Interlocked-Funktionen

Im heutigen Artikel werden wir uns mit dem Ablauf der im OpenGL-Programmbeispiel 12 durchgeführten thread-basierten Kollisionsberechnungen befassen. Sicher werden sich einige von Ihnen die Frage stellen, welche Vorteile wir von der Auslagerung der Kollisionsberechnungen zu erwarten haben oder ob wir die Berechnungen dadurch nicht unnötig verkomplizieren.
Um zu zeigen, wie viel Rechenleistung selbst einfachste Bounding-Sphären-Ausschlusstests bei einer zunehmenden Anzahl von potenziellen Kollisionspartnern beanspruchen, betrachten wir einige Zahlenbeispiele:

• 2 Objekte: 1 mögliches Kollisionspaar
• 3 Objekte: 3 mögliche Kollisionspaare
• 4 Objekte: 6 mögliche Kollisionspaare
• 100 Objekte: 4950 mögliche Kollisionspaare
• n Objekte: n*(n-1)/2 mögliche Kollisionspaare

Ohne zusätzliche Optimierungen – wie beispielsweise durch die Sektorisierung der Spielewelt – können die Kollisionsberechnungen einen Prozessor schneller als man denkt in die Knie zwingen. Die Framerate bricht ein, das Spiel beginnt zu ruckeln und wird unspielbar. Entkoppelt man jedoch diese Berechnungen vom eigentlichen Hauptprogramm und führt sie in einem separaten Thread aus, dann bleibt die Framerate stabil.

Multithread-optimierte Kollisionsberechnungen

Die wohl größte Herausforderung bei der Entwicklung von multithread-fähigen Anwendungen besteht darin, diese threadsicher zu konzipieren. Die in der Theorie so wohlklingende Idee des Multithreadings – die Parallelverarbeitung – sieht sich in der Realität mit ernst zu nehmenden Schwierigkeiten konfrontiert, denn echte Parallelverarbeitung funktioniert nur bei wirklich unabhängigen Aufgaben. In der Realität müssen Threads aufeinander warten, weil ein Thread die Berechnungen eines zweiten Threads benötigt oder werden geblockt, weil gerade ein zweiter Thread auf eine gemeinsam genutzte Ressource zugreift. Diese Mittel der Synchronisierung können jedoch in Echtzeit-Anwendungen schnell zu gravierenden Problemen führen.

Spielephysik (game physics): Tageszeitänderungen (scheinbare Sonnenbahnen)

Bevor wir mit der Simulation von Tageszeitänderungen beginnen können, müssen wir uns zuvor mit einem anderen Problem befassen – die wechselseitige Umrechnung von Simulationszeit und Uhrzeit.
Die Simulationszeit bemisst sich normalerweise in Sekunden. Da die Uhrzeit jedoch in Stunden, Minuten und Sekunden angegeben wird, benötigen wir eine Formel für die Umrechnung der Uhrzeit in Simulationszeit:

ActualTime = (float)Seconds + (float)Hours*3600.0f + (float)Minutes*60.0f;

Spielephysik (game physics): Impuls, Kraft, Arbeit und Energie

Da die Physik in modernen Computerspielen einen immer höheren Stellenwert einnimmt, sollte man sich zumindest mit einigen wenigen physikalischen Grundbegriffen vertraut machen. Besonders die Hobby-Entwickler unter Ihnen werden sich früher oder später mit dem Thema Spielephysik auseinandersetzen müssen, wenn die Evaluierung und mögliche Integration einer Physik-Engine in das eigene Spieleprojekt ansteht. Dieser Artikel soll Ihnen die wichtigen Begriffe Impuls, Kraft, Arbeit und Energie ein wenig näher bringen ohne die Sache unnötig zu verkomplizieren.

Spielephysik (game physics): Geschossflugbahnen (Ballistik)

Die Simulation von realistisch wirkenden Geschossflugbahnen zählt zu den zentralen Gamplay-Elementen eines jeden Kriegs- oder Strategiespiels. In Vergessenheit geraten ist hingegen das früher einmal so beliebte Genre der Artillerie-Spiele, in denen nicht die KI sondern wir als Spieler dafür verantwortlich waren, die feindlichen Ziele zu treffen. Vielleicht erinnern sich noch einige von Ihnen an das kostenlose Spiel Ballerburg (Neuauflage 2001 durch Ascaron). Als Herr einer Burg trat man gegen den Computer oder einen menschlichen Gegner an und musste Runde für Runde die feindliche Burg unter Beschuss nehmen, bis einer der Burgherren durch einen direkten Treffer getötet wurde.

Spielephysik (game physics): Federkräfte oder was einen Körper zusammenhält

Im heutigen Artikel werden wir der Frage nachgehen, wie sich die Stabilität des Massenpunktmodells und damit verbunden die Stabilität und Form eines Körpers gewährleisten lässt. Bedenken Sie in diesem Zusammenhang – damit ein Körper seine Form beibehalten kann, müssen die relativen Abstände (Bindungslängen) zwischen den Massenelementen nahezu konstant bleiben. Durch Kollisionen oder Rotationsbewegungen ändern sich diese Abstände zwischenzeitlich, wobei Kräfte auftreten, die es nun zu berechnen gilt.

Spielephysik (game physics): Schwerpunkt, Massenpunktmodell eines Körpers (mass-aggregate bodies)

Woraus besteht die Materie und wie lässt sich ihr Verhalten beschreiben? Unzählige Wissenschaftler haben sich bereits mit diesen Problemen befasst, und auch heute ist es noch immer nicht möglich, eine erschöpfende Antwort auf diese Fragen zu geben. Im Jahre 1808 stellte der Naturforscher John Dalton auf Grundlage der damals durchgeführten Experimente die Hypothese auf, dass alle Materie aus kleinsten Teilchen, den Atomen bestehen müsse. Die Idee vom Atom wurde zwar bereits in der griechischen Antike geboren, jedoch war John Dalton der erste Forscher, der mithilfe dieser Idee die experimentellen Ergebnisse seiner Zeit schlüssig erklären könnte.
In ihrer einfachsten Form hilft uns die Atomhypothese das makroskopische Verhalten (Translations- und Rotationsbewegungen) von dreidimensionalen Körpern mathematisch zu beschreiben.

Spielephysik (game physics): Auftriebskraft und Schwimmfähigkeit

Die Darstellung von realistischen Wassereffekten hat sich in den letzten Jahren kontinuierlich weiterentwickelt und ist aus modernen Computerspielen mittlerweile nicht mehr wegzudenken. Dabei kommt es natürlich nicht nur auf die grafische Umsetzung an – wirklich realistisch wird das Ganze erst durch eine glaubhaft wirkende Interaktion zwischen dem Wasser und den Spieleobjekten.
In diesem Zusammenhang steht neben der stark abbremsend wirkenden Newton-Reibung ein zweites Phänomen im Vordergrund, mit dem wir uns an dieser Stelle befassen werden – die Auftriebskraft (Buoyancy).

Spielephysik (game physics): Bodenreibung auf einer schiefen Ebene

Im ersten Kapitel über Bodenreibung haben wir uns auf lediglich die Bewegung in der horizontalen Ebene beschränkt. Für diesen Spezialfall berechnet sich die Reibungskraft gemäß der folgenden Beziehung:

F(Reibung) = -Bewegungsrichtung * m *g * µ = -Bewegungsrichtung * m * µ' mit  µ' = g * µ

Wenn wir nun beliebige Bewegungsrichtungen, also auch Steigungen und Gefälle zulassen, dann wird die Behandlung der Bodenreibung wird etwas komplizierter. In der nachfolgenden Abbildung ist eine solche Situation einmal dargestellt:

Spielephysik (game physics): Bodenreibung

Bei der Bodenreibung gilt es, zwei Reibungsformen auseinander zu halten:

Die Bodenhaftung (Haftreibung), die immer überwunden werden muss, um einen Körper  in Bewegung zu versetzen.

Die Gleitreibung, die alle bewegten Körper gleichmäßig abbremst.

Um dies zu veranschaulichen: Die Reibung kommt dadurch zustande, dass ein Körper durch seine Gewichtskraft auf den Boden gedrückt wird, wodurch eine Haftwirkung zwischen dem Körper und dem Boden ermöglicht wird. Für die Haftwirkung selbst sind zwischenmolekulare Wechselwirkungen verantwortlich.

Spielephysik (game physics): Newton-Reibung in Wasser und Luft (Luftwiderstand)

Bei der Bewegung eines Körpers durch Luft oder ein anderes Medium wirkt dieser Bewegung eine Kraft entgegen, die proportional zum Quadrat der Geschwindigkeit ist:

Spielephysik (game physics): Numerische Integration

Physikalische Simulationen mit sich schnell ändernden Kräften (z. B. ein Masse-Feder-System) tendieren mit der Zeit dazu, instabil zu werden. Da sich keine Aussagen darüber treffen lassen, wie sich die Kräfteverhältnisse und damit verbunden die Geschwindigkeiten zwischen zwei Zeitschritten verändern, vergrößern sich mit jedem Rechenschritt die Abweichungen vom realen Verhalten. Irgendwann sind die Berechnungsfehler so groß, dass die Bewegungsenergie der simulierten Körper über die Maßen ansteigt und die Simulation regelrecht explodiert.
Besonders problematisch ist die Situation bei Wechselwirkungskräften (z. B. Federkräfte), denn dann wirken sich die Berechnungsfehler zusätzlich auf alle miteinander wechselwirkenden Körper aus. Nachfolgend wird nun ein Integrationsverfahren vorgestellt, mit dessen Hilfe sich die Berechnungsfehler minimieren lassen.

Spielephysik (game physics): Planetenbewegung

Elite 2 Frontier gilt als das erste Spiel, in dem Gravitationskräfte auf Planeten und Raumschiffe korrekt simuliert werden. Es ist sogar möglich, so genannte Swing-By-Manöver zu fliegen, bei denen ein Raumfahrzeug im Einflussbereich des Gravitationsfelds eines Planeten zeitweilig von diesem mitgezogen wird, wobei sich seine Fluggeschwindigkeit relativ zur Sonne entweder erhöht oder erniedrigt (siehe hierzu http://de.wikipedia.org/wiki/Swing-by).

Planeten werden durch zwei Kräfte auf ihrer Bahn (Orbit) gehalten, die zwar vom Betrag her gleich groß sind, aber in entgegengesetzte Richtungen wirken. Die Zentrifugalkraft (Fliehkraft) zeigt von der Sonne weg und versucht einen Planeten gewissermaßen aus der Bahn zu schleudern. Die Zentripetalkraft zeigt in Richtung der Sonne und kompensiert die Fliehkraft vollständig. Ursache der Zentripetalkraft ist die Massenanziehung (Gravitation) der Sonne, die durch das Newtonsche Gravitationsgesetz beschrieben wird:

Spielephysik (game physics): Simulation von Beschleunigung und Bewegung (Einführung)

Die Physik spielt bei der Entwicklung von Computerspielen eine immer wichtigere Rolle. So realistisch die Simulationen letzten Endes auch erscheinen mögen, die grundlegende Physik dahinter ist überraschend einfach, denn alle Berechnungen lassen sich auf eine einfache Gleichung – das 2. Newtonsche Axiom – zurückführen:

Spielephysik (game physics): Kollisionen von Massenpunkten im 3D-Raum

Es gab Zeiten, da konnten Spieleentwickler von den Möglichkeiten heutiger Physik Engines nur träumen. An komplexe Echtzeitsimulationen war wegen der noch viel zu geringen Rechenleistung von CPU und GPU nicht zu denken. Um die Spiele realistischer zu gestalten, beschränkte man sich auf wenige einfache physikalische Effekte (Erdanziehung, Reibungseinflüsse, Stöße, usw.). Deren Berechnung in Echtzeit war jedoch nur im Rahmen einfacher Massenpunkts-Mechanik möglich; die Ausdehnung der Spieleobjekte wird hierbei vernachlässigt.
Kollidieren zwei Objekte mit den Massen m(a) und m(b) miteinander, lassen sich die Geschwindigkeiten nach der Kollision ( v(a, nachher), v(b, nachher) ) als Folge der Geschwindigkeiten von vor der Kollision ( v(a, vorher), v(b, vorher) ) berechnen. Bleibt die kinetische Energie (Bewegungsenergie) während des Stoßprozesses erhalten, so spricht man von einem elastischen Stoß. Hier die Gleichungen für die Berechnungen der Endgeschwindigkeiten im eindimensionalen Fall: