L系统

来自集智百科 - 伊辛模型
跳到导航 跳到搜索

程序运行说明

Lindermayer系统(简称L系统)是另外一种分形图形生成的方法,其主要原理是设定基本简单的绘图规则,然后让计算机根据这些规则进行反复跌代,就可以生成各种各样的图形来。用L系统可以非常逼真的模拟植物的生长过程。上面的程序就是L系统的一个展示。我们已经设定好了一个规则库,你可以通过选择不同的规则画出不同的图形来,同时,你可以通过“设置参数”来改变这些规则从而画出你自己的图形来

原理

你所看到的所有复杂图形都是用非常简单的规则生成的!究竟是怎么生成的呢?首先,我们来考察一下人们画图的过程。无论什么样的复杂图形,我们都可以把图形看成若干线条构成的,而一个线条是由起点和它的方向决定的,这样,人们复杂的画图动作可以分解为若干线条的连接组合。根据这些,我们来讨论计算机绘图。

首先,计算机绘图也是要确定一个起始点和开始画线的方向这叫做初始状态,当画图进行到任意一个阶段的时候,我们可以用(x,y,a)这三个量来确定任意一个画图的状态,即当前的坐标x,y和当前要画线条的方向角a。然后,我们需要考虑的是状态到状态是如何转换的。我们把状态之间的转换称为动作,不难看出,仅仅用平移和旋转方向就能完成状态之间的转换。接下来,我们用符号定义一些简单的动作(包括评议、旋转和辅助动作)。

F:表示在当前的位置画一条长为l的直线段。l是由用户事先任意设定的数值,表示基本线段的长度。

+:表示逆时针旋转一个角θ,θ的数值由用户事先确定

-:表示顺时针旋转一个角θ;

[:表示暂时保存当前的画图状态

]:表示提取出保存的画图状态。 “[”和“]”要成对的出现。


这样,确定了开始的坐标和方向,由上面符号组成的任意的一系列指令就能指导画图了。比如:FF+F,其中长度l=1,θ=90度角,开始坐标是2,0,开始方向角是90度。

其中蓝色的线条是画图指令画出的图。开始的时候画图状态为(2,0,90),也就是说起点在2,0这个点,并且这个时候画图的方向是朝上的,然后开始画指令F,它的意思是方向不变,往前走1个步长并且画线连接上起始的点和下一个将要移动到的点(2,1),因此画图机器就往正上方画了一条蓝色的长度为1的线段,并且把当前的状态改为了(2,1,90)就是说坐标移动到了2,1这个点,而方向角没变还是垂直向上。接下来画下一个F,仍然是朝上方画一个长度为1的线段。然后是+表示画图状态的方向逆时针旋转90度,然后这个时候的状态变为(2,2,180),就是说坐标为(2,2)方向朝左方。然后再画一个F,就是往左画一个小线段状态改为(1,2,90),到此画图命令FF+F执行结束。综合起来,我们能得到下面的表:

下面看看比较复杂的画图指令:FF[+F][-F],起始状态和刚才一样仍然是(2,0,90),且l为1,转角为90度。

指令 状态 画图动作
起始时刻 (2,0,90)
F (2,1,90) 向上画一条长为1的线段
F (2,2,90) 向上画一条长为1的线段
+ (2,2,180) 逆时针旋转90度,不画图
F (1,2,180) 向左画一条长为1的线段


前两个F和上面叙述的执行情况差不多,下面开始讲"["操作,"["操作的含义就是把当前的画图状态先存起来,假设有一个大皮包M可以存放这些状态,那么当执行完操作FF的时候,画图状态是(2,2,90),下面遇到了"[" 命令,那么我们把这个状态存到皮包M中,这样M={(2,2,90)},表示M中有一个状态为(2,2,90),"["指令除了存储状态到皮包中其他什么动作也不做,当前的状态仍然是(2,2,90)。接下来执行+命令,逆时针旋转90度,则状态变成(2,2,180),然后是F则往左画一条线段,状态为(1,2,180)。接下来执行指令"]",它表示从皮包中取出一个状态作为当前的状态,这样,皮包中有一个状态(2,2,90),因此当前的状态就变为了(2,2,90),也就是说我们的铅笔回到了(2,2)点,并且方向朝上,这个时候由于从皮包M中取走了东西,所以皮包就空了。结下的指令为[依然把状态(2,2,90)存到皮包中,然后-则顺时针旋转90度,状态变为(2,2,0),执行F则往右画一条线段。


画这个图形的命令执行、当前状态、存储情况如下表:

指令 状态 M中存储的值 画图动作
起始时刻 (2,0,90)
F (2,1,90) 向上画一条长为1的线段
F (2,2,90) 向上画一条长为1的线段
[ (2,2,90) (2,2,90)
+ (2,2,180) (2,2,90) 逆时针旋转90度,不画图
F (2,1,180) (2,2,90) 向左画一条长为1的线段
] (2,2,90)
[ (2,2,90) (2,2,90)
- (2,2,0) (2,2,90)
F (2,3,0) (2,2,90) 向右画一条长为1的线段
] (2,2,90)

我们已经知道了由F,+,-,[,]这样的符号可以构成一串画图的指令指导机器画图,也就是说给定一个符号串就能对应的画出这个符号串代表的图形,那么如果用一种办法能够生成这样的符号串序列,那么相当于可以构造出图形来。这种生成指令的办法是什么呢?答案就是产生式系统。

产生式(也叫做规则)是形如X->Y的式子,其中X叫做左件,Y叫做右件。X->Y表示X能够推导出Y。如果X是一个字符串,Y也是字符串,那么X->Y表示能够用Y来替换X。例如如果给定一个初始时刻的字符串ABXXTT,那么运用规则X->Y就能把这个字符串变成ABYYTT。如果产生式的右件多于一个字符,那么就能推导出比原来字符串更长的字符串来。例如如果X->YYY,那么ABXXTT会被替换成ABYYYTT,显然后来的字符串比原来的长。我们已经看到了从简单的字符串生成复杂字符串的可行性了。

接下来,要说明的是产生式可以进行嵌套的表示,比如说X->XY就是一种嵌套的形式。因为当你用右件XY代替前件X的时候产生的新字符又会产生X,而X又可以运用规则X->XY,这样可以无限次的迭代下去。

好了,有了产生式就不难理解产生式系统了,它就是由若干个产生式构成的一组语句。并且各个产生式之间可以相互替换字符串。比如如下的产生式系统:X->YF, Y->+FX,开始时刻的字符串是X,用这两个规则跌代1次就能得到字符串:+FXF,迭代2次就是+F+FXFF,3次是+F+F+FXFFF,……。(这里跌代一次表示的是用产生式系统中的所有产生式规则都来替换当前的字符串)。我们已经看到,最后的式子就是形如我们上面列举的指令例子,如果把最后的X忽略掉,这个指令串就能指导机器画图了!这就是L系统的工作原理!下面我们以画出下面的枝条为例,再看看L系统是如何运行的。


已知这个图形的产生式系统是:F->F[+F]F[-F]F,开始的时候字符串是F。转角为-25.7341度。这样,我们跌代6次就可以得到最终的画图指令(太长,此处略去),再把这个指令字符串对应的指导机器画出图形,就能得到上面的图。你可以点击程序中单步运行的按钮,看看系统跌代不同的次数能够产生什么样的图形。


引申

在这里我们看到了产生式系统是如何产生复杂的符号串序列,而符号串序列又是如何指导画图的。整个这个过程都体现了复杂系统的思想,也就是简单的规则孕育着复杂的行为。不难看出来,程序里的图形大部分都是类似于植物的,那么L系统的方法就给了我们启示,植物的生长是受类似于产生式规则指导的生成过程。如果我们完全把图形上画一条线段理解成植物枝干的一次生长,那么运用L系统的方法我们不难生成类似于真正植物的人工植物。

L系统的方法还能回答这个问题:为什么小小的种子可以孕育整个的植物呢?要知道,自然界的植物形态是非常非常复杂的,因此植物所包含的信息量也是很大的,种子这个小东西怎么能包含整个树木的信息呢?如果你理解了L系统的工作原理,你就不难回答这个问题了,那就是种子中包含的信息不是整个树的信息,而是生成这个树木的规则!而这个规则是简单的,信息量是很小的。这样,树木的生长就是一个根据种子中的规则和自然界的相互作用产生复杂树木的过程。

聪明的人可能会继续问,那种子中的规则从哪里来的呢?答案是自然进化来的,如果把树木理解为指令的生成结果,那么自然选择就是发生在规则层面的事情。也就是说自然选择不是简单的对树木进行直接选择,而是对种子中所蕴含的规则进行选择的。那么,在自然界,规则又是如何决定树木的生长的呢?答案是物理规律!正是自然界中的物理规律完成了从植物种子中解码指导植物生成的过程。

进一步,生命体也是这样,基因记载了指令,也就是生成动物特征的规则,物理规律决定了基因生成生命个体的过程。

编者推荐

集智视频推荐

系统科学概论

本课程将从科学发展的基本趋势出发,介绍系统科学的思想、方法和部分研究内容,包括自组织现象、动力学与混沌、分形结构、复杂网络、复杂适应性系统等,同时展示复杂性研究在社会经济系统与生命系统中的应用实例。

分形的世界

本课程中,主要介绍了分形现象、分形维数、利用分形规律的计算方法以及混沌。



本中文词条由不是海绵宝宝编辑,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。