Generierung der Welt

Autor: Tom Schneider

Grundgedanke

Anders als bei den meisten Spielen, sind die Welten in Plantex nicht von Hand gebaut, sondern werden prozedural generiert. Das bedeutet, dass das Terrain algorithmisch bei Spielstart erschaffen wird, anstatt es, aus einer vorgefertigten Datei, zu laden. Dadurch steigt der Wiederspielwert, da "keine Welt der anderen gleicht". Des Weiteren wird kein Speicherplatz für Ressourcen benötigt. Es fehlen jedoch, durch die algorithmische Erzeugung der Welt, Besonderheiten die sonst detailliert vom Designer eingefügt werden.

Generiert wird die Welt anhand eines Seeds, der beim Erstellen der Welt zufällig bestimmt wird. Dies bedeutet, dass bei Benutzung des selben Seeds, die exakt gleiche Welt erstellt wird. Verwendet wird hierbei ein unsigned Interger der Größe 64, um nahezu unendlich viele verschiedene Welten zu ermöglichen.

Um aus einer einfachen Zahl Terrain zu generieren, bietet sich eine Noise-Funktion an, da diese nicht nur unterschiedliche pseudo-Zufallswerte erzeugt, sondern diese auch interpoliert. In unserem Fall liegen die Werte zwischen Null und Eins. Als Grau-Werte sieht eine solche 2D-Funktion dann wie folgt aus.

Auswahl des Verfahrens

Da unsere Welt nicht nicht nur aus Bergen und Tälern bestehen, sondern auch Höhlen und nach Möglichkeit auch Flüsse und Seen beinhalten soll, gab es für uns zwei verschiedene Ansätze.

Eine Möglichkeit war, eine zwei-dimensionale Noise-Funktion zu verwenden. Diese hätte "nur" Berge und Täler generiert, da lediglich ein Höhen-Wert für jede Säule erstellt wird. Das hätte zur Folge, dass Höhlen und andere Phänomene nachträglich, zum Beispiel durch Perlin Worms, eingefügt werden müssten. Dies würde jedoch bedeuten, Terrain nachträglich zu bearbeiten und so zusätzliche Leistung zu beanspruchen. Dies könnte je nach Länge und Größe des Phänomens bedeuten, mehr Terrain zu generieren und so bei extremer Größe zu starken Leistungseinbrüchen führen. Des Weiteren ist es schwierig, nachträgliche Veränderungen natürlich aussehen zu lassen.

Die andere Möglichkeit war eine drei-dimensionale Funktion zu verwenden, welche Werte für jedes Teilstück einer Säule erstellt, da diese bereits Höhlen und Tunnel erzeugt. Dies hat den Vorteil, dass das Terrain nicht nachbearbeitet werden muss. Jedoch ist es uns so nicht möglich, den Verlauf der Tunnel direkt zu beeinflussen. Das Problem der Flüsse und Seen bleibt jedoch bestehen.

Entschieden haben wir uns für die drei-dimensionale Funktion, da das erzeugte Terrain deutlich interessanter und natürlicher aussieht und mit einem Threshold arbeitet. Dadurch lässt sich diese leicht von anderen Faktoren (siehe Biome beziehungsweise Temperatur) abhängig machen und erlaubt es so, unterschiedliche Landschaften mit der selben Noisemap zu erschaffen. Des Weiteren ist ein gleichbleibender Leistungsverbrauch den extremen Schwankungen der ersten Methode vorzuziehen.

Hügellandschaft mit open_simplex2

Terrain generiert mit open_simplex3

Umsetzung

Die Welt besteht aus einzelnen Hexagon-Säulen. Ein Verbund aus 16x16 Säulen bildet einen Chunk. Die Generierung der Welt findet im sogenannten WorldGenerator statt.

pub struct WorldGenerator {
    seed: u64,
    terrain_table: PermutationTable,
    plant_table: PermutationTable,
    temperature_table: PermutationTable,
    humidity_table: PermutationTable,
}

Dem Generator wird ein Seed übergeben, aus dem dann, mit Hilfe eines Random Generators, die benötigten Noise-Maps erstellt werden. Erstellt wird die Welt mit Hilfe folgender Methode, die einzelene Chunks erzeugt.

fn load_chunk(&self, index: ChunkIndex) -> Option<Chunk>

Diese bekommt lediglich den Index des benötigten Chunks übergeben. Aus dem ChunkIndex, welcher aus x und y Koordinaten besteht, kann nun die erste Säule bestimmt werden. Dies ist nötig, da über jede Säule iteriert werden muss, um diese zu erstellen. Das heißt, dass wir für jede Säule des Chunks folgenden Algorithmus anwenden.

load_chunk

Da wir mit der Noise Funktion open_simplex3 arbeiten, müssen wir die folgenden Schritte für jeden Teilblock der Säulen durchführen. Dies geschieht durch das drei-dimensionale Boolean-Array Fill. In diesem wird das setzen des Materials, als Teilblock, mit true und eine Lücke bzw. Luft mit false angezeigt.

Um zu gewährleisten, dass der Spieler die Welt nicht verlassen kann, wird auf der Höhe null immer ein Block des Materials gesetzt.

for i in 0..WORLDGEN_HEIGHT {
                if i == 0 {
                    fill[rel_pos.q as usize][rel_pos.r as usize][i as usize] = true;
                    continue;
                }

Nun wird mit Hilfe der Methode open_simplex3 der Wert an der Position des Säulen-Teilstücks abgefragt. Da sich dieser bei open_simplex zwischen -1 und 1 befindet wird der Wert um 1 erhöht und halbiert. So liegt er nun zwischen 0 und 1. Da dieser Wert nur als Entscheidungsgrundlage verwendet wird, benötigen wir einen Grenzwert, ab dem ein Teilstück gefüllt wird. Hierzu verwenden wir ein Sigmoid Funktion, da diese einen S förmigen Verlauf hat und sich die Steigung der Funktion gut verändern lässt. Dies ist besonders für den späteren Einfluss der Biome wichtig, da das Terrain je nach Biom unterschiedlich geformt sein soll. Ist der Noise-Wert größer als der Threshold, wird an die derzeitige Position im Array ein true gesetzt, welches setzen des Materials signalisiert.

 let thresh_steepness: f32 =
                    WorldGenerator::steepness_from_temperature(temperature_noise);

                let sig_thresh = 1.0 /
                                 (1.0 + f32::exp(-thresh_steepness * (height_pct - THRESH_MID)));

                let threshold = (sig_thresh + MIN_THRESH) / (1.0 + MIN_THRESH);

                fill[rel_pos.q as usize][rel_pos.r as usize][i as usize] = fill_noise > threshold;

Anhand des Arrays Fill kann nun die Säule erstellt werden. Hierzu wird ein neuer Vektor erstellt. Dieser speichert die einzelnen Teilstücke der Säule. Um die Teilstücke zu erzeugen, iterieren wir einmal über die gesamte Säule. Befindet sich an der Iteratorposition ein true und ist eine Höhe gegeben, wird diese erhöht. Ist eine Höhe gegeben, aber ein false an der Position, ist das obere Ende des Teilstücks erreicht und es wird erstellt und in den Vector gepusht. Da die Höhe in diesem Fall auf None gesetzt wird, passiert solange nichts, bis wieder ein true kommt. In diesem Fall wird die untere Grenze auf die Iteratorposition gesetzt und die Höhe auf 1. Dies wiederholt sich, bis die maximale Höhe erreicht ist.

let column = &fill[rel_pos.q as usize][rel_pos.r as usize];
let mut sections = Vec::new();
let mut low = 0;
let mut height = None;

for i in 0..WORLDGEN_HEIGHT {
                let material = current_biome.material();

                match (height, column[i]) {

                    (Some(h), true) => {
                        // Next one's still solid, increase section height
                        height = Some(h + 1);
                    }
                    (Some(h), false) => {
                        // Create a section of height `h` and start over
                        sections.push(PillarSection::new(material,
                                                         HeightType::from_units(low),
                                                         HeightType::from_units(low + h)));
                        height = None;
                    }
                    (None, true) => {
                        low = i as u16;
                        height = Some(1);
                    }
                    (None, false) => {}
                };
            }

Der Vektor und weitere Eigenschaften(siehe Generierung der Welt II) bilden nun die fertige Hexagon-Säule.