The Nature of Code閱讀心得與Python實作：5.5 Complex Systems

到目前為止，我們所設計出來的自主代理人都是孤鳥，既不知道有其他自主代理人的存在，也不會跟其他自主代理人有任何互動。在這一節，我們將讓自主代理人能感知到其他自主代理人的存在，並且與其他自主代理人互動，最後形成由自主代理人所組成的複雜系統(complex system)。

複雜系統？那是個怎麼樣的存在呢？

複雜系統的典型定義是：系統比其組成部分的總和還要多一些東西出來。或者也可以就說成2>1+1。用白話文來說，就是系統由非常簡單容易了解的個別元素所組成，但是整個系統卻會表現出非常複雜、聰明，而且難以預測的行為。例如，一窩螞蟻是由一隻隻螞蟻這種簡單的單元所組成，雖然單一一隻螞蟻這個簡單的單元只能感知到身旁近處的環境並據以做出反應，但透過這些簡單的單元之間的互動，一窩螞蟻卻可以表現出擴張、抵禦外敵、囤積食物等非常複雜的行為。一窩螞蟻的這些行為，可遠比單一一隻螞蟻的行為要複雜千萬倍；從一隻螞蟻的個別行為，是不可能預測出一窩螞蟻會表現出什麼樣的行為的。

除了螞蟻的例子外，用個比較戲謔一點的例子來說明，或許會更有感：由一百個天才所組成的團體，會表現出十足笨蛋的行為。這，就是複雜系統迷人的地方啊！

接下來在模擬複雜系統時，會依循下列三個主要的原則：

• 組成系統的簡單的單元只有小範圍的關聯。這也就是一直以來在設計vehicle時所遵循的原則：vehicle只有有限度的環境感知能力。
• 組成系統的簡單的單元會平行運作。在每一輪while迴圈中，所有的單元都會計算各自的轉向力，這樣可以讓所有的單元看起來像是在同時動作一樣。
• 把許多系統視為一個整體，則會展現出突現現象(emergent phenomenon)。單元間的互動，可以顯現出複雜的行為、樣態(pattern)、智慧。這種現象在自然界中非常常見，蟻群、遷徙模式(migration patterns)、地震、雪花等等都是；甚至於在高速公路上明明沒有交通事故但卻塞車，這種莫名其妙的情況也是一種突現現象。突現現象很有趣，問題在於我們能不能模擬出同樣的效果來。

除了以上三個主要的原則之外，下列三個複雜系統的特徵，也可以讓我們在進行模擬時有個方向，知道應該要把什麼樣的特徵放到系統中，才能得到我們想要的效果。不過要注意的是，一個複雜系統並不一定會同時具備這三個特徵，也有可能就只含有一部分而已。

• 非線性：系統的輸入與輸出之間，並非呈現出線性的關係。最通俗而大家耳熟能詳的例子，就是氣象學家Edward Norton Lorenz所提出的蝴蝶效應：一隻蝴蝶拍拍翅膀，結果在地球的另一端產生了一個龍捲風。這個效應所描述的，就是非線性系統對於初始條件非常敏感的特性；當非線性系統的初始條件有非常微小的改變時，會讓最後的輸出結果有翻天覆地的變化。不過要注意的是，並不是所有的非線性系統都會有蝴蝶效應產生；先前模擬過的單擺是個非線性系統，但不管一開始你把擺錘放在哪個位置，經過一段時間的擺盪之後，擺錘最後都會靜止不動。
• 競爭與合作：組成系統的元素間的競爭與合作是驅動複雜系統演變的一個因素。在接下來要介紹的群聚系統(flocking system)就具有競爭與合作的特徵。群聚系統包含了三個規則：對齊(alignment)、聚集(cohesion)、分離(separation)。對齊與聚集這兩個規則要求元素要試著待在一起以及一起行動，藉此來達到讓元素合作的目的；至於分離這個規則，則是要求元素間要彼此競爭空間。如果把複雜系統元素間的競爭關係或合作關係拿掉一個，則系統將會喪失其複雜性。只有在由具有生命的元素所組成的複雜系統中，才能看到競爭與合作的關係，在像是天氣這種由非生命的元素所組成的複雜系統中，是看不到競爭與合作關係的。
• 迴饋：複雜系統通常都會有個迴饋的迴圈；這也就是說，系統的輸出會被迴饋成為系統的輸入，藉此來強化或弱化系統的輸出。連假結束後要選擇哪個時間上高速公路回到工作崗位，就是一個常見的例子。半夜高速公路應該比較不會塞車，那就半夜上路吧！一開始的確是這樣，可是當越來越多人發現半夜不塞車之後，半夜上路的人會越來越多，最後的結果可想而知，當然是塞到不要不要的。然後呢？然後大家發現半夜很會塞車，那就不要半夜上路。這樣做的人越來越多，所以半夜的高速公路就漸漸的不塞了。等到大家發現半夜的高速公路不塞車之後，又開始一個一個選擇半夜上路，然後半夜的高速公路又開始塞了。就這樣，系統因為迴饋的作用而擺盪過來、擺盪過去，呈現出複雜的行為。

接下來，我們先讓vehicle能夠感知到在他附近的其他vehicle，然後讓各個vehicle互相影響彼此的行為，最後突現出群聚行為。

Implementing Group Behaviors (or: Let's Not Run Into Each Other)

要讓所有的vehicle都能夠感知到在他附近的其他vehicle，做法很簡單，就是用個List把所有的vehicle都裝進去，然後用個迴圈一個一個去看，除了自己之外的其他vehicle都在做些什麼。假設所有的vehicle都放在vehicles這個List中，對於self這個vehicle而言，要知道其他vehicle都在做些什麼，程式可以這樣寫：

for vehicle in vehicles:
    if vehicle is not self:
        :
        :

接下來就用這樣子的寫法，來讓所有的vehicle之間都能夠保持安全的社交距離。

要怎麼讓所有的vehicle之間都能夠保持安全的社交距離呢？這就需要靠分離(separation)這個轉向行為了。

根據Reynolds的定義，分離這個轉向行為，指的是讓自主代理人避免擠成一團的轉向行為。換句話說，當一個vehicle發現他和其他vehicle之間太過於接近時，就會產生轉向力來遠離對方；這樣子他們就不會擠在一起了。

那這個分離的轉向力要怎麼計算呢？先前在設計vehicle的尋標轉向行為時，vehicle會先算出指向目標物的速度v_desired，然後再算出所需的轉向力。既然在尋標時vehicle會朝目標物跑過去，那把另一個vehicle當成目標物，然後將尋標的v_desired反向，這樣算出來的轉向力，不就可以讓vehicle遠離另一個vehicle了嗎？

的確！上述的做法可以讓vehicle遠離另一個vehicle；但是萬一vehicle發現有很多個其他的vehicle都太過靠近時，那該怎麼辦呢？這其實不難，就只需要針對每一個太過靠近的vehicle算出對應的v_desired，然後取其平均值作為計算轉向力所需的v_desired，這樣所算出來的轉向力，就是可以同時遠離這些太過靠近的vehicle的分離轉向力了。

慢著！單純的取平均值，這樣會不會太過於一視同仁了？雖然同樣是太過靠近，但總有些特別靠近、有些比較沒那麼靠近吧？碰到特別靠近的，不是應該更用力地速速遠離嗎？

確實如此！如果能根據距離的遠近來調整v_desired的大小，讓越靠近的vehicle所對應的v_desired越大，這樣子所算出來的分離轉向力的效果，會比單純的取平均值要來得好。

綜合以上的分析，當vehicle感知到和其他的vehicle太過靠近而需產生分離轉向力時，計算v_desired的程式可以這樣寫：

desired_velocity = pygame.Vector2(0, 0)
for vehicle in vehicles:
    if vehicle is not self:
        d = self.position.distance_to(vehicle.position)
        # 跟計算尋標轉向力時所算出的v_desired方向相反
        v_desired = self.position - vehicle.position
        # 距離越近，v_desired要越大
        v_desired.scale_to_length(1/d)
        desired_velocity += v_desired

當然啦！也有可能vehicle會發現其他vehicle都和自己保持著安全的社交距離，那就沒有必要產生分離轉向力了。把這一部分也考慮進去，產生分離轉向力的separate()方法，完整的程式可以這樣寫：

def separate(self, vehicles):
    desired_separation = 4*self.radius
    desired_velocity = pygame.Vector2(0, 0)
    enable_separation = False
    for vehicle in vehicles:
        if vehicle is not self:
            d = self.position.distance_to(vehicle.position)
            if d < desired_separation:
                v_desired = self.position - vehicle.position
                if d > 1.e-5:
                    v_desired.scale_to_length(1/d)
                else:
                    v_desired *= 1.e10

                desired_velocity += v_desired
                enable_separation = True
    
    if enable_separation:
        if desired_velocity.length() > 1.e-5:
            desired_velocity.scale_to_length(self.max_speed)

        steer = desired_velocity - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        self.apply_force(steer)

程式裡頭的desired_separation是我們設定的安全社交距離，這裡設定成跟vehicle的半徑大小有關。這也就是說，這個安全的社交距離並不一定要是個定值不可，它是可以依照需要而設定成動態改變的。

Example 5.9: Separation

這個例子是separate()方法的應用。按滑鼠左鍵拖曳可以投放更多的vehicle。

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Example 5.9: Separation")

WHITE = (255, 255, 255)

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

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

n = 25  # 一開始vehicle的數量
vehicles = [Vehicle(random.randint(0, WIDTH), random.randint(0, HEIGHT)) for _ in range(n)]

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == pygame.MOUSEMOTION and event.buttons[0]:
            # 按滑鼠左鍵拖曳可以投放vehicle
            x, y = event.pos
            vehicles.append(Vehicle(x, y))

    screen.fill(WHITE)    
    
    for vehicle in vehicles: 
        vehicle.separate(vehicles)
        vehicle.update()
        vehicle.check_edges()
        vehicle.show()    
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 5.12

重點在把separate()方法中的

v_desired = self.position - vehicle.position

改成

v_desired = vehicle.position - self.position

完整程式如下：

def cohere(self, vehicles):
    desired_coherence = 4*self.radius
    desired_velocity = pygame.Vector2(0, 0)
    enable_coherence = False
    for vehicle in vehicles:
        if vehicle is not self:
            d = self.position.distance_to(vehicle.position)
            if d > desired_coherence:
                v_desired = vehicle.position - self.position 
                v_desired.scale_to_length(1/d)
                desired_velocity += v_desired
                enable_coherence = True
    
    if enable_coherence:
        if desired_velocity.length() > 1.e-5:
            desired_velocity.scale_to_length(self.max_speed)

        steer = desired_velocity - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        self.apply_force(steer) 

Exercise 5.13

因為路徑為環狀，所以follow_path()方法有兩個部分需修改。

第一個需修改的部分是，預測vehicle未來的位置時，需加入判斷式判斷vehicle的速度是否為0，否則可能會因為scale_to_length()無法處理零向量而出現錯誤。vehicle的速度之所以可能變成0，是因為當初始速度的方向與路徑的方向相反時，vehicle有可能會掉頭改變行進方向，因而在某個時間點上速度會是0。這個部分的程式就修改成：

if displacement.length()>1.e-5:
    displacement.scale_to_length(25)

第二個需修改的部分，是判斷交點是否在路徑上的方式。因為現在路徑是環狀，所以路徑的方向並不是只會由左至右，因此需把判斷方式改成Exercise 5.10中所提到的適用這種情況的方式。這個部分的程式就修改成：

da = normal_pt.distance_to(pt_start)
db = normal_pt.distance_to(pt_end)
dab = pt_start.distance_to(pt_end)
if abs(da+db-dab)>1.e-5:    
    normal_pt = pt_end.copy()

修改後的follow_path()方法完整程式碼如下：

def follow_path(self, path, show_details):
    displacement = self.velocity.copy()
    if displacement.length()>1.e-5:
        displacement.scale_to_length(25)
        
    future = self.position + displacement
    
    # 找出距離future最近的短路徑
    distance = float('inf')    
    for i in range(len(path.points)-1):
        # 路徑起點與終點
        pt_start = path.points[i]
        pt_end = path.points[i+1]
    
        vec_A = future - pt_start       
        vec_B = pt_end - pt_start
        normal_pt = pt_start + vec_A.project(vec_B)
        
        # 如果交點不在路徑上，就把路徑終點當作交點
        da = normal_pt.distance_to(pt_start)
        db = normal_pt.distance_to(pt_end)
        dab = pt_start.distance_to(pt_end)
        if abs(da+db-dab)>1.e-5:    
            normal_pt = pt_end.copy()

        d = future.distance_to(normal_pt)
        if d < distance:
            distance = d
            normal_point = normal_pt.copy()
            displacement = vec_B.copy()
    
    # 把目標物放在交點前方25像素處
    displacement.scale_to_length(25)
    target = normal_point + displacement

    is_strayed = distance > path.radius
    if is_strayed:
        self.seek(target)     
    
    if show_details:
        pygame.draw.line(self.screen, (0, 0, 0), self.position, future)
        pygame.draw.circle(self.screen, (0, 0, 0), future, 3)
        
        pygame.draw.line(self.screen, (0, 0, 0), future, normal_point)
        pygame.draw.circle(self.screen, (0, 0, 0), normal_point, 3)
        
        color = (255, 0, 0) if is_strayed else (0, 0, 0)
        pygame.draw.circle(self.screen, color, target, 5) 

程式執行時，按滑鼠左鍵可以投放vehicle；按「d」鍵可以切換是否顯示路徑循行細節。主程式如下：

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Exercise 5.13")

WHITE = (255, 255, 255)

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

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

n = 50  # 一開始vehicle的數量
vehicles = [Vehicle(random.randint(0, WIDTH), random.randint(0, HEIGHT)) for _ in range(n)]
for vehicle in vehicles:
    max_speed = random.uniform(2, 4)
    vehicle.velocity = pygame.Vector2(max_speed, 0)
    vehicle.max_speed = max_speed
    vehicle.max_force = 0.3

radius = 20
path = Path(radius)
offset = 50
path.add_point(offset, offset)
path.add_point(WIDTH - offset, offset)
path.add_point(WIDTH - offset, HEIGHT - offset)
path.add_point(WIDTH / 2, HEIGHT - offset * 3)
path.add_point(offset, HEIGHT - offset)
path.add_point(offset, offset)

show_details = False

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == pygame.MOUSEBUTTONDOWN:
            # 按滑鼠左鍵可以投放vehicle
            x, y = event.pos
            vehicle = Vehicle(x, y)
            max_speed = random.uniform(2, 4)
            vehicle.velocity = pygame.Vector2(max_speed, 0)
            vehicle.max_speed = max_speed
            vehicle.max_force = 0.3
            vehicles.append(vehicle)
        elif event.type == pygame.KEYDOWN:
            # 按「d」鍵可以切換是否顯示路徑循行細節
            if event.key == pygame.K_d:
                show_details = not show_details            

    screen.fill(WHITE)    
    
    path.show()
    
    for vehicle in vehicles: 
        vehicle.follow_path(path, show_details)
        vehicle.separate(vehicles)
        vehicle.update()
        vehicle.show()    
    
    pygame.display.update()
    frame_rate.tick(FPS)

Combining Behaviors

一個自主代理人是不是就只能有一種轉向行為呢？當然不是！如果自主代理人就只有一種轉向行為，那實在是跟發條玩具狗沒什麼兩樣，既單調又無趣，沒什麼好玩的。許多群體行為之所以有趣，就在於其組成分子具有多種的轉向行為，由此而展現出讓人驚奇、意想不到的結果。

那要怎麼讓自主代理人具有不只一種的轉向行為呢？這時程式又該怎麼寫呢？

要讓自主代理人具有多種轉向行為，原理其實挺簡單的。在第二章，我們模擬過多種作用力同時作用下的合力會對物體的運動造成什麼樣的影響。既然轉向力也是力，那相同的合力概念也可以應用到自主代理人的轉向力上來；只要把自主代理人所產生的所有轉向力的合力算出來，然後作用在自主代理人上，這樣就可以讓自主代理人同時具備多種的轉向行為了。

方法知道了，那程式要怎麼寫呢？既然轉向力是自主代理人自己產生的，那在Vehicle類別裡頭增加一個apply_behaviors()方法來管理所有的轉向行為，會是一個挺好的主意。舉個例子，假設我們要讓vehicle同時具備尋標和分離兩種轉向行為，這時apply_behaviors()方法應該可以寫成這樣：

def apply_behaviors(self, vehicles):
    separate = self.separate(vehicles)
    seek = self.seek(pygame.Vector2(pygame.mouse.get_pos()))
    
    steer = 1.5*separate + 0.5*seek
    self.apply_force(steer)

在這裡，我們設定作用在vehicle上的轉向力，是把分離和尋標這兩個轉向力分別乘上各自的權重1.5和0.5之後的合力。

給不同的轉向力不同的權重對表現出來的轉向行為有什麼影響呢？假如vehicle代表的是一群正在覓食的魚，而滑鼠游標是可口的食物，那上述的設定所代表的意義，就是比起追捕食物，這群魚在覓食的時候，會更傾向於避免跟其他的魚靠得太近。所以，藉由賦予不同的轉向力不同的權重，我們就可以調整自主代理人所表現出來的轉向行為。當然，這個權重並不一定非得是固定的值不可，它也可以隨著不同的條件而動態變化。例如，可以給vehicle設定一個代表飢餓程度的屬性，並讓尋標這個轉向力的權重隨著飢餓程度上升而增加。這樣子設定之後，飢餓程度越高的魚，就會越傾向優先追捕食物；畢竟都快餓死了，安全的社交距離也就沒那麼重要了。

設計好apply_behaviors()方法之後，還必須修改一下separate()和seek()這兩個方法，讓它們能傳回轉向力，這樣才能讓apply_behaviors()方法順利運作。修改的方式如下：

def separate(self, vehicles):
    :
    :
    if enable_separation:
        :
        :
        # self.apply_force(steer)  刪除這一行
        return steer
    else:
        return pygame.Vector2(0, 0)

def seek(self, target_position):
    :
    :
    # self.apply_force(steer)  刪除這一行
    return steer

Example 5.10: Combining Steering Behaviors (Seek and Separate)

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Example 5.10: Combining Steering Behaviors (Seek and Separate)")

WHITE = (255, 255, 255)

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

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

n = 50  # vehicle的數量
vehicles = [Vehicle(random.randint(0, WIDTH), random.randint(0, HEIGHT)) for _ in range(n)]

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

    screen.fill(WHITE)    
    
    for vehicle in vehicles: 
        vehicle.apply_behaviors(vehicles)
        vehicle.check_edges()
        vehicle.update()
        vehicle.show()    
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 5.14

讓尺寸大的vehicle比尺寸小的有更強的尋標驅動力。另外，尺寸大的會保持安全的社交距離，而尺寸小的則喜歡聚集在一起。

def apply_behaviors(self, vehicles):
    separate = self.separate(vehicles) if self.size>10 else pygame.Vector2(0, 0)
    seek = self.seek(pygame.Vector2(pygame.mouse.get_pos()))
    cohere = self.cohere(vehicles) if self.size<10 else pygame.Vector2(0, 0)
    
    steer = separate + (1-math.exp(-self.size/50))*seek + cohere
    self.apply_force(steer)

cohere()方法的修改方式如下：

def cohere(self, vehicles):
    :
    :
    if enable_coherence:
        :
        :
        # self.apply_force(steer)  刪除這一行
        return steer
    else:
        return pygame.Vector2(0, 0)

主程式

# python version 3.10.9
import math
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Exercise 5.14")

WHITE = (255, 255, 255)

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

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

# 不同尺寸vehicle的數量
n1 = 10  
n2 = 10
vehicles1 = [Vehicle(random.randint(0, WIDTH), random.randint(0, HEIGHT), 5) for _ in range(n1)]
vehicles2 = [Vehicle(random.randint(0, WIDTH), random.randint(0, HEIGHT), 20) for _ in range(n2)]
vehicles = vehicles1 + vehicles2

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

    screen.fill(WHITE)    
    
    for vehicle in vehicles: 
        vehicle.apply_behaviors(vehicles)
        vehicle.check_edges()
        vehicle.update()
        vehicle.show()    
    
    pygame.display.update()
    frame_rate.tick(FPS)

Flocking

群聚(flocking)是許多生物，如鳥類、昆蟲、魚類等，都會表現出來的群體行為。Reynolds在1986年設計了用來模擬群聚行為的模擬程式，並在他的論文＜Flocks, Herds, and Schools: A Distributed Behavioral Model＞中，介紹了這個程式所使用的演算法。接下來，利用這一章到目前為止所介紹的內容，我們也來設計模擬群聚行為的模擬程式。

Reynolds創造了「boid」這個字，用來指稱群聚系統中的個別元素。要讓boid展現出群聚行為，就只需要三條規則：

• 分離(separation)：也叫做迴避(avoidance)，指的是避免撞到鄰居。
• 對齊(alignment)：也叫做仿效(copy)，指的是保持跟鄰居相同的行進方向。
• 聚集(cohesion)：也叫做集中(center)，指的是移到一群鄰居的中間。

現在我們要做的，就是設計一個Boid類別，並把這三條規則實作成三個方法，分別傳回三種轉向力，然後賦予這三種轉向力各自的權重並算出其合力；這個合力就是能讓boid展現群體行為的轉向力。

Boid類別的設計很簡單，就把Vehicle類別拿來修改，並加入對齊和聚集這兩個新的方法就可以了。設計好的Boid類別會長這樣：

class Boid:
    def __init__(self, x, y, size=12, mass=1):
        # 取得顯示畫面及其大小
        self.screen = pygame.display.get_surface()
        self.width, self.height = self.screen.get_size()
        
        # 讓傳遞進來的數值來決定boid的質量
        self.mass = mass
        
        # boid的大小，長 x 寬 = size x size/2
        self.size = size
        
        # boid的初始位置、初始速度、初始加速度
        self.position = pygame.Vector2(x, y)
        self.velocity = pygame.Vector2(random.uniform(-1, 1), random.uniform(-1, 1))
        self.acceleration = pygame.Vector2(0, 0)
        
        # boid的最大速率、最大出力
        self.max_speed = 3
        self.max_force = 0.05
        
        # 設定boid所在surface的格式為per-pixel alpha，並在上面畫出boid
        self.surface = pygame.Surface((self.size, self.size/2), pygame.SRCALPHA)
        body = [(0, 0), (0, self.size/2), (self.size, self.size//4)]
        pygame.draw.polygon(self.surface, (0, 0, 0), body)    

    def apply_force(self, force):
        self.acceleration += force/self.mass

    def update(self):
        self.velocity += self.acceleration
        if self.velocity.length() > self.max_speed:
            self.velocity.scale_to_length(self.max_speed)
        
        self.position += self.velocity
        
        self.acceleration *= 0

    def seek(self, target_position):
        desired = target_position - self.position
        if desired.length() > 1.e-5:
            desired.scale_to_length(self.max_speed)
        
        steer = desired - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        return steer
        
    def separate(self, boids):
        desired_separation = 25
        desired_velocity = pygame.Vector2(0, 0)
        enable_separation = False
        for boid in boids:
            if boid is not self:
                d = self.position.distance_to(boid.position)
                if d < desired_separation:
                    v_desired = self.position - boid.position
                    if d > 1.e-5:
                        v_desired.scale_to_length(1/d)
                    else:
                        v_desired *= 1.e10
                        
                    desired_velocity += v_desired
                    enable_separation = True
        
        if enable_separation:
            if desired_velocity.length() > 1.e-5:
                desired_velocity.scale_to_length(self.max_speed)

            steer = desired_velocity - self.velocity
            if steer.length() > self.max_force:
                steer.scale_to_length(self.max_force)
            
            return steer
        else:
            return pygame.Vector2(0, 0)
    
    def align(self, boids):
        :
        :
        
    def cohere(self, boids):
        :
        :
            
    def flock(self, boids):
        separation = self.separate(boids)
        alignment = self.align(boids)
        coherence = self.cohere(boids)
        
        steer = 1.5*separation + alignment + coherence
        self.apply_force(steer)
                
    def check_edges(self):
        if self.position.x > self.width+self.size/2:
            self.position.x = -self.size/2
        elif self.position.x < -self.size/2:
            self.position.x = self.width + self.size/2
    
        if self.position.y > self.height+self.size/2:
            self.position.y = -self.size/2
        elif self.position.y < -self.size/2:
            self.position.y = self.height + self.size/2 

    def show(self):
        # 旋轉surface，讓boid面朝前進方向
        heading = math.atan2(self.velocity.y, self.velocity.x)
        rotated_surface = pygame.transform.rotate(self.surface, -math.degrees(heading))
        rect_new = rotated_surface.get_rect(center=self.position)
                
        # 把boid所在的surface貼到最後要顯示的畫面上
        self.screen.blit(rotated_surface, rect_new

這裡頭的separate()方法，基本上就是Vehicle類別中的separate()方法，只不過把參數由vehicles改成boids而已。另外，flock()方法雖然名稱不同，但其實寫法和Vehicle類別中的apply_behaviors()方法沒什麼太大差別。所以，真正需要設計的，就只有align()和cohere()這兩個方法而已。

align()方法實作的是「對齊」這條規則，也就是可以讓boid能夠產生保持跟鄰居相同行進方向的轉向力。那這個轉向力要怎麼計算呢？計算轉向力的關鍵就在於要怎麼計算v_desired。既然希望能和鄰居保持相同的行進方向，而鄰居的行進方向就包含在其速度向量中，那把所有鄰居速度向量的平均值作為v_desired，不就可以達到目的了嗎？所以align()方法可以這樣設計：

def align(self, boids):
    neighbor_distance = 50
    desired_velocity = pygame.Vector2(0, 0)
    enable_alignment = False
    for boid in boids:
        if boid is not self:
            d = self.position.distance_to(boid.position)
            if d < neighbor_distance:
                desired_velocity += boid.velocity
                enable_alignment = True
    
    if enable_alignment:
        if desired_velocity.length() > 1.e-5:
            desired_velocity.scale_to_length(self.max_speed)

        steer = desired_velocity - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        return steer
    else:
        return pygame.Vector2(0, 0)

這裡頭的neighbor_distance這個變數內所設定的，是用來判定同伴是不是鄰居的門檻值；距離小於這個門檻值的同伴，才會被認定是鄰居。另外要注意的是，程式中並沒有去計算鄰居速度向量的平均值，而是直接將鄰居速度向量的和作為v_desired使用。之所以可以這麼做的原因在於，算出v_desired之後，會先將其大小調整成max_speed，然後才拿來計算轉向力；所以是不是使用平均值，根本就沒差。

Exercise 5.15

除了距離之外，還要再看看其他的boid是否落於視角之內。

要判斷某個目標物是否落於boid的視角，也就是aov (angle of view)之內，方法很簡單。假設a是和中心視線，也就是目前行進方向的視線，有相同方向的向量，而b是由boid目前位置到目標物位置的向量，則利用向量內積，就可以很容易地算出這兩個向量間的夾角θ。如果

θ ≤ aov/2

則目標物就是位於視角之內。

修改後的align()方法如下：

def align_aov(self, boids):
    neighbor_distance = 50
    aov = 60  # 視角(angle of view)，單位為「度」
    desired_velocity = pygame.Vector2(0, 0)
    enable_alignment = False
    for boid in boids:
        if boid is not self:
            d = self.position.distance_to(boid.position)
            if d < neighbor_distance:
                if d < 1.e-5:
                    angle_rad = 0
                else:    
                    a = self.velocity
                    b = boid.position - self.position
                    angle_rad = math.acos(a.dot(b)/(a.length()*b.length()))
                
                if math.degrees(angle_rad) <= aov/2:
                    desired_velocity += boid.velocity
                    enable_alignment = True
    
    if enable_alignment:
        if desired_velocity.length() > 1.e-5:
            desired_velocity.scale_to_length(self.max_speed)

        steer = desired_velocity - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        return steer
    else:
        return pygame.Vector2(0, 0) 

設計好align()方法之後，接下來來看看cohere()方法。cohere()方法實作的是「聚集」這條規則。做法很簡單，就是把所有鄰居位置的平均值當作目標物的位置，然後用seek()方法來產生需要的轉向力。程式可以這麼寫：

def cohere(self, boids):
    neighbor_distance = 50
    target_position = pygame.Vector2(0, 0)
    count = 0
    for boid in boids:
        if boid is not self:
            d = self.position.distance_to(boid.position)
            if d < neighbor_distance:
                target_position += boid.position
                count += 1
    
    if count>0:
        target_position /= count
        steer = self.seek(target_position)
        
        return steer
    else:
        return pygame.Vector2(0, 0)

在第4章模擬粒子系統時，我們設計了Emitter這個專門用來管理系統內所有粒子的類別。在這裡，同樣的做法，我們也設計一個叫做Flock的類別，用來管理群聚系統內所有的boid。Flock類別的長相和Emitter類別差不多，程式碼如下：

class Flock:
    def __init__(self):
        self.boids = []
        
    def run(self):
        for boid in self.boids:
            boid.flock(self.boids)
            boid.update()
            boid.check_edges()
            boid.show()
            
    def add_boid(self, boid):
        self.boids.append(boid)

接下來就來看看實際的應用結果。

Example 5.11: Flocking

按滑鼠左鍵拖曳可以投放新的boid。

# python version 3.10.9
import math
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Example 5.11: Flocking")

WHITE = (255, 255, 255)

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

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

n = 120  # boid的數量 

flock = Flock()
for _ in range(n):
    flock.add_boid(Boid(WIDTH//2, HEIGHT//2))
    
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == pygame.MOUSEMOTION and event.buttons[0]:
            # 按滑鼠左鍵拖曳可以投放boid
            x, y = event.pos
            flock.add_boid(Boid(x, y))            

    screen.fill(WHITE)    
    
    flock.run()
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 5.16

當按下滑鼠左鍵時，滑鼠指標會成為boid尋標的目標物，讓boid除了群聚行為外，也會有尋標轉向行為。做法是在Example 5.11主程式的

flock.run()

這一行之前，加上下列程式碼

if pygame.mouse.get_pressed()[2]:
    target = pygame.Vector2(pygame.mouse.get_pos())
    for boid in flock.boids:
        steer = boid.seek(target)
        boid.apply_force(steer)

Exercise 5.17

假設boid所在的位置是p₀，而擋住視線的另一個boid位於p₁。b是由p₀到p₁的向量，則v_desired是與b垂直的向量乘上權重。將所有擋住視線的boid所對應的v_desired加總，即為產生轉向力所需v_desired。權重可設定為p₀到p₁距離的倒數，這樣子距離越近，轉向力就會越大。

根據上述的設計，view()方法的程式碼如下：

def view(self, boids):
    neighbor_distance = 50
    aov = 60  # 視角(angle of view)，單位為「度」
    desired_velocity = pygame.Vector2(0, 0)
    view_blocked = False
    for boid in boids:
        if boid is not self:
            d = self.position.distance_to(boid.position)
            if d < 1.e-5:
                # 和其他boid在同一個位置，掉頭向後轉
                desired_velocity += (-10*self.velocity)
                view_blocked = True
            elif d < neighbor_distance:
                a = self.velocity
                b = boid.position - self.position
                angle_rad = math.acos(a.dot(b)/(a.length()*b.length()))
                if math.degrees(angle_rad) <= aov/2:
                    # 在視角之內，也就是擋住視線了
                    b.scale_to_length(1/d)
                    desired_velocity += b.rotate(90)
                    view_blocked = True  
    
    if view_blocked:
        desired_velocity.scale_to_length(self.max_speed)
        steer = desired_velocity - self.velocity
        if steer.length() > self.max_force:
            steer.scale_to_length(self.max_force)
        
        return steer
    else:
        return pygame.Vector2(0, 0) 

要讓boid也具有view的轉向行為，flock()方法修改如下：

def flock(self, boids):
    separation = self.separate(boids)
    alignment = self.align(boids)
    coherence = self.cohere(boids)
    view = self.view(boids)
 
    steer = 1.5*separation + alignment + coherence + view
    self.apply_force(steer)

Exercise 5.18

新增get_parameters()方法，用來設定各個參數，使其隨時間變動。

def get_parameters(self):
    # boid的最大速率
    x = noise.pnoise1(datetime.datetime.now().microsecond/10**6)
    self.max_speed = 3 + x

    # boid的最大出力        
    x = noise.pnoise1(datetime.datetime.now().microsecond/10**6)
    self.max_force = 0.05 + x/100
    
    # 分離轉向力權重
    x = noise.pnoise1(datetime.datetime.now().microsecond/10**6)
    self.separation_weight = 1.5 + x
    
    # 對齊轉向力權重
    x = noise.pnoise1(datetime.datetime.now().microsecond/10**6)
    self.alignment_weight = 1 + x
    
    # 聚集轉向力權重
    x = noise.pnoise1(datetime.datetime.now().microsecond/10**6)
    self.cohesion_weight = 1 + x 

修改flock()方法：

def flock(self, boids):
    separation = self.separate(boids)
    alignment = self.align(boids)
    coherence = self.cohere(boids)
    
    steer = self.separation_weight*separation + self.alignment_weight*alignment + self.cohesion_weight*coherence
    self.apply_force(steer)

修改Flock類別的run()方法，加入boid的get_parameters()方法。

def run(self):
    for boid in self.boids:
        boid.get_parameters()
        boid.flock(self.boids)
        boid.update()
        boid.check_edges()
        boid.show()

Exercise 5.19

程式執行後，散布各處的boid會聚集凝結成團，有點像是泡沫不斷聚攏在一起的樣子。

程式變動不大，稍微修改幾個地方就可以了。

修改__init__()方法，把boid改成圓形，並修改最大速率、最大出力：

# boid為半徑為radius的圓
self.size = size
self.radius = self.size/2

# boid的最大速率、最大出力
self.max_speed = 1.5 
self.max_force = 1 

# 設定boid所在surface的格式為per-pixel alpha，並在上面畫出boid
self.surface = pygame.Surface((self.size, self.size), pygame.SRCALPHA)
pygame.draw.circle(self.surface, (0, 0, 0, 100), (self.radius, self.radius), self.radius)

修改separate()方法的設定：

desired_separation = self.radius

修改主程式，讓boid一開始時是散布在各處

for _ in range(n):
    flock.add_boid(Boid(random.randint(0, WIDTH), random.randint(0, HEIGHT)))