摘 要： 人工魚群算法是一種新型仿生優化算法，著重構造自治體尋優模型，其研究應用已經滲透到多個領域。對人工魚群算法模型進行深入研究，并對其實施優化和擴展用于構建游戲動力系統，為游戲AI運動引擎的設計與實現提供技術與理論參考。
關鍵詞： 人工魚群算法；動力系統；人工智能；搜索行為
人工智能技術在游戲設計中的應用越來越廣泛，已經成為游戲設計成功與否的關鍵因素。游戲角色的運動控制是游戲AI設計中的核心問題之一。復雜的游戲角色運動行為需要創建一個由多種不同規則和方法組成的游戲動力系統來實現控制。一個智能游戲動力系統可以為不同角色提供動力，這些動力用于影響角色的行為方式，完成游戲角色既定的各種任務行為。例如，包括漫游、追捕、搜尋、規避、群體等行為。本文對人工魚群算法模型進行深入研究，并對其實施優化和擴展用于構建一個游戲動力系統，從而為游戲AI運動引擎的設計與實現提供技術與理論參考。
1 游戲動力系統
動力系統[1]是一個數學概念，始于19世紀末龐加萊常微分方程定性理論的研究。在動力系統中存在一組固定的規則，描述了幾何空間中的一個點隨時間變化的情況。在動力系統中以狀態的概念描述一個對象，狀態是一組可以被確定下來的實數。對象狀態的微小變動對應這組實數的微小變動。這組實數也是一種流形的幾何空間坐標。動力系統的演化規則是一組函數的固定規則，它描述未來狀態如何依賴于當前的狀態。這種規則是確定性的，即對于給定的時間間隔內，從現在的狀態只能演化出一個未來的狀態。例如描述天體的運動、河流中水的流動、湖中不同季節魚的數量，凡此等等的數學模型都屬于動力系統。
游戲動力系統其核心思想是基于動力系統的數學模型，是動力系統應用研究的實例，也是游戲引擎的重要組成部分。電子游戲需要創造一個虛擬的游戲環境世界，讓游戲對象在虛擬環境中進行信息交互、運動碰撞從而產生了游戲性。游戲環境及對象都是建立在對現實世界抽象和仿真的基礎上。游戲動力系統就是為游戲世界中對象運動提供的數學模型。游戲動力系統利用不同的規則來約束游戲對象不同的狀態運動，如圖1所示。游戲動力系統的優劣在于約束規則劃分是否合理，其對應設計的運動控制算法能否具有低耗性和高效性。
2 基本人工魚群算法（AFSA）[2]
在一個特定的水域中，魚往往根據區域食物的濃度和魚群的密度選擇游向，魚數量與食物濃度成正比關系。AFSA算法就是根據這一自然現象建立數學模型，模仿魚群的覓食、追尾、聚群和隨機等行為，從而實現特定環境下對象尋優運動。
AFSA算法最早是由李曉磊博士于2002年提出的，此算法以一個多維向量X=（x1，x2，x3，…，xn）定義人工魚個體的狀態，xi（i=1，2，...，n）是向量X的的第i個分量，分別作為各條魚在尋優過程中的變量。人工魚當前位置的食物濃度表示為Y=f（x），如i和j為隨機的兩條魚，則它們的距離表示為Di，j=║xi-xj║，Visual表示人工魚的感知范圍，Step表示人工魚移動的步長，δ表示擁擠度因子，N為魚群中魚的數目。具體行為描述如下：
（1）覓食行為[3]。在人工魚當前狀態xi的Visual距離鄰域內搜索出更優的解，則向該位置前進一步，如果經過trynum次搜索，無法找到更優的解，則執行隨機行為。
（2）聚群行為。若發現人工魚當前狀態xi的Visual距離鄰域內中心位置的食物濃度更高且不太擁擠，則向中心位置前進。
（3）追尾行為。搜索人工魚當前狀態xi的Visual距離鄰域內伙伴的最優解，如果發現該位置的食物濃度Y值更高且不太擁擠，則向其前進一步。
（4）隨機行為。人工魚在Visual距離鄰域中隨機選擇一個狀態，然后向該方向移動，它是覓食行為的一個缺省行為。
（5）約束行為。在尋優過程中，若出現無效狀態，就需要加入相應的約束來對其進行調整，由無效狀態或不可行狀態轉變成可行的。
（6）公告板。記錄當前對象所屬的類和當前最優的函數值，若發現當前對象聚類要求達到滿意值，則可以停止搜索。
（7）選擇策略。根據獲得更優解的原則選擇合適的行為方式，即只要任何一種行為能夠得到比當前更優的解，則選擇該種行為。
AFSA算法采用自下而上的設計方法，著重構造自治體尋優模型，該模型對實現游戲動力系統仿真自治運動效果良好。AFSA算法的行為方式為實現游戲動力系統的行為提供依據。可見，AFSA算法的數學模型可以作為構建游戲動力系統的基礎。
3 優化AFSA構建游戲動力系統
游戲動力系統中的對象具有自治性、交互性、多樣性的特點，基本AFSA算法對決定對象交互性和多樣性運動的控制不夠理想。例如，玩家控制游戲對象的某些運動行為以及對象在特定任務下的復雜運動方式，AFSA算法的行為模型很難滿足其要求。可見，要利用AFSA算法構建完整的游戲動力系統，需要對基本AFSA算法進行優化和擴展。
3.3 聚群與追尾行為的優化與擴展
基本AFSA算法的聚群和追尾行為是緊密聯系的，其構建的模型需要對象遵守局部相互作用的規則，分別是：（1）分離。盡量避免與臨近伙伴過于擁擠；（2）排隊。調整相鄰對象的平均速度；（3）內聚。盡量朝臨近伙伴的中心移動。這些規則為實現游戲動力系統群體行為奠定了良好的基礎。聚群行為是建立在食物濃度差異的基礎上的，所以在動力系統中可以主動動態改變環境食物濃度值來實現群體的運動變化。此外，設置不同類型的對象適應不同的食物，這樣可以通過控制不同食物濃度來實現多種群的運動。
此外，可以通過建立領頭對象實現群體運動。領頭對象是群體運動的核心和領導，具有最高碰撞級別，無需執行運動對象規避行為，其Ymax具有最高值。其他對象需向領頭對象靠近執行追尾行為并遵守分離和排隊等規則，而且不能阻擋領頭對象的路徑，若對象處在領頭對象速度的前方要先執行規避行為。
動力系統是游戲引擎的重要組成部分，其核心AI算法跟一般程序的算法要求不同的是，除了要考慮時間復雜度與空間復雜度的因素，還要滿足游戲仿真性、交互性、可玩性等要求。本文在對人工魚群算法進行優化和擴展的基礎上構建一個簡單的游戲動力系統，對幾種動力模型進行了分析研究。對相關游戲程序設計具有一定的應用參考價值。
參考文獻
[1] ROBINSON R C.動力系統導論[M].北京：機械工業出版社，2007.
[2] 李曉磊.一種新型的智能優化方法—人工魚群算法[D].杭州：浙江大學，2003.
[3] 蘇錦旗，吳慧欣，薛惠鋒.基于人工魚群算法的聚類挖掘[J].計算機仿真，2009，26（2）：147-150.
[4] PETERS K. Flash ActionScript3.0動畫高級教程[M].北京：人民郵電出版社，2010.
[5] STAHLER W.游戲編程數學和物流基礎[M].北京：機械工業出版社，2008.