processingの備忘録 -L-system-

こんにちは。

今回は「L-systemで描画してみよう」という題です。

L-systemとは

L-systemは、リンデンマイヤーさんが提唱した、自然物の構造を表現できるアルゴリズムだそうです。
「L-system」という単語は提唱者の名前をとった「Lindenmayer system」の略だとか。

以前に「processingでフラクタル」とかいうシリーズをつくりましたが（結局1つしか記事が無いですが）、L-systemを使えば大抵のフラクタルは表現できるらしいです。

L-systemの中身

それでは、プログラム化していくにあたって具体的にどのような中身なのかをまとめておきます。

おおまかな操作方法としては、ある文字列をある規則に従って変化させていき（ここが自然物の「成長」に相当）、その文字列を一文字ずつに分けたときにその文字に対応する処理を行って図にする、というような流れです。

例えば、ある文字列として「A」があり、「A」を「ABA」に置換する、「B」を「BBB」に置換する、という規則に従って変化させていくと、操作の回数を「世代」と呼ぶとすれば、

初め：A
第一世代：ABA
第二世代：ABABBBABA
第三世代：ABABBBABABBBBBBBBBABABBBABA
第四世代：ABABBBABABBBBBBBBBABABBBABABBBBBBBBBBBBBBBBBBBBBBBBBBBABABBBABABBBBBBBBBABABBBABA
・・・

というように文字列が変化していきます。

ここで、「A」に対して「線を描きながら前進」という処理、「B」に対して「線を描かずに前進」という処理を対応させて図示すると、

このように、フラクタルのひとつである「カントール集合」のような図が描けます。

処理の指定に「前進」という表現を使いましたが、これは「LOGO」というプログラム言語で同様に図を描く際に、亀（turtle）の軌跡として表現したことに由来するそうです。

プログラム化する

文字列の変形

まずは文字列の変形を行うコードを書いてみます。

String current; //今の文字列を保存する場所
int count = 0;

void setup(){
    current = "A"; //初めの文字列は「A」
    println("Generarion " + count + " : " + current);
}

void draw(){
}

void mousePressed(){
    String next = ""; //変化後の文字列をつくっていく場所
    
    for(int i = 0; i < current.length(); i ++){ //文字の数だけ繰り返す
        char c = current.charAt(i); //i番目の文字が
        if(c == 'A'){ //「A」なら
            next += "ABA"; //nextに「ABA」を追加
        }
        else if(c == 'B'){ //「B」なら
            next += "BBB"; //nextに「BBB」を追加
        }
    }
    
    current = next; //つくった文字列を今の文字列とする
    count ++;
    
    println("Generarion " + count + " : " + current);
}

これを実行すると、画面をクリックするたびに世代が上がっていき、文字列が変化していきます。

Generarion 0 : A
Generarion 1 : ABA
Generarion 2 : ABABBBABA
Generarion 3 : ABABBBABABBBBBBBBBABABBBABA
Generarion 4 : ABABBBABABBBBBBBBBABABBBABABBBBBBBBBBBBBBBBBBBBBBBBBBBABABBBABABBBBBBBBBABABBBABA

図に変換

文字列を図に変換するコードを追加します。

String current;
int count = 0;
float len;

void setup(){
    size(500, 200);
  
    current = "A";
    println("Generarion " + count + " : " + current);
    
    len = width; //初めの長さの指定
}

void draw(){
    background(255);
    translate(0, height/2); //原点を左端の真ん中に移す
    render(); //図を描く
}

void mousePressed(){
    String next = "";
    
    for(int i = 0; i < current.length(); i ++){
        char c = current.charAt(i);
        if(c == 'A'){
            next += "ABA";
        }
        else if(c == 'B'){
            next += "BBB";
        }
    }
    
    current = next;
    count ++;
    len /= 3; //長さを1/3倍する
      
    println("Generarion " + count + " : " + current);
}

void render(){ //図を描く関数
    for(int i = 0; i < current.length(); i ++){
        char c = current.charAt(i);
        if(c == 'A'){
            line(0, 0, len, 0); //線を描き
            translate(len, 0); //位置を移動
        }
        else if(c == 'B'){
            translate(len, 0); //位置の移動のみ
        }
    }
}

render()という関数を追加し、文字に対応する処理を実行するようにしています。

実行すると、先に描いたようなカントール集合の絵が描かれたと思います。
ただし一世代分しか描かれないので、並べて描きたければ繰り返すなりすれば良いかと。

別バージョン

先の例では文字に「A」と「B」を使いました。
しかし、よく使われるのは「F」「G」「+」「-」「[」「]」のようで、それぞれが

F：線を描きながら前進  
G：線を描かずに前進  
+：右に回転  
-：左に回転  
[：今の位置・回転の情報を保存  
]：保存した情報を呼び出す  

という処理と対応しています。

これをprocessingでのコードで表すと、

F：line(0, 0, 0, -len); translate(0, -len);  
G：translate(0, -len);  
+：rotate(theta);  
-：rotate(-theta);  
[：pushMatrix();  
]：popMatrix();  

となります。

例えば、以下のコードは文字列「F」から始めて、「F」を「FF+[+F-F]-[-F+F]」に置換するという規則を、その他諸条件の元で適用しています。

String current;
int count = 0;
float len, theta;
float rate;

void setup(){
  size(500, 500);   
    current = "F";
    println("Generarion " + count + " : " + current);
    
    len = height/3;
    theta = radians(30);
    rate = 0.5;
}

void draw(){
    background(255);
    translate(width/2, height);
    render();
}

void mousePressed(){
    String next = "";
    
    for(int i = 0; i < current.length(); i ++){
        char c = current.charAt(i);
        if(c == 'F'){
            next += "FF+[+F-F]-[-F+F]";
        }
        else{
            next += c;
        }
    }
    current = next;
    
    len *= rate;
    count ++;
    
    println("Generarion " + count + " : " + current);
}

void render() {
    for(int i = 0; i < current.length(); i ++){
        char c = current.charAt(i);
        if(c == 'F'){
            line(0, 0, 0, -len);
            translate(0, -len);
        }
        else if(c == 'G'){
            translate(0, -len);
        }
        else if(c == '+'){
            rotate(theta);
        }
        else if(c == '-'){
            rotate(-theta);
        }
        else if(c == '['){
            pushMatrix();
        }
        else if(c == ']'){
            popMatrix();
        }
    }
}

これを実行すると、世代が上がるごとに図のような木が描かれます。

「FF+[+F-F]-[-F+F]」という謎の文字列が出できたので、亀がどのように動いているかを示してみます。

第一世代では図の2番目の形になります。 文字列は「FF+[+F-F]-[-F+F]」となりますが、亀の動きを順に見ていくと、

次の世代では、今描いた線の始点すべてから同じような図が描かれるような文字列となっているため、先の図の3番目のような木になります。

追記（2022/03/15）

初めの文字列や変換規則、亀の初期位置や移動距離・角度などの指定が必要になりますが、このままでは変更時にあちこち変えなければならず、そのときにコード本体を変えてしまうと面倒です。

そこで、setup()の中で指定するだけで条件を変更できるように変えてみました。
（といってもだいたい「Nature of Code」の受け売りですが…）

//L-systemのコード本体

Lsystem lsystem;
Rule[] ruleset;
Turtle turtle;
int count = 0;

void setup(){
    size(500, 500);
    
    //ここを変えれば良い
    lsystem = new Lsystem("F");
    ruleset = new Rule[1];
    ruleset[0] = new Rule('F', "FF+[+F-F]-[-F+F]");
    turtle = new Turtle(width/2, height, height/3, radians(30));
        //(亀の初めのx座標, 亀の初めのy座標, 一辺の長さ, 回転の角度)の順で指定
    turtle.rate = 0.5;
    //
    
    println("Generarion " + count + " : " + lsystem.current);
}

void draw(){
    background(255);
  
    translate(turtle.startx, turtle.starty);
    turtle.render();
    
    noLoop();
}

void mousePressed(){
    lsystem.changeSentence();
    turtle.changeLength();
    
    count ++;
    
    println("Generarion " + count + " : " + lsystem.current);
    
    redraw();
}

//クラス「Lsystem」

class Lsystem{
   String current;
   
   Lsystem(String _c){
       current = _c;
   }
  
   void changeSentence(){
      StringBuffer newSentence = new StringBuffer();
      for(int i = 0; i < current.length(); i ++){
          char c = current.charAt(i);
          String replace = "" + c;
          
          for(int j = 0; j < ruleset.length; j ++){
              if(c == ruleset[j].getCharacter()){
                  replace = ruleset[j].getRule();
                  break;
              }
          }
          newSentence.append(replace);
      }
      current = newSentence.toString();
   }
}

//クラス「Rule」

class Rule{
    char character;
    String RuleOfChange;
  
    Rule(char _c, String _r){
        character = _c;
        RuleOfChange = _r;
    }
    
    char getCharacter(){
        return character;
    }
    
    String getRule(){
        return RuleOfChange;
    }
}

//クラス「Turtle」

class Turtle{
    float startx, starty;
    float len, theta;
    float rate;
  
    Turtle(float _x, float _y, float _l, float _t){
        startx = _x;
        starty = _y;
        len = _l;
        theta = _t;
    }
    
    void render(){
        for(int i = 0; i < lsystem.current.length(); i ++){
            char c = lsystem.current.charAt(i);
            if(c == 'F'){
                line(0, 0, 0, -len);
                translate(0, -len);
            }
            else if(c == 'G'){
                translate(0, -len);
            }
            else if(c == '+'){
                rotate(theta);
            }
            else if(c == '-'){
                rotate(-theta);
            }
            else if(c == '['){
                pushMatrix();
            }
            else if(c == ']'){
                popMatrix();
            }
        }
    }
    
    void changeLength(){
        len *= rate;
    }
}

もっと良いやり方もあるかもしれませんが、とりあえずは動くし条件は変えやすくなったのでこれで良しとします。

以上

余談

今回は「Nature of Code」や「Wikipedia」にあったような「FG+-[]」を用いたL-systemで描画しましたが、絶対守らなければならないわけではありません。
別のサイト（L-System manual）を見ると他にたくさんの文字があるように、自分なりに処理を追加することも可能ですのでより自由度の高いL-systemをつくることもできるかと思います。

また、「Nature of Code」で挙げられているコードはより一般化してあって、初見は難しいですが慣れれば扱いやすいかもしれませんので、そちらをまねてみるのもよいかと思います。

まとめ

以上でL-systemをprocessingに実装することができました。

中身がわかれば「FF+[+F-F]-[-F+F]」とかいう謎の文字列も解読できるので、自分なりのフラクタルをつくることも楽しいと思います。

参考

• The Nature of Code

• 8.5: L-Systems - The Nature of Code - YouTube

• L-system - Wikipedia