每日算法 — 使用java实现L系统：文法规则迭代与分形植物生成

引言

L系统（L-system，全称Lindenmayer system）是匈牙利生物学家Aristid Lindenmayer于1968年为描述植物生长过程而提出的一种形式文法。它以极其简洁的字符串重写规则，通过迭代生成复杂的分形结构和自然形态。L系统在计算机图形学、程序化内容生成、艺术设计和生物学建模中有着广泛应用。本文将讲解L系统的文法理论，实现确定性上下文无关L系统（D0L-system），并提供完整的Java代码来生成经典的分形植物和几何图案。

L系统的数学理论

基本定义

一个L系统由四元组 $G = (V, \omega, P, F)$ 组成：

• 字母表 V：所有可用符号的集合，如 ${F, +, -, [, ]}$
• 公理（初始串）$\omega$：迭代开始的字符串
• 产生式规则 P：形如 $A \to \alpha$ 的重写规则，表示符号 $A$ 被替换为字符串 $\alpha$
• 解释函数 F：将符号映射为绘图指令

迭代过程

从公理 $\omega$ 开始，对当前字符串中的每个符号应用产生式规则，生成下一代字符串：

$$\omega_0 = \omega$$
$$\omega_{n+1} = \text{applyProductions}(\omega_n)$$

经过 n 次迭代后，得到的字符串通过解释函数转换为图形绘制指令。

turtle 图形解释

L系统最常用的图形解释是 turtle 几何（海龟绘图）：

经典L系统实例

1. Koch雪花曲线

• 公理：F++F++F
• 规则：F → F-F++F-F
• 角度：60°
• 迭代：4次生成经典雪花

2. Sierpinski三角形

• 公理：F-G-G
• 规则：F → F-G+F+G-F, G → GG
• 角度：120°

3. 龙形曲线（Dragon Curve）

• 公理：FX
• 规则：X → X+YF+, Y → -FX-Y
• 角度：90°

4. 二叉树（植物模拟）

• 公理：X
• 规则：X → F+[[X]-X]-F[-FX]+X, F → FF
• 角度：25°

Java实现

以下实现包含L系统核心引擎、turtle解释器和可视化绘制。

import javax.swing.*;
import java.awt.*;
import java.awt.geom.Line2D;
import java.util.*;
import java.util.List;

/**
 * L系统分形生成器
 * 支持确定性上下文无关L系统（D0L-system）
 */
public class LSystemFractal extends JPanel {

    private String axiom;           // 公理（初始串）
    private Map<Character, String> rules;  // 产生式规则
    private double angle;           // 转角（度）
    private double stepSize;        // 步长
    private int iterations;         // 迭代次数
    private String currentString;   // 当前迭代得到的字符串
    private List<Line2D.Double> lines; // 生成的线段列表

    /**
     * 构造函数
     */
    public LSystemFractal(String axiom, Map<Character, String> rules,
                          double angle, double stepSize, int iterations) {
        this.axiom = axiom;
        this.rules = rules;
        this.angle = Math.toRadians(angle);
        this.stepSize = stepSize;
        this.iterations = iterations;
        this.lines = new ArrayList<>();

        // 执行迭代
        this.currentString = iterate(axiom, iterations);
        // 解析字符串生成线段
        parseAndDraw();
    }

    /**
     * L系统核心：字符串迭代重写
     * @param start 起始字符串
     * @param n 迭代次数
     * @return 迭代n次后的字符串
     */
    public String iterate(String start, int n) {
        String current = start;
        for (int i = 0; i < n; i++) {
            StringBuilder next = new StringBuilder();
            for (char c : current.toCharArray()) {
                // 如果有对应规则则替换，否则保留原符号
                next.append(rules.getOrDefault(c, String.valueOf(c)));
            }
            current = next.toString();
            System.out.println("迭代 " + (i + 1) + ": 长度 = " + current.length());
        }
        return current;
    }

    /**
     * Turtle解释器：将L系统字符串解析为线段列表
     */
    private void parseAndDraw() {
        // 初始位置和方向（向上）
        double x = 0, y = 0;
        double dir = -Math.PI / 2; // 向上（负y方向）

        // 状态栈，用于处理分支 [ ]
        Deque<TurtleState> stack = new ArrayDeque<>();
        lines.clear();

        // 先进行一次遍历，计算边界框，用于居中显示
        double minX = 0, maxX = 0, minY = 0, maxY = 0;
        double cx = 0, cy = 0, cdir = -Math.PI / 2;

        for (char c : currentString.toCharArray()) {
            switch (c) {
                case 'F':
                case 'G': // 有些L系统用G也画线
                    cx += stepSize * Math.cos(cdir);
                    cy += stepSize * Math.sin(cdir);
                    minX = Math.min(minX, cx); maxX = Math.max(maxX, cx);
                    minY = Math.min(minY, cy); maxY = Math.max(maxY, cy);
                    break;
                case 'f':
                    cx += stepSize * Math.cos(cdir);
                    cy += stepSize * Math.sin(cdir);
                    break;
                case '+':
                    cdir += angle;
                    break;
                case '-':
                    cdir -= angle;
                    break;
                case '[':
                    stack.push(new TurtleState(cx, cy, cdir));
                    break;
                case ']':
                    if (!stack.isEmpty()) {
                        TurtleState s = stack.pop();
                        cx = s.x; cy = s.y; cdir = s.dir;
                    }
                    break;
            }
        }

        // 计算缩放和偏移，使图形居中
        double width = maxX - minX;
        double height = maxY - minY;
        double scale = Math.min(getWidth() * 0.85 / Math.max(width, 1),
                                 getHeight() * 0.85 / Math.max(height, 1));
        double offsetX = (getWidth() - width * scale) / 2 - minX * scale;
        double offsetY = (getHeight() - height * scale) / 2 - minY * scale;

        // 第二次遍历：实际生成线段（带缩放）
        x = offsetX;
        y = offsetY;
        dir = -Math.PI / 2;
        stack.clear();

        for (char c : currentString.toCharArray()) {
            switch (c) {
                case 'F':
                case 'G':
                    double nx = x + stepSize * scale * Math.cos(dir);
                    double ny = y + stepSize * scale * Math.sin(dir);
                    lines.add(new Line2D.Double(x, y, nx, ny));
                    x = nx; y = ny;
                    break;
                case 'f':
                    x += stepSize * scale * Math.cos(dir);
                    y += stepSize * scale * Math.sin(dir);
                    break;
                case '+':
                    dir += angle;
                    break;
                case '-':
                    dir -= angle;
                    break;
                case '[':
                    stack.push(new TurtleState(x, y, dir));
                    break;
                case ']':
                    if (!stack.isEmpty()) {
                        TurtleState s = stack.pop();
                        x = s.x; y = s.y; dir = s.dir;
                    }
                    break;
            }
        }
    }

    /**
     * Turtle状态：位置和方向
     */
    private static class TurtleState {
        double x, y, dir;
        TurtleState(double x, double y, double dir) {
            this.x = x; this.y = y; this.dir = dir;
        }
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);
        g2d.setColor(new Color(34, 139, 34)); // 森林绿
        g2d.setStroke(new BasicStroke(1.2f));

        for (Line2D.Double line : lines) {
            g2d.draw(line);
        }

        g2d.setColor(Color.BLACK);
        g2d.drawString("迭代次数: " + iterations + 
                      " | 字符串长度: " + currentString.length() +
                      " | 线段数: " + lines.size(), 10, 20);
    }

    // ================== 工厂方法：预设经典L系统 ==================

    /**
     * Koch雪花曲线
     */
    public static LSystemFractal createKochSnowflake(int iterations, int size) {
        Map<Character, String> rules = new HashMap<>();
        rules.put('F', "F-F++F-F");
        return new LSystemFractal("F++F++F", rules, 60, size / Math.pow(3, iterations), iterations);
    }

    /**
     * Sierpinski三角形
     */
    public static LSystemFractal createSierpinski(int iterations, int size) {
        Map<Character, String> rules = new HashMap<>();
        rules.put('F', "F-G+F+G-F");
        rules.put('G', "GG");
        return new LSystemFractal("F-G-G", rules, 120, size / Math.pow(2, iterations), iterations);
    }

    /**
     * 龙形曲线
     */
    public static LSystemFractal createDragonCurve(int iterations, int size) {
        Map<Character, String> rules = new HashMap<>();
        rules.put('X', "X+YF+");
        rules.put('Y', "-FX-Y");
        return new LSystemFractal("FX", rules, 90, size / Math.sqrt(Math.pow(2, iterations)), iterations);
    }

    /**
     * 分形植物（二叉树）
     */
    public static LSystemFractal createFractalPlant(int iterations, int size) {
        Map<Character, String> rules = new HashMap<>();
        rules.put('X', "F+[[X]-X]-F[-FX]+X");
        rules.put('F', "FF");
        return new LSystemFractal("X", rules, 25, size / Math.pow(2, iterations), iterations);
    }

    /**
     *  Hilbert曲线（空间填充曲线）
     */
    public static LSystemFractal createHilbertCurve(int iterations, int size) {
        Map<Character, String> rules = new HashMap<>();
        rules.put('A', "-BF+AFA+FB-");
        rules.put('B', "+AF-BFB-FA+");
        return new LSystemFractal("A", rules, 90, size / Math.pow(2, iterations), iterations);
    }

    // ================== 主程序 ==================

    public static void main(String[] args) {
        // 选择要展示的分形类型和迭代次数
        String[] options = {"Koch雪花", "Sierpinski三角形", "龙形曲线", "分形植物", "Hilbert曲线"};
        int choice = 3; // 默认展示分形植物
        int iterations = 5;
        int panelSize = 700;

        LSystemFractal fractal;
        switch (choice) {
            case 0: fractal = createKochSnowflake(iterations, panelSize); break;
            case 1: fractal = createSierpinski(iterations, panelSize); break;
            case 2: fractal = createDragonCurve(iterations, panelSize); break;
            case 3: fractal = createFractalPlant(iterations, panelSize); break;
            case 4: fractal = createHilbertCurve(iterations, panelSize); break;
            default: fractal = createFractalPlant(iterations, panelSize);
        }

        JFrame frame = new JFrame("L系统分形生成 - " + options[choice]);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(panelSize + 20, panelSize + 50);
        frame.add(fractal);
        frame.setVisible(true);
    }
}

扩展：随机L系统与参数化L系统

import java.util.Random;

/**
 * 随机L系统（Stochastic L-System）
 * 每个符号可以有多个产生式规则，按概率选择
 */
public class StochasticLSystem {

    private Random random;
    // 随机规则：每个符号对应多个（规则，概率）对
    private Map<Character, List<Rule>> stochasticRules;

    static class Rule {
        String replacement;
        double probability;
        Rule(String r, double p) { this.replacement = r; this.probability = p; }
    }

    public StochasticLSystem(long seed) {
        this.random = new Random(seed);
        this.stochasticRules = new HashMap<>();
    }

    public void addRule(char symbol, String replacement, double probability) {
        stochasticRules.computeIfAbsent(symbol, k -> new ArrayList<>())
                       .add(new Rule(replacement, probability));
    }

    /**
     * 根据概率随机选择产生式
     */
    public String applyRule(char symbol) {
        List<Rule> rules = stochasticRules.get(symbol);
        if (rules == null) return String.valueOf(symbol);

        double r = random.nextDouble();
        double cumulative = 0;
        for (Rule rule : rules) {
            cumulative += rule.probability;
            if (r <= cumulative) {
                return rule.replacement;
            }
        }
        return rules.get(rules.size() - 1).replacement;
    }

    public String iterate(String start, int n) {
        String current = start;
        for (int i = 0; i < n; i++) {
            StringBuilder next = new StringBuilder();
            for (char c : current.toCharArray()) {
                next.append(applyRule(c));
            }
            current = next.toString();
        }
        return current;
    }
}

复杂度分析

由于字符串长度呈指数增长，实际应用中迭代次数通常控制在4-7次。对于更高迭代的需求，可采用即时解释（on-the-fly parsing）避免存储完整字符串。

应用场景

1. 程序化植物生成：游戏和电影中的植被、树木自动生成
2. 纹理合成：分形纹理、地形高度图的程序化生成
3. 建筑设计：参数化建筑外立面和结构形态探索
4. 艺术生成：生成艺术（Generative Art）和算法绘画
5. 生物学建模：植物生长模拟、细胞分裂模式研究
6. 电路设计：分形天线、空间填充曲线的电路布局优化
7. 数据可视化：空间填充曲线（Hilbert、Peano）用于高维数据降维可视化

总结

L系统以极简的文法规则展现了复杂性科学的深刻思想：简单的局部规则通过迭代可以涌现丰富的全局结构。本文实现了确定性L系统的核心引擎和turtle图形解释器，提供了Koch雪花、Sierpinski三角形、龙形曲线、分形植物和Hilbert曲线等经典实例。理解L系统不仅对于程序化内容生成至关重要，更可以帮助开发者建立”规则驱动生成”的思维方式，在游戏开发、数据可视化和创意编程中发挥巨大价值。