L-system

形式文法とアルゴリズム

---

以前の投稿に続き，今回はアリステッド・リンデンマイヤーという人が提唱したL-systemというもののシミュレーションを行ってみたい．これは再帰的に文字列を書き換えることで、自己相似性やフラクタル的な複雑なパターンを簡潔に表現できる．

import math
import matplotlib.pyplot as plt
import imageio
import io
import numpy as np

# 文字列の次世代を生成する関数
def generate_next_string(current, rules):
    next_string = ""
    for ch in current:
        if ch in rules:
            next_string += rules[ch]
        else:
            next_string += ch
    return next_string

# タートル解釈を行い、線分のリストを返す関数
def interpret_lsystem(instructions, angle_deg, line_length):
    x, y = 0, 0
    angle = 90  # 初期角度：上向き
    segments = []
    stack = []
    for cmd in instructions:
        if cmd == 'F':
            new_x = x + line_length * math.cos(math.radians(angle))
            new_y = y + line_length * math.sin(math.radians(angle))
            segments.append(((x, y), (new_x, new_y)))
            x, y = new_x, new_y
        elif cmd == 'G':
            x += line_length * math.cos(math.radians(angle))
            y += line_length * math.sin(math.radians(angle))
        elif cmd == '+':
            angle += angle_deg
        elif cmd == '-':
            angle -= angle_deg
        elif cmd == '[':
            stack.append((x, y, angle))
        elif cmd == ']':
            x, y, angle = stack.pop()
        # 他の文字は無視
    return segments

# 得られた線分を描画し、画像（numpy配列）として返す関数
def plot_segments(segments, margin=10):
    # segmentsが空の場合は背景だけの画像を作成
    if not segments:
        fig, ax = plt.subplots(figsize=(6,6))
        ax.set_aspect('equal')
        ax.axis('off')
        ax.set_xlim(-margin, margin)
        ax.set_ylim(-margin, margin)
        buf = io.BytesIO()
        plt.savefig(buf, format='png', bbox_inches='tight', pad_inches=0)
        buf.seek(0)
        img = imageio.v2.imread(buf)
        plt.close(fig)
        return img
    
    xs, ys = [], []
    for seg in segments:
        (x1, y1), (x2, y2) = seg
        xs.extend([x1, x2])
        ys.extend([y1, y2])
    xmin, xmax = min(xs), max(xs)
    ymin, ymax = min(ys), max(ys)
    
    fig, ax = plt.subplots(figsize=(6,6))
    for seg in segments:
        (x1, y1), (x2, y2) = seg
        ax.plot([x1, x2], [y1, y2], color='black', linewidth=1)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_xlim(xmin - margin, xmax + margin)
    ax.set_ylim(ymin - margin, ymax + margin)
    
    buf = io.BytesIO()
    plt.savefig(buf, format='png', bbox_inches='tight', pad_inches=0)
    buf.seek(0)
    img = imageio.v2.imread(buf)
    plt.close(fig)
    return img

# 各フレームのサイズを統一するためにパディングする関数
def pad_frames(frames):
    max_h = max(frame.shape[0] for frame in frames)
    max_w = max(frame.shape[1] for frame in frames)
    padded_frames = []
    for frame in frames:
        h, w = frame.shape[:2]
        pad_bottom = max_h - h
        pad_right = max_w - w
        # 画像の下部と右側に余白（白背景）を追加
        padded = np.pad(frame, ((0, pad_bottom), (0, pad_right), (0, 0)),
                        mode='constant', constant_values=255)
        padded_frames.append(padded)
    return padded_frames

# L-systemの各世代の描画を行い、GIFを出力する関数
def lsystem_to_gif(axiom, rules, angle_deg, initial_length, iterations, scale_factor, gif_filename):
    frames = []
    current_string = axiom
    line_length = initial_length
    for i in range(iterations + 1):
        print(f"Iteration {i}, string length: {len(current_string)}")
        segments = interpret_lsystem(current_string, angle_deg, line_length)
        img = plot_segments(segments)
        frames.append(img)
        current_string = generate_next_string(current_string, rules)
        line_length *= scale_factor  # 線分長さの縮小
    # すべてのフレームのサイズを統一するためにパディング
    frames = pad_frames(frames)
    imageio.mimsave(gif_filename, frames, duration=0.5)
    print("GIF saved as", gif_filename)

# メイン処理
if __name__ == "__main__":
    # Fractal Plant の例
    # 公理：X
    # 規則：
    #   X -> F-[[X]+X]+F[+FX]-X
    #   F -> FF
    # 回転角：25°
    axiom = "X"
    rules = {
        "X": "F-[[X]+X]+F[+FX]-X",
        "F": "FF"
    }
    angle_deg = 25
    initial_length = 100  # 初期線分長さ
    iterations = 5        # 世代数（0世代～5世代）
    scale_factor = 0.5    # 各世代ごとの線分長さの縮小率
    gif_filename = "lsystem_simulation.gif"
    
    lsystem_to_gif(axiom, rules, angle_deg, initial_length, iterations, scale_factor, gif_filename)

参考文献

• An Introduction to Lindenmayer Systems https://www-archiv.fdm.uni-hamburg.de/b-online/e28_3/lsys.html