Tag 14: Die mathematisch beschriebene Landschaft

Es gibt natürlich viele Möglichkeiten eine solche Landschaft zu generieren, doch die Zufallskomponente ist in jeder drin. Die Frage ist hier nur, an welchen Stellen man den Zufall einbaut und wie man die Landschaft generiert.

Eine einfache Variante ist das zufällige Überlagern von Sinuswellen. Wer schon einmal mit einem Audiobearbeitungsprogramm gearbeitet hat, kennt das vielleicht. Hier mal ein einfaches Beispiel:

Ich habe MuPad (einem Algebra-Programm) verwendet, allerdings kann man hier auch jedes andere beliebige Programm nutzen. Ein solches Programm hilft einem in diesem Stadium ungemein, um kleine Versuche zu unternehmen und schnell Daten zu visualisieren. Natürlich kann man hier auch GnuPlot plus eine bevorzugte Skriptsprache wählen um das gleiche zu erreichen.

So sieht es bei mir nach etwas herumprobieren aus. Ich habe mich entschlossen, drei Sinus-Kurven zu mischen, deren Verschiebung Höhe und Länge von einem Zufallsfaktor abhängig ist. Wer sich meine Versuche anschauen möchte, kann sich das MuPad-File anschauen, es liegt im snippets-Verzeichnis.

Um mit dem Zufall zu arbeiten, muss man zuerst vernünftige Zufallszahlen erzeugen können. Dafür gibt es die Funktion rand(), die eine zufällige Integer-Zahl erzeugt. Da wir aber Zufallszahlen in einem bestimmten Intervall haben wollen, habe ich diese etwas erweitert (ich weiß, der Platz in der draw.c Datei ist noch etwas unglücklich, aber das kann man ja noch ändern.

float _random(float from, float to) {
  return ((to-from)*((float)rand()/RAND_MAX))+from;
}

Damit auch wirklich bei jedem Start eine neue Zufallszahl generiert wird, müssen wir den Zufallsgenerator zuerst anwerfen und mit einem Startwert initialisieren. Als Startwert nehmen wir einfachheitshalber den aktuellen Zeitstempel.

time_t start; srand(start);

Nachdem die Zufallszahlen stehen, können wir uns an die Implementierung der Landschaft machen:

int* generateTerrain(float peakheight, float flatness) {
  time_t start; srand(start);

  float offset = (float)SCREEN_HEIGHT/2;
  float r1 = _random(1.0, 5.0);
  float r2 = _random(1.0, 5.0);
  float r3 = _random(1.0, 5.0);
  int *yvals = (int*)malloc(SCREEN_WIDTH*sizeof(int));

  for (int x=0; x<SCREEN_WIDTH; x++) {
    float y;
    y  = peakheight/r1*sin((x/flatness*r1)+r1);
    y += peakheight/r2*sin((x/flatness*r2)+r2);
    y += peakheight/r3*sin((x/flatness*r3)+r3);
    y += offset;
    yvals[x] = (int)y;
  }

  return &(yvals[0]);
}

Eigentlich eine recht übersichtliche Funktion, bis auf das * und das &, aber dazu gleich mehr, zuerst die Funktion selbst: Wir generieren drei Zufallszahlen für unsere Sinuswellen und reservieren für die Y-Werte der Landschaft genügend Speicher (Wir brauchen Fensterbreite*(Größe eines Integers) Platz für die Werte). Danach generieren wir für jeden X-Werte den entsprechenden Y-Wert, in dem wir zu y drei Sinuswellen mit unterschiedlichen Zufallswerten addieren. Der Offset ist nur dazu da, damit in unserer Landschaft keine Flüsse entstehen. Am Ende speichern wir den Y-Wert als Integer im zuvor reservierten Speicher.

Nun zum Rückgabewert, der sieht etwas komisch aus. Bei der Funktionsdefinition haben wir ja schon kenntlich gemacht, dass die Funktion einen Pointer zurück gibt, dies machen wir hier auch. Wir nehmen uns das erste Element von yvals und lesen mit dem & die Adresse davon aus, also den Zeiger auf das erste Element des Arrays. Da wir genau wissen, wie groß unser Array ist, können wir dies bedenkenlos machen, wüssten wir die Länge nicht, könnten wir am anderen Ende mit dem Pointer nicht viel anfangen, da wir nicht wüssten, was und wie viel sich dahinter verbirgt.

Nun müssen wir nur noch das Array erzeugen und mit einer simplen for-Schleife anzeigen. Die beiden Werte peakheight und flatness sind zusätzliche Parameter, um die Landschaft zu verändern.

terrain = generateTerrain(150.0, 180.0);
for (int x=0; x<SCREEN_WIDTH; x++) drawLine(x, terrain[x], x, SCREEN_HEIGHT, white);

Fertig sieht es beispielsweise so aus.

Dies war jetzt eine Möglichkeit, eine Landschaft zu erzeugen. Ich habe mich etwas umgesehen und noch weitere spannende Möglichkeiten entdeckt. Eine Davon wird in diesem Tutorial beschrieben. Man nehme sich einen ersten zufälligen Punkt. Der nächste Punkt daneben variiert um 1px nach oben oder nach unten, dabei fällt der Zufallsgenerator 90% in die Richtung des vorherigen und 10% in die andere, so kann man spitze Berge und Täler erzeugen.

Eine weitere sehr interessante Möglichkeit ist es, eine Fraktaltechnik zu verwenden. Auf gameprogrammer.com gibt es einen sehr guten Einstieg dazu. Die Grundidee ist folgende: Man zeichnet zuerst eine horizontale Linie in einer zufälligen Höhe. Dann teilt man diese Linie in der Mitte und verschiebt die beiden so neu entstandenen Punkte zufällig nach oben oder unten, als würde man mit zwei Fingern ein Gummiband nach oben ziehen oder nach unten drücken. Danach fährt man mit den beiden neu entstandenen Linien gleichermaßen fort, bis man den gewünschten Detailgrad erwünscht hat.

Eine weitere sehr interessante Technik ist die Perlin Noise Technik. Hier und hier wird das ziemlich gut erklärt. Es werden hier zufällige Punkte in ein Koordinatensystem gezeichnet und die fehlenden Punkte zwischendrin durch Interpolation dazugerechnet. Hätte man die zufälligen Punkte als Matrix vorliegen, könnte man auch die Methode der kleinsten Quadrate verwenden, um ein Polynom hohen Grades daran anzugleichen. Dies würde aber erheblich mehr Rechenleistung und Programmieraufwand bedeuten.

Soweit steht also unsere Landschaft. Der komplette Sourcecode steht natürlich wieder in Github zur Verfügung. Wer sich an einer weiteren Methode versuchen möchte, kann dies gerne tun, ich würde mich sehr darüber freuen. Übermorgen werden wir uns etwas ums Ambiente kümmern. Momentan sieht die Landschaft noch sehr trist aus.