摘  要： 人工魚群算法是一種新型仿生優(yōu)化算法，著重構(gòu)造自治體尋優(yōu)模型，其研究應(yīng)用已經(jīng)滲透到多個領(lǐng)域。對人工魚群算法模型進行深入研究，并對其實施優(yōu)化和擴展用于構(gòu)建游戲動力系統(tǒng)，為游戲AI運動引擎的設(shè)計與實現(xiàn)提供技術(shù)與理論參考。
關(guān)鍵詞： 人工魚群算法；動力系統(tǒng)；人工智能；搜索行為

　人工智能技術(shù)在游戲設(shè)計中的應(yīng)用越來越廣泛，已經(jīng)成為游戲設(shè)計成功與否的關(guān)鍵因素。游戲角色的運動控制是游戲AI設(shè)計中的核心問題之一。復(fù)雜的游戲角色運動行為需要創(chuàng)建一個由多種不同規(guī)則和方法組成的游戲動力系統(tǒng)來實現(xiàn)控制。一個智能游戲動力系統(tǒng)可以為不同角色提供動力，這些動力用于影響角色的行為方式，完成游戲角色既定的各種任務(wù)行為。例如，包括漫游、追捕、搜尋、規(guī)避、群體等行為。本文對人工魚群算法模型進行深入研究，并對其實施優(yōu)化和擴展用于構(gòu)建一個游戲動力系統(tǒng)，從而為游戲AI運動引擎的設(shè)計與實現(xiàn)提供技術(shù)與理論參考。
1 游戲動力系統(tǒng)
　動力系統(tǒng)[1]是一個數(shù)學(xué)概念，始于19世紀末龐加萊常微分方程定性理論的研究。在動力系統(tǒng)中存在一組固定的規(guī)則，描述了幾何空間中的一個點隨時間變化的情況。在動力系統(tǒng)中以狀態(tài)的概念描述一個對象，狀態(tài)是一組可以被確定下來的實數(shù)。對象狀態(tài)的微小變動對應(yīng)這組實數(shù)的微小變動。這組實數(shù)也是一種流形的幾何空間坐標。動力系統(tǒng)的演化規(guī)則是一組函數(shù)的固定規(guī)則，它描述未來狀態(tài)如何依賴于當(dāng)前的狀態(tài)。這種規(guī)則是確定性的，即對于給定的時間間隔內(nèi)，從現(xiàn)在的狀態(tài)只能演化出一個未來的狀態(tài)。例如描述天體的運動、河流中水的流動、湖中不同季節(jié)魚的數(shù)量，凡此等等的數(shù)學(xué)模型都屬于動力系統(tǒng)。
　游戲動力系統(tǒng)其核心思想是基于動力系統(tǒng)的數(shù)學(xué)模型，是動力系統(tǒng)應(yīng)用研究的實例，也是游戲引擎的重要組成部分。電子游戲需要創(chuàng)造一個虛擬的游戲環(huán)境世界，讓游戲?qū)ο笤谔摂M環(huán)境中進行信息交互、運動碰撞從而產(chǎn)生了游戲性。游戲環(huán)境及對象都是建立在對現(xiàn)實世界抽象和仿真的基礎(chǔ)上。游戲動力系統(tǒng)就是為游戲世界中對象運動提供的數(shù)學(xué)模型。游戲動力系統(tǒng)利用不同的規(guī)則來約束游戲?qū)ο蟛煌臓顟B(tài)運動，如圖1所示。游戲動力系統(tǒng)的優(yōu)劣在于約束規(guī)則劃分是否合理，其對應(yīng)設(shè)計的運動控制算法能否具有低耗性和高效性。

2 基本人工魚群算法（AFSA）[2]
　在一個特定的水域中，魚往往根據(jù)區(qū)域食物的濃度和魚群的密度選擇游向，魚數(shù)量與食物濃度成正比關(guān)系。AFSA算法就是根據(jù)這一自然現(xiàn)象建立數(shù)學(xué)模型，模仿魚群的覓食、追尾、聚群和隨機等行為，從而實現(xiàn)特定環(huán)境下對象尋優(yōu)運動。
　AFSA算法最早是由李曉磊博士于2002年提出的，此算法以一個多維向量X=（x1，x2，x3，…，xn）定義人工魚個體的狀態(tài)，xi（i=1，2，...，n）是向量X的的第i個分量，分別作為各條魚在尋優(yōu)過程中的變量。人工魚當(dāng)前位置的食物濃度表示為Y=f（x），如i和j為隨機的兩條魚，則它們的距離表示為Di，j=║xi-xj║，Visual表示人工魚的感知范圍，Step表示人工魚移動的步長，δ表示擁擠度因子，N為魚群中魚的數(shù)目。具體行為描述如下：
　（1）覓食行為[3]。在人工魚當(dāng)前狀態(tài)xi的Visual距離鄰域內(nèi)搜索出更優(yōu)的解，則向該位置前進一步，如果經(jīng)過trynum次搜索，無法找到更優(yōu)的解，則執(zhí)行隨機行為。
?。?）聚群行為。若發(fā)現(xiàn)人工魚當(dāng)前狀態(tài)xi的Visual距離鄰域內(nèi)中心位置的食物濃度更高且不太擁擠，則向中心位置前進。
?。?）追尾行為。搜索人工魚當(dāng)前狀態(tài)xi的Visual距離鄰域內(nèi)伙伴的最優(yōu)解，如果發(fā)現(xiàn)該位置的食物濃度Y值更高且不太擁擠，則向其前進一步。
　（4）隨機行為。人工魚在Visual距離鄰域中隨機選擇一個狀態(tài)，然后向該方向移動，它是覓食行為的一個缺省行為。
　（5）約束行為。在尋優(yōu)過程中，若出現(xiàn)無效狀態(tài)，就需要加入相應(yīng)的約束來對其進行調(diào)整，由無效狀態(tài)或不可行狀態(tài)轉(zhuǎn)變成可行的。
?。?）公告板。記錄當(dāng)前對象所屬的類和當(dāng)前最優(yōu)的函數(shù)值，若發(fā)現(xiàn)當(dāng)前對象聚類要求達到滿意值，則可以停止搜索。
?。?）選擇策略。根據(jù)獲得更優(yōu)解的原則選擇合適的行為方式，即只要任何一種行為能夠得到比當(dāng)前更優(yōu)的解，則選擇該種行為。
　AFSA算法采用自下而上的設(shè)計方法，著重構(gòu)造自治體尋優(yōu)模型，該模型對實現(xiàn)游戲動力系統(tǒng)仿真自治運動效果良好。AFSA算法的行為方式為實現(xiàn)游戲動力系統(tǒng)的行為提供依據(jù)?？梢?，AFSA算法的數(shù)學(xué)模型可以作為構(gòu)建游戲動力系統(tǒng)的基礎(chǔ)。
3 優(yōu)化AFSA構(gòu)建游戲動力系統(tǒng)
　游戲動力系統(tǒng)中的對象具有自治性、交互性、多樣性的特點，基本AFSA算法對決定對象交互性和多樣性運動的控制不夠理想。例如，玩家控制游戲?qū)ο蟮哪承┻\動行為以及對象在特定任務(wù)下的復(fù)雜運動方式，AFSA算法的行為模型很難滿足其要求。可見，要利用AFSA算法構(gòu)建完整的游戲動力系統(tǒng)，需要對基本AFSA算法進行優(yōu)化和擴展。

3.3 聚群與追尾行為的優(yōu)化與擴展
　基本AFSA算法的聚群和追尾行為是緊密聯(lián)系的，其構(gòu)建的模型需要對象遵守局部相互作用的規(guī)則，分別是：（1）分離。盡量避免與臨近伙伴過于擁擠；（2）排隊。調(diào)整相鄰對象的平均速度；（3）內(nèi)聚。盡量朝臨近伙伴的中心移動。這些規(guī)則為實現(xiàn)游戲動力系統(tǒng)群體行為奠定了良好的基礎(chǔ)。聚群行為是建立在食物濃度差異的基礎(chǔ)上的，所以在動力系統(tǒng)中可以主動動態(tài)改變環(huán)境食物濃度值來實現(xiàn)群體的運動變化。此外，設(shè)置不同類型的對象適應(yīng)不同的食物，這樣可以通過控制不同食物濃度來實現(xiàn)多種群的運動。
　此外，可以通過建立領(lǐng)頭對象實現(xiàn)群體運動。領(lǐng)頭對象是群體運動的核心和領(lǐng)導(dǎo)，具有最高碰撞級別，無需執(zhí)行運動對象規(guī)避行為，其Ymax具有最高值。其他對象需向領(lǐng)頭對象靠近執(zhí)行追尾行為并遵守分離和排隊等規(guī)則，而且不能阻擋領(lǐng)頭對象的路徑，若對象處在領(lǐng)頭對象速度的前方要先執(zhí)行規(guī)避行為。
　動力系統(tǒng)是游戲引擎的重要組成部分，其核心AI算法跟一般程序的算法要求不同的是，除了要考慮時間復(fù)雜度與空間復(fù)雜度的因素，還要滿足游戲仿真性、交互性、可玩性等要求。本文在對人工魚群算法進行優(yōu)化和擴展的基礎(chǔ)上構(gòu)建一個簡單的游戲動力系統(tǒng)，對幾種動力模型進行了分析研究。對相關(guān)游戲程序設(shè)計具有一定的應(yīng)用參考價值。
參考文獻
[1] ROBINSON R C.動力系統(tǒng)導(dǎo)論[M].北京：機械工業(yè)出版社，2007.
[2] 李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法[D].杭州：浙江大學(xué)，2003.
[3] 蘇錦旗，吳慧欣，薛惠鋒.基于人工魚群算法的聚類挖掘[J].計算機仿真，2009，26（2）：147-150.
[4] PETERS K. Flash ActionScript3.0動畫高級教程[M].北京：人民郵電出版社，2010.
[5] STAHLER W.游戲編程數(shù)學(xué)和物流基礎(chǔ)[M].北京：機械工業(yè)出版社，2008.