L系统节点重写示例

Question

L系统节点重写示例

algorithmfractalsprocedural-programmingprocedural-generationl-systems

5

这是我在Stack Overflow的第一篇文章。最近我开始阅读一本名为“植物算法之美”的书，在第1章中，他解释了L系统。（您可以在此处阅读该章节。）

所以据我所理解，有两种类型的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

所以n=0时（忽略公理中的X），它只是一个指向上方的直线。

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系统生成器，我认为它会帮助我更好地理解这个问题，所以我输入了相同的值，以下是n=1时的输出结果。

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

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

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

抱歉发了这么长的帖子，并且在pre标签中放了链接。我不能发布超过2个链接。

- Plato Manchi

重要的是要区分指导如何绘制分形图形的命令（例如您的字母）和仅用于规则变异中的命令。这里的X属于后者，而其余部分属于前者。因此您不能只是“忽略”X，但您不会绘制它，因为它对您屏幕上的分形图形没有可见影响，但它将在规则变异期间用于生成下一代。因此，FX表示绘制一条线，并忽略X。但随后当您进行变异时，F表示为F，而X表示为+F-F-F+FX。 - Lasse V. Karlsen

是的，我的意思是忽略在屏幕上绘制，但它将在生成下一个变异规则时使用。我从第一个例子中理解了这一点。但是看看书中的例子。我无法理解迭代是如何发生的。如果您可以向我展示第一次迭代和第二次迭代的样子，那将非常有帮助。谢谢。 - Plato Manchi

这是一个简单的替换规则。在生成n(x)时，您需要取n(x-1)，并对其中每个具有替换规则的字符进行替换。当n(0) = "FX"和"X=+F-F-F+FX"时，n(1)变为"F+F-F-F+FX"。n(2)变为"F+F-F-F+F+F-F-F+FX"，每次您都会用其值（包括新的X）替换每个X。可能会有多个替换规则，因此通常会逐个字符循环输入，如果该字符有替换，则输出该替换，否则只输出该字符。 - Lasse V. Karlsen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lasse V. Karlsen · Accepted Answer

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

有了这个起始信息：

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

基本上，为了生产下一代系统，您需要取出上一代系统中的每个字符并应用相应的替换规则。

您可以使用以下算法来生成下一代系统：

对于上一代系统中的每个字符：
- 检查该字符是否有替换规则
  - 是：添加替换字符
  - 否：添加原始字符

因此：

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