張 超，魏三強(qiáng)，陳 偉

(宿州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)信息系，安徽 宿州 234101)

一種基于螢火蟲算法的群體動(dòng)畫行為控制仿真設(shè)計(jì)

張 超，魏三強(qiáng)，陳 偉

(宿州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)信息系，安徽 宿州 234101)

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

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

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

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

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

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

1 螢火蟲算法

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

1.1 螢火蟲算法的仿生原理

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

1.2 螢火蟲算法的數(shù)學(xué)描述和分析[3，7-8]

螢火蟲算法包含2個(gè)要素：亮度和吸引度。亮度體現(xiàn)了螢火蟲所處位置的優(yōu)劣并決定其移動(dòng)方向；吸引度決定了螢火蟲移動(dòng)的距離。通過亮度和吸引度的不斷更新可實(shí)現(xiàn)目標(biāo)優(yōu)化。數(shù)學(xué)描述如下：

定義1 亮度

(1)

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

定義2 吸引度

(2)

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

定義3 位置更新

螢火蟲i被吸引向螢火蟲j移動(dòng)的位置更新公式：

(3)

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

2 基于力的螢火蟲算法的改進(jìn)設(shè)計(jì)

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

2.1 基于力的位置更新計(jì)算

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

Position(new)=position(old)+velocity

(4)

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

(5)

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

2.2 亮度的計(jì)算

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

(6)

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

2.3 動(dòng)物遷徙時(shí)聚集和自覺排列行為模擬方案

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

2.3.1 聚集行為的模擬

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

2.3.2 排列行為的模擬

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

圖2 速度力計(jì)算演示圖Fig.2 Velocity force calculation

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

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

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

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

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

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

6) 轉(zhuǎn)到步驟3)進(jìn)行下一次迭代。

具體流程如圖3所示。

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

3 碰撞檢測和避免

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

3.1 碰撞檢測

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

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

圖4 碰撞檢測Fig.4 Collision detection

3.2 碰撞避免

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

4 群體動(dòng)畫的仿真實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)部署

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

5 結(jié)束語

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

[1] 饒?jiān)撇?陳雷霆,周駿,等.計(jì)算機(jī)群體動(dòng)畫中的真實(shí)感行為綜述[J].計(jì)算機(jī)應(yīng)用,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] 余魚.動(dòng)物們的整齊隊(duì)列[J].大科技.科學(xué)之謎,2011(10):1.

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

[3] 程美英,倪志偉,朱旭輝.螢火蟲優(yōu)化算法理論研究綜述[J].計(jì)算機(jī)科學(xué),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] 白永珍.基于參數(shù)方差調(diào)節(jié)螢火蟲算法的三維路徑規(guī)劃[J].計(jì)算機(jī)系統(tǒng)應(yī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ìn)螢火蟲算法的人群疏散仿真[J].山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),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].微型機(jī)與應(yīng)用,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)管理學(xué)報(bào),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]鄭延斌,劉晶晶,王寧.基于智能算法的群體動(dòng)畫設(shè)計(jì)與實(shí)現(xiàn)[J].中原工學(xué)院學(xué)報(bào),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的四維時(shí)空層次包圍盒碰撞檢測方法[J].計(jì)算機(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.

(責(zé)任編輯 楊文青)

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

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

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

張超，魏三強(qiáng)，陳偉.一種基于螢火蟲算法的群體動(dòng)畫行為控制仿真設(shè)計(jì)[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，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