一種基于螢火蟲算法的群體動畫行為控制仿真設計

張 超，魏三強，陳 偉

(宿州職業(yè)技術學院 計算機信息系，安徽 宿州 234101)

一種基于螢火蟲算法的群體動畫行為控制仿真設計

張 超，魏三強，陳 偉

(宿州職業(yè)技術學院 計算機信息系，安徽 宿州 234101)

自然界中很多生物在遷徙時會自動聚集，并在行進中自覺地排成隊列。為了仿真模擬這一有趣的群體運動行為而制作了群體動畫，在深入研究螢火蟲算法的基礎上，設計了一種仿真模擬方案。該方案基于螢火蟲算法思想，使用速度力的方式實現螢火蟲個體的位置更新計算，并給每只螢火蟲個體設計感知觸須，通過感知觸須的探測，控制亮度低的螢火蟲在最大安全距離閾值范圍內向亮度高的螢火蟲移動，當超出最大安全距離時，將其速度縮放一定比例，通過對速度的控制使亮度低的個體總是排列在亮度高的個體后面，從而避免了個體之間的穿插和碰撞。使用Flash Develop+Action Script3.0工具開發(fā)了仿真實驗平臺。仿真實驗結果表明：該方案逼真地模擬了生物群體在遷徙時涌現的聚集及自覺排列行為，有效解決了群體動畫制作中自碰撞穿插問題。

群體動畫；螢火蟲算法；碰撞檢測與避免；群體行為；智能算法

群體動畫是利用計算機技術模擬自然界生物群體的運動行為。在《冰河世紀》《指環(huán)王》《昆蟲總動員》等影視作品中為我們呈現了極具視覺沖擊力的群體動畫場景。近年來，群體動畫成為國內外學者研究的熱點，已被廣泛應用于影視、虛擬現實、游戲、模擬訓練等領域[1]。本文仿真模擬的群體動畫場景是自然界中很多動物在遷徙時會自動聚集并在行進中自覺排成隊列這一有趣的群體運動行為[2](如圖1所示)。要實現該群體動畫的模擬，需解決2個關鍵問題：群體的整體聚集和個體的自覺排列。本文基于螢火蟲算法思想，設計了一種實現該群體動畫群體行為的模擬方案。

圖1 動物的聚集和排列行為Fig.1 Animals’ gathering and queuing behaviors

動物們在一個地點休息或覓食結束后，會自動聚集進行遷徙，并在行進中自覺地排成隊列，在此過程中動物個體的行為呈現一定的趨眾性和自組織性，處于后面位置的個體總是依據某種規(guī)則跟隨其前面的個體向前運動，這種規(guī)則與螢火蟲算法中亮度低的螢火蟲總是被亮度高的螢火蟲吸引而向其位置移動，并尋找最優(yōu)的聚集目標點有著類似的行為。為此，基于螢火蟲算法實現該動畫群體行為的模擬在理論上是可行的。

螢火蟲算法中亮度低的螢火蟲向亮度高的螢火蟲位置移動時，會出現多只螢火蟲最終聚集在最優(yōu)目標點，并在顯示上出現碰撞和穿插的現象，不符合群體動畫的制作要求[3]。為此，對螢火蟲算法的位置更新方式進行修正，修正后的算法使亮度低的螢火蟲總是在安全距離閾值范圍內，排列在亮度高的螢火蟲的后面，并向最優(yōu)目標點移動。修正的算法實現了個體的自覺排列，有效解決了螢火蟲個體的自碰撞和穿插問題。螢火蟲算法是在虛擬的空間中進行最優(yōu)位置搜索，每只螢火蟲可以到達搜索空間中的任意一個位置。然而，在真實環(huán)境中通常會有障礙物，個體會根據自己的感知自動避開障礙，避免與之發(fā)生碰撞。為此，在仿真時加入了碰撞檢測和避免策略，從而提高了群體動畫的真實性。具有真實感行為的群體動畫模擬能夠增加影視作品的感染力和視覺沖擊力。

1 螢火蟲算法

2008年，劍橋學者Yang Xinshe根據螢火蟲會發(fā)光和互相吸引的群體行為提出了螢火蟲算法(firefly algorithm,FA)[4]。近年來，螢火蟲算法在路徑規(guī)劃[5]和人群疏散仿真[6]領域也得到了應用。

1.1 螢火蟲算法的仿生原理

仿生原理：將螢火蟲個體與搜索空間內的一組隨機初始解對應，將螢火蟲個體所處位置的好壞與待優(yōu)化或求解的目標函數值對應，將求最優(yōu)解的搜索迭代過程模擬成螢火蟲個體的吸引和移動過程。在螢火蟲算法中，螢火蟲個體的吸引和移動依賴于2個關鍵因素：亮度和吸引度。螢火蟲的亮度由待優(yōu)化的目標函數值決定，亮度越高表示螢火所處位置的目標值越好。吸引度與亮度成正比，越亮的螢火蟲擁有越強的吸引度，能夠吸引視線范圍內亮度比其弱的螢火蟲向這個方向移動。亮度相同的螢火蟲各自隨機移動。亮度和吸引度與螢火蟲之間的距離成反比，會隨著距離的增加而減小。

1.2 螢火蟲算法的數學描述和分析[3，7-8]

螢火蟲算法包含2個要素：亮度和吸引度。亮度體現了螢火蟲所處位置的優(yōu)劣并決定其移動方向；吸引度決定了螢火蟲移動的距離。通過亮度和吸引度的不斷更新可實現目標優(yōu)化。數學描述如下：

定義1 亮度

(1)

其中：I0為螢火蟲的最大亮度，即自身(r=0處)熒光亮度；rij為螢火蟲i與j之間的空間距離。

定義2 吸引度

(2)

其中：β0為最大吸引度，即光源處(r=0處)的吸引度，一般取值為1；γ為光強吸收系數，影響吸引度的變化，取值越小吸引度越大，聚類越快，實際應用時常取γ∈[0.1,10]；rij為螢火蟲i與j之間的空間距離，m≥1,一般取2。

定義3 位置更新

螢火蟲i被吸引向螢火蟲j移動的位置更新公式：

(3)

其中：xi，xj為螢火蟲i和j所處的空間位置；α為隨機步長，取值范圍為[0,1]；rand為[0,1]上服從均勻分布的隨機因子。

2 基于力的螢火蟲算法的改進設計

螢火蟲算法將螢火蟲個體看成搜索空間中的一個位置點，此“點”沒有質量、速度等動力學屬性。在MAYA、3DMAX、FLASH等動畫制作軟件的動力學模塊中，每個粒子對象均具有質量、速度、位置、加速度等動力學屬性，使用他們自帶的MEL、ActionScript3.0等腳本語言可以精確控制粒子的運動。為了使本文的研究結果能夠在這些流行的動畫制作軟件中使用，為每只螢火蟲個體添加質量、位置、速度、最大速度等動力學屬性，基于動力學對螢火蟲算法進行修正，實現本文要仿真模擬的群體動畫。

2.1 基于力的位置更新計算

力可以改變角色的速度和位置，在數學上使用向量來表示這些屬性，通過向量的計算來表示力。CraigReynolds在文獻[9]利用歐拉積分方法給出了物體新位置的計算公式：

Position(new)=position(old)+velocity

(4)

速度向量的大小決定了動畫播放時每幀移動的距離，速度向量的方向決定了個體向哪個方向移動。鑒于此，將螢火蟲的位置更新式(3)使用式(4)的位置計算方法表示，即式(5)：

(5)

其中：position為當前螢火蟲個體的位置向量；a是一個臨時變量，為一個向量，是當前螢火蟲個體按照式(3)進行位置更新預計要到達的空間位置；b為亮度高的螢火蟲位置向量；updateBeta(a,b)為按照式(2)計算的吸引度更新函數。這樣，在每次幀更新迭代的過程中，螢火蟲個體就擁有了一個速度力，這個速度力的方向朝向亮度高的螢火蟲個體，大小為按照式(3)進行位置移動的距離。基于這個速度力，可以對螢火蟲個體的聚集和排列行為進行更精準的控制。

2.2 亮度的計算

基本螢火蟲算法應用的核心是將要解決的實際問題利用數學的方法進行描述(即轉化為待優(yōu)化的目標函數)，從而確定螢火蟲個體的亮度取值。所有螢火蟲個體在亮度大小的指引下，按照式(2)和(3)更新每只螢火蟲的吸引度和位置，對目標問題進行優(yōu)化。本文仿真模擬的動物聚集和排列行為是其在尋找新目標聚集點的遷徙過程中涌現的，鑒于此，將每只螢火蟲與新目標聚集點距離的反比作為亮度的計算依據，即螢火蟲個體距離目標點越近其亮度越高。計算公式如下：

(6)

其中：light(i)為螢火蟲i的亮度；xi為螢火蟲i的位置；traget為新目標聚集點的位置。

2.3 動物遷徙時聚集和自覺排列行為模擬方案

動物遷徙時的聚集和自覺排列行為仿真模擬是基于螢火蟲算法思想，并在本文2.1和2.2節(jié)中關于亮度和位置更新的約束下設計的模擬方案。

2.3.1 聚集行為的模擬

在算法進化初期，亮度低的螢火蟲會迅速向局部極值周圍聚集，因此能夠很好地模擬動物在遷徙初始期的聚集行為，但螢火蟲算法的這種特點也容易使算法出現局部最優(yōu)而陷入“早熟收斂”現象，使螢火蟲個體在進化后期停滯不前。本研究中,很多螢火蟲聚集在離目標點較遠的位置而非常緩慢地向目標點移動，這不符合動物遷徙的行為特征，也不符合群體動畫的視覺顯示要求。為此，對螢火蟲算法描述中的“當亮度相同時，螢火蟲個體隨機移動”進行具體化操控，即當亮度相同時，給螢火蟲個體一個朝著目標點運動的最大速度力，使其擺脫局部極值的束縛，從而影響螢火蟲個體在進化后期以一個合適的速度向目標點運動。

2.3.2 排列行為的模擬

動物們在行進中自覺地排成隊列，處于后面位置的個體總是依據某種規(guī)則跟隨其前面的個體向前運動。按照式(6)的計算方法，亮度低的螢火蟲個體相對于目標點總是處于亮度高的螢火蟲個體的后面。為了使亮度低的螢火蟲個體向亮度高的螢火蟲個體聚集移動時總是保持一定的安全距離，不出現穿插和碰撞，在亮度低的螢火蟲向亮度高的螢火蟲移動的過程中，給每只螢火蟲個體一個速度方向上的感知觸須，即向量feeler，長度為h(如圖2所示)，h=個體長度/2+最大安全距離r。在以觸須的空間位置中心為圓心、以最大安全距離r為半徑的感知區(qū)域內，如果存在某個亮度高的螢火蟲位置與當前螢火蟲感知區(qū)域的圓心之間的距離d小于最大安全距離r，將對當前螢火蟲個體的前進速度進行適當縮放，控制亮度低的螢火蟲在最大安全距離允許的范圍內跟隨亮度高的螢火蟲向目標點移動。隨著迭代次數的增加，動物們在亮度和感知觸須的約束下能夠自覺地排成隊列。

圖2 速度力計算演示圖Fig.2 Velocity force calculation

2.4 基于力的螢火蟲算法流程

1) 初始化算法參數。設置螢火蟲個數n、最大速度maxvelocity、隨機步長α、最大吸引度β0、光強吸收系數γ、感知觸須長度h、最大安全距離r的取值。

2) 隨機初始化螢火蟲的位置、初始速度和質量。

3) 根據式(2)和(6)計算螢火蟲的吸引度和初始相對亮度，依據相對亮度決定螢火蟲的移動方向。

4) 當滿足最大安全距離時，使用式(5)基于速度力的計算方式更新螢火蟲的位置，否則將速度縮放一定比例。

5) 根據更新后的位置，重新計算螢火蟲的亮度。

6) 轉到步驟3)進行下一次迭代。

具體流程如圖3所示。

圖3 基于力的螢火蟲算法流程Fig.3 Based on the force of the firefly algorithm flow chart

3 碰撞檢測和避免

碰撞檢測和避免是群體動畫模擬中最基本的研究問題，其目的是為了實現具有真實感行為的群體動畫，從而增加影視作品的感染力和視覺沖擊力。其有效的研究方法是在仿真環(huán)境中隨機添加若干障礙物，模擬個體自動避開障礙物的行為。

3.1 碰撞檢測

碰撞檢測算法目前主要有層次包圍盒、空間分解法和距離跟蹤法[10]。層次包圍盒使用基本幾何體作為物體的包圍體(bounding volume,BV)進行碰撞測試，通過減少不必要的碰撞檢測從而提高檢測效率[11]。本文使用層次包圍盒和歐式距離相結合的碰撞檢測算法。

將障礙物模型包裹在圓(2D空間)或球體中(3D空間)中。在碰撞檢測時使用基于歐式距離的判斷方法。將螢火蟲個體的感知觸須feeler作為碰撞躲避的開始距離。再創(chuàng)建一個與感知觸須方向一致，大小為其一半的向量feeler2。當feeler、feeler2和個體的位置向量position與包圍圓之間的歐式距離小于其半徑r(如圖4所示)，那么個體即將與障礙物發(fā)生碰撞，需要采取碰撞避免策略。

圖4 碰撞檢測Fig.4 Collision detection

3.2 碰撞避免

當檢測到個體將要與最近的障礙物發(fā)生碰撞時，給它一個垂直于速度方向上的排斥力引導個體躲避障礙物。垂直與速度方向上的向量有2個(如圖5所示)：n1和n2。當個體的速度方向位于個體與包圍圓連線上方時選擇n1方向，位于下方時選擇n2方向。具體實現時選擇法線向量與個體到包圍圓中心的向量的點積小于零的向量作為躲避引導力。

4 群體動畫的仿真實驗

為了驗證本文基于螢火蟲算法思想設計的方案，在模擬動物遷徙時自動聚集并在行進中自覺排成隊列這一群體行為的有效性，使用Flash Develop+Action Script3.0工具搭建仿真實驗場景進行仿真實驗。

4.1 實驗部署

仿真程序參數設置：螢火蟲數目設為80，最大速度為2，隨機步長α=0.2，光強吸收系數γ=0.05，感知觸須長度h=60、最大安全距離r=50，質量在[20,40]之間,舞臺尺寸800×600，幀頻為12。機器配置：主頻2.53 GHZ的CPU；2GB內存；32位Win7旗艦版操作系統(tǒng)。

在舞臺上隨機初始化若干個障礙物，障礙物包圍圓的位置和大小由仿真程序隨機分配。為每只螢火蟲個體設計一個亮度顯示屏，實時地顯示螢火蟲隨著位置更新后的亮度大小，便于在實驗進行時觀察每個螢火蟲的運動狀態(tài)。

4.2 實驗結果與分析

隨機進行一次仿真實驗，選取3個關鍵階段的實驗結果截圖進行實驗分析。3個階段螢火蟲個體的運動狀態(tài)如圖6～8所示。圖6為螢火蟲初始化狀態(tài)。圖中樹被包裹在包圍圓中，亮度顯示屏中顯示了當前位置的亮度。因為螢火蟲和障礙物的位置均由仿真程序隨機分布，可以看到有的螢火蟲落入到包圍圓內部。在仿真實驗啟動后，這些螢火蟲會依據碰撞檢測算法避開障礙物，有效驗證了模擬方案使用的碰撞檢測和避免算法。

圖7為仿真初期螢火蟲個體聚集后準備往目標點遷徙的運動狀態(tài)。這時，螢火蟲個體由初始位置開始向目標點聚集。通過對光強吸收系數γ進行取值對比實驗表明：γ的取值越小，在這個階段的聚類越快。通過對比實驗，一方面驗證了基于力的螢火蟲改進算法仍然具有基本螢火蟲算法屬性，另一方面根據群體動畫的視覺效果要求，通過調節(jié)γ控制這個階段個體的聚集速度。

圖6 螢火蟲初始化狀態(tài)Fig.6 Initialization state of firefly

圖7 仿真初期聚集狀態(tài)Fig.7 Aggregation state at the beginning of simulation

圖8 仿真中后期自覺排列運動狀態(tài)Fig.8 The conscious queuing state during the middle and later period of simulation

圖8為螢火蟲個體排成隊列向目標點運動的狀態(tài)。在螢火蟲感知觸須的探測下，每只螢火蟲總是很有秩序地自覺排列在比其亮度高的螢火蟲后面，并遵循最大安全距離的約束，實現了排列行為和個體的自我碰撞檢測和避免。從多次實驗的整個運行過程看，本文設計的仿真方案很好地模擬了群體在遷徙過程中自覺排成隊列這一群體行為。

以上實驗結果表明：本文設計的基于速度力的螢火蟲改進算法，對動物在遷徙過程中呈現的聚集和排列的群體行為進行了仿真，有效解決了個體之間的自我碰撞檢測和避免。群體行為表現為群體的整體運動行為和個體的運動行為，而螢火蟲算法是一種智能算法，螢火蟲個體具有智能性，每個個體通過自己的運動行為，自下而上地影響整個群體的運動行為，因此整個群體的運動行為具有隨機性。為此，仿真程序設計了路徑導出功能，選擇一次滿意的仿真實驗，將個體的路徑數據導出，使用MAYA的路徑動畫技術制作群體動畫。也可以使用MAYA的粒子系統(tǒng)和MEL腳本實現本文設計的方案，在MAYA中進行仿真，選擇滿意的一次實驗渲染輸出制作群體動畫。

5 結束語

為了仿真模擬生物群體在遷徙時涌現的聚集和自覺排列行為，基于螢火蟲算法思想，使用速度力的方式實現螢火蟲個體的位置更新計算，并給每只螢火蟲個體設計感知觸須，通過感知觸須的探測，控制亮度低的螢火蟲在最大安全距離閾值范圍內向亮度高的螢火蟲移動，當超出最大安全距離時，將其速度縮放一定比例，從而避免個體之間的穿插和碰撞，實現了個體排列行為的模擬。為了提高群體動畫的真實性，在仿真平臺中設計添加了環(huán)境障礙物。仿真實驗結果表明，該方案逼真地模擬了生物群體在遷徙時涌現的聚集及自覺排列行為，有效解決了群體的自碰撞穿插問題，在群體動畫制作中具有較好的推廣應用價值。

[1] 饒云波,陳雷霆,周駿,等.計算機群體動畫中的真實感行為綜述[J].計算機應用,2010,30(3):571-578.

RAO Yunbo,CHEN Leiting,ZHOU Jun,et al.Survey on realistic behavior in crowd animation[J].Joumal of Computer Applications,2010,30(3):571-578.

[2] 余魚.動物們的整齊隊列[J].大科技.科學之謎,2011(10):1.

YU Yu.Queue of Animals[J] Super Science-Mystery of Science,2011(10):1.

[3] 程美英,倪志偉,朱旭輝.螢火蟲優(yōu)化算法理論研究綜述[J].計算機科學,2015,42(4):19-24.

CHENG Meiying,NI Zhiwei,ZHU Xuhui.Overview on Glowworm Swarm Optimization or Firefly Algorithm[J].Computer Science,2015,42(4):19-24.

[4] YANG X S,Nature-Inspired Metaheuristic Algorithms[M].[S.l.]：Luniver press,2010.

[5] 白永珍.基于參數方差調節(jié)螢火蟲算法的三維路徑規(guī)劃[J].計算機系統(tǒng)應用,2015,34(5):92-99.

BAI Yongzhen.Three-Dimensional Path Planning Based on Parameter Variance Adjustment Firefly Algorithm[J].Computer Systems & Applications,2015,34(5):92-99.

[6] 晁素娜,劉弘,張鵬.基于改進螢火蟲算法的人群疏散仿真[J].山東師范大學學報(自然科學版),2015,30(1):33-37.

CHAO Suna,LIU Hong,ZHANG Peng.Crowd Evacuation Simulation Based on Improved Glowworm Swarm Optimization Algorithm[J].Journal of Shandong Normal University (Natural Science),2015,30(1):33-37.

[7] 王沈娟,高曉智.螢火蟲算法研究綜述[J].微型機與應用,2015,34(8):8-11.

WANG Shenjuan,GAO Xiaozhi.A survey of research on firefly algorithm[J].Microcomputer & ITS Applications,2015,34(8):8-11.

[8] 劉長平,葉春明.具有混沌搜索策略的螢火蟲優(yōu)化算法[J].系統(tǒng)管理學報,2013,4(7):538-543.

LIU Changping,YE Chunming.Firefly Algorithm with Chaotic Search Strategy[J].Journal of System & Management,2013,4(7):538-543.

[9] REYNOLDS C.Steering behaviors for autonomous characters[C].In:Game Developers Conference,1999:763-782.

[10]鄭延斌,劉晶晶,王寧.基于智能算法的群體動畫設計與實現[J].中原工學院學報,2013,24(4):26-30.

ZHENG Yanbin,LIU Jingjing,WANG Ning.Design and Implementation of Group Animation Based on Intelligent Optimization Algorithm[J].Journal of ZhongYuan University of Technology,2013,24(4):26-30.

[11]方彬,王竹林,郭希維.基于AABB的四維時空層次包圍盒碰撞檢測方法[J].計算機測量與控制,2014,22(2):397-399,420.

FANG Bin,WANG Zhulin,GUO Xiwei.Four-Dimessional Space and Time Hierarchical Collision Detection Method Based on AABB Bounding Box[J].Computer Measurement & Control,2014,22(2):397-399,420.

(責任編輯 楊文青)

The Simulation Design of Crowd Animation Behavior Control Based on Firefly Algorithm

ZHANG Chao, WEI San-qiang, CHEN Wei

(Department of Computer Information, Suzhou Vocational and Technological College,Suzhou 234101, China)

Many organisms are always automatically gathering and consciously queuing in migration in the nature. In order to simulate this interesting flock movement and make the crowd animation, the author designs a simulation program based on the deep research of firefly algorithm (FA). According to the firefly algorithm, this program employs velocity force to calculate the firefly individual position update and designs a perception feeler for each firefly, in order to control the low brightness firefly to follow the range of threshold of the maximal secure distance while moving toward the high brightness one. When the maximal secure distance is about to go beyond the toplimit, the plan zooms the speed on a scale, thus it will always make the low brightness individual follow the high brightness one, and avoid the individuals’ intersection and collision. The simulation experiment platform was developed with Flash Develop and ActionScript3.0 device. The simulation experiment results show that it vividly simulates the biological groups’ consciousness of gathering and queuing behaviors, which can effectively resolve the self-collision problem in making crowd animation.

crowd animation; firefly algorithm; collision detection and avoidance; group behavior; intelligence algorithm

2016-10-18

安徽省高校省級自然科學基金重點資助項目(KJ2016A781,KJ2016A778)；安徽省高校省級質量工程項目(2015jyxm512, 2014jxtd065)；宿州市“551”產業(yè)創(chuàng)新團隊項目(宿人才2014[2]號)

張超(1980—)，男，安徽宿州人，碩士，講師，主要從事智能算法、動漫設計與制作方向的研究,E-mail:zc2001888@163.com；魏三強(1980—)，男，安徽宿州人，博士研究生，副教授，主要從事高效能算法、信息安全研究, E-mail:121165708@qq.com。

張超，魏三強，陳偉.一種基于螢火蟲算法的群體動畫行為控制仿真設計[J].重慶理工大學學報(自然科學)，2017(1):100-106.

format：ZHANG Chao, WEI San-qiang, CHEN Wei.The Simulation Design of Crowd Animation Behavior Control Based on Firefly Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2017(1):100-106.

10.3969/j.issn.1674-8425(z).2017.01.016

TP391.72；TP18

A

1674-8425(2017)01-0100-07