L-system

L-system（エルシステム、Lindenmayer system）は形式文法の一種で、植物の成長プロセスを初めとした様々な自然物の構造を記述・表現できるアルゴリズムである。自然物の他にも、反復関数系（Iterated Function System; IFS）のようないわゆる自己相似図形やフラクタル図形を生成する場合にも用いられる。L-System は1968年、ハンガリーユトレヒト大学の理論生物学者にして植物学者であったアリステッド・リンデンマイヤー（Aristid Lindenmayer）により提唱され、発展した。

起源

L-system により生成された3次元の樹木モデル。

生物学者としてリンデンマイヤーは、酵母や糸状菌、そして藍藻類の Anabaena catenula のような藻類など、様々な生物の成長パターンを研究していた。もともと L-system は、そのような単細胞生物もしくは体制の単純な多細胞生物の成長様式や、植物細胞における近隣の細胞の相互関係を記述するために開発されたものであった。後に L-system はより高等な植物の形態や、複雑な分岐構造を記述する為のツールとして発展を遂げるのである。

L-system の構造

L-system の基本は再帰性で、自己相似図形やフラクタル図形のような形状を簡単に記述する事ができる。植物やその他の見た目が自然な生物構造も同様に簡単に定義でき、再帰呼出の回数を増やす事であたかも構造が「成長」し、複雑化していくように見える。L-system は人工生命の生成にもよく用いられる。

L-system の文法は en:Unrestricted grammar のものに似ている（→ チョムスキー階層）。現在では、以下のような四ツ組によって定義されることが多い。

G = {V, S, ω, P},

各要素は、

• V（文字）： 置換規則（後述の P ）により順次置き換えられてゆく変数の集合。L-system の再帰的な反復計算が進んでいく時に、物として「成長」してゆくのはこの V の要素からなる文字列である。
• S ： 計算が進んでも変化しない定数の集合。
• ω ： システムの初期状態を示すV の要素からなる文字列。
• P ： V を変化させてゆく置換規則の集合。各要素は、例えば (A → AB) のように、置換前（置換対象）の文字列と置換後の文字列の組み合わせにより記述される。

置換規則 P において、置換対象が単独の文字のみである場合、L-system は文脈自由言語である。一方、置換規則が近隣の文字との相互関係まで考慮するものである場合、L-system は文脈依存言語である。また、置換規則Pが各文字に対して毎回確実に適用される時、L-system は「決定論的」であると言われ、D0L-system（deterministic context-free L-system ）などと呼ばれる。逆に、置換規則の適用が確率に左右される場合には「確率論的」L-system と呼ばれる。

L-system をグラフィックスに応用する場合、L-system が生成する文字列を、何らかの形で画面上の図形に変換しなければならない。例えば FractInt というプログラム（文末の外部リンク参照）では、LOGOのようなタートルを利用してグラフィックスを生成する。つまりプログラムが L-system の文字列をタートルの制御命令に翻訳し、図形を描画させている。

L-systems の実例

例1：藻類

L-system 誕生の契機となった、藻類の成長を記述する例。

V ： A, B

S ： なし

ω： A

P ： (A → AB), (B → A)

順次計算してゆくと、文字列は以下のように成長する。

n = 0 ： A

n = 1 ： AB

n = 2 ： ABA

n = 3 ： ABAAB

n = 4 ： ABAABABA

この例では、置換規則 P において、(A → AB) は不均等な細胞分裂により通常の細胞Aと未熟な細胞Bが生じる事を表し、(B → A) は未熟な細胞Bが成長して分裂可能な細胞 A へと成熟する事を表している。この文字列を図形化（例えば A を分枝型の細胞、B を小型の細胞の図などにそれぞれ置き換える）する事で、あたかも寒天培地上に展開した藻類のコロニーのような絵を得る事ができる。

例2：フィボナッチ数列

V ： A, B

S ： なし

ω： A

P ： (A → B), (B → AB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： B

n = 2 ： AB

n = 3 ： BAB

n = 4 ： ABBAB

n = 5 ： BABABBAB

n = 6 ： ABBABBABABBAB

n = 7 ： BABABBABABBABBABABBAB

この文字列の各文字数を n=0 から順に数えると、フィボナッチ数列（1 1 2 3 5 8 13 21 34 55 89 …）となっている。この例では文字列の内容は問わず長さだけに注目しているので、例えば置換規則の (B → AB) を (B → BA) で置き換えても同様の数列を得る事ができる。

例3：カントール集合

V ： A, B

S ： なし

ω： A

P ： (A → ABA), (B → BBB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： ABA

n = 2 ： ABABBBABA

n = 3 ： ABABBBABABBBBBBBBBABABBBABA

この文字列の A を線分、B を抜き取られた部分に置き換えると下のような図が得られる。置換規則の (A → ABA) は線分（閉区間）を3等分して中央を抜き取る操作に相当する。(B → BBB) は一度取り除かれた区間が戻らない事を意味する。詳しくはカントール集合（Cantor set）を参照

例4：コッホ曲線

直角で構成されるコッホ曲線の描画例。

V ： F

S ： +, -;

ω： F

P ： (F → F+F-F-F+F)

上記において、F はタートルによる直線の描画、+ はタートルを左へ90°回転、同じく- は右へ90°回転する事を意味する。これを順次計算すると、以下のような図形が得られる。

n = 0 ：

F

n = 1 ：

F+F-F-F+F

n = 2 ：

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

n = 3 ：

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

例5：ペンローズ・タイル

L-system を利用して、下図のような平面充填模様を生成する事もできる。詳しくはペンローズ・タイル及びロジャー・ペンローズを参照。

例6：シェルピンスキーの三角形

L-system でシェルピンスキーの三角形を作図する例。

V ： A, B

S ： +, -

ω： A

P ： (A → B−A−B), (B → A+B+A)

上記において、A 及び B はタートルによる直線の描画、+ はタートルを左へ60°回転、同じく- は右へ60°回転する事を意味する。同様の図形を描く置換規則は他にもあるが、この規則の場合、タートルは三角形の左下から描き始める事になる。

n = 2, n = 4, n = 6, n = 8 の時にそれぞれ描画される図形。n → ∞ の時、シェルピンスキーの三角形に等しくなる。

例7：コッホ曲線の変形

通常のコッホ曲線に、周期的な角度の変更を加えながら描画したフラクタル図形の一種。

その他の L-system を利用したグラフィックス

• 地衣類、あるいは蘚苔類：

• 草本の作図例：

• 木本の作図例：

• 原生動物など：

（参考）ヘッケルによる放散虫のスケッチ。

既知の問題

L-system に関する問題は数多く存在するが、その最たるものは L-system を逆に辿る事が困難であるというものである。具体的には、ある構造が示された時に、その構造を生成するパラメータや置換規則を見つける事が難しい。これは自然物のような複雑な（反復回数の多い）過程を経て形成された図形に顕著である。

L-system の種類

実数列における L-system：

• Thue-Morse sequence

平面における L-system：

• 平面充填曲線・図形（Space-filling curve）ほか：
  • ヒルベルト曲線（Hilbert curve）
  • ペアノ曲線（Peano's curves）
  • コーラム（Kolam）
  • レヴィC曲線（Lévy C curve）
  • ドラゴン曲線（Dragon curve）
  • ペンローズ・タイル（Penrose tiling）

空間における L-system：

• 自然物
  • 植物
    • 木本
    • 草本
    • シダ植物
  • 藻類・原生動物
    • 放散虫

確率的L-system

確率的 (Stochastic) L-systemは、L-systemを拡張して確率的に分岐できるようにしたものである。確率的L-systemには標準が無いため、ソフトウェアによって文法が異なる。

以下は確率的な分岐を行うL-systemの実装毎の例である。

Tong Linの実装 (1996)	Houdini (L-system SOP)	Cinema 4D (MoSplineのTurtle)
A=(0.5)FA A=(0.25)+F-A A=(0.25)-F+A	A=FA:0.5 A=+F-A:0.25 A=-F+A:0.25	A:(rnd(1)<0.5)=FA A:(rnd(1)<0.75)=+F-A A:(rnd(1)>0.75)=-F+A

文脈依存L-system

文脈依存 (Context-sensitive) L-systemは、L-systemを拡張したものであり、パターンマッチングによって文脈に依存した分岐が可能となっている。文脈依存L-systemを実装したものとしては、Tong Linの実装などが存在する。

関連項目

• フラクタル
  • 反復関数系
  • フラクタル幾何
    • シェルピンスキーのギャスケット
    • コッホ曲線
• 先端成長

参考文献

• Przemyslaw Prusinkiewicz - en:The Algorithmic Beauty of Plants PDF version available here for free

外部リンク

• David J. Wright's article on L-systems
• Algorithmic Botany at the University of Calgary
• Branching: L-system Tree L-systemを用いて木の生長をシミュレートするJavaアプレット（英語）
• Fractint L-System True Fractals
• "An introduction to Lindenmayer systems", by Gabriela Ochoa. Brief description of L-systems and how the strings they generate can be interpreted by computer.
• "powerPlant" an open-source landscape modelling software
• Fractint home page

• "L-system in Falk arts" The FORMA commurative issue of the conference ISKFA06
• A simple L-systems generator (Windows)
• Lyndyhop: another simple L-systems generator (Windows & Mac)
• An evolutionary L-systems generator (anyos*)
• L-systems gallery – a tribute to Fractint
• "LsystemComposition". Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music.
• eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.
• A JAVA applet with many fractal figures generated by L-systems.
• L-systems in Architecture; genetic housing.
• L-systems in Plant Growth,Simulation and Visualization (PlantVR).
• Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms.
• LSys/JS - Interactive L-System interpreter using the Canvas HTML element.