algorithm - L 系统节点重写示例

Question

这是我在 stackover flow 中的第一篇文章。最近我开始阅读名为“植物的算法之美”的书，其中在第 1 章中，他解释了 L 系统。 (您可以阅读章节 here )。

据我所知，有两种类型的 L 系统。边重写和节点重写。

边缘重写相对来说非常简单。有一个初始的起始多边形和一个生成器。初始多边形的每条边(边)将被生成器替换。

但是这个节点重写很困惑。根据我收集到的信息，有两个或更多规则，并且每次迭代都会将规则中的变量替换为其常量对应项。

对于海龟解释，这些是标准规则

F : Move turtle forward in current direction (initial direction is up)
+ : rotate turtle clock wise
- : rotate turtle anti clock wise
[ : Push the current state of the turtle onto a pushdown operations stack. 
    The information saved on the stack contains the turtle’s position and orientation, 
    and possibly other attributes such as the  color and width of lines being drawn.
] : Pop a state from the stack and make it the current state of the turtle

因此请考虑本网站中显示的示例。 http://www.selcukergen.net/ncca_lsystems_research/lsystems.html

Axiom     : FX
Rule      : X= +F-F-F+FX 
Angle     : 45

所以 at n=0(忽略公理中的 X)

只有 F 表示一条直线向上。

在 n=1

用规则替换公理中的X

F+F-F-F+F(再次忽略最后的X)

输出是这样的

http://www.selcukergen.net/ncca_lsystems_research/images/noderewrite.jpg

一个简单的例子，一个规则就可以了。但是在第 25 页的“植物的算法之美”一书中，有一些规则我不确定如何解释。

X
X = F[+X]F[-X]+X
F = FF

请看这张图片。

https://lh6.googleusercontent.com/g3aPb1SQpvnzvDttsiiBgiUflrj7R2V29-D60IDahJs=w195-h344-no

在 n=0

只是'X'。不知道这是什么意思

在 n=1

应用规则 1 (X->F[+X]F[-X]+X):F[+]F[-]+ 忽略所有 X。这只是一条直线.

应用规则 2 (F->FF) : FF[+]FF[-]。这只是一条直线。

根据我的理解，最终输出应该是乌龟向上移动四次。或者至多最终输出应该只包含四行。

我在网上找到了一个L-system generator我认为这会帮助我更好地理解这一点，所以我输入了相同的值，这是 n=1 时的输出结果

https://lh6.googleusercontent.com/-mj7x0OzoPk4/VK-oMHJsCMI/AAAAAAAAD3o/Qlk_02_goAU/w526-h851-no/Capture%2B2.PNG

输出绝对不是一条直线，最糟糕的是它有 5 条线，这意味着最终输出方程中应该有 5 F。

帮助我理解这个节点重写。如果不理解这一点，我就无法进一步阅读本书。

很抱歉这篇文章太长了，对于 pre 标签中的链接。我不能发布超过 2 个链接。感谢您耐心地从头到尾阅读它。

Answer 1

L 系统非常简单并且依赖于文本替换。

有了这个起始信息:

Axiom     : FX
Rule      : X= +F-F-F+FX 

然后基本上，要生成下一代系统，您需要使用上一代系统，并为其中的每个字符应用替换。

您可以使用此算法生成一代:

• 对于上一代的每个角色:
  • 检查我们是否有该字符的替换规则
    • 是:附加替换
    • NO:追加原字符

因此:

n(0) = FX

            +-- from the X
            |
        v---+---v
n(1) = F+F-F-F+FX
       ^
       +- the original F

如果你有这个开始:

Axiom : ABA
Rule  : A = AB

然后你会得到这个:

        +--------+
        |        |
n(0) = ABA       |
       | |       |
       | ++      |
       |  |      |
       vv vv     |
n(1) = ABBAB     |
         ^       |
         +-------+

基本上:

• 对于X世代的每个A，在产生X+1世代时，输出AB
• 对于没有规则的所有其他字符，只输出该字符(这处理所有 B)

这将是一个每代长度加倍的系统:

Axiom : A
Rule  : A = AA

将创建:

n(0) = A
n(1) = AA
n(2) = AAAA
n(3) = AAAAAAAA