The Nature of Code閱讀心得與Python實作：8.4 Trees

更新於 2025/07/07發佈於 2025/07/07閱讀時間約 24 分鐘

碎形樹(fractal tree)是碎形界除了Cantor集、Koch曲線外，另一個無人不知、無人不曉的圖案。比較特別的是，製作Cantor集跟Koch區線時，所使用的方法是確定性的(deterministic)，不帶有任何隨機性在裡頭；但在製作碎形樹時，可以加入隨機性，讓畫出來的碎形樹長相，更接近大自然中樹木的真實模樣。

The Deterministic Version

先來看不含隨機性，也就是確定性版的碎形樹要怎麼畫。

確定性版碎形樹的製作規則非常簡單，步驟為：

畫一條線段。
在線段的尾端分別向右、向左轉一個角度，然後各畫一條短一點的線段。
重複步驟2。

搭配下圖來看會更清楚一些：

製作碎形樹的重點，在於如何找出線段分岔之後，那兩條比較短的線段的方向。這個其實不難，我們可以用向量來描述線段的方向，然後旋轉向量就可以了。假設dir是pygame.Vector2物件，裡頭放的是線段的方向。要找出dir向右、向左旋轉angle度之後的方向，程式可以這樣寫：

dir_right = dir.rotate(angle)
dir_left = dir.rotate(-angle)

如果用線段的長度來作為判斷是否符合基底情況的條件，那製作碎形樹的遞迴函數可以這樣寫：

def branch(surface, length, start, direction, angle_deg):
    # 基底情況
    if length < 2:
        return
    
    vec = direction.copy()
    
    # 線段終點位置
    vec.scale_to_length(length)
    end = start + vec
    
    # 畫出線段
    pygame.draw.line(surface, (0, 0, 0), start, end)
    
    # 分支長度與方向
    length *= 0.67
    direction_right = vec.rotate(angle_deg)
    direction_left = vec.rotate(-angle_deg)

    branch(surface, length, end, direction_right, angle_deg)
    branch(surface, length, end, direction_left, angle_deg)

Exercise 8.6

在圖中，數字代表處裡的順序。因為branch()函數在最後兩行呼叫自己時，是先處理右邊的分支，然後再處理左邊的，所以在畫完右邊的分支之後，才會畫左邊的分支。

Example 8.6: A Recursive Tree

在這個例子中，我們利用滑鼠來控制碎形樹分岔的角度；移動滑鼠就可以看到碎形樹變換成不同的模樣。

第二張圖是分支的方向是旋轉90度時的碎形樹。很令人驚奇的是，除了一開始的那條垂直線段外，整棵碎形樹的長相，就跟Exercise 8.1所畫出來的圖案是一樣的。

主程式如下：

# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 8.6: A Recursive Tree") 

WHITE = (255, 255, 255)

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

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

length = 100
start = pygame.Vector2(WIDTH/2, HEIGHT)
direction = pygame.Vector2(0, -1)

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

    screen.fill(WHITE)
    
    x, y = pygame.mouse.get_pos()
    angle_deg = (x/WIDTH)*90

    branch(screen, length, start, direction, angle_deg)
    
    pygame.display.update()
    frame_rate.tick(FPS)

利用遞迴函數來畫碎形樹，程式雖然非常簡短，但卻也限制了應用的範圍。例如，如果想將碎形樹的成長製作成動畫，用遞迴函數的方式來做，將會有相當大的困難度。然而，如果像先前在寫Koch曲線時一樣，也使用物件導向的方式來寫，把碎形樹的每條線段都視為是物件，那將可大大地增廣應用範圍與可能性；而碎形樹的成長動畫，也就只是小菜一碟罷了。

Exercise 8.7

在branch()函數中，加入用來控制線段粗細的參數thickness即可。

def branch(surface, length, thickness, start, direction, angle_deg):
    # 基底情況
    if length < 2:
        return
    
    vec = direction.copy()
    
    # 線段終點位置
    vec.scale_to_length(length)
    end = start + vec
    
    # 畫出線段
    pygame.draw.line(surface, (0, 0, 0), start, end, thickness)
    
    # 分支長度、粗細、方向
    length *= 0.67
    thickness = int(0.8*thickness)
    direction_right = vec.rotate(angle_deg)
    direction_left = vec.rotate(-angle_deg)

    branch(surface, length, thickness, end, direction_right, angle_deg)
    branch(surface, length, thickness, end, direction_left, angle_deg)


# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Exercise 8.7") 

WHITE = (255, 255, 255)

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

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

length = 100
start = pygame.Vector2(WIDTH/2, HEIGHT)
direction = pygame.Vector2(0, -1)
thickness = 15

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

    screen.fill(WHITE)
    
    x, y = pygame.mouse.get_pos()
    angle_deg = (x/WIDTH)*90

    branch(screen, length, thickness, start, direction, angle_deg)
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 8.8

class Branch:
    def __init__(self, start, direction, growth_speed, time_span):
        self.start = start.copy()
        self.direction = direction.normalize()
        self.growth_speed = growth_speed
        # 生長時間長度
        self.time_span = time_span
        
        self.end = self.start.copy()
        self.time_left = self.time_span

        self.growing = True        
        self.ready_to_branch = False
        
    def grow(self):
        self.time_left -= 1
        self.end += self.growth_speed*self.direction        

    def update(self):
        if self.growing:
            self.grow()
            # 如果生長時間用罄則停止生長，樹枝可以分岔了
            if self.time_left <= 0:
                self.growing = False
                self.ready_to_branch = True
        
    def show(self, surface):
        pygame.draw.line(surface, (0, 0, 0), self.start, self.end)
        
    def branch(self, angle_deg):
        self.ready_to_branch = False
        branch_direction = self.direction.rotate(angle_deg)
        return Branch(self.end, branch_direction, self.growth_speed, 0.67*self.time_span)


class Leaf:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
    def show(self, surface):
        pygame.draw.circle(surface, (0, 255, 0), (self.x, self.y), 3)


# python version 3.10.9
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Exercise 8.8") 

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)

length = 100
start = pygame.Vector2(WIDTH/2, HEIGHT)
direction = pygame.Vector2(0, -1)
growth_speed = 1
time_span = length/growth_speed

tree = [Branch(start, direction, growth_speed, time_span)]
leaves = []

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

    screen.fill(WHITE)

    new_branches = []    
    for branch in tree:
        branch.update()
        branch.show(screen)
        if branch.ready_to_branch:
            new_branches.append(branch.branch(30))
            new_branches.append(branch.branch(-30))
    
    if len(tree) < 128:    
            tree += new_branches
    else:
        for branch in new_branches:
            leaves.append(Leaf(branch.end.x, branch.end.y))

    for leaf in leaves:
        leaf.show(screen)
            
    pygame.display.update()
    frame_rate.tick(FPS)

The Stochastic Version

確定版的碎形樹最大的問題是太確定了，整棵樹裡裡外外精確到不像是真的。真實的樹木樹枝分岔的角度不會都一樣；分支的數量也不會固定就是2支。那要怎麼做，才能讓碎形樹長得不那麼精確，看起來比較真實一點呢？

要讓碎形樹長得比較真實一些，方法挺簡單的，加點隨機性就可以了。下面這個例子，就是在樹枝分岔的角度以及分支的數量上加入隨機性，讓碎形樹看起來不再那麼死板。

Example 8.7: A Stochastic Tree

def branch(surface, length, start, direction):
    # 基底情況
    if length < 2:
        return
    
    vec = direction.copy()
    
    # 線段終點位置
    vec.scale_to_length(length)
    end = start + vec
    
    # 畫出線段
    pygame.draw.line(surface, (0, 0, 0), start, end, 2)
    
    # 分支長度
    length *= 0.67
    
    # 分支數量1～3支；角度-90度～90度
    n = random.randint(1, 3)
    for i in range(n):
        angle_deg = random.uniform(-90, 90)
        direction_branch = vec.rotate(angle_deg)
        branch(surface, length, end, direction_branch)

        
# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 8.7: A Stochastic Tree") 

WHITE = (255, 255, 255)

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

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

length = 100
start = pygame.Vector2(WIDTH/2, HEIGHT)
direction = pygame.Vector2(0, -1)

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

    screen.fill(WHITE)
    
    branch(screen, length, start, direction)
    
    pygame.display.update()
    frame_rate.tick(FPS)

加入隨機性的碎形樹雖然看起來不再那麼死板，但離栩栩如生還差得遠了。想要讓碎形樹更真實一些，還需要針對隨機性的參數精雕細琢一番；加入Perlin noise也是個可以考慮的方向。

Exercise 8.9

def branch(surface, length, start, direction, angle_deg, perlin1, perlin2):
    # 基底情況
    if length < 2:
        return
    
    vec = direction.copy()
    
    # 線段終點位置
    vec.scale_to_length(length)
    end = start + vec
    
    # 畫出線段
    pygame.draw.line(surface, (0, 0, 0), start, end)
    
    # 分支長度
    length *= 0.67

    # 分支方向
    perlin1 += 0.011
    perlin2 += 0.013
    angle_right = angle_deg + 10*noise.pnoise1(perlin1)
    angle_left = -angle_deg + 10*noise.pnoise1(perlin2)
    direction_right = vec.rotate(angle_right)
    direction_left = vec.rotate(angle_left)
    
    branch(surface, length, end, direction_right, angle_right, perlin1, perlin2)
    branch(surface, length, end, direction_left, angle_left, perlin1, perlin2)


# python version 3.10.9
import sys

import noise # version 1.2.2
import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Exercise 8.9") 

WHITE = (255, 255, 255)

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

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

length = 100
start = pygame.Vector2(WIDTH/2, HEIGHT)
direction = pygame.Vector2(0, -1)
angle_deg = 30

# 取Perlin noise值之引數
perlin1, perlin2 = 0, 100

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

    screen.fill(WHITE)
    
    perlin1 += 0.011
    perlin2 += 0.013
    branch(screen, length, start, direction, angle_deg, perlin1, perlin2)
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 8.10

略

ysf的沙龍Nature of Code閱讀心得與Python實作Chapter 8

留言

留言分享你的想法！

ysf的沙龍

19會員

156內容數

寫點東西自娛娛人

ysf的沙龍的其他內容

2025/06/23

The Nature of Code閱讀心得與Python實作：8.3 The Koch Curve

Koch曲線(Koch curve)，碎形界另一個名氣響噹噹的圖案，是由瑞典數學家Helge von Koch在1904年所提出的。Koch曲線的製作規則非常簡單，就是把一段線段三等分，然後以中間那等分為底部畫出正三角形，接著把底部挖掉。不斷針對新形成的線段重複同樣的動作，就可以產生Koch曲線了。