10行代码，在Unity感受植物算法之美(递归/L算法/程序生成 ...

stonstad

0.效果



1.代码

        /// <summary>
        /// 画一棵树
        /// </summary>
        /// <param name="origin">树主干的起点</param>
        /// <param name="end">树主干的终点</param>
        /// <param name="angle">树枝的分叉角度</param>
        public void Draw(Vector3 origin, Vector3 end, float angle)
        {
            float growthRate = 0.67f;

            IEnumerator enumerator()
            {
                Debug.DrawLine(origin, end, Color.green, 3f);
                yield return new WaitForSeconds(0.1f);
                float sqrLength = Vector3.SqrMagnitude(end - origin);

                if (sqrLength > 0.1f * 0.1f)
                {
                    //向左分叉
                    Quaternion leftRotation = Quaternion.Euler(new Vector3(0, 0, angle));
                    Vector3 leftParent = end - origin;
                    Vector3 leftBranch = leftRotation * leftParent * growthRate + end;
                    Draw(end, leftBranch, angle);
                    yield return new WaitForSeconds(0.1f);

                    //向右分叉
                    Quaternion rightRotation = Quaternion.Euler(new Vector3(0, 0, -angle));
                    Vector3 rightParent = end - origin;
                    Vector3 rightBranch = rightRotation * rightParent * growthRate + end;
                    Draw(end, rightBranch, angle);
                    yield return new WaitForSeconds(0.1f);
                }
            }
            StartCoroutine(enumerator());
        }2.要点

非常简单的两种递归，分别向左进行树干分叉和向右进行树干分叉，每次递归都进行一次生长长度衰减，直到不符合递归条件，结束递归。条件的判断是对比平方长度而不是真实长度，节省了开平方的耗时。如果在分叉角度上将固定的值变为较为随机的值，可以得到更加多样的树木生长结构。


3.L系统算法

上述的树木生成大家可能觉得意犹未尽，因为它过于简单了，在生成的样式上并不能做到多样化，也只能在生长角度等细微之处动动手脚。那么我们能不能用一些方法来生成更加多样的植物呢？答案是肯定的。
L系统，全称为Lindenmayer系统，匈牙利植物学家Aristid Lindenmayer于1968年提出。L系统是一种形式语法，定义字符串生成规则，然后将生成的字符串翻译成几何结构，来模拟复杂植物的发育过程。
1.语句生成

L系统由三部分组成：

• 字母表(Alphabet)：L系统的字母表由任意可以包含的有效字符组成。例如，我们可以说字母表是“ABC”，这意味着 L 系统中任何有效的“句子”（字符串）只能包含这三个字符。
  
• 公理(Axiom)：L系统的初始状态，例如字母表为“ABC”，那么公理可以为“A”，“CBA”，“AB”，只要是字母表内的组合都可以。
  
• 规则(Rules)：规则应用于公理，然后递归，一代又一代的生成新的句子，规则的定义像这样：A→BAC。例如迭代字符串时，遇到A，那么就把这个A替换为BAC。
  

那么我们先来定义一个我们自己的简单L系统：

• 字母表：AB
  
• 公理：A
  
• 规则：（A→AB）（B→BA）
  

公理为A是我们系统的初始状态，所以我们开始迭代：

• 第一次迭代的结果为：AB
  
• 第二次迭代的结果为：ABBA
  
• 第二次迭代的结果为：ABBABAAB
  

以此类推，也就是说随着迭代一直组合这个句子，遇到A就将它替换为AB，遇到B就将它替换为BA。这就是L系统的语句生成原理。
2.语句翻译

语句翻译的意思就是将我们上述生成的句子，让它作用于植物的生长，L系统的正规字母表一般不用我们上述示例中ABCD这种无意义的字符，而是一列有含义的字符，比如下列所示：

• F：画一条线的同时位置向前走
  
• X：不做任何事情
  
• +：右转
  
• -： 左转
  
• [：保存当前位置
  
• ]：恢复以前的位置
  

所以一个正规的L系统就像如下的样子：

• 字母表：F + - [ ]
  
• 公理：F
  
• 规则：F → FF-[-F+F+F]+[+F-F-F]
  
• 迭代次数：4
  
• 树枝的转向角度：22.5°
  

这些要素准备完毕后，我们就可以生成结构更加复杂，更加美丽的植物了：



迭代4次，22.5°，F→FF-[-F+F+F]+[+F-F-F]



迭代7次，25.7°，(X →F[+X][-X]FX) (F →FF)



迭代5次，25.7°，F →F[+F]F[-F]F

4.L系统源码

为了各位阅读文章体验更佳，就不在这里展示代码了，可以移步到GitHub获取，在Unity即刻体验。
5.接下来何去何从

对于L系统和植物生成算法更加详细的讨论，我们可以欣赏Lindenmayer的原著《植物的算法之美》，很幸运这本著作以免费形式供所有感兴趣的人欣赏。

ChuanXin

写的真棒，有机会动手跟着实现一下[爱]