The Nature of Code閱讀心得與Python實作：8.5 L-systems

L-system是Lindenmayer system的簡稱，是由匈牙利生物學家Aristid Lindenmayer在1968年所開發出來的。Lindenmayer開發L-system的主要目的，是要建立可用於描述植物在生長發展中，其細胞交互作用行為的數學模型。時至今日，L-system也用於描述整株植物的發展型態。

這裡要稍微離題一下。原書寫說Lindenmayer是植物學家，但維基百科上寫的是生物學家，而在《The Algorithmic Beauty of Plants》這本Lindenmayer是共同作者的書中，也提到Lindenmayer是生物學家。

• 字母表(alphabet)：內含所有可以被使用的有效字元；這些字元可以被用來組成字串，形成所謂的「句子」。因此，這個L-system任何有效的「句子」中，就只會看到在字母表中所列出的字元。例如，如果字母表內含有ABC$這三個字元，那就表示這個L-system中的「句子」，就只能由ABC這三個字元來排列組合而成。
• 公理(axiom)：描述系統初始狀態的句子。例如，如果字母表中含有ABC這三個字元，那可能的公理，就可以是AAA、B、ACBAB等句子。根據Yahoo奇摩英英字典，「axiom」這個字的意思是

a statement or proposition on which an abstractly defined structure is based

    從這個解釋可以更清楚地看出來，「公理」在L-system中所扮演的角色。

• 規則(rules)：** 用來描述如何變換句子的製作規則。每條規則會包含稱為前身(predecessor)及接替者(successor)的兩個L-system句子；通常記為
  前身⟶接替者
  例如，規則A⟶AB代表當句子中有A，也就是前身出現時，在下一世代中，就必須用AB，也就是接替者，來取代它。利用這些製作規則，可以從公理中產生新的句子；針對這些新的句子，又可以利用這些製作規則產生新的句子。如此這般遞迴地利用這些製作規則，就可以一代一代地產生新的句子。

接下來就來看看Lindenmayer最初用來描述水藻生長的L-system。這個L-system其實挺簡單的，它長這樣：

字母表：A、B  
公理：A  
規則：A⟶AB、B⟶A

依照第一條規則，公理，也就是A，會轉變成AB。接著針對AB進行轉換。依照第一條規則，A會轉變成AB；而依照第二條規則，B則轉變成為A。所以，最後會把AB轉變成為ABA。這個轉換的過程可以一直持續下去，直到滿意為止。下面這張圖所顯示的，是轉換到第四代時所得到的結果。

L-system產生樣式的方式非常簡單，那程式要怎麼寫呢？其實挺容易的，關鍵就在用一個dictionary來存放所有的規則，像這樣：

rules = {'A': 'AB', 'B': 'A'}

如果要轉換的字串是放在string這個變數中，那只要一行就可以完成轉換了：

''.join([rules[char] for char in string])

下面這個例子是轉換到第7代時，每一代所得到的結果。

Example 8.8: Simple L-system Sentence Generation

# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 8.8: Simple L-system Sentence Generation") 

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 200
screen = pygame.display.set_mode(screen_size)

FPS = 30
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

axiom = 'AB'
rules = {'A': 'AB', 'B': 'A'}

# 世代數量
generation = 8

sentences = [axiom]
for i in range(generation):
    sentence = ''.join([rules[char] for char in sentences[i]])
    sentences.append(sentence)
    
font = pygame.font.SysFont('courier', 16)
for i in range(generation):
    string = str(i) + ': ' + sentences[i]
    text = font.render(string, True, (0, 0, 0))
    screen.blit(text, (10, 10+20*i))
 
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)

L-system就這樣而已，挺簡單的。然後呢？從L-system得到的，就只是一大串的字串而已，那跟碎形的圖案有什麼關聯？其實，關鍵就在於，在L-system的字母表中的那些字元，就是畫圖的指令；只要依照這些指令把圖畫出來，就是漂亮的碎形圖案了。來看個簡單的例子會比較清楚要怎麼做。如果有個L-system長這樣：

字母表：A、B
公理：A
規則：A⟶ABA、B⟶BBB

這個L-system前幾世代的輸出為

世代0：A
世代1：ABA
世代2：ABABBBABA}
世代3：ABABBBABABBBBBBBBBABABBBABA

如果規定A和B所要執行的畫圖動作分別為

A：向前移動並畫線
B：向前移動但不畫線

那每一代所產生的句子，就可以畫出這樣的圖案：

這個圖案，其實就是先前畫過的Cantor集。

通常，我們會使用稱為烏龜繪圖(turtle graphics)的架構來設計L-system字母表中各字元所代表的繪圖動作。烏龜繪圖源自用來教小孩子寫程式的Logo程式語言，在Python中可以用來畫圖的turtle module，也是源自於此。在L-system中，使用烏龜繪圖架構所設計的繪圖動作，通常會長這樣：

F：向前移動一段距離並畫線
f：向前移動一段距離但不畫線
+：向左轉一個角度
-：向右轉一個角度
[：將目前的狀態push進堆疊中
]：由堆疊中pop出狀態來重置目前的狀態

要注意的是，這些字元所代表的繪圖動作並非絕對的，可依照個人喜好或需求來定義。例如，跟上面常見的設計有所不同，原書所採用的，是另一種也很常見的設計：用G來代表向前移動一段距離但不畫線；用+代表向右轉一個角度，而-則代表向左轉一個角度。

接下來，就來將這一些寫成程式。程式包含兩個類別，一個是用來產生L-system句子的LSystem類別，另一個則是用來進行烏龜繪圖的Turtle類別。

LSystem類別長這樣：

class LSystem:
    def __init__(self, axiom, rules):
        self.sentence = axiom
        self.rules = rules
        
    def generate(self):
        self.sentence = ''.join([rules[char] if char in rules else char 
                                 for char in self.sentence])        

這個類別長得很單純，重點在於用來產生新世代L-system句子的generate()方法。先前轉換字串來產生新世代L-system句子時，程式是這樣寫的：

''.join([rules[char] for char in string])

不過在generate()方法中的寫法卻不一樣；這是因為，先前的寫法是假設在字母表中的字元都會出現在規則中，然而現在加入了烏龜繪圖的功能，像$+、-、[、]$這些字元，並不一定會出現在規則中。所以，當在轉換句子時，如果碰到規則中不存在的字元，那就不需進行轉換，保持原樣就好。

接下來來設計Turtle類別。既然叫烏龜繪圖，那就想像有一隻烏龜爬呀爬的在畫圖。為了要讓烏龜在畫布上畫出我們想要的圖案，我們賦予烏龜下面這些屬性：

surface：pygame.Surface物件；烏龜要在上面畫圖的畫布。
position：pygame.Vector2物件；烏龜的位置。  
heading：烏龜的行進方向，單位是「度」。  
length：烏龜每次移動的距離。  
angle：烏龜每次轉動的角度大小，單位是「度」。  
state_stack：list變數；用來存放烏龜狀態的堆疊。烏龜的狀態包括position及heading這兩個屬性。  
drawing_rules：dictionary變數；存放繪圖指令字元及其對應的畫圖動作。例如F這個key，對應的是move_forward_draw()方法，可以讓烏龜向前移動大小為length的距離，並且畫出線段。

設計好的Turtle類別長這樣：

class Turtle:
    def __init__(self, surface, position, heading, length, angle):
        self.surface = surface  # pygame.Surface物件
        self.position = position  # pygame.Vector2物件
        self.heading = heading  # 單位「度」
        self.length = length
        self.angle = angle  # 單位「度」
        
        self.state_stack = []
        self.drawing_rules = {
            'F': self.move_forward_draw,
            'f': self.move_forward_not_draw,
            '+': self.turn_left,
            '-': self.turn_right,
            '[': self.push_state,
            ']': self.pop_state
            }
        
    def render(self, sentence):
        for char in sentence:
            self.drawing_rules[char]()
        
    def move_forward_draw(self):
        direction = pygame.Vector2.from_polar((1, self.heading))
        end_position = self.position + self.length*direction
        pygame.draw.line(self.surface, (0, 0, 0), self.position, end_position)
        self.position = end_position.copy()
        
    def move_forward_not_draw(self):
        direction = pygame.Vector2.from_polar((1, self.heading))
        self.position += self.length*direction
        
    def turn_left(self):
        self.heading += self.angle
        
    def turn_right(self):
        self.heading -= self.angle
        
    def push_state(self):
        self.state_stack.append([self.position.copy(), self.heading])
        
    def pop_state(self):
        self.position, self.heading = self.state_stack.pop()

接下來，就利用LSystem和Turtle這兩個類別來將下列這個L-system畫出來：

字母表：F、f、+、-、[、]
公理：F
規則：F⟶FF+[+F-F-F]-[-F+F+F]

這個L-system所畫出來的圖案是一棵樹──一棵看起來還挺逼真的樹。

Example 8.9: An L-system

# python version 3.10.9
import sys

import pygame  # version 2.3.0
  
  
pygame.init()

pygame.display.set_caption("Example 8.9: An L-system") 

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 320
screen = pygame.display.set_mode(screen_size)

FPS = 60
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

axiom = 'F'
rules = {'F': 'FF+[+F-F-F]-[-F+F+F]'}

lsystem = LSystem(axiom, rules)

# 演化次數
n = 4
for _ in range(n):
    lsystem.generate()

x, y = WIDTH//2, HEIGHT-5
position= pygame.Vector2(x, y)

turtle = Turtle(screen, position, -90, 5, 25)
turtle.render(lsystem.sentence)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 8.11

設計一個Trail類別，用來描述烏龜所畫下的線段。程式如下：

class Trail:
    def __init__(self, start, end):
        # 線段起點和終點都是pygame.Vector2物件
        self.start = start
        self.end = end

在Turtle類別的__init__()方法中，新增用來儲存烏龜所畫下線段的屬性：

self.trails = []

修改move_forward_draw()方法，將

pygame.draw.line(self.surface, (0, 0, 0), self.position, end_position)

改成

self.trails.append(Trail(self.position, end_position))

這樣當執行render()方法時，就會將烏龜畫下的線段記錄在trails這個list中。

Exercise 8.12

在L-system中加入隨機性。具體的做法是：在規則中，前身的接替者不再是固定的，而是會隨機變動。例如下面這個L-system

字母表：F、f、+、-、[、]
公理：F
規則：F_0.33⟶F[+F]F
F_0.33⟶F[+F]F[-F]F
F_0.34⟶F[-F]F

在規則中，前身，也就是字母F，右下角所標註的數字，是這條規則會被採用的機率。所以，在這個系統中，前身F會有三個不同的接替者，而每個接替者雀屏中選的機率都大約是1/3。

程式部分，需修改的地方有兩個：一個是rules這個dictionary；另一個是LSystem類別的generate()方法。rules的寫法要改成

rules = {'F': (accessors, probabilities)}

其中

accessors = ('F[+F]F[-F]F', 'F[+F]F', 'F[-F]F')
probabilities = (0.33, 0.33, 0.34)

至於generate()方法，則改成

def generate(self):
    self.sentence = ''.join([random.choices(rules[char][0], rules[char][1])[0]
                             if char in rules else char for char in self.sentence]) 

主程式

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Exercise 8.12") 

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 320
screen = pygame.display.set_mode(screen_size)

FPS = 1
frame_rate = pygame.time.Clock()

screen.fill(WHITE)

accessors = ('F[+F]F[-F]F', 'F[+F]F', 'F[-F]F')
probabilities = (0.33, 0.33, 0.34)

axiom = 'F'
rules = {'F': (accessors, probabilities)}

# 演化次數
n = 4

# 起始點位置
x, y = WIDTH//2, HEIGHT-5
position= pygame.Vector2(x, y)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()  

    screen.fill(WHITE)

    lsystem = LSystem(axiom, rules)
    
    for _ in range(n):
        lsystem.generate()
    
    turtle = Turtle(screen, position, -90, 5, 25)
    turtle.render(lsystem.sentence)
    
    pygame.display.update()
    frame_rate.tick(FPS)

執行程式之後，會不斷重新繪製圖案。因為具有隨機性，所以每次畫出來的圖案都不同。下面是兩張擷取出來的圖案：

Exercise 8.13

略