L-Systeme in C++: Prozedurale Baum-Modellierung für Cs334/Ece30834

Einführung in L-Systeme und prozedurale Modellierung

L-Systeme (Lindenmayer-Systeme) sind eine leistungsstarke Methode zur Erzeugung komplexer, natürlicher Formen durch wiederholte Anwendung einfacher Regeln. Ursprünglich von Aristid Lindenmayer zur Modellierung des Pflanzenwachstums entwickelt, finden sie heute Anwendung in der Computergrafik, der Spieleentwicklung und sogar in der KI-gestützten Architektur. In dieser Anleitung zeigen wir dir, wie du für die Cs334/Ece30834 Aufgabe einen prozeduralen Baum-Modellierer in C++ implementierst – ganz ohne die vollständige Lösung zu verraten.

Grundlagen: Aufbau eines L-Systems

Ein L-System besteht aus einem Axiom (Startstring), einem Drehwinkel A, einer Iterationszahl N und Regeln R. Jede Regel hat einen Vorgänger (ein Zeichen) und einen Nachfolger (eine Zeichenkette). In jeder Iteration wird jedes Zeichen im aktuellen String durch seinen Nachfolger ersetzt (falls eine Regel existiert), sonst bleibt es erhalten.

Beispiel aus der Aufgabenstellung: A = 25.7, N = 6, Axiom = f, Regel: f -> f[+f]f[-f]f. Nach 6 Iterationen entsteht ein komplexer Baum.

Implementierung der Parser-Funktion

Deine erste Aufgabe ist es, die parse() Methode in lsystem.cpp zu implementieren. Lies die Datei zeilenweise ein: erste Zeile = Winkel A, zweite = Iterationen N, dritte = Axiom S, danach folgen die Regeln. Ignoriere Leerzeichen. Speichere die Regeln in einer std::map. Achte darauf, dass der Vorgänger ein einzelnes Zeichen ist.

void LSystem::parse(const std::string& filename) {
    std::ifstream file(filename);
    if (!file) throw std::runtime_error("Datei nicht gefunden");
    file >> angle >> iterations;
    file >> axiom;
    std::string line;
    while (std::getline(file, line)) {
        if (line.empty()) continue;
        char pred; std::string succ;
        std::stringstream ss(line);
        ss >> pred;
        char colon; ss >> colon;
        std::getline(ss, succ);
        // Whitespace entfernen
        succ.erase(std::remove_if(succ.begin(), succ.end(), ::isspace), succ.end());
        rules[pred] = succ;
    }
}

Regelanwendung: Von der Iteration zum String

Die applyRules() Methode bekommt einen Input-String und gibt den String nach einer Iteration zurück. Für jedes Zeichen im Input: Wenn eine Regel existiert, hänge den Nachfolger an, sonst das Zeichen selbst. So entsteht schrittweise der endgültige String.

std::string LSystem::applyRules(const std::string& input) const {
    std::string output;
    for (char c : input) {
        auto it = rules.find(c);
        if (it != rules.end())
            output += it->second;
        else
            output += c;
    }
    return output;
}

Nach N Iterationen erhältst du den vollständigen String, der die Geometrie des Baums beschreibt.

Turtle-Grafik: Geometrie erzeugen

Die createGeometry() Methode interpretiert den finalen String als Turtle-Befehle. Die Turtle hat eine Position (x,y) und eine Orientierung (Winkel). Befehle:

• f, F, g, G: Zeichne eine Linie der Länge 5 und bewege dich vorwärts.
• s, S: Bewege dich vorwärts ohne zu zeichnen.
• +: Drehe um A Grad gegen den Uhrzeigersinn.
• -: Drehe um A Grad im Uhrzeigersinn.
• [: Pushe den aktuellen Zustand (Position+Winkel) auf einen Stack.
• ]: Pope den letzten Zustand vom Stack und setze ihn als aktuellen Zustand.

Verwende eine std::stack für die Zustände. Die Liniensegmente speicherst du in einem Vektor von LineSegment (z.B. zwei Punkte).

void LSystem::createGeometry(const std::string& str, std::vector<LineSegment>& segments) {
    struct State { double x, y, angle; };
    std::stack<State> stateStack;
    State current = {0.0, 0.0, 90.0}; // Start nach oben
    double step = 5.0;
    for (char c : str) {
        switch (c) {
            case 'f': case 'F': case 'g': case 'G': {
                double newX = current.x + step * cos(current.angle * M_PI / 180.0);
                double newY = current.y + step * sin(current.angle * M_PI / 180.0);
                segments.push_back({{current.x, current.y}, {newX, newY}});
                current.x = newX; current.y = newY;
                break;
            }
            case 's': case 'S': {
                current.x += step * cos(current.angle * M_PI / 180.0);
                current.y += step * sin(current.angle * M_PI / 180.0);
                break;
            }
            case '+': current.angle += angle; break;
            case '-': current.angle -= angle; break;
            case '[': stateStack.push(current); break;
            case ']': if (!stateStack.empty()) { current = stateStack.top(); stateStack.pop(); } break;
        }
    }
}

Stochastische Erweiterungen für organische Bäume

Um natürlichere Formen zu erzeugen, kannst du zufällige Variationen einbauen. Die Aufgabenstellung bietet zwei Optionen:

Zufälliger Winkel-Jitter (10%)

Füge einen optionalen Jitter-Wert J hinzu (z.B. 25.7<5>). Bei jedem + oder - wird der Winkel um einen zufälligen Wert zwischen -J und +J variiert. Verwende std::uniform_real_distribution.

// In createGeometry:
double jitter = (jitterEnabled) ? distribution(generator) * 2 - 1 : 0.0; // [-1,1]
current.angle += (c == '+') ? angle + jitter * angleJitter : angle - jitter * angleJitter;

Stochastische Regeln (Bonus 15%)

Erlaube mehrere Regeln mit demselben Vorgänger, jede mit einem Gewicht. Die Auswahl erfolgt zufällig entsprechend der Gewichtung. Ändere die Datenstruktur von std::map<char, std::string> zu std::map<char, std::vector<std::pair<double, std::string>>>. Beim Parsen: Wenn nach dem Vorgänger eine Zahl kommt, ist es das Gewicht; sonst Gewicht = 1. In applyRules() wähle zufällig eine Regel basierend auf den kumulierten Gewichten.

// Neue Datenstruktur
std::map<char, std::vector<std::pair<double, std::string>>> rules;

// Regelauswahl
char c = input[i];
auto it = rules.find(c);
if (it != rules.end()) {
    double totalWeight = 0.0;
    for (auto& p : it->second) totalWeight += p.first;
    double r = distribution(generator) * totalWeight;
    double sum = 0.0;
    for (auto& p : it->second) {
        sum += p.first;
        if (r <= sum) { output += p.second; break; }
    }
} else {
    output += c;
}

Trend-Beispiel: KI-generierte Kunst und Gaming

Stell dir vor, du entwickelst ein Indie-Game, in dem Bäume prozedural generiert werden – ähnlich wie in No Man's Sky oder Minecraft mit Mods. Mit L-Systemen kannst du unendlich viele Baumvarianten erzeugen, ohne jedes Modell von Hand zu modellieren. Oder du nutzt sie für KI-generierte Kunst: Ein neuronaler Netzwerk-Trainingsdatensatz könnte aus L-System-Bäumen bestehen. Die prozedurale Modellierung ist ein heißes Thema in der Spieleentwicklung (z.B. Hytale, Valheim) und in Architektur-Software.

Häufige Fehler und Tipps

• Vergiss nicht, Whitespace zu ignorieren – sonst liest du leere Regeln.
• Stack nicht leeren – bei ']' prüfen, ob Stack nicht leer ist, sonst Absturz.
• Winkel in Radiant umrechnen – cos und sin erwarten Radiant.
• Keine plattformspezifischen Includes – vermeide windows.h.
• Teste mit den mitgelieferten Beispielen – z.B. tree1.txt.

Zusammenfassung

Du hast nun die Grundlagen der L-System-Implementierung in C++ kennengelernt: Parsen, Regelanwendung, Turtle-Grafik und stochastische Erweiterungen. Diese Techniken sind nicht nur für die Uni-Aufgabe relevant, sondern auch für reale Anwendungen in der Computergrafik. Experimentiere mit verschiedenen Winkeln, Iterationen und Regeln, um faszinierende Baumstrukturen zu erzeugen. Viel Erfolg bei deiner Cs334/Ece30834 Abgabe!