碎形樹(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
略
