L-systemで植物を描く
L-system入門（2013/11/26）の続き。
前回は、L-systemで有名なフラクタルを描きましたが、今回は植物を描いてみます。植物を描くためには前回導入した記号に加えて次の2つの記号を新たに導入します。
[ : 亀の状態（位置と向き）をスタックにプッシュ ] : 亀の状態をスタックからポップ
この2つだけです。スタックからポップするときは、亀の位置が変わりますが、その間は線を引きません。NetLogoで書くと下のようなコードになります。ここで、(xcor, ycor)が亀の位置、headingが亀の向いている方向です。
; タートルの状態をプッシュ
if action = "[" [
let turtle-state (list xcor ycor heading)
set stack lput turtle-state stack
]
; タートルの状態をポップ
if action = "]" [
pen-up
let turtle-state last stack
set stack but-last stack
set xcor item 0 turtle-state
set ycor item 1 turtle-state
set heading item 2 turtle-state
]この2つの記号を使って、植物のような絵を描いてみます！初期文字列はすべてFです。
なかなか美しい植物ではないでしょうか？もっとリアルな植物を描きたいときは、L-systemに葉っぱを付けたり、花をつけたりするコマンドを用意することもできるようです。Lindenmayerさんの本には、下のような花の例が載っています。
この花は、下の初期状態と書き換え規則から生成されるそうです。
L-systemの拡張はたくさん提案されていて、
- 規則を文脈依存にする（書き換え規則の左側で複数文字列OK）
- 複数の規則を確率的に選択する
- 文字列にパラメータを導入する
- 様々な拡張記号を導入する => L-systems: from the Theory to Visual Models of Plants (PDF)
- 3Dで描画する
- 遺伝的アルゴリズムで進化させる
などがあります。例えば、munimuniさんのこの動画は3Dの木の高さと広がりを適合度として遺伝的アルゴリズムで木を進化させているみたいです。けっこう自然な木ができるので驚きました。
他にも「盲目の時計職人」で紹介されているバイオモルフのように適合度を人間が決める人為淘汰を導入するとさらに面白そうです。
- 作者: リチャード・ドーキンス,日高敏隆,中島康裕,遠藤彰,遠藤知二,疋田努
- 出版社/メーカー: 早川書房
- 発売日: 2004/03/24
- メディア: 単行本
- 購入: 10人 クリック: 112回
- この商品を含むブログ (51件) を見る
3DレンダリングソフトのBlenderには、L-systemでリアルな樹木を描くプラグインがあるので今度試してみたいと思います。Skyrimなどの3Dゲームでも普通に使われている技術なんでしょうかね？
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のサンプルプログラム。上のプログラムはこれをベースにしました。
ライフゲームの世界
ニコニコ動画の複雑系コミュニティの発起人のはむくんがライフゲームの世界というとても面白い動画を投稿されています。Twitterでは何度かツイートしてたけど完結したのでブログでも紹介させていただきます。
ライフゲームの世界1
John Horton Conwayが提案したライフゲーム（Conway's Game of Life）の基本的なルールを解説しています。また頻繁に現れる4種の物体（ブロック、蜂の巣、ブリンカー、グライダー）を紹介しています。最後の作品紹介は、P416 60P5H2V0 gunというすさまじいパターンが出てきます。グライダー銃から発射したグライダーたちが滑走路を通ります。グライダーの集合先では、発射された複数のグライダーが合体して宇宙船が組み立てられます。
ライフゲームの世界2
いろんな振動子（パルサー、タンブラー、銀河）が鑑賞できます。作品紹介では大量の振動子が勢揃いします。周期が40894なんてとんでもないパターンもあります。BGMと相まって圧巻です。
ライフゲームの世界3
ライフゲームの歴史的側面を解説しています。無限増殖するパターン発見への道のりです。Rペントミノ、どんぐり、宇宙船、シャトルの発見へと続いて次回へ。作品紹介では、移動物体であるいろんな宇宙船が紹介されています。
ライフゲームの世界4
MITのBill Gosperらが無限増殖するパターン、グライダー銃をついに発見。グライダーを無限に発射し続けるパターン。こんなのよく見つけたなぁ。作品紹介では、複数の物体を衝突して新たな物体を合成する研究が紹介されています。非常に美しいです。新たな生命が生まれるみたいな感じ。
ライフゲームの世界5
休憩編ということで視聴者のコメントに回答。この動画では、Gollyというライフゲームプログラムを使っているとのことです。動画で紹介しているパターンも付属しているので自分で試してみたい！iPad版アプリも公開されています。他にもライフゲームの世界2の大量の振動子群にグライダーをぶつける実験（笑）とか。世界が崩壊していくぅ。あとただの直線からフラクタルのシェルピンスキーのギャスケットができるのもすごい。ライフゲームの宇宙は奥が深すぎる・・・
ライフゲームの世界6
グライダー13機からグライダー銃を合成する発見。また、もう1つの無限増殖パターン、物体をまき散らしながら移動していくシュッポシュッポ列車の発見、さらに移動するグライダー銃の発見。Pufferは見ていて気持ちがいい。
ライフゲームの世界7
無限増殖装置を無限増殖するパターンBreederの紹介。GOLLYって文字を生成するパターンとか面白かった。
ライフゲームの世界8
ライフゲームのパターンがチューリングマシンと同等の機能を持つことの証明。ライフゲームでライフゲームをシミュレートするOTCA metapixelの紹介。ここまで奥深いとは呆然としてしまった。
ライフゲームの世界 最終回
いよいよ最終回！ライフゲームをより一般化したセルオートマトン上でのさまざまな自己複製機械の紹介。フォン・ノイマンの自己複製機械が実際に動いているところを始めてみました。2010年になってライフゲーム上でも自己複製機械が発見されたとのこと。
非常に面白い動画で一気に見てしまいました！最近までいろんな発見が続いてたんですね。非常に単純な規則でここまで壮大な宇宙を創り出せるライフゲームはやはりすごかった。
関連リンク
- ライフゲーム - Wikipedia
- LifeWiki
- Conway's Game of Life
- Golly - ライフゲームシミュレータ
- Golly - iPad版のGolly
- Javaで作ったライフゲーム（2004/12/25）
- Pythonで作ったライフゲーム（2008/9/14）
- セルオートマトン（2012/1/13）
- ラングトンの自己複製オートマトン（2012/1/21）
