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

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

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

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