L-system入門
今回は、植物の成長をモデル化したLindenmayer system、略してL-systemの実験をしてみます。ライフゲームと同じく非常に単純な規則から複雑な形状が発生する複雑系の興味深い例です。
L-system
L-systemは、初期文字列と書き換え規則から構成されます。たとえば、
初期文字列：b 書き換え規則1：a -> ab 書き換え規則2 : b -> a
書き換え規則は、->の左側を右側に書き換えろという意味です。すごく簡単でしょ？この書き換え規則を初期文字列に適用します。この例の場合、
b -> a -> ab -> aba -> abaab -> abaababa -> ...
のような感じで書き換えていきます。ポイントは、現在の文字列のすべての文字に対して書き換え規則を適用することです。書き換え規則の左側が必ず1文字（文脈自由）でかつ決定論的に書き換えていくL-systemをDeterministic Context Free (DOL) Systemsと呼びます。
Turtle Graphics
L-systemを画像として描画する方法がTurtle Graphicsです。L-systemの各文字に描画コマンドを割当て、前の文字から順番に「亀」を動かしていくことでさまざまな模様を描けます。何で亀なんだ・・・という感じがしますが、元となったLogo言語に由来するようです。具体例で見てみるとすごく簡単です。
たとえば、
初期文字列: F-F-F-F 書き換え規則: F -> F-F+F+FF-F-F+F
のようなL-systemを考えます。使われている文字は、F、-、+の三種類です。これらの各文字に対して次のような描画コマンドを割り当てます（fは後で使います）。
F : 亀の通り道に線を描きながら前方に距離dだけ移動させる f : 線を描かずに亀を前方に距離dだけ移動させる + : 亀の向きを左にδ度だけ回転させる - : 亀の向きを右にδ度だけ回転させる
ここで、dとδはパラメータで自由に設定できます。たとえば、dを1マス、δを90度として、FFF-FF-F-F+F+FF-F-FFFという文字列を描画すると下のような形になります。
（The Algorithmic Beauty of Plants, p.7より引用）
砂浜の上の亀のように亀が通った道筋で絵を描くわけですね。というわけでいろいろな例を試してみたいと思います！
コッホ曲線
後述するNetLogoのプログラムを実行した様子を表しています。initial-stringが初期文字列を表します。rule1とrule2が書き換え規則です。2つまで指定できますが、1つの場合は片方を空にしておきます。step-sizeが移動距離d、angle-incrementが回転角度δのパラメータです。(initial-x, initial-y)は亀の初期位置です。初期状態では亀は上方向（0度）を向いていると仮定しています。画像の上にあるticksは書き換え規則を適用した回数を表しています。この形は有名なフラクタルコッホ曲線（Koch Curve）です。
これはコッホ島（Koch island）です。
同一初期文字列からのさまざまな派生
書き換え規則を変えることで同一の初期文字列からさまざまな形状へ派生していきます。下の4枚はすべて初期文字列がF-F-F-Fですが、まったく違う図形へ成長していきます。
ドラゴン曲線
文字列や規則は複数指定することもできます。下の例では、A、Bという二つの文字を導入しています。ただ、どちらの文字もFと同じ意味で「描画しながら前へ進め」というコマンドです。
この図形はドラゴン曲線（Dragon curve）と呼ばれるフラクタルです。
これもドラゴン曲線ですが、さっきのと少し違いますね。ここで、XとYは「何もしないコマンド」です。
NetLogoプログラム
上のNetLogoプログラムです。NetLogoをインストールして、下のファイルをダブルクリックするだけでGUIが立ち上がります。Mac版のNetLogoだと日本語コメントが使えたのですが、Windows版は日本語が使えませんでした。もしかしたら文字化けするかもしれません。
NetLogoはTurtle Graphicsに基づいているため、L-systemはわりと簡単に書けます。ただ、構文が独特なので慣れないとかなり戸惑いますね。NetLogoは、Complexity Explorer（2013/10/21）でも紹介したので興味があったら読んでください。
植物はどうなった・・・
L-systemでいろんなフラクタルが描けるのは面白いですね！ただ実はこれだけでは肝心の植物を描くことができません。植物を描くには、新たにスタックへのプッシュとポップを表す記号を導入する必要があります（上のプログラムではすでに入ってますが・・・）。というわけでL-systemで植物を描く方法は次回（2013/11/26）取り上げたいと思います。
参考文献
- Algorithmic Botany - Lindenmayerさんの本「The Algorithmic Beauty of Plants」が無料で公開されています。Publicationsから。
- An Introduction to Lindenmayer Systems - L-systemの解説。上の本の一番重要なところを抜粋した感じ。
- L-Systems Turtle Graphics Renderer - HTML5 Canvas - by Kevin Roast - HTML5で実装したL-system。ブラウザ上で気軽に試せます。
- L-systems and Beyond - まだ読んでないけどL-systemの解説みたい。
- mihi-tr / complexity-explorer - Complexity Explorer（2013/10/21）のForumで公開されていたNetLogoによるL-systemのサンプルプログラム。上のプログラムはこれをベースにしました。
