21.06 Eine Physikengine in Java ME

Physikalisch korrekte Kollision zweier Bälle

Normalerweise werden in einfachen Spielen die Sprites einfach über die x- und y- Koordinaten sowie über die Breite und die Höhe eines Sprites abgefragt, also über das Box-System. Überschneiden sich die Boxen zweier Sprites, haben wir eine Kollision. Wenn die Sprites die Box allerdings nicht ausfüllen (wie es z. B. Bälle nicht tun), kommt es zu großen Ungenauigkeiten, die in einer programmierten Physik zu eklatanten Fehlern führen können.

Im Beispielbild berühren sich zwar die Boxen, die Bälle haben aber keinen Kontakt. Bei schnellen Bewegungen würde das vielleicht gar nicht auffallen, aber bei Stillstand ist der Fehler in der Kollisionsabfrage offensichtlich:

Im linken Bild wird nur die Box abgefragt, d.h. der Ball schwebt im ungünstigen Fall mitten in der Luft zwischen zwei darunter liegenden Bällen. In der Realität würde der Ball aber den direkten Kontakt zu den beiden anderen Bällen suchen und durch die Schwerkraft in die Lücke fallen.

Nun bestünde zwar die Möglichkeit, die beiden Sprites Pixel für Pixel zu kontrollieren oder die beiden Sprites in Teilsprites und damit Teilboxen aufzuteilen, um die Kollision etwas genauer abzufragen, aber J2ME bietet bislang leider nur unzureichende Pixelabfragen und zweitens würde bei vielen Bällen die Geschwindigkeit immens leiden, da die Anzahl der Kollisionsabfragen mit der Anzahl der Teilboxen multipliziert werden müsste.

Es gibt einen deutlich einfacheren Weg, der auf die besonderen Eigenschaften eines Ball zurückgreift: Jeder Punkt an der Oberfläche eines Balls hat den identischen Abstand zur Ballmitte. Wir müssten also nur prüfen, ob der Abstand zweier Mittelpunkte kleiner ist als die Summer ihrer Radien.

Ein Beispiel: Ein Ball mit dem Radius 3 cm und ein Ball mit dem Radius 5 cm berühren sich, sobald der Abstand ihrer Mittelpunkte geringer ist als 3 cm + 5 cm = 8 cm.

Doch wie kommt man an den Abstand der Mittelpunkte? Liegen die beiden Mittelpunkte auf einer x- oder y-Höhe, lässt sich der Abstand relativ einfach ausrechnen:

Im Beispiel im Bild müssen nur die jeweiligen x-Koordinaten voneinander abgezogen werden und sobald der absolute Wert (ohne Vorzeichen) kleiner ist als 3 cm + 3 cm = 6 cm hat eine Kollision stattgefunden. Doch sobald sich beide Koordinaten voneinander unterscheiden, ist die Abstandsberechnung nur auf dem ersten Blick etwas schwieriger.

In diesem Fall erinnern wir uns einfach an den Mathematikunterricht der 8. Klasse und den Pythagoras. Den Abstand zweier Punkte im Koordinatennetz (Hypothenuse) berechnet man einfach, in dem man die Differenz der x- und y-Koordinaten (Seitenlängen) jeweils quadriert, miteinander addiert und davon die Wurzel zieht. Soll heißen:

(Differenz der x-Werte)² + (Differenz der y-Werte)² = (Abstand der Mittelpunkte)²

Da wir aber nur vergleichen müssen und Wurzelziehen wertvolle Ressourcen und Prozessorgeschwindigkeit frisst, sparen wir uns das Wurzelziehen einfach und vergleich das Ergebnis einfach mit dem Quadrat der Addition beider Radien:

Ist (Abstand der Mittelpunkte)² < (Radius 1 + Radius 2)² ? Dann hat eine Kollision stattgefunden und die Bälle prallen voneinander ab. Bei kleinen Bällen kann man den Abprallwinkel sehr gut dadurch nachprogrammieren, wenn man von einem Aufprallwinkel von 45° ausgeht. Dies erreich wir, in dem die beiden Richtungsvariablen eines Balls einfach vertauscht und negiert werden: xR wird zu –yR und yR wird zu –xR. Eine Einschränkung hat diese Vereinfachung allerdings: Bei größeren Bällen ist diese Berechnung zu ungenau und sichtbar, wir können den Algorithmus trotzdem anwenden, da diese bei derlei Spielen eher seltener vorkommen.

Hier nun der zusätzliche Codeschnipsel:

// Hintergrund loeschen
g.setColor(0,0,0); 
g.fillRect(0, 0, Xmax, Ymax);
// Kollisionsabfrage
for (p=0;p<3;p++) {
  // Kollision?
  for (i=0;i<3;i++) {
    // keine Kollision mit sich selbst
    if (i!=p) {
    if ( ((x[p]+xR[p])/100 - (x[i]+xR[i])/100) *
      ((x[p]+xR[p])/100 - (x[i]+xR[i])/100) +
      ((y[p]+yR[p]) - (y[i]+yR[i])) *
      ((y[p]+yR[p]) - (y[i]+yR[i])) <=
      (r[p] + r[i]) * (r[p] + r[i]) ) {
        merke = xR[p];
        xR[p]=-yR[p]*100;
        yR[p]=-merke/100;
        merke = xR[i];
        xR[i]=-yR[i]*100;
        yR[i]=-merke/100;
    }
  }
}
// Erdbeschleunigung
yR[p]++;

Vorher müssen allerdings die beiden neu dazugekommenen Variablen i und merke in der Klasse MyCanvas initiiert werden:

private int p=0, i=0; // Hilfsvariablen p, i (fuer Zaehler)
private int merke=0;

Voilà, wir haben drei Bälle, die in einigermaßen korrekter Spielphysik voneinander abprallen. Doch können wir damit schon richtige Spiele programmieren?

Anwendungsmöglichkeiten

Aber natürlich! Lassen wir die Schwerkraft aus dem Code weg, lässt sich ohne Weiteres eine 2D-Billardsimulation damit gestalten. Lässt man zusätzlich das Abprallen weg, hat man schnurstraks mit dem oben dargestellten Code einen Breakout-Klon programmiert. Wenn man nun über die Tastaturabfrage die Richtungen manipuliert (z. B. link: xR--; rechts: xR++; und Feuer: yR--;) hat man das Grundgerüst für das legendäre „Lunar Lander“, bei dem ein Raumschiff (der Ball) sanft auf der Mondoberfläche gelandet werden muss. Allerdings sollte in diesem Fall auch die Erdanziehungskraft stark reduziert werden, sonst ist der Spielspass schnell hinüber.

Ebenso das Prinzip der Worms-Spiele lässt sich nun leichter programmieren. Der eingegebenen Winkel ergibt sich aus dem Sinus bzw Kosinus unserer xR– und yR-Werte, dazu die Geschwindigkeit angepasst und wir können den Schuss auf unseren Gegner los lassen.

Auch lässt sich die bisherige Physikengine beliebig erweitern und natürlich ausbauen. Soll z. B. Wind auf die Steuerung oder das Geschehen Einfluss haben, so genügt es, wenn die x-Koordinate in jedem Schritt um einen konstanten Wert nach links oder rechts (je nach Windrichtung) versetzt wird.

Von Bällen zu Partikeln

Aber auch andere Effekte lassen sich mit dem oben dargestellten Code erreichen: Ein Feuerwerk oder eine Explosion ist nichts anderes, als ein Ansammlung vieler Partikel, die allesamt (ohne Kollision) von einem Startpunkt starten und in einer Parabel-förmigen Wurfbahn weggeschleudert werden. Die dazugehörigen xR– und yR-Variablen lassen sich einfach über Zufallszahlen generieren, die Radien der Bälle werden einfach auf r=1 reduziert und wir haben unseren ersten Partikeleffekt programmiert, der allerdings noch nicht besonders prickelnd ist. Schließlich leuchtet jeder einzelne Partikel unendlich lang und verglüht nicht.

Hier wird nun eine weitere Variable l (für Lebenszeit) eingeführt. Diese wird zu Beginn auf einen beliebigen Wert (z. B. 100 +/- 20) gesetzt und während der Durchführung einfach auf 0 heruntergezählt. Wird in Abhängigkeit des Wertes auch noch die Farbe des einzelnen Partikels angepasst, verwandelt sich dieser während seiner Lebenszeit von weiß-glühend zu einem schwarzen Pixel, er „verglüht“. Erreicht wird dies mit einer Änderung des Befehls

// Ball zeichnen
g.setColor(l[p], l[p], l[p]); // Farbwert abhaengig von Lebenszeit
g.fillArc( (x-r), (y-r), 2*r, 2*r, 0, 360);

Nach diesem Prinzip lassen sich nun auch Flammen physikalisch programmieren. Gehen wir davon aus, dass ein Energie-Partikel von einem Punkt aus (z. B. Kerzendocht) gleißend weiß beginnt und durch die Hitze nach oben (xR=-1) wandert, dabei leicht nach außen gedrückt (yR=+/- 1 bis +/- 5) wird und dabei erlischt, haben wir mit ein paar wenigen Partikeln bereits eine kleine Flamme erzeugt.

Bei großen, lodernden Flammen und Explosionen hingegen wäre die Lösung über Partikel ressourcenraubend. Viele Partikel würden übereinander liegen und unlogische Lücken erzeugen. Außerdem ist eine lodernde Flamme viel wilder und unberechenbarer als eine kleine Kerzenflamme.

Hier genügt es, wenn wir die Partikel in ein zweidimensionales Array setzen und jedes Pixel einzeln setzen. Da wir ausschließlich die Farben Gelb und Rot für die Flammenfarben brauchen, benötigen wir nur zwei Farbarrays, da Blau als dritter Wert immer 0 gesetzt ist.

Doch zuerst bauen wir wieder unseren bekannten Ground-Zero-Rahmen in Java ME, von dem aus wir das Flammenmeer entwickeln werden:

import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;
import java.util.*;
import java.lang.Math.*;

public class Fire extends MIDlet {

  private Display display;
  private MyCanvas canvas;

  public Fire() {
    display = Display.getDisplay(this);
    canvas = new MyCanvas(this);
  }

  protected void startApp() {
    display.setCurrent(canvas);
  }

  protected void pauseApp() {}

  protected void destroyApp(boolean unconditional) {}

  public void exitMIDlet() {
    destroyApp(true);
    notifyDestroyed();
  }
}

class MyCanvas extends Canvas implements CommandListener {

  private Command commandExit;
  private Fire main;
  private Random random = new Random(); // Zufallsgenerator initiieren
  private int p = 0, i = 0; // Hilfsvariablen fuer Zaehler und Schleifen
  private int xMax = getWidth(), yMax = getHeight(); // max. Display

  public MyCanvas(Fire main) {
    this.main = main;
    setFullScreenMode(true);
  }

  protected void paint(Graphics g) {
    long started = System.currentTimeMillis();
    // Hintergrund loeschen
    g.setColor(0, 0, 0);
    g.fillRect(0, 0, xMax, yMax);
    while (System.currentTimeMillis() - started < 100) {}
    repaint();
  }

  public void commandAction(Command c, Displayable d) {}

  protected void keyPressed(int code) {
    switch (getGameAction(code)) {
      default:
        main.exitMIDlet();
    }
  }
}

Nun benötigen wir die Arrays, aus denen wir die Werte lesen können, weil Java ME ja leider kein getPixelColor() kennt:

private int px=4; // Pixelbreite
private int max=xMax/px;
private int[][] colR = new int[99][20]; // Rot-Werte
private int[][] colG = new int[99][20]; // Gruen-Werte

Um die Flammen über die komplette Bildschirmbreite züngeln zu lassen, variieren wir die Pixelbreite, die natürlich nicht zu grob ausfallen darf. Unser Array ist 100 Pixel breit und 20 Pixel hoch, die Größe dürfte von jedem Handy gut und einigermaßen schnell verarbeitet
werden, auch auf den Geräten, die bereits vor zwei Jahren veraltet waren.

Nun initialisieren wir die Startwerte, der Code bedarf eigentlich keiner großen Erklärung. Zuerst wird geschaut, dass wir später nicht umsonst Pixel berechnen, die über den Bildschirm herausragen, dann holen wir uns wieder Bildschirmbreite und –höhe und in den beiden Schleifen werden die Rot- und Grün-Werte auf Null gesetzt! Warum Grün? Weil sich die Farbe Gelb, die wir für den Flammenschein benötigen aus den Farbwerten Rot und Grün mischen lässt. 100% Rot und 100% Grün ergibt ein kräftiges Gelb!

public MyCanvas(Fire main) {
  
  this.main = main;
  setFullScreenMode(true);
  if (xMax > px * 99) {
    max = 98;
  }
  xMax = getWidth();
  yMax = getHeight();
  for (i = 0; i < 20; i++) {
    for (p = 0; p < 99; p++) {
      colR[p][i] = 0;
      colG[p][i] = 0;
    }
  }
}

Bevor wir nun zum eigentlichen Algorithmus gehen, wird es nun wieder etwas theoretisch: Da die Flamme theoretisch am Erzeugungspunkt am heißesten ist, haben wir in der untersten Linie (Arrayzeile 19) die höchsten (Farb-)Werte, die nach oben hin langsam „ausglühen“, also an Farbe verlieren. Letztendlich haben wir nichts anderes als einen Farbverlauf von hell nach dunkel (von unten nach oben) gesehen. Lineare Flammen gibt es aber nicht, wir wollen es ja schön züngelnd haben, also machen wir uns wieder eine physikalische Eigenschaft zu eigen.

Wenn man in ein Wasserbad einen Eiswürfel legt und direkt daneben heißes Wasser schüttet, wird sich das Wasser je nach Nähe der Temperatur angleichen. Im Idealfall haben wir zwischen Eiswürfel (0°C) und Heißwasserquelle (100°C) mittendrin einen Punkt, bei dem die Wassertemperatur nur 50°C hat, also genau die Mitte. Dieses Beispiel verdeutlicht, dass sich die verschiedenen Temperaturen aufeinander beziehen. Vor allem, wenn man bedenkt, dass das Wasserbad zuvor vielleicht eine Grundtemperatur von 25°C hatte.

Ähnlich ist es auch bei den Flammen. Angenommen man hat zwei Funken (Pixel oder Partikel) direkt nebeneinander. Das eine ist 120°C heiß (hat den Farbwert (120,120,0)), das andere 150°C (Farbwert (150,150,0)), dann wird der Funken direkt darüber von diesen beiden Funken beeinflusst. Im Idealfall hätte dieser die Temperatur (120°C + 150°C) / 2 = 135°C (Farbwert (135,135,0)). Da aber auch dieser Funken bereits eine bestimmte Temperatur hat (z. B. 100°C) muss diese mit der beeinflussenden Temperatur verrechnet werden, da sich diese ja beeinflussen. Angenommen, wir würden die unterschiedlichen Temperaturen nicht gewichten, dann würden wir auf eine Gesamttemperatur von (120°C + 150°C + 100°C) / 3 = 123,33°C kommen.

Nun haben wir in einem Pixelraster natürlich keine halben Pixel, wie in der Darstellung oben angegeben ist. Hier lassen wir unsere Temperaturen bzw. Farbwerte wie folgt beeinflussen:

Die drei darunter liegenden Temperaturen werden addiert und die Temperatur des mittleren, oberen Pixels mit gleicher Gewichtung dagegen gesetzt. Da der Eigenwert die drei unteren Pixel ausgleichen muss, wird er mit dem Faktor 3 gewichtet. Wir haben also folgende Rechnung:

(Pixel links darunter) + (Pixel direkt darunter) + (Pixel rechts darunter) + 3 x (Pixel darüber)

Was in diesem Fall 113,33°C ergeben würde:

(110°C + 120°C + 150°C + 3 x 100°C) / 6 = 113,33°C

Da die Flamme allerdings auch an Temperatur verliert, je weiter sie vom Ursprung entfernt ist, teilen wir den Wert nicht mehr durch seine sechs Anteile, sondern einfach durch sieben, um so eine konstante „Auslöschung“ zu erhalten.

(110°C + 120°C + 150°C + 3 x 100°C) / 7 = 97,14°C

Wenn wir nun ständig in der untersten Zeile die selben Werte hätten, dann hätten wir nach wenigen Sekunden einen sehr gleichmäßigen Farbverlauf, der allerdings nicht besonders effektvoll wäre. Da unsere Flamme realiätsnah wirken soll, geben wir der untersten Zeile des Arrays in jeden Durchgang Zufallsfarbwerte bzw. –temperaturen, schließlich brennt kein normales Feuer konstant, wie man an jedem Lagerfeuer gut beobachten kann.

So, nun haben wir lange genug gefackelt, hier kommt der Quellcode:

protected void paint(Graphics g) {
  
  long started = System.currentTimeMillis();
  // Hintergrund loeschen
  g.setColor(0, 0, 0);
  g.fillRect(0, 0, xMax, yMax);
  // Glut (unterste Zeile Zufallsfarbwert setzen)
  for (p = 0; p < max; p++) {
    colR[p][0] = 100 + Math.abs(random.nextInt()) % 155;
    colG[p][0] = 100 + Math.abs(random.nextInt()) % 100;
    if (Math.abs(random.nextInt()) % 4 == 0) {
      colR[p][0] = 0;
      colG[p][0] = 0;
    }
  }
  // Flamme nach oben ausblenden
  // (unterliegende Felder berechnen, gewichten und
  // Durchschnittswert)
  for (i = 1; i < 20; i++)
    for (p = 1; p < max; p++) {
      colR[p][i] = (4 * colR[p - 1][i - 1] + 4 * colR[p][i - 1] + 4 * colR[p + 1][i - 1] + 12 * colR[p][i]) / 25;
      colG[p][i] = (4 * colG[p - 1][i - 1] + 4 * colG[p][i - 1] + 4 * colG[p + 1][i - 1] + 12 * colG[p][i]) / 28;
      g.setColor(colR[p][i], colG[p][i], 0);
      g.fillRect(p * px, yMax - i * px, px, px);
    }
  while (System.currentTimeMillis() - started < 100) {}
  repaint();
}

Im Code ist statt der einfachen Gewichtung jeder Wert noch einmal zusätzlich mit dem Faktor vier gewichtet, um einen besonders schönen und weichen Farbverlauf zu bekommen. Aufmerksamen Beobachtern ist vielleicht schon aufgefallen, dass der Grün-Wert durch den Teiler 28 stärker abnimmt. Durch die schnellere Abnahme des Grün-Werts wird nach oben hin die Farbe Rot dominant, die langsamer abnimmt. So kriegen wir einen glühenden Gelb- Rot-Verlauf hin, wie man ihn von echtem Feuer kennt.

Anwendungsmöglichkeiten

Das war auch schon alles! Doch nicht nur Feuereffekte können mit dem einfache Algorithmus erzeugt werden. Arbeitet man z. B. mit reinen Grauwerten, hat man einen idealen Code, um Rauchschwaden zu erzeugen. Dreht man den Array um (es genügt die umgekehrte Darstellung bei g.fillRect) und arbeitet mit den Farben Weiß/Hellblau und Dunkelblau, erhält man einen perfekten Wasserfall.

Fazit

Mit ein wenig Know-How und wenigen Zeilen Code kann man seinen Java ME Spielen wunderschöne Effekte hinzufügen, die sich in gewissen Grenzen zudem auch noch physikalisch korrekt verhalten. Natürlich ist das noch nicht alles. Wie man bereits ganz oben bei der Physikengine sehen konnte, bieten die behandelten Codes genügend Spielraum für eigene Kreativität und weiteren physikalischen Experimenten, die durchaus auch das Potential haben, noch weiter perfektioniert zu werden.

Dieser Artikel wurde uns von Patrick Völcker zur Verfügung gestellt.