Mathematikgrundlagen zur Spieleprogrammierung

Dieses Tutorial geht auf die häufigsten mathematischen Probleme ein, die besonders bei der 2D-Spieleentwicklung auftauchen.

Richard Schubert 07/2003

 Anregungen oder Tipps an Richard
 
  Einführung voriges Thema [ Top ] nächstes Thema

Der Traum vieler Computerspieler ist es selbst Spiele zu entwickeln. Viele versuchen ihr Glück, doch schon nach kurzer Zeit nach Beginn des Programmierens tauchen schon die ersten Probleme auf. Wie mache ich dies, wie soll das gehen? Diese Hindernisse sind meist mathematischer Natur, denn ein Spiel besteht im Kern ausschließlich aus Mathematik. Deshalb geht dieses Tutorial auf die häufigsten mathematischen Probleme ein, die besonders bei der 2D-Spieleentwicklung auftauchen.

Man beachte dabei, Mathematik besteht eher weniger aus Gleichungen und Regeln die man auswendig kennen muss, sondern vielmehr aus der Fähigkeit selbst neue Regeln aufzustellen, die auf bereits bekannte Regeln aufbauen. Die Technik, selbst neue Probleme zu lösen, wird in jedem Themengebiet näher erläutert.

 
  Logik voriges Thema [ Top ] nächstes Thema

Die Logik bildet für alles die Grundlage. Mit ihr ist man in der Lage, Situationen richtig zu analysieren und Bedingungen ordnungsgemäß zu formulieren. Dieses Themengebiet muss unbedingt beherrscht werden, um selbst Regeln aufstellen zu können.

Um Logik beim Programmieren richtig zu verwenden, muss man jede Gesetzmäßigkeit in eine Aussage, die nur "Wahr" oder "Falsch" beinhalten kann, umwandeln können.
 
Ein kleines Beispiel:

Wir wollen eine Aussage schaffen, die beinhaltet ob eine Variable X gleich 5 ist.
Die Logik diktiert:    Aussage = ( X = 5 )

Wenn X jetzt zum Beispiel 3 wäre dann würde die Aussage "Falsch" enthalten, da 3 ungleich 5 ist. Falls X den Wert 5 annimmt, würde die Aussage "Wahr" enthalten, da 5 gleich 5 ist.

Diese Art und Weise einen Ausdruck zu betrachten und zu bearbeiten nennt sich Boolesche Algebra (George Boole, englischer Mathematiker, 1815-1864).

Verknüpfungen

Beim Aufstellen von Aussagen werden verschiedene Verknüpfungen verwendet, die einem eine Vielzahl von Regeln ermöglichen. Die Variablen a, b und c sind binäre Aussagen die "Wahr" oder "Falsch" beinhalten können.

Verknüpfung

Negation

Konjunktion

Disjunktion

Alternative

Implikation

Äquivalenz

ASM

NOT

AND

OR

XOR

IMP

XAND

Symbol

Negation:
Gesprochen: "nicht a"

Jede Aussage wird bei der Negation invertiert, d.h. eine wahre Aussage wird eine falsche Aussage und umgekehrt.

Konjunktion:
Gesprochen: "a und b" oder "sowohl a als auch b"

Zwei Aussagen können mit einer Und-Verknüpfung verbunden werden. Die Gesamtaussage wird nur dann "Wahr", wenn beide Teilaussagen "Wahr" beinhalten.

Disjunktion:
Gesprochen: "a oder b" oder "einschließendes oder"
Die Gesamtaussage wird dann "Wahr", sobald eine Teilaussage "Wahr" ist.
Alternative:
Gesprochen: "entweder a oder b" oder "ausschließendes oder"
Die Gesamtaussage wird dann "Wahr", wenn beide Teilaussagen ungleich sind.
Alternative Schreibweise:   oder 
Implikation:
Gesprochen: "wenn a dann b"
Die Gesamtaussage wird dann "Wahr", wenn b "Wahr" beinhaltet oder a "Falsch" ist.
Alternative Schreibweise: 
Äquivalenz:
Gesprochen: "genau dann a wenn b"

Die Gesamtaussage wird dann "Wahr", wenn beide Teilaussagen gleich sind. Im Grunde eine Negation der Alternative.

Alternative Schreibweise: oder 

Zur Verdeutlichung der Funktionsweise jeder einzelnen Verknüpfung sind hier noch Wahrheitstabellen aufgelistet.
Rechenregeln

Da die letzten drei Verknüpfungen durch NOT, AND und OR dargestellt werden können, gehen wir nicht weiter auf diese ein. Die folgenden Rechengesetze helfen beim Aufstellen, Umstellen und Vereinfachen von Aussagen.
Im allgemeinen gilt auch die Schreibweise für und für "Wahr" steht die 1, und für "Falsch" die 0. Und-Verknüpfungen sind hochrangiger als Oder-Verbindungen, und es ist in den folgenden Regeln nicht festgelegt, welche Variable "Wahr" oder "Falsch" ist.

1. Doppelte Verneinung
2.
3.
4.
5.
6.
7.
8.
9.
10.
11. Kommutativgesetz
12. Kommutativgesetz
13. Assoziativgesetz
14. Assoziativgesetz
15. Distributivgesetz
16. Distributivgesetz

Zum Abschluss sind noch ein paar Beispiele aufgelistet, wie man Anhand der oben gezeigten Rechenregeln komplizierte Ausdrücke vereinfachen kann.

17.
18.
19.
20.
21.
22.
 
  Koordinatensysteme voriges Thema [ Top ] nächstes Thema

Der Aufbau und die Funktionsweise von Koordinatensystemen muss als selbstverständlich gelten, um ein einfaches Arbeiten zu ermöglich. Da es aber eine Unzahl an Koordinatensystemarten gibt, werden hier nur die wichtigsten behandelt.

Das kartesische Koordinatensystem der Ebene

In diesem Koordinatensystem liegen die Achsen (Abszisse und Ordinate) senkrecht aufeinander. So ist es hier möglich einen Punkt zu setzen der durch zwei Argumente (X, Y) definiert ist.

In leicht abgewandelter Form wird diese Art des Koordinatensystems bei der Ausgabe auf dem Bildschirm des Computers verwendet. Der einzige Unterschied besteht in der Ausbreitungsrichtung der Ordinate.

Das kartesische Koordinatensystem des Raumes

In der Mathematik findet dieses Koordinatensystem eher selten Anwendung. Ein Punkt ist hier durch drei Argumente definiert (X, Y, Z).

In Direct3D wird zur besseren Übersicht die Z-Koordinate als Tiefenargument verwendet.
In OpenGL werden außerdem alle Ausbreitungsrichtungen der Achsen umgekehrt.
 
  Funktionen voriges Thema [ Top ] nächstes Thema

Funktionen an sich sind bei der Spielentwicklung weniger wichtig, als die Art und Weise ihrer Anwendung. Ihre Funktionsweise ist dabei am meisten gefragt. Die am häufigsten benötigte Funktionsart wird hier näher erläutert.

Lineare Funktionen

Lineare Funktionen sind sehr einfach zu beschreiben, sind aber gleichzeitig die nützlichste Funktionsart. Eine lineare Funktion ist grafisch dargestellt eine Gerade, die eine unendliche Anzahl von Wertepaaren beinhaltet. Eine solche Funktion lässt sich durch 2 Punkte eindeutig beschreiben und kann in folgender Weise dargestellt werden:

Der Faktor m ist der Anstieg der Funktion f, dieser gibt an wie stark die Gerade steigt oder fällt. n ist das Y-Argument des Punktes Sy(0;n) der der Schnittpunkt der Funktion mit der Ordinate ist.

Beispiel:
 
Der Satz des Pythagoras voriges Thema [ Top ] nächstes Thema
Wer war Pythagoras

Pythagoras von Samos lebte ungefähr von 580 - 496 v. Chr. und bis heute ist nicht sicher, ob er es war, der diesen bedeutenden Lehrsatz entdeckt hat.

Denn schon die Ägypter haben um einen rechten Winkel zu schaffen das Seitenverhältnis 5:4:3 verwendet. Sie waren sich der Verwendung dieses Gesetzes vielleicht nicht bewusst, aber hatten mit ihrem ägyptischen Dreieck sicherlich die Überlegungen von Pythagoras beeinflusst.

Am Ende ist es aber auch weniger relevant wer diese Gesetzmäßigkeit entdeckt hat. Es ist nur wichtig, sie sinnvoll einzusetzen.

Was beinhaltet der Satz des Pythagoras

Im rechtwinkligen Dreieck ist das Quadrat über der Hypotenuse gleich der Summe der Quadrate über den Katheten.

a² + b² = c²

Jeder wird diesen Lehrsatz schon einmal in der Schule behandelt haben. Noch mal zur Auffrischung, die Hypotenuse ist die längste Seite eines rechtwinkligen Dreiecks.

Warum ist der Lehrsatz beim Programmieren so wichtig

Der Nutzen des Satzes ist auf dem ersten Blick nicht so einfach zu erkennen. Doch bei näherer Betrachtung erinnert man sich vielleicht an die Rechtwinkligkeit von kartesischen Koordinatensystemen. So kann man mit diesem Lehrsatz im kartesischen Koordinatensystem direkte Abstände zwischen zwei Punkten ermitteln.

 
  Mittelwerte voriges Thema [ Top ] nächstes Thema

Mittelwerte sind beim Programmieren eher weniger von nutzen, sie sind vielmehr eine Hilfe um Probleme besser lösen zu können. Mittelwerte sind auch als Durchschnitt bekannt, wenn man zum Beispiel den Durchschnitt seiner Zensuren des Zeugnisses berechnen will.

Wie kann man Mittelwerte errechnen?

An sich ist die Berechnung ganz einfach. Man addiert alle Elemente (a), die zusammen den Mittelwert bilden sollen zu einer Summe. Diese Summe muss schließlich durch die Anzahl (n) der Elemente, die die Summe bilden, dividiert werden.

Das Ergebnis wird auch genannt (gesprochen: X-Quer).
 
  Trigonometrie voriges Thema [ Top ] nächstes Thema

Unter Trigonometrie (Dreiwinkelmessung) versteht man das Messen oder das Berechnen von Dreiecken, in die jede geradlinig begrenzte Figur durch Diagonalen zerlegt werden kann.

Die Grundlagen der Trigonometrie

Um Trigonometrie anwenden zu können, muss man erst mal die Grundlagen beherrschen. So muss als erstes geklärt werden, was die Begriffe Sinus und Kosinus bedeuten. Das folgende Beispiel soll dabei eine Hilfe sein.

Ihr Browser ist nicht java-f&aumlhig!

Wie man an der obigen Abbildung erkennen kann, sind die Funktionen Sinus und Kosinus von einem Winkel (hier RAD) abhängig. Dieser Winkel wird im Bogenmaß angegeben, d.h. er ist nicht in Grad angegeben und entspricht den Größenangaben der Achsen. Da es sich um einen Einheitskreis handelt (der Radius beträgt 1) beträgt der Umfang des Kreises 2xPI. So wiederholen sich die Funktionswerte von Sinus und Kosinus bei 2xPI als wäre RAD gleich 0.

Dadurch kann man nicht nur an der Abbildung die Periodität von Sinus und Kosinus erkennen, sondern auch, dass die beiden Funktionen phasenverschoben sind ( Sin(X+PI/2) = Cos(X) ).

Im Grunde liefert die Sinusfunktion den Y-Wert eines Punktes auf einem Kreis und die Kosinusfunktion liefert den X-Wert eines Punktes auf einem Kreis. Man benötigt nur den Winkel im Bogenmaß um die Koordinaten des Punktes zu erfahren. Alle Punkte dieser Funktionen liegen wie schon erwähnt auf einem Kreis mit dem Radius 1. Falls die Ergebnisse aber auf einer Kreisbahn mit einem anderen Radius liegen sollen, so braucht man die Ergebnisse nur mit dem gewünschten Radius zu multiplizieren.

Ein freier Schenkel des Winkels der Größe x in einem beliebigen Kreis schneidet im Punkt P(u; v).

Da der Sinus und der Kosinus nur für den Einheitskreis gelten, müssen bei beliebigen Kreisen die u- und v-Werte erst durch den Radius dividiert werden, bevor man die Winkel erhalten kann.

Der Tangens eines Winkels ist als Sinus des Winkels dividiert durch den Kosinus des Winkels definiert. Oder kurz: Der Tangens eines Winkels gibt die Steigung des Schenkels an. Dadurch ist der Tangens an den Winkeln 0.5*PI und 1.5*PI nicht definiert.

Berechnung rechtwinkliger Dreiecke

Wir beschränken uns auf das Berechnen von rechtwinkligen Dreiecken. Die Zerlegung von anderen Formen in Dreiecke würde in diesem Tutorial zu weit führen, und jetzt kommen wir zur Zauberei, wie viele sagen würden, die sinnfrei solche Floskeln auswendig lernen.

GAGA
HHAG

(gesprochen: Gaga HummelHummel AG)

Jedenfalls kann man auf so etwas verzichten, wenn man verstanden hat, worum es eigentlich geht. Es geht nämlich um das Berechnen von Winkeln aus Seiten von rechtwinkligen Dreiecken und umgekehrt.

Die letzte Gleichung beschreibt den Kotangens, der nichts weiter bedeutet, als 1 dividiert durch Tangens, und daher außerordentlich nebensächlich ist. Diese Gleichungen muss man nicht auswendig lernen, da man sie leicht durch solch eine Skizze schon in Gedanken herleiten kann.

 
  Framerate (FPS) voriges Thema [ Top ] nächstes Thema
Wenn man ein Spiel programmiert, ist es in der Regel wichtig zu wissen wie schnell es läuft. Die Framerate gibt an, wie viele Bilder (Frames) pro Sekunde vom Computer dargestellt werden können. Wenn die einzelnen Bilder zu langsam hintereinander ablaufen, ruckelt eine Animation, da erst ab 25 Bilder pro Sekunde der Mensch die einzelnen Bilder als Film bzw. Animation sieht.

So kann man mit einer FPS-Messung sehr gut die Geschwindigkeit von verschiedenen Algorithmen unterscheiden, um somit mehr Leistung aus dem Programm zu holen. Da aber auf jedem Rechner, aufgrund der unterschiedlichen CPU-Taktraten, Spiele unterschiedlich schnell ablaufen, ist solch eine Messung außerdem sehr gut zur Geschwindigkeitskontrolle des Spiels geeignet.

Wie berechnet man die FPS?

Sollen berechnet werden, wie viele Frames in einer Sekunde berechnet/dargestellt werden, ist es sinnvoll die Gegebenheiten eines Spiels näher zu betrachten. Das Spiel läuft in einer Schleife. In einem Schleifendurchlauf wird ein Frame berechnet/dargestellt.

Wir müssen also jeden Frame irgendwas machen, damit wir die Frames berechnen können. Die einfachste Möglichkeit wäre zu zählen, wie viele Frames in einer Sekunde berechnet/dargestellt werden. Ein Problem fällt dabei sofort auf, die Framerate wird nur alle 1000 ms erneuert. Das reicht vielleicht um eine gute Messung zu erhalten, und es ist für eine Geschwindigkeitskontrolle des Spiels zu langsam.

Eine bessere Variante ist es, zu messen wie lange es dauert, einen Frame zu berechnen / darzustellen und das Ergebnis auf eine Sekunde hochzurechnen. So hat man für jeden Frame eine neue Messung, und kann die Spielgeschwindigkeit sofort korrigieren.

 
  2D-Kollisionserkennung voriges Thema [ Top ] nächstes Thema

In Spielen ist es häufig notwendig eine Kollisionserkennung zu implementieren. Es werden hier die am häufigsten benötigten Kollisionsarten angesprochen.

Kollision zweier Rechtecke

Dies ist die einfachsten Kollisionserkennungen, und  wie eine solche auszusehen hat kann man sich schnell überlegen. Man hat nur bestimmte Angaben der Rechtecke, die diese aber eindeutig definieren. So kann man auch nur diese für die Kollisionserkennung verwenden. Wenn man die Rechtecke und den Raum in dem sie sich befinden näher betrachtet, fällt einem auf, dass die Angaben der Rechtecke eine bestimmte Menge aus dem Raum, in dem die Rechtecke sich befinden, definieren. Da die Angaben der Rechtecke diese Mengen begrenzen, braucht man nur testen ob diese Grenzen überschritten werden.

So kann man eine einfache Abfrage gestalten:
Wenn
      (R1.Bottom > R2.Top
    UND
      R1.TOP < R2.Bottom
    UND
      R1.Right > R2.Left
    UND
      R1.Left < R2.Right)
dann: KOLLISION!!!
Hier ein Beispiel: Kollisionserkennung 2D
Kollision zweier Kreise

Die Kollision zwischen zwei Kreisen zu realisieren, scheint auf den ersten Blick ziemlich komplex zu sein. Beim genaueren Betrachten der Angaben die für einen Kreis notwendig sind, stellt sich heraus, das es noch einfacher wird als eine Rechteckkollision. Der Kreismittelpunkt und der Radius eines Kreises definieren ihn eindeutig. So ist jeder Punkt Element des Kreises, wenn er mindestens genauso nah wie der Radius lang ist, vom Mittelpunkt entfernt ist.

Im Falle einer Kollision zwischen zwei Kreisen gibt es also immer mindestens einen Punkt der ein Element beider Kreise ist. Dieser ist dann zwangsläufig nicht weiter entfernt von den Mittelpunkten der Kreise als der Radius dieser. Daraus folgt, dass genau dann eine Kollision stattfindet, wenn die Mittelpunkte der Kreise näher aneinander sind, als die Summe der Radien groß ist.

Die Umsetzung ist sehr einfach. Berechnet wird die Entfernung (Pythagoras sei Dank) zwischen zwei Punkten, wobei man am Besten den Mittelpunkt der Objekte nimmt. Ist dann die errechnete Distanz kleiner als der Radius beider Objekte, liegt eine Kollision vor.

So könnte man solch eine Abfrage gestalten:
Wenn
   
(Wurzel((K1.X - K2.X)*(K1.X - K2.X) + (K1.Y - K2.Y)*(K1.Y - K2.Y))
    <
    (K1.Radius + K2.Radius))
dann: KOLLISION!!!
Hier ein Beispiel: Kollisionserkennung (Distanz-Berechnung)
Kollision zweier Linien

Wenn man zwei Linien betrachtet die überprüft werden sollen, kann man schnell die Ähnlichkeit zu linearen Funktionen herleiten. Denn die Linien sind bloß Ausschnitte von linearen Funktionen wenn man so will.

Als erstes muss man aus den gegebenen Linien zwei Funktionen machen. Die Werte "m" und "n" müssen daher berechnet werden. Die Steigung einer Funktion (oder der Linie) berechnet sich ganz einfach durch den Term (Y2-Y1) / (X2-X1) wie nach dem so genannten Steigungsdreieck.
Wenn man die Funktion  nun nach "n" umstellt und einige bekannte einsetzt X1, Y1 und m so erhält man den Wert für "n".

Den Schnittpunkt der Funktionen zu ermitteln ist nun sehr einfach. Man setzt beide Funktionen gleich und formt diese Gleichung solange um, bis man das X-Argument des Schnittpunktes besitzt. Im Computer geht das ganz analog dazu, nur das man die Gleichsetzung schon im Voraus so umstellt das man sofort das Ergebnis erhält. Jetzt wurde der Schnittpunkt von zwei Funktionen ermittelt, da wir aber den Schnittpunkt zwischen zwei Linien berechnen wollten, muss noch abgefragt werden ob der Schnittpunkt ein Element der beiden Linien ist.

Ein paar Probleme wirft diese Art der Lösung doch auf. Wenn eine der Linien Senkrecht zur X-Achse steht, kann die Steigung nicht berechnet werden, da sie an dieser Stelle unendlich ist, oder wenn die Linien parallel verlaufen, haben sie keinen Schnittpunkt oder sie liegen genau aufeinander. Für diese Probleme kann man Abfragen erstellen, die diese Schwierigkeiten eliminieren. Man kann es aber auch sein lassen, da in einem Spiel Linien mit Gleitkomma-Koordinaten nur mit extrem geringer Wahrscheinlichkeit genau Senkrecht oder Parallel werden.

Hier ein Beispiel: Linienkollision
 
  Winkelermittlung voriges Thema [ Top ]
Wozu ist Winkelermittlung nützlich?
In vielen Spielen gibt es Objekte die sich drehen können. Häufig ist es notwendig zu wissen wie man diese Objekte drehen soll, da diese sich eventuell auf andere Objekte ausrichten sollen. 
Da man aber die Ausrichtung nur über einen Winkel angeben kann, muss man eben den Winkel errechnen den das Objekt in Bezug auf das sich drehbare Objekt hat.
Wie kann man es umsetzen?
In diesem Fall möchte man aus X-, Y-Koordinaten einen Winkel erhalten. Mit den Winkelfunktionen lassen sich ja Mühelos X- und Y-Koordinaten aus einem Winkel berechnen, doch geht das auch umgekehrt so einfach? Nein, leider nicht. Da die Umkehrungen der Winkelfunktionen nicht eindeutig sind, muss man ein paar zusätzliche Abfragen realisieren. Die Umkehrfunktion die in den meisten Programmiersprachen vorhanden ist, ist der Arkustangens (Atn).
Hier ein Beispiel: Winkelermittlung

Startseite | VB/VBA-Tipps | Projekte | Tutorials | API-Referenz | Komponenten | Bücherecke | VB-/VBA-Forum | VB.Net-Forum | DirectX | DirectX-Forum | Foren-Archiv | VB.Net | Chat | Links | Suchen | Stichwortverzeichnis | Feedback | Impressum

Seite empfehlen Bug-Report
Letzte Aktualisierung: Dienstag, 08. Juni 2004