书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第8章目录

8.6　L系统

1、L系统

• 1968年，匈牙利植物学家Aristid Lindenmayer开发出了一套基于语法的系统，用于模拟植物的生长模式。
• 这套系统称作L系统（Lindenmayer系统的简称）。

2、基础知识

(a)递归；
(b)变换矩阵；
(c)字符串。

一个L系统主要包括3个元素。

• 字母表　
  L系统的字母表由系统可能出现的合法字符组成。
  比如字母表“ABC”，意思是L系统中的任何“语句”（由字符组成串）只能包含这3个字符。
• 公理　
  公理是一个语句，用于描述系统的初始状态。
  举个例子，对于字母表为“ABC”的L系统，它的公理可以是“AAA”“B” 或 “ACBAB”。
• 规则　
  L系统的规则首先作用于公理，然后递归作用于结果，每次作用都会产生
  一个新的语句。一个规则包括“前身”和“继任者”两部分。比如，规则“A->AB”的意思就是：把字符串中的所有“A”都替换成“AB”。

3、示例

类似于递归分形，我们可以把规则的应用当成一次迭代。按照这个定义，公理就是第0代。

4、代码实现

• 下面讨论如何用代码实现迭代。我们先用一个字符串存储公理：
  String current = "A";
• 就像生命游戏和科赫曲线的实现，我们要用一个完全独立的字符串跟踪下一代：
  String next = "";
• 下一步：把规则应用于当前字符串，然后把结果放到next变量中。

for (int i = 0; i < current.length(); i++) {
    char c = current.charAt(i);
    if (c == 'A') {　　　　生成规则 A -> AB
        next += "AB";
    } else if (c == 'B') {　　　生成规则 B -> A
        next += "A";
    }
}

• 循环完成之后，current的值就等于next。
  current = next;
• 为了确保程序能正常工作，我们把这些操作放到一个函数中，并在鼠标被按下时调用该函数。

  由于规则递归地应用于每一代，字符串的长度呈指数性增长。在第11代，字符串共有233个字符；到第22代，字符的个数就超过了46 000。

5、优化

• 在大字符串拼接方面，Java的String类的效率非常低。String对象是“不可变”的，也就是说，String对象在创建后就无法改变。每次在String对象末尾添加内容时，Java都必须创建一个全新的String对象（尽管你用的是同一个变量名）。
• 为了提高L系统的运行效率，我们应该使用StringBuffer类。StringBuffer对字符串拼接操作做了特别的优化，在拼接完成后，它也可以被轻易地转化为String对象。

StringBuffer next = new StringBuffer();　　　这个StringBuffer对象代表“下一代”语句
for (int i = 0; i < current.length(); i++) {
    char c = current.charAt(i);
    if (c == 'A') {
        next.append("AB");　　　用append()函数代替+=
    } else if (c == 'B') {
        next.append("A");
    }
}
current = next.toString();　　　StringBuffer可以被轻易地转化回String对象

6、工作原理

• 我们可以把L系统的语句当作绘图指令。
  下面用另一个例子说明其中的工作原理。

  

7、海龟绘图法

• “FG+-[]”是L系统常用的字母表，它的含义如下。
  F： 画一个线段，然后向前移动
  G： 向前移动（不画任何线段）
  +： 向右转
  -： 向左转
  [： 保存当前的位置
  ]： 恢复之前的位置

• 这种绘图框架通常称为“Turtle graphics”（海龟绘图法，源自早期的LOGO编程）。想象你的电脑屏幕中有一只海龟，你可以对它下一些命令：向左转、向左转、画一个线段等。Processing并不会自动以这种方式工作，但在translate()、rotate()和line()函数的帮助下，我们可以轻易地实现Turtle graphics引擎。

• 可以按照以下方式把字母表翻译为Processing代码。
  F：line(0,0,0,len); translate(0,len);
  G：translate(0,len);
  +：rotate(angle);
  -：rotate(-angle);
  [：pushMatrix();
  ]：popMatrix();

8、3个类

• Rule类 　负责存放L系统规则的“前身”和“继任者”。
• LSystem类　 负责L系统的迭代计算（用到了上面所说的StringBuffer类）。
• Turtle类　阅读L系统产生的语句，执行相应的绘图指令。