群體動畫路徑規(guī)劃方法研究

董哲++蔡瓊++胡潔

摘 要：傳統(tǒng)動畫制作軟件大多采用關(guān)鍵幀技術(shù)進行創(chuàng)作，所創(chuàng)作的群體動畫在真實性和智能性上存在一定不足。為使群體動畫產(chǎn)生逼真的運動路徑，采用碰撞檢測和碰撞避免的方法模擬群體運動，并基于微粒群算法提出一種群體動畫路徑自動規(guī)劃方法。仿真實驗結(jié)果表明，該方法能夠改變?nèi)后w動畫運動路徑，快速有效地生成群體動畫。

關(guān)鍵詞：群體動畫；微粒群算法；路徑規(guī)劃

DOIDOI：10.11907/rjdk.151601

中圖分類號：TP301

文獻標識碼：A 文章編號文章編號：16727800（2015）009003004

0 引言

人們經(jīng)常觀察到自然界的群體運動現(xiàn)象，比如螞蟻搬家、一群蜜蜂來到花叢中采蜜、候鳥遷徙、羊群遭遇危險集體竄逃等。這些群體運動中的單個個體看上去行為自由、表現(xiàn)隨機且不受周圍環(huán)境干擾；但反觀由單個個體組成的整體，它們卻能夠朝著共同的目標方向前進，而且在前進過程中維持相對的距離，個體與個體之間有很好的交互性。群體動畫[1]是群體行為動畫的簡稱，是群體智能的一種應(yīng)用表現(xiàn)，主要用來研究和模擬群體與環(huán)境之間以及群體中個體之間的互動行為。多媒體數(shù)字處理技術(shù)和計算機圖形學(xué)技術(shù)的飛速發(fā)展，以及計算機硬件成本的不斷降低，推動了群體動畫技術(shù)的發(fā)展和應(yīng)用。

群體動畫是動漫產(chǎn)業(yè)中的一個特殊成員，它具有大規(guī)模的群體數(shù)量、逼真的群體仿真效果，以及創(chuàng)作難度大且成本相對較高等特點。群體動畫在游戲、娛樂、教育、軍事模擬、虛擬現(xiàn)實等多個領(lǐng)域發(fā)揮著重要作用。Chenney借助于勢場和能量場提出了一種稱作流動條目的技術(shù)，用來代表和設(shè)計流動場，并且提供了大城市街道上人群模擬的應(yīng)用實例。而WeiShao等在深入研究自主人體行為控制后，提出了一種新的模擬人群運動的控制方法，將自主行

人的感知模塊分為靜態(tài)感知序列圖和動態(tài)感知序列圖兩個部分，并通過發(fā)放射線的方法感知外界環(huán)境，最后對車站人群運動進行模擬實驗，驗證了該方法的有效性。

群智能算法起初針對群體運動，為了能夠更好地模擬群體運動，使得在群體動畫中產(chǎn)生出更加逼真的運動路徑。本文對微粒群算法進行研究和改進，并將其應(yīng)用于群體動畫的路徑規(guī)劃中。

1 基本特征和基本規(guī)則

目前，關(guān)于群體行為還沒有一個嚴格的定義，但人們對群體行為的特點已達成共識：①簡單性。單個個體的智能程度相對簡單；②自組織性。通過每個個體的獨立行為表現(xiàn)出群體行為的整體特性，群體中的單個個體運動看起來是隨機的，但就整個群體而言，卻是整體一致的；③魯棒性。單個個體的行為變化對整個群體的行為不會產(chǎn)生特別大的影響。

由于追求的是整個群體效應(yīng)，如果要對整個群體動畫進行模擬實驗，單一個體運動時，會受到自身群體中其它單個個體運動路線的干擾，所以制作群體動畫時應(yīng)該充分考慮如下規(guī)則：①群體中的單一個體應(yīng)該有屬于自己的運動區(qū)域，一旦剩余的單獨個體進入此運動區(qū)域，那么單一個體本能地會保持固有距離，以保持單一個體的運動區(qū)域不被其他個體侵占，從而避免個體之間相互干擾帶來的碰撞；②從整體性來看，整個群體中的個體與其它個體應(yīng)該朝同一個方向、同一個目標運動，具有統(tǒng)一性；③比較大的群體而言，應(yīng)當(dāng)細分成幾個比較小的群體，而且每一個小的群體通過自身條件判斷應(yīng)該與相鄰的比較小的群體重新組建成一個比較大的群體。

2 群體動畫中的關(guān)鍵問題

對群體動畫的模擬需要注意以下兩個關(guān)鍵問題：

（1）加大運動路徑逼真程度。在群體動畫中使個體運動軌跡既符合各自運動的獨立性又能合乎群體運動規(guī)律，進而能夠產(chǎn)生逼真的運動路徑，這是檢測判斷群體運動真實性的標準[2]，在產(chǎn)生運動路徑時，如何避免個體間的相互碰撞至關(guān)重要。

（2）提高群體運動速度。不能因為某一個體的速度而限制整體的運動速度，為更加強調(diào)群體的智能性，很大程度上增加了計算量，進而影響了動畫創(chuàng)作的實時性，影響了動畫的生成速度。

3 微粒群算法

微粒群算法是一種群智能優(yōu)化算法，通過對環(huán)境的適應(yīng)性進行評估，將群體中的一些個體移動到較好區(qū)域，強調(diào)群體效果模型。在人工生命模型開發(fā)和應(yīng)用中，群體智能很多優(yōu)點的實現(xiàn)都需要借助粒子群算法的思想。在研究過程中，如果需要將整個群體中的某些成員描述為沒有重量、沒有體積，而且還要描述這些成員的運動方向及運動速度等，就需要引入“粒子”概念代替這些描述。針對上述問題，使用微粒來表示某一個隱含的解，這意味著每一個微粒存在一個通過優(yōu)化函數(shù)決定的適應(yīng)值，并且可以自定義速度，通過計算速度差值選擇偏離的路線。設(shè)置pbest為單個個體的極限值，表示微粒剛剛經(jīng)過的最優(yōu)化解；使用gbest為全局極限值，表示所有種群當(dāng)前的最優(yōu)解，通過這兩個極值來更新其位置和速度，使實驗的微?？梢愿櫘?dāng)前的最優(yōu)微粒，找到自己的區(qū)域，并且落在最優(yōu)位置上。不斷循環(huán)這一過程，最終達到預(yù)期目的，找到最優(yōu)解。

在整個求解過程中，應(yīng)該首先明確局部和全局在整個搜索過程中所占比例，提出一種帶有權(quán)重的改進微粒群算法，其方程如下：

vij（t+1）=wvij（t）+c1r1j（t）[pij（t）-xij（t）]+c2r2j（t）[pgj（t）-xij（t）]（1）

xij（t+1）=xij（t）+vij（t+1）（2）

其中，j=1，2，...，n； i=1，2，.....s； t表示迭代次數(shù)，w為慣性權(quán)重，如果w的值比較小，則局部的收斂能力會比較強，收斂速度可能會慢些，一旦w值逐漸增大，則會導(dǎo)致全局收斂能力比較強，而且收斂的速度也會變得很快。式（1）中，定義兩個加速常數(shù)C1和C2，微粒能夠通過自身條件判斷尋找更合適的位置；為了使群體多樣化，可以設(shè)定兩個隨機函數(shù)a1、a2；微粒根據(jù)自身的環(huán)境適應(yīng)性以及與其它鄰近微粒之間的信息交流動態(tài)地調(diào)整自身速度，最終全部在最優(yōu)點上降落。由于粒子的速度沒有可控性，Vij設(shè)置在固定值內(nèi)。

4 路徑規(guī)劃

本文改變算法中的步驟和參數(shù)，并將修改的參數(shù)應(yīng)用到路徑規(guī)劃中，使其生成效果更加真實的路徑，為群體動畫中的角色找到一條最好的運動路徑，是群體動畫模擬研究中的關(guān)鍵。

4.1 碰撞檢測

關(guān)于碰撞的例子生活中較常見，比如汽車發(fā)生正面碰撞，發(fā)動機能夠吸收沖擊力下沉脫出發(fā)動機艙，提升車輛應(yīng)對沖擊時的安全性能。針對碰撞情況，采用相應(yīng)的防范措施必不可少。

碰撞檢測算法的種類很多，主要有如下幾類：基于空間剖分的碰撞檢測法、基于特征的碰撞檢測法和基于包圍盒碰撞檢測法[3]。

由于本文探討的是單一粒子運動情形，不需要外部干擾，采用基于包圍盒碰撞檢測方法，使用圓柱體的包圍盒，使得碰撞檢測過程更加簡便。檢測過程中主要對距離進行計算。包圍障礙物圓柱體的圓心位置用position[k]表示，粒子新變化后的新位置用y[k]表示，其中y為k維向量，粒子的運動過程是隨機的，粒子與障礙物之間設(shè)置一個距離值為d，如式（3）所示：

d=∑ki=1（x[i]-position[i]）2（3）

受實驗條件限制，本文實驗系統(tǒng)設(shè)置為3維，所以令k值為3，針對碰撞設(shè)定一個碰撞條件：粒子與障礙物之間的距離小于粒子半徑與障礙物半徑之和。很明顯，當(dāng)粒子半徑或者障礙物半徑足夠大時，粒子飛不過去，必然會發(fā)生碰撞。相應(yīng)地，粒子相互之間的碰撞檢測條件：兩個粒子的半徑之和大于飛躍障礙物的空間，公式如下：

d=∑ki=1（x1[i]-x2[i]）2（4）

個體在運動過程中難免會發(fā)生穿透現(xiàn)象，針對個體的運動步長進行調(diào)整，則不會看到穿透現(xiàn)象。由圖1可知，根據(jù)粒子群算法得到下一個粒子將要落入的位置A′，粒子一開始在點A處，連接A到A′的距離，可以看到在點A′的位置上，A′O的距離已經(jīng)大于圓的半徑，也即粒子和障礙物之間的距離相對大一些，不滿足碰撞條件，則不會發(fā)生碰撞；但是通過AA′的虛線連線可以明顯地看到發(fā)生碰撞，那么僅僅對步長作出調(diào)整在某些階段可以使粒子不會發(fā)生穿透。然而，在大多情況下如果步長限制過小是不科學(xué)的，甚至?xí)l(fā)生某些異常情況。本文通過對兩個夾角大小的檢測來避免發(fā)生穿透。

從圖1可以看出，當(dāng)β>α?xí)r，粒子可以穿透到障礙物的另一側(cè)，當(dāng)β<α?xí)r，粒子不能穿透到障礙物的另一側(cè)。實驗中，為看到明顯的檢測變化，可以設(shè)置另外一個點A″，如果按照之前設(shè)定的檢測方法和條件來判斷，粒子會穿透過去，不會產(chǎn)生規(guī)避，如此進行下去會增大失誤率，不能帶來高效的探測效果。對本實驗的碰撞方法性能進行分析，設(shè)算法時間復(fù)雜度為O（n2）。實驗?zāi)M中，為了達到更好的效果將粒子數(shù)目設(shè)定在55左右，當(dāng)障礙物的數(shù)量小于35時，可以看到非常真實的仿真效果，基本上能夠達到理想實驗效果。

圖1 夾角大小比較

f（x）=沒有發(fā)生穿透，AA″

發(fā)生穿透，AA″≥AB（5）

4.2 碰撞避免

碰撞避免的策略雖有多種，但從根本上無非是等待和轉(zhuǎn)向兩種，其它碰撞避免策略都是在這兩種策略上進行深化或者改進得到。（1）等待法。顧名思義，就是等待另一運動個體先行通過，該方法適用于追尾碰撞和側(cè)面碰撞。在追尾碰撞時，后一障礙物可以先停止運動，等待前一障礙物運動到出口位置或者目標點再繼續(xù)運動；在側(cè)面碰撞時，其中一個障礙物可以等待另一障礙物運動過碰撞點后再按照先前運動方向繼續(xù)運動。（2） 轉(zhuǎn)向法。正面碰撞時，在未來某一時點必然相撞，可以計算出一旦無碰撞，則向該方向運動；追尾碰撞時，如果前一障礙物運動速度過慢，而后面障礙物運動速度過快，使用等待法不切合實際，后一障礙物可以轉(zhuǎn)向另一無碰撞方向運動；側(cè)面碰撞時可以通過該方法轉(zhuǎn)向任一無碰撞方向來避免。

為了提升動畫的真實美感，借鑒上述兩種碰撞避免方法?？煽吹綀D1中存在兩條邊界切線，試想粒子如果在邊界線外繞過則不會發(fā)生碰撞，為了不讓粒子發(fā)生穿透，則需要改變運動粒子的方向，可以設(shè)定為粒子連著邊界線移動。

將點A定為起點， G定為終點，如果AA2與AG的夾角大于AA1與AG之間的夾角，通過在AA1上改變下一個定點位置，如果AA1與AG之間的夾角大于AA2與AG兩條線之間的夾角，則應(yīng)該在AA2上改變下一個定點位置?？赏ㄟ^縮小步長的策略來解決粒子與粒子之間的碰撞，一旦啟動停止模式，所有粒子都會靜止。通過對大規(guī)模粒子進行路徑研究，具體示例變化如圖2所示，從左至右依次為初始化效果，中間為運行多代后的效果，最右邊為自由運動路線，可以看出該方法的效果。

4.3 分散和聚集行為運動

群體的分散運動在大自然中隨處可見，比如當(dāng)羊群受到攻擊時四處逃竄。微粒群算法作為群體算法的一種，對群體分散運動路徑規(guī)劃的研究具有重要價值[4]，本文主要對算法中計算適應(yīng)度值（app）的方法作出修改。

圖2 粒子運動軌跡

app=（x-gx）2+（y-gy）2+（z-gz）2 （6）

其中，（x，y，z）表示離子的當(dāng)前位置，分散時的初始起點用坐標點（gx，gy，gz）表示。根據(jù)公式可以計算出粒子的確切位置以及運行速度，粒子可以定向移到很遠。分散行為的算法應(yīng)用如下：

進行初始化，首先設(shè)定起點位置，并設(shè)定粒子個數(shù)、群體的迭代次數(shù)，以及粒子最初軸線的范圍加速常數(shù)c1、c2等。

while（當(dāng)前迭代次數(shù)未達到提前設(shè)定的最大次數(shù)）{

Step1：選擇每個粒子的目標位置，計算每個粒子新位置的app值，對每個粒子進行計算，若粒子的app值優(yōu)于原來的個體極限值pbest，那么設(shè)置當(dāng)前app值為個體的極限值pbest；Step2：由粒子的個體極限值pbest的計算結(jié)果找出全局極值；Step3：更新微粒速度并將更新后的速度值限制在最大設(shè)定值內(nèi)；Step4：采取碰撞檢測方法，若發(fā)生碰撞情形，則實行相應(yīng)的避免策略；Step5：重新設(shè)定原來的位置和速度；}

聚集行為是一種普遍存在的生物運動行為，聚集算法同樣采用微粒群方法。由于聚集行為與分散行為是兩個相對層面，因此可以使用一種對立的計算公式，設(shè)定一個警示值h，讓最終的落點成為中心，以警示值h為半徑，所有落入該半徑內(nèi)的點都可為靜止狀態(tài)，并且通過改變app值，使得粒子分散開來，防止集中在某一點上，同樣，參數(shù)坐標值設(shè)定如下：

app=（x-gx）2+（y-gy）2+（z-gz）-rand（h）（7）

4.4 仿真實驗

借助于Visual Studio 2008和ACIS等平臺，同時采

用HOOPs框架模型，將路徑規(guī)劃產(chǎn)生的數(shù)據(jù)導(dǎo)入Maya 軟件中，根據(jù)變化的場景和不同的動畫效果來完成仿真實驗?zāi)M。實驗結(jié)果如圖3所示，圖3（a）是通過讀取數(shù)據(jù)生成的路徑曲線圖，圖3（b）是動畫與場景相互融合的圖形，圖3（c）是最終生成的動畫效果。

圖3 仿真效果

5 結(jié)語

本文對群體動畫路徑規(guī)劃方法進行了研究，并對微粒群算法的系列參數(shù)作出了調(diào)整。實驗結(jié)果表明，改進后的方法相對于傳統(tǒng)的基于關(guān)鍵幀技術(shù)的方法而言，能夠更好地提高群體動畫的生成效率，進一步提高真實程度。后續(xù)研究中，將進一步研究其它群體算法優(yōu)勢，以找出更有效的方法運用于群體動畫中。

參考文獻參考文獻：

[1] 涂曉媛.人工魚計算機動畫的人工生命方法[M].北京：清華大學(xué)出版社，2001：610.

[2] 魏麗.群體動畫中路徑自動規(guī)劃方法研究[J].計算機工程與應(yīng)用，2012（25）：8387.

[3] 張淑軍，班曉娟，陳勇，等.基于記憶的人工魚認知模型[J].計算機工程，2007（19）：56.

[4] 鄭慧杰，劉弘，鄭向偉.基于改進群搜索優(yōu)化算法的群體路徑規(guī)劃方法[J].計算機應(yīng)用，2012（8）：1013.

責(zé)任編輯（責(zé)任編輯：陳福時）