Landschaftsgenerator

In diesem Kapitel möchte ich euch die Technik zur Erstellung einer 2D - Landschaft, wie ich sie in dem Spiel Castles verwendet habe, vorstellen. Auch in diesem Fall gilt wieder, dass ich auf die Main - Klasse des Applets nicht näher eingehen werde, genausowenig werde ich die Klasse Stars besprechen, die im Hintergrund die Sterne zeichnet. Beide Klassen sind jedoch denkbar einfach und sollten eigentlich kein Problem darstellen. Widmen wir uns nun also zunächst der Problemstellung.

Das Problem

Wir wollen eine bergige Landschaft erzeugen um sie in einem Spiel wie Castles zu verwenden. Die Landschaft soll in jedem Spiel anders aussehen, also zufallsgeneriert sein, was die Verwendung von *.gif's o. ä. ausschließt, und muss die Fähigkeit besitzen nachträglich noch verändert werden zu können, z. B. wenn Bomben einschlagen... . Desweiteren darf die Menge an Daten, die gespeichert werden muss um die Landschaft festzulegen, nicht allzu groß sein um das Spiel nicht unnötig langsam zu machen. Zudem müssen wir uns auch überlegen, wie wir die Daten speichern wollen. Es gibt für diese Problemstellung sicherlich viele passende und gute Lösungen, von denen ich nun auf eine genauer eingehen möchte.

Die Idee und Beschreibung des Algorithmus

Um die Datenmenge möglichst gering zu halten möchte ich die Landschaft aus vielen vertikalen Linien, und nicht aus einzelnen Punken, aufbauen. Reiht man für die gesamte Länge der Landschaft senkrechte Linien aneinander, so entsteht, sind alle Linien gleich lang und haben den selben Start- und Endpunkt, ein Rechteck. Ein Punkt der Linie, in unserem Fall der Untere (untere Grenze des Applets) kann für jede Linie einer Zufallslandschaft konstant gewählt werden. Wir müssen also nur den oberen Punkt, der sozusagen die Oberfläche der Landschaft bestimmt, variieren und in einem Array speichern.

Zunächst muss klar sein, dass es keinen Nutzen bringt, jeden Oberflächenpunkt mit Hilfe eines Zufallsgenerators zu bestimmen. Denn die so erzeugte "Landschaft" würde dann alles andere als eine zusammenhängende, strukturierte Oberfläche besitzen. Das Ergebniss eines solchen Versuchs ist in dem Bild neben diesem Absatz zu sehen.

Um eine zusammenhängende, strukturierte Oberfläche zu generieren, müssen wir etwas tiefer in die Trickkiste greifen. Ich möchte es zunächst etwas einfacher machen, als ich es in Castles umgesetzt habe:

1. Wir legen zunächst zufällig einen Startpunkt fest.
2. Nun initialisieren wir den zweiten Punkt bzw. die zweite Linie so, dass sie sich nur um eins plus oder minus von der anderen, ersten Zahl unterscheidet.
3. Wir initialisieren auf diese Art und Weise alle Einträge im Array, indem wir vom letzten Eintrag entweder 1 abziehen oder hinzuaddieren.
4. Die Entscheidung über addieren oder subtrahieren überlassen wir ebenfalls dem Zufall, wobei in 90% der Fälle die eingeschlagene Richtung (also plus oder minus eins) beibehalten wird, während sie in 10% der Fälle wechseln soll.

Wie ihr hier sehen könnt ist das Ergebniss dieses Ansatzes schon ziemlich brauchbar. Es gibt nur ein paar kleine Probleme und "Unschönheiten". Zu einen passiert es immer wieder, dass die "Berge" und "Täler" über die Ober- und Untergrenzen des Applets hinausgehen. Zum Anderen sind die meisten Landschaften noch sehr monoton. In dem nun folgenden Teil möchte ich euch meinen "fertigen" Ansatz zur Generierung der Zufallslandschaft vorstellen. Davor noch kurz ein paar Hinweise. Zum einen habe ich nun einen weiteren Parameter eingeführt, der auch auf die Höhe der Addition bzw. Subtraktion Einfluss hat, wodurch steilere und weniger steilere Berge entstehen. Zum anderen variiere ich die Farbe der Linien und speichere diese Änderungen in einem Colorarray. Zu guter Letzt halte ich noch die Höhe bzw. Tiefe der Linien in einem gewissen Maximal- und Minimalbereich um Berge und Täler nicht zu hoch oder zu tief werden zu lassen.

Der Algorithmus

public void generateLandscape ()
{
/* Initialisierung von plus, diese Variable bestimmt, wieviel hinzugezählt bzw. abgezogen wird */
plus = 1;

// Initialisierung des Faktors (Wert + oder - 1) faktor = 1; // Initialisierung des Startwertes der Oberfläche
start = Math.abs(300 + (rnd.nextInt() % 50));

// Speichern des Startwertes an der ersten Stelle des Arrays
map [0] = start;

// Initialisierung der Startwerte für die Farben
int greenvalue = 200;
int redvalue = Math.abs(rnd.nextInt() % 200);
int bluevalue = Math.abs(rnd.nextInt() % 201);

// Speichern des ersten Startwertes für das Farbenarray
colors [0] = new Color (redvalue, greenvalue, bluevalue);

// Loop zur Initialisierung aller anderen Arrayfelder
for (int i = 1; i < mapsize; i ++)
{
// Speichern der letzten Arrayposition des Höhenarrays
last = map [i - 1];

// Entscheidet, ob die eingeschlagene Richtung gewechselt wird
change = Math.abs(rnd.nextInt() % 10);
// In 10% der Fälle ändert sich die Richtung und möglicherweise plus
if (change > 8)
{
// Ändern der Richtung
faktor = - (faktor);

// Wieviel wird addiert bzw. substrahiert
plus = 1 + Math.abs(rnd.nextInt() % 2);

}

/* Wird ein bestimmter Wert unter- bzw. überschritten, dann wird die Richtung geändert */ if (last > 350 || last < 120)
{
// Ändern der Richtung
faktor = - (faktor);

}

// Hält die Farbwerte immer in einem bestimmten Rahmen
if (greenvalue > 240)
{
// Wenn Farbwert zu groß wird, erniedrigen des Wertes
greenvalue -= 10;

}
else if (greenvalue < 100)
{
// Wenn Farbwert zu klein wird erhöhen des Farbwertes
greenvalue += 10;

}

// Werte für das Feld an i - Stelle werden berechnet
map [i] = last + (faktor * plus);

/** Um die Farbewerte für zunehmende Höhe heller werden zu lassen, wird der Faktor umgekehrt. Dies ist wegen dem umgekehrten Koordinatensystem von Java nötig */
greenvalue = greenvalue + (-faktor * plus);
colors [i] = new Color (redvalue, greenvalue, bluevalue);

}
}

Sind die beiden Arrays erst einmal initialisiert, so kann die Landschaft mit einer einfachen Paint - Methode die Farb- und Höhenarray durchläuft und jeweils eine Linie vom "Boden" des Applets zum Arraywert an der Stelle i in der dazugehörigen Farbe im Farbarray zeichnet, gezeichnet werden. Das Ergebniss dieses Algorithmus könnt ihr neben diesem Text sehen. Womit wir eigentlich schon am Ende dieses Kapitels angekommen sind. Wie ich schon erwähnt habe, könnte man auch jeden einzelnen Punkt der Landschaft speichern, wodurch sich vor allem noch interessantere Farbeffekte erziehlen lassen würden. Die Methode, wie ich sie vorgestellt habe ist allerdings ziemlich flexibel, schnell und sieht auch nicht unbedingt schlecht aus. Solltet ihr eingene Ideen haben, schickt sie mir oder am besten beschreibt sie kurz und schickt mir euer eigenens "Tutorial" Wie immer am Schluss könnt ihr euch das Applet ansehen und auch den Sourcecode runterladen!

Nächstes Kapitel