<div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even"> <p>起始元（Initiator）與生成元（Generator）是描繪碎形的方式之一，若想以簡約語言來記錄碎形生成過程，我們可以採用L-system制定正式文法（Formal grammar），而這也便於使用機器處理這類碎形語言，令碎形的描述與繪製過程通用化。</p>
<p><span style="font-size:28px;"><strong>碎形圖案</strong></span></p>
<p>在繪製碎形圖案時，海龜繪圖是經常運用的方法之一，因為透過海龜的操作，開發者可以免除複雜的數學計算，只要透過程式碼操作海龜相關動作，命令它前進、轉彎等，之後就可以繪製出複雜的碎形圖案。</p>
<p>儘管使用的程式語言或程式庫不同，然而，我們應該還是可以察覺到：在繪製各種碎形時，看似不同的程式進行流程，卻又似乎隱含著某種流程的相似性，因此，我們可否將這類流程抽出，令其通用化，之後只要撰寫相異部份的程式碼就可以了？</p>
<p>若試著採用Koch發展出來的「起始元與生成元」，透過這種碎形描繪方式來實現程式碼，我們就可以更進一步發現：流程中隱含的相似性，來自於碎形的自相似性；在起始元與生成元方法中，起始元是初始圖案，生成元會「取代」前次迭代的某圖案單元，而不同的圖案單元則會有各自對應的生成元。</p>
<p>例如，超始元定義為實心三角形，而實心三角形的生成元是將之畫分為四個小三角形，中間三角形為空，其餘三角形實心，在每次迭代時，將先前全部的實心三角形以生成元取代，就會生成自相似的謝爾賓斯基三角形（Sierpiński triangle）。</p>
<p>根據起始元與生成元的取代過程，顯而易見地，生成元就是自相似性的來源；只不過方才描述超始元、生成元的方式過於冗長了，可否有正式、精確些的描述方式？</p>
<p><span style="font-size:28px;"><strong>L-system規範碎形構造</strong></span></p>
<p>在先前<a href="https://www.ithome.com.tw/voice/110732" target="_blank">專欄〈遞迴、碎形與數學〉</a>談過「1,1,1,2,1,2,3,1,2,4,3,1,5,2,4,6...」這串像密碼般的數字，因為數列中的子數列具有自我相似性，是一種碎形數列；談到密碼，人們常稱費式數列是大自然的密碼，因為費式數列與許多生物的成長規律有關，而Fn = Fn-1 + Fn-2是人們熟知的描述方式。</p>
<p>其實，換個方式來描述費式數列，也可以視其為碎形數列。而這種方式是給個起始元A，以及兩個生成元A→AB、B→A，在首次迭代時，根據A→AB，A被生成元AB取代，接著第二次迭代時就會是ABA（因為AB取代前次的A，而A取代前次的B），三次迭代時，就會是ABAAB，接著是ABAABABA、ABAABABAABAAB……數數看每次迭代的符號數量，會發現是1,2,3,5,8,13. ……這不就是費式數列！（因為是從起始元A開始，也就只有一個1作為數列開頭）</p>
<p>若將A看為成年兔子，B視為未成年兔，A→AB就是每個月成年兔會生出一隻未成年兔（而成為兩隻），B→A表示在未成年兔下個月成長為成年兔，A、A→AB、B→A就描述了費式數列介紹時常見的兔生兔範例了。想知道某個月成年兔、未成年兔各是幾隻嗎？數數看符號中A與B的數列就知道了，例如，某月的ABAABABA，代表有五隻成年、三隻未成年兔。</p>
<p>A、A→AB、B→A實際上是生物學家Lindenmayer研究海藻生長時，為了以符號描述其成長模型而提出，後來這種符號描述方式正式規範為L-system（L代表Lindenmayer），而成為一套文法描述方式，L-system的定義為G={V,ω,P}，G代表文法，V是符號集合，ω是起始元，P是衍生規則，以方才的範例來說，V是{A, B}，ω是A，P是{A→AB, B→A}。</p>
<p>若將零到一的線予以三等分，去掉中間的線，左右的線依同樣方式，持續區分下去，得到的會是康托爾集（Cantor set），這是個無限大的集合，然而，這個集合中又什麼都沒有。假如康托爾集用L-system來描述的話，起始元是A，衍生規則是A→ABA，B→BBB。</p>
<p>如果A代表往前移動畫線，B代表往前移動不畫線，在每次迭代時畫出的圖案，會是有趣的紋身圖案（可參考維基百科〈<a href="https://en.wikipedia.org/wiki/Cantor_set" target="_blank">康托爾集</a>〉條目的圖片）。</p>
<p><span style="font-size:28px;"><strong>L-system與海龜繪圖</strong></span></p>
<p>方才建立碎形圖案時採用的起始元與生成元方法，與L-system其實是同種方式，而在我談康托爾集時，曾說到A、B可代表前進時畫線與否，就像在命令海龜，實際上以L-system來描述碎形圖案的建構，是常見的應用。</p>
<p>例如，起始元F，衍生規則F→F-F++F-F，描述的就是科赫（Koch）曲線的生成文法，因為F代表命令海龜前進並繪線，+表示左轉，-表示右轉，若前進長度固定為1，轉動角度固定為60度，F-F++F-F就是一次科赫曲線，F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F就是二次科赫曲線，依此類推。</p>
<p>在L-system結合海龜繪圖時有幾個常用符號，各對應至海龜的指令，除了方才談到的F+-之外，還有f為前進不繪線，|轉動180度，[將目前海龜狀態置入堆疊，]將海龜狀態從堆疊中取出等。</p>
<p>光這幾個符號，就可以創造諸多L-system文法，建構許多碎形圖案，我在〈<a href="https://github.com/JustinSDK/dotSCAD/blob/master/examples/turtle/lsystem2_collection.scad" target="_blank">lsystem2_collection</a>〉收集一些規則，有興趣者可以參考。</p>
<p>我們也可以將其擴充至3D版的海龜繪圖，最基本的就是增加&（抬頭）、^（低頭）、\（左滾）、/（右滾）等符號，我在〈<a href="https://github.com/JustinSDK/dotSCAD/blob/master/examples/turtle/lsystem3_collection.scad" target="_blank">lsystem3_collection</a>〉也收集了幾個3D版的L-system。</p>
<p>從海龜的角度來看，F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F就是語言，畢竟它看懂並遵照指示繪圖，若以方才的F+-|[]符號構造L-system文法規則，生成的語言是屬於下推自動機（PushDown Automaton），因為其具有堆疊結構，也就是說，若想實現可指定規則並繪圖的L-system程式庫，首先要依規則及迭代次數生成程式碼（像是F-F++F-F），接著剖析程式碼並執行。</p>
<p>回到一開始的話題「可否將這類流程抽取出來，令其通用化，之後只要撰寫相異部份的程式碼就可以了呢？」若我們只是根據相異部份程式碼來執行，那麼，就是方才談到的「剖析程式碼並執行」的階段。</p>
<p><span style="font-size:28px;"><strong>試著實現L-system</strong></span></p>
<p>既然L-system本身就是文法系統，文法如果越豐富，功能就會越強。常見的一種變化，是可設定每次迭代時，是否採用某規則的機率，而這常用於模擬植物生成時既有規律、又具備隨機而產生的多樣性，此時的L-system被擴充為Stochastic L-system，也就是隨機L-system。</p>
<p>方才所談到的做法，都是上下文無關（Context-free）的L-system，也可以進一步增加文法至上下文相關。有興趣的話，我們可參考《The Algorithmic Beauty of Plants》第一章〈Graphical modeling using L-systems〉，當中從基本的L-system談到上下文相關的L-system，是個非常詳盡的介紹。</p>
<p>整體而言，我們可以試著自行實現L-system並結合海龜繪圖指令，這並不難，而在這個過程中，能夠體會到構造簡單語言、碎形創作等樂趣。若要從簡單的範例開始，可以參考《用Python做科學計算》的〈<a href="https://wizardforcel.gitbooks.io/hyry-studio-scipy/content/37.html" target="_blank">繪製L-System的碎形圖</a>〉。</p>
</div></div></div><div class="field field-name-field-tags field-type-taxonomy-term-reference field-label-above"><div class="field-label">Tags: </div><div class="field-items"><div class="field-item even"><a href="/tags/%E7%A2%8E%E5%BD%A2">碎形</a></div><div class="field-item odd"><a href="/tags/l-system">l-system</a></div><div class="field-item even"><a href="/tags/%E7%A8%8B%E5%BC%8F%E5%AD%B8%E7%BF%92">程式學習</a></div><div class="field-item odd"><a href="/tags/%E6%9E%97%E4%BF%A1%E8%89%AF">林信良</a></div><div class="field-item even"><a href="/tags/%E6%B5%B7%E9%BE%9C%E7%B9%AA%E5%9C%96">海龜繪圖</a></div></div></div>
