Die Untersuchung der Grenzen der reinen prozeduralen Generierung mit Fokus auf Questreihen und Rätsel

Inhalt

0. Abbildungsverzeichnis

1. Einführung
1.1 Vorstellung des Themas
1.2 These und Herleitung
1.3 Relevanz für Industrie und Zielgruppe
1.4 Abgrenzung des Begriffs der reinen Prozeduralen Generierung

2. Grundlagen
2.1 Prozedurale Generierung in Spielen
2.1.2 Vorteile der Prozeduralen Generierung
2.1.3 Nachteile der Prozeduralen Generierung
2.2 Das Terrain
2.2.1 Anforderungen an die Welt
2.2.1.1 Berge und Hügel
2.2.1.2 Flüsse und Seen
2.2.1.3 Vegetation
2.2.3 Methoden zur Generierung von Landschaften
2.2.3.1 Zufallszahlen-basierte Methode
2.2.3.2 Midpoint Displacement
2.2.3.3 Diamond-Square
2.2.3.4 Value Noise
2.2.3.5 Perlin Noise
2.2.3.6 Simplex Noise
2.2.3.7 Sketchbasierte Methode
2.2.4 Initialisierung
2.2.4.1 Erstellung der Terrain-Heightmap
2.2.4.2 Erweiterung der Features
2.2.4.3 Softwarebasierte Agenten
2.2.4.4 Küstenlinienagent
2.2.4.5 Glättungsagent
2.2.4.6 Strandagenten
2.2.4.7 Bergagenten
2.2.4.8 Flussagenten
2.3 Städte-Systeme
2.3.1 Wachstumsregeln
2.3.2 L-System und seine Modifikation
2.3.3 Die Legung des Straßennetzes mittels L-System
2.3.4 Grundlagen des Multiagentensystems für den Straßenbau
2.3.5 Extender-Agent
2.3.6 Connector-Agent
2.4 Siedlungsgenerierung
2.4.1 Grundstückslegung
2.4.2 Gebäudegenerierung Agentensystem
2.4.3 Gebäudegenerierung L-System

3. Methodik
3.1 Beschreibung der Herangehensweise
3.2 Begründung der Forschungs- und Datenerhebungsmethod
3.3 Statistische Datenerhebung ± Befragung per Fragebogen und Interview
3.3.1 Die Befragungstypen
3.3.2 Art der Strukturierung des Fragebogens
3.3.3 Die Interviewtypen
3.3.4 Art der Strukturierung des Interviews
3.4 Die Strukturierung des Fragebogens
3.4.1 Das CASI als Distributionsmittel
3.4.2 Die Auswahl der Experten

4. Durchführung
4.1 Erstellung des Fragebogens
4.1.1 Der Hauptteil
4.1.2 Die Verabschiedung
4.2 Gespräche mit Experten Basic
4.2.1 Fragenkatalog
4.3 Durchführung der Interviews
4.3.1 Tobias Heim
4.3.2 Andre Neumann
4.3.3 Gereon Vienken
4.3.4 Prof. Schmidt
4.3.5 Franz Wittkamp

5. Ergebnis
5.1 Darstellung der Ergebnisse des Fragebogens
5.1.1 Stärken und Schwächen der prozeduralen Generierung
5.1.2 Die Bestimmung des Tätigkeitsbereiches
5.1.3 In welchen Fällen wurde die prozedurale Generierung von den Probanden angewendet?
5.1.4 Die Grenzbereiche der prozeduralen Generierung und wie es dazu kam?
5.1.5 Haben Sie schon einmal mit Questreihen oder Rätseln gearbeitet und wenn ja, nach welchem Schema haben Sie diese aufgebaut?
5.2 Fragebogen Ergebnisinterpretation
5.3 Interview Ergebnisinterpretation
5.4 Schlussfolgerung

6. Zusammenfassung
6.1 Fazit
6.2 Kritische Stellungnahme
6.3 Ausblick

7. Quellen
7.1. Literaturverzeichnis
7.2 Bildverzeichnis

8 Anhang

Interview

Mein Survio Bogen Mein Survio Bogen

0. Abbildungsverzeichnis

Auswertung Frage 1 Mein Survio Seite Antwort Bogen 1

Auswertung Frage 2 Mein Survio Seite Antwort Bogen 2

Auswerung Frage 3 Mein Survio Seite Antwort Bogen 3

Auswertung Frage 4 Mein Survio Seite Antwort Bogen 4

Auswertung Frage 5 Mein Survio Seite Antwort Bogen 5

1. Einführung

1.1 Vorstellung des Themas

Das Thema, welches ich in meiner Bachelor-Arbeit bearbeiten möchte, ist die Untersuchung der Grenzen der reinen prozeduralen Generierung mit Fokus auf Questreihen und Rätsel.

Ich möchte herausfinden, ob und wenn ja, welche Grenzen die prozedurale Generierung in ihrem Schaffungsprozess erfährt und ob es Lösungen oder Workarrounds für diese gibt.

1.2 These und Herleitung

Meine These lautet: ÄAlleine mit den Möglichkeiten, welche uns die reine prozedurale Generierung bietet, ist es nicht möglich, Rätsel und Questreihen in einer sinnvollen Reihenfolge zu erstellen. Vielmehr werden Workarrounds genutzt, um diese zu erstellen." Das Ziel dieser Arbeit ist es, die Grenzbereiche der prozeduralen Generierung näher zu beleuchten. Hierbei wird ein besonderes Augenmerk darauf gelegt, wie diese Grenzbereiche zustande kommen und warum diese immer noch bestehen. Hierbei werden dann alternative Varianten, welche genutzt werden, um diese Grenzgebiete auszufüllen, aufgezeigt und in ihrer Funktion beschrieben. Dies sorgt für einen allgemeinen Überblick über die Möglichkeiten der prozeduralen Generierung und wird im weiteren Verlauf der Arbeit tiefere Einblicke und eventuelle Lösungen für diese Grenzgebiete aufzeigen.

1.3 Relevanz für Industrie und Zielgruppe

Dieses Thema hat äußerste Relevanz in der Industrie, da die Ansprüche der Konsumenten stetig steigen, allerdings die Zeit, welche man für das Erstellen von Spielen hat, stetig reduziert wird. Demzufolge wird die prozedurale Generierung in Zukunft besonders für Indie-Entwickler bei dem Erstellen ihrer Produkte weiter an Relevanz gewinnen. Hierbei wäre es möglich, dass das Ergebnis meiner Arbeit ein neues Licht auf die prozedurale Generierung wirft und eben diesen Indie- Entwicklern dazu verhilft, ihre Produktpalette um ein weiteres Genre zu erweitern. Hierbei hat meine Arbeit aber nicht nur die eben genannten Indie- Entwickler als Zielgruppe, vielmehr hoffe ich, auch Neueinsteiger, welche gerade beginnen, sich mit dem Feld der prozeduralen Generierung zu beschäftigen, als Zielgruppe gewinnen zu können.

1.4 Abgrenzung des Begriffs der reinen Prozeduralen Generierung

Der Begriff der reinen Prozeduralen Generierung bezieht sich auf den Prozess der erstellung von Objekten, welcher ohne den Zusatz von Hilfsprogrammen, wie z.B. einem Mustererkennungs Algorithmus oder Sprachsynthese funktioniert.

2. Grundlagen

2.1 Übersicht

In dem Grundlagenkapitel werden die Möglichkeiten der prozeduralen Generierung anhand der meistgenutzten Anwendungsarten beschrieben. Hierbei wurden die Erstellung des Terrains und die Erstellung eines Städtesystems gewählt, da diese die beiden größten Anwendungsgebiete darstellen.

2.1.1 Prozedurale Generierung in Spielen

Prozedurale Generierung, beschreibt die Möglichkeit, Objekte mithilfe von Algorithmen zu generieren. Hierbei ist der Zufall von entscheidenden Relevanz. Um den Faktor Zufall in Bahnen zu lenken, die dem Spiel zuträglich sind, erstellt der Programmierer Regeln. Diese Regeln steuern nicht nur die Ausmaße des Zugriffs für den Algorithmus, sondern schreiben ihm auch genau vor, wo er anzusetzen hat und wo seine Arbeit nicht notwendig ist (vgl. Zurschmitten 2013).

2.1.2 Vorteile der prozeduralen Generierung

Das Potenzial der prozeduralen Generierung macht es dem Programmierer möglich, bei der richtigen Auslegung des Algorithmus, alles von dem Aussehen eines Volkes bis hin zur individuellen Generierung und Einstellung des Volkes gegenüber anderen Völkern prozedural generieren zu lassen und dies in einer geringen Zeitspanne (vgl. Klaß 2012). Dieser Aspekt macht diese Art Spiele herzustellen, besonders günstig. Besonders für Indie-Entwickler bietet die Möglichkeit der prozeduralen Weltgenerierung die Möglichkeit zu wachsen, da sie durch das Einsparen, von z. B. Gehaltskosten, mehr Geld in ihr Endprodukt investieren können. Hierbei ist es auch nicht unwichtig zu erwähnen, dass die Methode der prozeduralen Generierung besonders ressourcenbewusst mit der Leistung des Computers umgeht (vgl. Bojaryn 2014). Dies wiederum kommt Entwicklern jeder Sparte der Spielbranche zugute, da sie sich weniger Sorgen um die Auslastung beim Generierungsprozess machen müssen und so die ansonsten für den Prozess der Weltengenerierung aufgewendete Leistung auf andere Bereiche des Spiels umwälzen können. Des Weiteren bietet die prozedurale Generierung den Spielern, welche sich wirklich mit dem Spiel auseinandersetzen, ein hohes Maß an Forschungsmöglichkeiten. Denn die in Spielen per Zufall generierte KI bietet den Spielern die Möglichkeit, herauszufinden, wie sie tickt und warum sie Dinge so tut wie sie es tut. Dies kann der Spieler wiederum nutzen, um seine Vorteile aus den gewonnenen Erkenntnissen zu ziehen (vgl. Rudolph 2014).

2.1.3 Nachteile der prozeduralen Generierung

Trotz der mannigfaltigen Vorteile, die die prozedurale Generierung bietet, gibt es auch einige Nachteile. Ein wichtiger Nachteil der prozeduralen Generierung ist, dass sie nicht universell auf jedes Spielgenre anwendbar ist. Dies wird dadurch bedingt, dass die prozedurale Generierung unfähig ist, Dinge wie Storylines oder Rätsel sinnvoll anzuordnen. Rätsel bieten hierbei eine besondere Herausforderung, da sie zumeist aus kleinen, logischen Schritten bestehen, die nacheinander in der richtigen Reihenfolge ausgeführt werden müssen. Ein weiterer Grund, warum es Spielen, die die prozedurale Generierung als einziges Werkzeug zur Erstellung von Storylines nutzen, schwer fällt diese Interessant zu gestalten ist, dass der Hersteller die Möglichkeit verliert, den Spannungsbogen im Spiel anzupassen oder sogar komplett einzubauen (vgl. Steinlechner 2015). Hinzu kommt, dass der Benutzer der prozeduralen Generierung durch das Unvermögen, seine Welt mit Details auszustatten, eine Welt erschafft, die einfach Änur" groß ist, aber ansonsten nichts zu bieten hat. Des Weiteren kommt es auf der Konsumentenseite bei Spielen, die mit prozeduraler Generierung erstellt wurden, zu keinem Emotional Attachment zu der Welt oder dem Charakter, da der Benutzer nicht die Möglichkeit bekommt, beim Entstehen, z. B. des Charakters, Einfluss zu nehmen. Aber nicht nur in der Zuordnung der Genres könnte es bei einem Spiel, das rein mit prozeduraler Generierung erstellt wurde, zu Problemen kommen. Denn auch auf der technischen Seite weist die prozedurale Generierung einige Stolperfallen auf. Eine dieser Fallen liegt in dem Zeitaufwand, der erbracht werden muss, um einen funktionierenden Algorithmus zu erstellen. Hierbei sind die Gesetze oder Regeln, die der Programmierer erstellen muss, von größter Wichtigkeit und nehmen in der Durchführung oder besser gesagt in der Übertragung in den Algorithmus am meisten Zeit in Anspruch. Ein weiteres Problem liegt in der Findung von auftretenden Fehlern, welche im letztendlichen Spiel verheerende Folgen hervorrufen können. Dies wird durch die komplexe Struktur des Algorithmus ausgelöst. Ein weiteres Problem liegt in der Fehleranfälligkeit, die der Algorithmus aufweist. Bei der kleinsten Veränderung des Codes kann es dazu kommen, dass eine ganz andere Welt entsteht, was wiederum das Testen auf Fehler und die QA (Qualitätssicherung) erschwert und länger andauern lässt als bei den per Hand erstellten Welten (vgl. Schier 2015).

2.2 Das Terrain

2.2.1 Anforderungen an die Welt

Die Anforderungen, welche an ein Terrain gestellt werden, sind im Großen und Ganzen immer die gleichen. Das Terrain soll ein realitätsnahes Bild, welches für den jeweiligen Zweck variieren kann, darstellen. Das heißt, dass das Terrain Steigungen und Senkungen haben sollte. Des Weiteren wären Vegetation und Flüsse dem Zweck nicht abträglich und verschiedene Bereiche wie z. B. Küsten oder Wälder sind dem Ziel dienlich. Beim Erstellen solch eines Terrain unterteilt man den Erstellungsprozess in 4 grobe Schritte. All diese Schritte können entweder nacheinander oder simultan ausgeführt werden. Der erste Schritt besteht darin, Bereiche wie z. B. Küstenlinien zu definieren, um das Terrain in grobe Bereiche aufzuteilen. Der zweite Schritt besteht darin, Berge und Hügel zu generieren, um von dem flachen Terrain abzuweichen und ein realitätsnahes Bild zu erstellen. Der dritte Schritt besteht im Generieren von Flüssen und Seen. Der vierte und letzte Schritt besteht darin, der Welt mit Pflanzen oder Tieren Leben einzuhauchen (vgl. Eibensteiner 2015, S. 7).

2.2.1.1 Berge und Hügel

Die Generierung von Hügeln und Bergen stellt einen zentralen Schritt auf dem Weg zu einem realistisch wirkenden Terrain dar. Die Erschaffung von Bergen oder Hügeln wird durch eine Werteänderung in der der Heightmap-eigenen Matrix realisiert. Da es allerdings nicht wirklich realistisch aussähe, wenn es nur Berge gäbe, die ohne jegliche Vertiefung existierten, ist es ratsam, rund um den Berg durch eine Senkung der Höhenwerte ein realitätsnahes Bild zu erschaffen. Durch die Möglichkeit, die ÄAbfallrate" anzupassen, ist es möglich, die unterschiedlichsten Gebilde als Berge zu generieren (vgl. Eibensteiner 2015, S. 7).

2.2.1.2 Flüsse und Seen

Neben der Erschaffung von Bergen und Hügeln stellt die Generierung von Flüssen oder Seen einen weiteren wichtigen Schritt der Terrainerstellung da. Dieser Schritt kann bei dem Ziel, realistisch wirkende Flüsse oder Seen zu erschaffen, mit die meiste Zeit in Anspruch nehmen, da das realistische Designen von Flüssen oder Seen ein sehr komplexer Vorgang ist (vgl. Eibensteiner 2015 S. 8).

2.2.1.3 Vegetation

Die Erstellung von Vegetation hilft zusätzlich dabei, das Terrain lebendig aussehen zu lassen. Allerdings gibt es auch hier ein Hindernis. Aufgrund des Problems, dass Objekte des Typs Vegetation nicht direkt in der Heightmap gespeichert werden können, sondern in einem externen Schritt auf das Terrain gestellt werden müssen, geht bei diesem Schritt zumeist viel Zeit verloren. Dabei ist es unerheblich, ob das jeweilige Objekt im Vorfeld designt oder generiert wurde (vgl. Eibensteiner 2015, S. 8).

2.2.3 Methoden zur Generierung von Landschaften

Es gibt viele Möglichkeiten, Terrain zu generieren, in dieser Arbeit allerdings werden die 3 beliebtesten vorgestellt und erläutert, wie diese funktionieren. Diese drei Ausrichtungen sind die zufallszahlenbasierte Methode, die sketchbasierte Methode und die softwarebasierenden Agenten (vgl. Eibensteiner 2015, S. 11)

2.2.3.1 Zufallszahlenbasierte Methode

Die zufallszahlenbasierte Methode unterteilt sich in viele verschiedene Ausrichtungen. Die Ausrichtungen, welche hier erläutert werden, sind die gebräuchlichsten. Die Ausrichtungen, die im Folgenden dargelegt werden, sind das Midpoint Desplacement, Diamond Square, Value Noise und das Simplex Noise (vgl. Eibensteiner 2015, S. 11)

2.2.3.2 Midpoint Displacement

Der Midpoint-Displace-Algorithmus ist ein einfach einzusetzender Algorithmus, der die Grundlage des Diamond-Square-Verfahrens darstellt. Auf dem Weg zur Generierung sind die Abläufe, welche der Algorithmus tätigt, in 5 grobe Schritte einzuteilen. Zuerst werden zwei Ausgangspunkte ausgewählt. Das Kriterium, welches diese beiden Punkte erfüllen muss, ist, dass sie die Möglichkeit haben, eine gerade Linie zu bilden. Als zweites wird der Mittelpunkt dieser Linie errechnet. Wenn dies geschehen ist, wird diesem Mittelpunkt der Durchschnittswert der Werte der zwei Punkte zugewiesen. Dieser wird dann mit einem zufälligen Fehlerwert addiert. Dieser Wert des Fehlers darf nicht den Wert der maximalen Länge der Linie überschreiten. Wenn dies nicht eingehalten wird, kommt es zu einem unklaren Ergebnis. In dem dritten Schritt wird der vierte Punkt aus dem Durchschnittswert der Höhenwerte und der vier umliegenden Eckpunkte errechnet. Des Weiteren wird in dem vierten Schritt der seitliche Mittelpunkt aus den Werten der Eckpunkte, zwischen denen er liegt, errechnet. In dem fünften und letzten Schritt wird der Vorgang für den ersten und zweiten Punkt sowie für den dritten und vierten Punkt solange ausgeführt, bis es zu einem zufriedenstellenden Ergebnis kommt. Das Ergebnis besteht in einem Feld, in dem jedem ÄFeld" ein Wert zugeordnet wurde (vgl. Eibensteiner 2015, S. 11-12).

2.2.3.3 Diamond-Square

Der Diamond-Square-Algorithmus ist eine Erweiterung des Displacement- Algorithmus. Der Diamond-Square-Algorithmus bietet neben den Eigenschaften, die der Displacement-Algorithmus hat, nebenbei auch Schutz gegen das Bilden von Artefakten. Der größte Unterschied zwischen dem Diamond-Square- und dem Displacement-Algorithmus besteht in der Berechnung der seitlichen Mittelpunkte. Denn zur Berechnung des Mittelpunktes werden im Gegensatz zum Displacement-Algorithmus vier umliegende Punkte anstatt zweier Punkte genutzt. Des Weiteren verfügt der Diamond-Square-Algorithmus über die Fähigkeit, den zu berechnenden Punkt an den Rand des Quadrates zu stellten, wo dementsprechend nur 3 Punkte zur Berechnung vorhanden sind. Um das ÄProblem", welches aus dem Fehlen eines vierten Punktes für die Berechnung entsteht, zu beheben, stellt der Diamond-Square-Algorithmus vier mögliche Lösungsansätze zur Verfügung. Es gibt die Möglichkeit, die Berechnung ohne einen vierten Punkt auszuführen, was durch die Berechnungsweise ermöglicht wird, die dem Diamond-Square-Algorithmus zu eigen ist. Des Weiteren gibt es die Möglichkeit, dem vierten Punkt einen zufälligen Wert zuzuteilen, welcher in etwa dieselbe Menge besitzt wie die anderen drei Durchschnittswerte. Die dritte Möglichkeit besteht darin, dem vierten Punkt einen Standardwert zuzuweisen, der dieselbe Menge wie die der beiden Eckpunkte aufweist. Des Weiteren ist es möglich, den am nächsten gegenüberliegenden Punkt des Quadrates für die Berechnung zu verwenden (vgl. Eibensteiner 2015, S. 12-13)

2.2.3.4 Value Noise

Der Value-Noise-Algorithmus bedient sich, um zu funktionieren, der Zufallszahlen. Er erzeugt initial keine Ergebnisse fraktaler Natur. Des Weiteren ist der Faktor der Selbstähnlichkeit frei variierbar. Zur ÄVerähnlichung³ des Ergebnisses nutzt der Value-Noise-Algorithmus,die Fractional-Brownian-Motion- Funktion. In dieser Funktion werden verschiedene Oktaven von Rauschen zusammengefasst. Das Rauschen muss, um zusammengefasst zu werden, stetig steigende Werte im Bereich der Frequenz und fallende Werte im Bereich der Amplitude aufweisen. Bei der eigentlichen Umsetzung wird zuerst ein Grit g mit zufälligen Werten erstellt. Direkt folgend werden die konkreten Höhenwerte berechnet. Dies resultiert aus dem Überordnen einer Koordinate über das Grit g und dem Herausfinden der 4 umliegenden Grit-Punkte. Letztendlich wird der konkrete Höhenpunkt durch die Interpolation der Werte der vier umliegenden Grit-Punkte ermittelt. Allerdings ist es von entscheidender Wichtigkeit, welche Interpolationsfunktion zum Erreichen des Ergebnisses genutzt wird, da das Ergebnis von Funktion zu Funktion variieren kann. Die drei gängigsten Interpolationsfunktionen, sind die lineare, die Kosinus- und die kubische Interpolation. Diese drei Funktionen unterscheiden sich allerdings in puncto Geschwindigkeit und Genauigkeit. Die lineare Interpolation ist z. B. schneller, erzeugt jedoch auch die ungenauesten Ergebnisse der drei Varianten. Die Kosinus-Variante erzeugt im Gegensatz zur linearen Variante ein runderes Ergebnis, tut dies allerdings auf Kosten der Effizienz in puncto Zeit. Als dritte Möglichkeit erzeugt die kubische Interpolation das beste Ergebnis, ist dafür aber auch die langsamste der drei zur Verfügung stehenden Möglichkeiten. Jedoch bietet das Value Noise noch einen großen Vorteil, und zwar den Vorteil der Anpassungsfähigkeit. Der Nutzer kann bei der Verwendung des Value Noises Parameter wie die Anzahl der verwendeten Oktaven, die Frequenz und die Höhe einstellen. Diese Werte können dementsprechend auch von den Amplituden genutzt werden (vgl. Eibensteiner 2015, S. 14).

2.2.3.5 Perlin Noise

Der Perlin-Noise-Algorithmus ist der Noise-Algorithmus, der aufgrund seiner Geschwindigkeit, in der er Terrains generiert, am häufigsten gebraucht wird. Zusätzlich generiert der Perlin-Noise-Algorithmus gute Ergebnisse, ist dafür allerdings im Vergleich zu anderen Algorithmen seiner Klasse nicht einfach zu verstehen oder zu bedienen. Bei der Nutzung des Perlin Noise beginnt alles, ebenso wie bei dem Value-Noise-Algorithmus, mit einem Grit. Allerdings unterscheidet sich dieses Grit zu dem Grit des Value Noises. Das Grit des Perlin- Noise-Algorithmus unterscheidet sich in puncto Steigungsvektoren von dem Grit des Value Noises. Die Steigungsvektoren, die in das Grit des Perlin Noises eingefügt werden, zeigen alle in eine andere Richtung, ganz im Gegensatz zu den Vektorenwerten des Value-Noise Grits. Dementsprechend ist jedem Punkt des Grits ein Vektor zugeordnet. Um mit dem Perlin-Noise-Algorithmus nun eine Heightmap zu erzeugen, müssen folgende Schritte ausgeführt werden. Als Basis dient hierbei wie auch bei anderen Noise-Algorithmen ein 2D-Steigungsvektor- Grit g. Im ersten Schritt werden hier Steigungsvektoren v1 bis v4 aus dem Grit g ausgewählt. Die Auswahl der Steigungsvektoren ist hierbei von dem Zielpunkt p abhängig. Dies resultiert aus der Tatsache, dass die Steigungsvektoren rund um den Zielpunkt angeordnet sein müssen. Nachdem die Steigungsvektoren gesetzt wurden, wird zwischen ihnen und einem Distanzvektor das Skalarprodukt errechnet. Der Distanzvektor ergibt sich aufgrund des ausgewählten Punktes p und des nächstgelegenen Grit-Punktes pg. Der nächste Schritt beinhaltet die Berechnung des Skalarproduktes s1 bis s4 durch lineare Interpolation (vgl. Eibensteiner 2015, S. 15-16).

2.2.3.6 Simplex Noise

Der Simplex-Noise-Algorithmus stellt eine Erweiterung des Perlin-Noise- Algorithmus dar. Er enthält deutliche Leistungssteigerungen in den Kategorien Geschwindigkeit und Ergebnisgenauigkeit in Berechnungen von Grits, welche sich in der vierten oder fünften Dimension befinden. Dies hängt mit der Art der Berechnung zusammen. Der Simplex-Noise-Algorithmus arbeitet mit einem polynominalen System, wohingegen der Perlin-Noise-Algorithmus mit einem Exponentialsystem arbeitet, welches in höheren Dimensionen des Grits nicht mehr effizient funktioniert. Des Weiteren benötigt der Simplex-Noise- Algorithmus keine Interpolation für die Errechnung seiner Ergebnisse. Dies macht ihn zusätzlich schneller als den Perlin-Noise-Algorithmus (vgl. Eibensteiner 2015, S. 16-17).

2.2.3.7 Sketchbasierte Methode

Die sketchbasierte Methode der Terrainerstellung wurde von Huafei und Changwen Zheng zum ersten Mal angewendet. Dieser Ansatz der Terrainerstellung basiert auf der Idee, dass Landschaften aufgrund eines grob gezeichneten Sketches generiert werden können. Der Algorithmus der zu der sketchbasierten Generierung von Terrains verwendet wird, unterteilt sich in drei große Sparten. Diese Sparten sind die Initialisierung, das Erstellen der Terrain- Heightmap und die Erweiterung der Features (vgl. Eibensteiner 2015, S. 18).

2.2.4 Initialisierung

Bei der Initialisierung wird ein bereits vorhandener Sketch eingescannt. Dieser Sketch enthält bereits Features, die farbig markiert wurden. Aus den eingescannten Informationen wird eine Matrix von dem Programm erstellt, welche dazu dient, die bereits farbig markierten Features zu kategorisieren. Um Auskunft darüber zu erhalten, wo sich welches Feature aktuell auf der Karte befindet, verwendet das Programm einen berechnenden Algorithmus, der sich immer an einem Ausgangspunkt auf der Karte orientiert (vgl. Eibensteiner 2015, S. 18).

2.2.4.1 Erstellung der Terrain-Heightmap

Bei der Erstellung der Heightmap wird aufgrund der Matrix, welche im ersten Schritt erstellt wurde, jedem Feld aufgrund seines Inhaltes eine entsprechende Höhe zugeordnet. Hierbei ist es von entscheidender Wichtigkeit für die Höhe des Feldes, ob sich z. B. ein Feature auf diesem Feld befindet, da dies das Ergebnis drastisch beeinflusst. So werden für Berge oder Schluchten feste Plus- oder Minuswerte vergeben und bei dem Lesen der Matrix an die Heightmap weitergegeben (vgl. Eibensteiner 2015, S. 18-19).

2.2.4.2 Erweiterung der Features

Manche Features müssen, um glaubhafte realistische Kopien darzustellen, erweitert werden. Schluchten oder Gebirgskämme sind in ihrer Gestaltung und Form so komplex, dass sie besonderes Augenmerk benötigen, um realistisch zu wirken. Um die Gestaltung dieser realistischen Gebirgskette zu ermöglichen, wird die normale Erstellung um einige Schritte erweitert. Die Berechnung der Aspekte wird z. B. besonders ausgedehnt, da das realistische Darstellen der Gebirgskette ohne die Berechnung der Steigung oder des Gefälles der einzelnen Teilstücke nur schwerlich auskommt. Des Weiteren wird die Suche nach geeigneten Heightmap- Punkten ausgeweitet. Hierbei werden naheliegende Orientierungspunkte zusammengelegt, um in der Gesamtheit ein klareres Bild erschaffen zu können. Der letzte Punkt, der erweitert wird, ist die Berechnung der Höhenwerte. Hierbei wird ein Midpoint-Displacement-Algorithmus verwendet, um die Höhenpunkte zu errechnen (vgl. Eibensteiner 2015, S. 19).

2.2.4.3 Softwarebasierte Agenten

Das Grundprinzip, das hinter den softwarebasierten Agenten steckt, ist, dass das Terrain von eigenständigen Objekten, welche Agenten genannt werden, erstellt wird. Hierbei ist es wichtig zu wissen, dass Agenten eigenständige Objekte darstellen, die mit ihrer Umwelt interagieren und diese durch Sensoren wahrnehmen. Des Weiteren ist es für diese Agenten möglich, ihre Umwelt im Rahmen von definierbaren oder vordefinierten Regeln zu verändern. Für die Terrainerstellung unterteilen sich die Agentensysteme in drei übergeordnete Gruppen. Jede dieser Gruppen hat ihr eigenes Wirkungsfeld und ist manuell einstellbar, um den Wünschen des Entwicklers Ausdruck zu verleihen. Diese drei Hauptgebiete der Agentensysteme sind der Küstenlinienagent, der Landschaftsagent und der Erosionsagent. Diese drei Agenten repräsentieren gleichzeitig jeweils eine Phase in der Entstehung eines Terrains. In der ersten Phase werden Küsten erzeugt, welche Flüsse, Seen und Ozeane von den Landmassen trennen. Dies ist die Küstenlinienphase. In der Landschaftsphase, welche die zweite Phase darstellt, werden Berge, Strände und andere grobe Strukturen der Landschaft geformt. Die letzte Phase ist die Erosionsphase. Diese Phase wird zuletzt ausgeführt, da sie mit den Ergebnissen der vorhergegangenen Phasen arbeitet. Sie erodiert Flüsse und Berge, um ein realitätsnahes ÄGrundgerüst" zu erstellen. In den einzelnen Phasen arbeiten gleichzeitig immer mehrere Agenten, welche Zugriff auf das gesamte Terrain haben. Allerdings wird ihr Zugriff durch sogenannte Tokens begrenzt. Jeder Agent bekommt bei seiner ÄEntstehung³ eine feste Anzahl an Tokens. Diese Tokens darf er dann investieren, um unter Berücksichtigung der Regeln Bereiche des Terrains zu editieren. Diese Tokens stellen gleichzeitig seine Lebensdauer dar. Denn wenn ein Agent keine Tokens mehr besitzt, wird er von dem weiteren Entstehungsprozess des Terrains ausgeschlossen und gelöscht. Nachdem die Agenten ihre Arbeit verrichtet haben, generieren sie Heigtmaps. Letzten Endes ist noch zu ergänzen, dass sich die drei übergeordneten Klassen der Agenten in insgesamt fünf Unterklassen aufteilen. Hierzu zählt der Küstenlinien-, der Glättungs-, der Strand-, der Berg- und der Flussagent (vgl. Eibensteiner 2015, S. 26-27).

2.2.4.4 Küstenlinienagent

Der Küstenlinienagent generiert, wie der Name schon vermuten lässt, Küstenlinien. Er beginnt auf einem Feld, welches vollständig unter Wasser steht. Dieses Feld markiert er dann als zu bearbeitendes Feld. Nachdem der Markierungsprozess abgeschlossen ist, teilt sich der Agent in zwei weitere Agenten auf und gibt ihnen jeweils die Hälfte seines zuvor markierten Gebietes zur Bearbeitung. Dieser Prozess wird so lange durchgeführt, bis der Satz der zu bearbeitenden Küstenmasse erreicht ist. Der zu erreichende Satz kann in den Einstellungen der Agenten manuell angepasst werden. Auf diese Weise werden die Küstenlinien des gesamten Terrains erstellt. Dieses Verfahren hat den Vorteil, dass die Küstenlinien abwechslungsreich und interessant gestaltet werden anstatt alle gleich auszusehen. Trotz der vermeintlichen ÄKreativität", welche diese Küstenlinien vermuten lassen, folgt die eigentliche Generierung strikten Regeln und einem festgelegten Ablauf. Jeder der Agenten beginnt in dem ihm zugeordneten Feld am Rand mit einer festgelegten ÄBlickrichtung". Als erstes sucht der Agent nach bereits existierenden Küstenlinien; falls er keine Küstenlinien finden sollte, fährt er mit dem nächsten Schritt fort. Anschließend sucht sich der Agent zwei zufällige Punkte in dem ihm zur Verfügung stehenden Bereich aus und speichert sie ab. Diese Punkte nennt man Attractor und Repulsor. Diese beiden Punkte werden nach dem Kriterium ausgewählt, dass sie, ausgehend von der Startposition und Richtung, in die der Agent zu Beginn seines Prozesses blickt, in die entgegengesetzte Richtung zueinander stehen müssen. Diese beiden Punkte dienen dem Agenten bei seinem Generierungsprozess als Anhaltspunkte, um die Wertigkeit der Felder, die sich um ihn herum befinden, festzustellen. Der Attractor und Repulsor werden zusätzlich verwendet, wenn der Agent ein neues Feld betritt, da er auch hier einen Wertevergleich durchführen muss, wofür er die Werte des Attractors und Repulsors benötigt. Anhand der errechneten Wertigkeit jedes Feldes, welches von dem Agenten betreten wird, wird festgelegt, ob das Feld mit einer Landmasse belegt wird oder in seinem jetzigen Zustand verbleibt. Dieser Prozess wird von dem jeweiligen Agenten so lange wiederholt, bis er alle seine Tokens aufgebraucht hat und so sein Editierungsrecht verliert und gelöscht wird (vgl. Eibensteiner 2015, S. 27-28).

2.2.4.5 Glättungsagent

Der Glättungsagent ist ein Agentensystem, welches in einem lokalen Bereich arbeitet. Der Glättungsagent arbeitet hierbei mit einem Extended-van-Neumann- Algorithmus, um sich zu bewegen und seine Arbeit verrichten zu können. Er verbraucht, wie auch alle anderen Agenten, für jede Glättung einer groben Unebenheit einen Token. Diese Tokens begrenzen wie auch bei allen anderen Agenten sowohl ihre Editierungen als auch ihre Lebensdauer. Bei dem Glättungsagenten lässt sich genau wie bei dem Küstenlinienagenten einstellen, wie oft er zu seinem Ausgangspunkt zurückkehren soll und wie weit der Glättungsgrad, welchen er erzeugen soll, ist. (vgl. Eibensteiner 2015, S. 28-29).

2.2.4.6 Strandagenten

Der Strandagent beginnt seine Arbeit auf einem Gebiet, welches sich nah an einem Küstengebiet befindet. In diesem Gebiet führt er genau wie der

Glättungsagent Glättungsoperationen in einem zuvor definierten

Parameterbereich aus. Der Strandagent nutzt zur Orientierung einen Breath-First- Search-Algorithmus. Sollte der Strandagent bei seiner Arbeit auf einen Höhenwert stoßen, welcher sich über einer einstellbaren Höchstgrenze befindet, springt er zurück auf seinen Anfangspunkt. Der Strandagent bietet dem Nutzer ein hohes Maß an Designfreiheit, da von der Höhe der zu bearbeitenden Hügel bis zur maximalen Ausdehnung des Strandgebietes alles konfigurierbar ist (vgl. Eibensteiner 2015, S. 22-30).

2.2.4.7 Bergagenten

Der Bergagent generiert auf dem Terrain Berge in jeglichen Formen und Größen. Er ist sogar in der Lage, ganze Bergzüge oder Bergketten zu generieren. Den Generierungsvorgang startet der Agent an einem zufälligen Punkt des Terrains. Nachdem der Agent generiert wurde, sucht er zufällig eine Richtung aus, in die er wandert. Während seiner Bewegung sucht der Agent ständig nach Feldern, die den vordefinierten Anforderungen entsprechen, um sie zu editieren. Die Grundform, auf der der potenzielle Berg oder die potenzielle Bergkette erstellt wird, hat die Form eines V. Diese Grundform beschränkt die maximale

Ausbreitung, die der Berg oder die Bergkette haben kann. Auf der Basis dieser V- Form wird dann berechnet, wie weit der ÄGrundstamm" des Berges oder der Bergkette reichen darf, damit die Steigungen oder Senkungen, die in die Ausdehnung des Berges miteinberechnet werden müssen, nicht diese V-Form verlassen. Verschiedene Abhänge oder Steigungen werden unter Zuhilfenahme der zur Verfügung stehenden Werte eines definierten Wertebereiches generiert. Aber nicht nur das Generieren von Bergen ist mit den softwarebasierten Agenten möglich. Denn ein softwarebasierter Agent, der Hügelagent genannt wird, generiert Hügel mit kleinerer Steigung. Dies tut er auf die gleiche Weise wie der Bergagent. Dies basiert auf der Tatsache, dass der Hügelagent eine besondere Form des Bergagenten ist (vgl. Eibensteiner 2015, S. 30).

2.2.4.8 Flussagenten

Der Flussagent beginnt seine Arbeit, sobald sowohl Küstenlinien als auch Berge generiert wurden. Dies macht er, da er, sobald er beginnt, jeweils zwei Punkte als Start- und Endpunkte setzen muss. Diese Start- und Endpunkte sind jeweils zufällige Punkte in einem Gebirge und ein zufälliger Punkt an einer Küste. Sobald diese beiden Punkte gesetzt wurden, wandert der Agent unter Berücksichtigung der Steigung der Felder, die er in seinem Umfeld hat, von dem Startpunkt zu dem Endpunkt. Bei dieser Wanderung beschreibt sein zurückgelegter Weg einen potenziellen Flussverlauf. Da ein potenzieller Fluss aus seinem zurückgelegten Weg entstehen könnte, achtet der Agent darauf, auf seinem Weg vom Start- zum Endpunkt Felder mit einer hohen Steigung zu meiden, damit der Flussverlauf später realistisch wirkt. Sobald der Agent an dem Endpunkt angekommen ist, legt er die Strecke vom End- zum Startpunkt auf seinem zuvor bereits begangenen Weg noch einmal zurück. Bei seiner Bewegung kerbt er eine Schneise in das Terrain, welches sich unter dem vordefinierten Weg befindet. Diese Schneise wird immer breiter, je länger der Agent diesen Weg bestreitet. Sollte der Fall eintreten, dass der Agent bei dem Zurücklegen seines Weges auf einen bereits existierenden Fluss trifft, beendet er seinen Weg bei dem Fluss und führt beide Flüsse zusammen. Sollte allerdings der Fall eintreten, dass der Agent seinen Zielpunkt zu früh erreicht, bricht der Agent seine aktuelle Aufgabe ab und beginnt den Vorgang mit einem anderen Start- und Endpunkt erneut. Allerdings kann es auch vorkommen, dass es aufgrund der Gestaltung des Geländes unmöglich ist, Flüsse zu erstellen, welche den Anforderungen entsprechen. Wenn es dazu kommen sollte, bricht der Agent seine Aufgabe ab. Der Agent versucht allerdings bis zu einem eingestellten maximalen Wert diesen Vorgang auszuführen, bevor er den Generierungsprozess komplett abbricht. Dies macht er, um zu verhindern, dass zu viele unvollendete Flussläufe auf dem Terrain entstehen (vgl. Eibensteiner 2015, S. 30-32).

2.3 Städtesysteme

2.3.1 Wachstumsregeln

Die Wachstumsregeln dienen dem Straßensystem als Indikator, ob seine Ausdehnung den gegebenen Regeln entspricht. Hierbei kommen die Wachstumsregeln hauptsächlich bei der Erstellung von Abzweigungen zum Tragen. Die Wachstumsregeln steuern sowohl die Häufigkeit der Erstellung von Abzweigungen als auch deren Ausrichtung. Hierbei folgen die Regeln drei Grundkonzepten der Straßenlegung. Diese sind das Ringsystem, die Rasterstruktur und die natürliche Verzweigung. Alle diese Bautypen folgen ihren eigenen Regeln bezüglich der Häufigkeit, der Ausrichtung und der Länge der Straßen (vgl. Petrasch 2008, S. 22-23).

2.3.2 L-System und seine Modifikation

Um das Straßennetz zu legen, wird eine modifizierte Version des L-Systems genutzt. Bei dieser Modifikation handelt es sich um das Ersetzen der reinen Textersetzungsfunktion mit einer implizierten Objektersetzung. Diese kleine Änderung ermöglicht nicht nur eine schnellere Ersetzung der Objekte, sondern führt auch zu einer erhöhten Beeinflussbarkeit durch den Nutzer (vgl. Petrasch 2008, S. 22).

2.3.3 Die Legung des Straßennetzes mittels L-System

Um das Straßennetz zu generieren, nutzt das L-System einen definierbaren Punkt des Terrains als Ausgangspunkt. Von diesem Ausgangspunkt ausgehend, wird nun, wie bei der dem L-System zugrunde liegenden Pflanzengenerierung, sukzessive ein Teilstück der Straße durch neue Stücke der Straße und potenziell durch eine Abzweigung ersetzt. Bei der Straßengestaltung wird dem Nutzer die Möglichkeit eingeräumt, großen Einfluss auf das Straßennetz zu nehmen. Dies verwirklicht er durch Abänderung der Parameter in den Wachstumsregeln. Hier kann er nicht nur die Häufigkeit der Abzweigungen bestimmen, sondern auch deren Aussehen, Neigung sowie deren Abstände zu anderen Straßen. Allerdings wird dem User durch ein weiteres Kontrolltool geholfen, eine Straße, trotz Veränderung in den Wachstumsregeln, geometrisch zu legen. Dies übernimmt ein eigenständiger Algorithmus. Dieser gesamte Prozess generiert letzten Endes einen Grafen, der mit seinen Knoten Kreuzungen und mit seinen Kanten Straßen beschreibt (vgl. Petrasch 2008, S. 21-22).

2.3.4 Grundlagen des Multiagentensystems für den Straßenbau

Konträr zu dem L-System verhält sich das Multiagentensystem. Das Multiagentensystem findet meistens Anwendung in Simulationen. Allerdings ermöglicht die einzigartige Verwendungsmöglichkeit, die das Multiagentensystem bietet, auch die Anwendung im PCG-Bereich. Das Multiagentenwachstum arbeitet in einer zweidimensionalen Matrix. Allerdings benötigt das Multiagentensystem neben der zweidimensionalen Matrix noch Terraininformationen als Input, um richtig zu arbeiten. Diese Terraininformationen dienen dem Multiagentensystem als Anker in der Welt und sollten sowohl Informationen über die Höhe als auch über die Breite enthalten. Hierbei ist es unerheblich, welches Objekt die Informationen übergibt. Die Hauptsache ist, dass sich das Objekt nach dem Übergeben der Informationen nicht mehr in punkto Höhe oder Breite verändert. Nachdem der Anker gelegt wurde, kann der Nutzer nun die Höheninformationen aller Felder, außer das Feld des Ankers, manuell anpassen, um die Generierung der Objekte des spezifischen Feldes den individuellen Bedürfnissen anzupassen. Allerdings ist es für das Multiagentensystem unerheblich, ob diese Informationen manuell oder prozedural erzeugt wurden. Diese Informationen können nun genutzt werden, um das letztendliche Straßensystem zu etablieren. Dies geschieht durch einen von zwei Agenten. Die Agenten unterteilen sich in Extender-Agent und Connector-Agent (vgl. I. H. Parish 2001, S. 301)

2.3.5 Extender-Agent

Sobald die Daten in die 2-D-Matrix eingespeist wurden, beginnt die Generierungsarbeit des Extender-Agenten. Der Agent wandert über das bereits erstellte Terrain und sucht dabei nach Feldern, die noch nicht von Straßen unterstützt werden. Um diese Felder zu identifizieren, untersucht der Agent die umliegenden Felder auf ihre Informationen bezüglich der Distanz, Neigung usw. Sobald der Agent dann ein Feld gefunden hat, das nicht von einer Straße unterstützt wird, begibt er sich dorthin. Nachdem er dort angekommen ist, macht er sich auf den Weg zu einer nahen Kreuzung. Auf seinem Weg dorthin beschreibt er durch seinen bereits zurückgelegten Weg eine mögliche Position der neuen Straße. Des Weiteren negiert er Felder, die der Straße eine hohe Neigung geben könnten. Sobald der Extender-Agent an seinem anvisierten Wegstück angekommen ist, überprüft er noch einmal die Position der Straße, die er vorgefertigt hat. Diese Überprüfung dient dazu, sicherzustellen, dass die zukünftige Straße weder zu nah an einer anderen Kreuzung liegt noch über eine zu geringe Straßendichte verfügt. Des Weiteren wird überprüft, ob auch in punkto Steigung oder Neigung nicht gegen die vorgegebenen Regeln verstoßen wird. Wenn die Straße allen Kriterien entspricht, wird sie erstellt. Falls sie allerdings gegen die gegebenen Regeln verstößt, wird sie gelöscht und der gesamte Vorgang beginnt von neuem (vgl. I. H. Parish 2001, S. 302-303).

2.3.6 Connector-Agent

Der Connector-Agent beginnt seine Arbeit, sobald ein Stück des Straßennetzes existiert. Er wandert dieses Stück der Straße entlang und definiert innerhalb eines anpassbaren Radius ein Ziel. Dies geschieht über eine Breitensuche-Funktion. Sollte der Endpunkt einen gewissen Radius überschreiten, versucht der Agent zwischen dem Startpunkt und dem zuvor definierten Endpunkt, eine Straße zu errichten. Hierbei handelt der Connector-Agent nach der gleichen Vorgehensweise und beachtet dieselben Regeln wie der Extender-Agent (vgl. I. H. Parish 2001, S. 305).

2.4 Siedlungsgenerierung

2.4.1 Grundstückslegung

Nach dem Abschluss der Straßenlegung wird eine Polygonenbeschreibung genutzt, um die freien Flächen zwischen den Straßen zu ermitteln. Wenn dies geschehen ist, bietet diese Erkenntnis den Grundstein zu der Erstellung von Gebäuden. Bevor Gebäude gebaut werden können, muss erst einmal entschieden werden, welche Häuser auf welchem Platz erstellt werden sollen. Hierzu werden der Residential-Agent oder der Commercial-Agent genutzt. Der Residential- Agent untersucht das Straßennetz im Hinblick auf seine offenen Felder und entscheidet dann aufgrund der vorgegebenen Parameter, welche Art dem jeweiligen Feld zugewiesen wird. Um dann Wohngebiete aus dem Pool der möglichen Bauplätze zu ermitteln, werden die Bauplätze im Hinblick auf ihre Nähe zu Straßen überprüft. Bei den Straßen wiederum entscheidet der Dichtegrad. Wenn diese beiden Werte möglichst klein sind (manuell vom Nutzer anpassbar), wird das anliegende Feld als Residential-Areal definiert und der Beginn eines Wohnhauses beginnt. Im Gegensatz zu dem Residential Agent sucht der Commercial-Agent nach Orten mit einer möglichst hohen Straßendichte und unmittelbarer Straßennähe. Falls er Felder findet, die diesen Anforderungen entsprechen, wird das anliegende Feld als kommerziell nutzbares Gebiet definiert. Dieses Gebiet beherbergt dann Gebäude wie Fabriken oder Einkaufsläden (vgl. I. H. Parish 2001, S. 306-308).

2.4.2 Gebäudegenerierung Agentensystem

Da für die Erstellung ein softwarebasierendes Agentensystem genutzt wird, empfiehlt es sich, die Generierung der Gebäude nach dem CGA (Computer- Generated-Architektur) durchzuführen. Dies empfiehlt sich, da das CGA im Gegensatz zu dem L-System einen entscheidenden Vorteil bietet. Das CGA enthält nämlich, durch seine Eigenschaft, den Produktionsprozess sequenziell abzuhandeln, eine größere Spezialisierungsmöglichkeit für den Nutzer als das L- System mit seiner simultanen Abhandlung der Produktionsschritte. Allerdings ist es hierbei nicht unerheblich, zu erwähnen, dass das CGA trotz seiner anderen Strukturierung eine ähnliche Grammatik wie das L-System verwendet. Beide nutzen Stackoperationen und Parameter und Zufallszahlen, um bei der ÄGrundsteinlegung" des jeweiligen Gebäudes ein Symbol zu erzeugen. Dieses Symbol ist einzigartig für jedes einzelne Haus, da es Parameter beinhaltet, die wiederum Positionsvektoren wie x, y, z und s für die Skalierung beinhalten. Diese Vektoren bilden in ihrer Gesamtheit die Baundingbox des Gebäudes. Des Weiteren werden, um die Reihenfolge der Symbole zu ordnen, Prioritäten von dem User vergeben. So lässt sich der Entwicklungsprozess beliebig steuern. Um die Vielfalt der Gebäudevariationen zu erhöhen, werden die Produktionsanwendungen mit Zufallszahlen kombiniert. Diese Produktionsanwendungen greifen dann wiederum auf Werte wie die Skalierung, die Translation und die Rotation zu, um möglichst viele Ergebnisse zu erzeugen. Des Weiteren kommt hier die Split-Regel in vollem Ausmaß zum Tragen. Doch bevor der ÄProduktionsprozess" des Hauses beginnt, werden zuerst noch die maximalen Ausmaße des Hauses per Anxiom-Vermessung des Grundstücks festgelegt. Sobald dies erledigt ist, wird ein grobes 3D-Gerüst des Hauses erzeugt, welches dann per Algorithmus unter Berücksichtigung der zuvor festgelegten Gesetze die Außenseite des Hauses generiert. Um letzten Endes dann noch das Dach fertigzustellen, wird die Straight-Skeleton-Methode verwendet (vgl. Dettmers 2014, S. 14-15).

2.4.3 Gebäudegenerierung L-System

Auch bei der Erstellung der Gebäude durch das L-System werden die zuvor generierten Grundstücksgrenzen genutzt. Als erstes entsteht ein grobes Grundkonstrukt der späteren Häuserform. Dieses Grundkonstrukt wird als erstes kleiner skaliert, damit trotz Anwendung weiterer Funktionen gewährleistet werden kann, dass das letztendliche Gebäude nicht die Grundstücksgrenze überschreitet.

Um zu gewährleisten, dass diese Form des Gebäudes ohne Probleme auch von externen Programmen eingelesen werden kann, wird sie im Wavefront-Format gespeichert. Nachdem die Poligone des Gebäudes skaliert wurden, wird letzten Endes noch Textur aufgetragen (vlg. Petrasch 2008, S. 28-29).

[...]