用于游戲NPC路徑規(guī)劃的改進遺傳算法*

李井頌， 錢 謙,3, 孫銘會

(1.昆明理工大學(xué) 云南省計算機技術(shù)應(yīng)用重點實驗室，云南 昆明 650500；2.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；3.吉林大學(xué) 符號計算與知識工程教育部重點實驗室，吉林 長春 130012)

計算與測試

用于游戲NPC路徑規(guī)劃的改進遺傳算法*

李井頌1， 錢 謙1,3, 孫銘會2,3

(1.昆明理工大學(xué) 云南省計算機技術(shù)應(yīng)用重點實驗室，云南 昆明 650500；2.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；3.吉林大學(xué) 符號計算與知識工程教育部重點實驗室，吉林 長春 130012)

針對游戲非玩家控制(NPC)路徑規(guī)劃中傳統(tǒng)遺傳算法計算速度慢、正確率低等問題，設(shè)計了改進型遺傳算法。提出了最佳種群規(guī)模估計方法，設(shè)計了基于精英主義思想的遺傳算子。根據(jù)游戲地圖的特點，引入了基于啟發(fā)式深度優(yōu)先搜索的變異操作。與傳統(tǒng)遺傳算法以及其他學(xué)者的改進算法進行了對比實驗。實驗結(jié)果表明：算法能夠在保證正確率的前提下，提高計算速度，并且在多目標(biāo)的環(huán)境下同樣適用。

人工智能； 路徑規(guī)劃； 遺傳算法； 種群規(guī)模； 精英主義； 啟發(fā)式深度優(yōu)先搜索

0 引 言

計算出游戲非玩家控制(NPC)角色從起點到目標(biāo)點的最短路徑是游戲開發(fā)中最基本的問題。游戲NPC屬于智能Agent的一種，研究出快速且高效的尋徑方法,而且對于車輛路徑規(guī)劃[1]和機器人路徑規(guī)劃[2]以及最短路徑路由問題[3]都有重要的借鑒意義。游戲地圖一般存在多條從起點柵格到終點柵格的最短路徑。而遺傳算法由于其并行搜索方式，每次運行時一般可以得到不同的路徑，被廣泛用到游戲?qū)接嬎阒衃4～6]。

傳統(tǒng)遺傳算法存在計算速度慢、正確率低等諸多問題。因此，多位學(xué)者對其進行了改進。黎忠文等學(xué)者[4]提出了節(jié)點復(fù)雜度算子的概念。節(jié)點復(fù)雜度，即圖中邊的條數(shù)和節(jié)點個數(shù)平方的比越大代表可行走的區(qū)域越寬廣，采用較大的交叉率與變異率來避免陷入局部最優(yōu)解。此做法雖然提高了搜索成功率，但是增加了運行時間。孫寶林[7]和李擎[8]主要對遺傳算法中的傳統(tǒng)隨機變異進行了改進，使變異能夠朝著最優(yōu)解的方向進行，雖然縮短了求得最優(yōu)解所需的進化代數(shù)，但是計算速度并沒有明顯提高。

在遺傳算法中，種群規(guī)模越大，全局搜索能力就越強，但是速度也就越慢[9]，而遺傳進化代數(shù)與網(wǎng)絡(luò)規(guī)模相關(guān)性并不大[10]。故本文提出了一種最佳種群規(guī)模估計方法，期望使用的種群規(guī)模具有全局搜索性而又不浪費；設(shè)計了基于精英主義思想的遺傳算子，以保留種群中的優(yōu)秀個體；引入了基于啟發(fā)式深度優(yōu)先搜索的變異操作，以縮短進化到最優(yōu)解所需的迭代次數(shù)。

1 傳統(tǒng)遺傳算法游戲NPC路徑規(guī)劃

1.1 游戲地圖介紹

游戲地圖由多個圖層構(gòu)成，圖層?xùn)鸥癯１环Q為瓦片，每個瓦片都有自己的唯一坐標(biāo)(圖1)。在碰撞檢測層中，通過定義瓦片的“鍵——值”對定義該瓦片作為可通過節(jié)點還是障礙物節(jié)點。

圖1 游戲地圖示意

1.2 遺傳編碼與初始群體的生成

在遺傳編碼時，一般將瓦片的坐標(biāo)作為基因進行實數(shù)編碼，染色體的第一個基因為起點坐標(biāo)，最后一個基因為終點坐標(biāo)，中間的基因為路徑經(jīng)過的每一個瓦片的坐標(biāo)。

在生成染色體時，由起點出發(fā)，隨機選擇當(dāng)前結(jié)點的鄰居節(jié)點中的可通過節(jié)點，將其坐標(biāo)加入染色體，依此循環(huán)，直到找到目標(biāo)點為止，生成了一條染色體。重復(fù)上述操作，直到達到指定的種群規(guī)模。

1.3 遺傳操作

遺傳操作包括選擇、交叉、變異3種操作：1)選擇操作常用精英選擇方式，即用部分優(yōu)秀個體替換部分較差個體[11]。2)交叉操作首先找到兩父代染色體的共有基因集合，然后從中隨機選取基因作為交叉點進行交叉，從而避免了交叉后產(chǎn)生的子代染色體所代表的路徑不連通的現(xiàn)象。3)變異操作首先將父代染色體刪除，然后隨機生成一條新的染色體，作為子代染色體。

2 基于改進遺傳算法的游戲NPC路徑規(guī)劃

2.1 確定種群規(guī)模與遺傳算子的執(zhí)行順序

種群規(guī)模過大，會影響計算速度；過小，又會降低全局搜索能力。本文定義最佳種群規(guī)模bestpop的計算公式為

bestpop=[n/min{row,col}]

(1)

式中n為地圖的可通過節(jié)點數(shù)；row為地圖的行節(jié)點數(shù)；col為地圖的列節(jié)點數(shù)；min{row,col}表示行、列較小者的節(jié)點數(shù)；[ ]為四舍五入取整運算。式(1)中用行或列的較小者中的節(jié)點數(shù)作為分子，而不用行、列的平均節(jié)點數(shù)，目的是首要考慮搜索成功率，而把計算速度放在次要位置。

不同于傳統(tǒng)遺傳算法，為使交叉算子和變異算子更好地配合，本文將遺傳算子執(zhí)行順序設(shè)置為：選擇、變異、交叉。

2.2 設(shè)計適應(yīng)度函數(shù)

本文直接將染色體的長度定義為染色體的適應(yīng)度，即

fitness(xi)=distance(xi),i=1,2,...,M

(2)

式中xi為第i個個體，distance(xi)為第i個個體的長度，M為種群規(guī)模。相應(yīng)地調(diào)整進化規(guī)則：保留適應(yīng)度小的染色體，淘汰適應(yīng)度大的染色體。

2.3 生成初始種群

傳統(tǒng)遺傳算法在生成染色體時會產(chǎn)生環(huán)路，從而產(chǎn)生大量較差個體。初始群體的優(yōu)秀程度是提高算法時間效率的關(guān)鍵[12]，為了避免產(chǎn)生環(huán)路，采用文獻[13]的做法：凡是加入到染色體的節(jié)點，都做一個標(biāo)記，只有沒有被標(biāo)記過的節(jié)點才能被選作新的節(jié)點。同時又產(chǎn)生一個新的問題：由于加入到染色體的節(jié)點都做了標(biāo)記，如果生成染色體的過程中遇到了“死胡同”，程序?qū)o法退出“死胡同”。因此，首先判斷當(dāng)前基因鄰居節(jié)點中可行走的節(jié)點數(shù)是否為0。如果是，則從染色體中刪除當(dāng)前基因，再考察當(dāng)前基因的上一個基因。如圖2，生成染色體的過程中已經(jīng)走進了“死胡同”，此時節(jié)點D位于染色體頭部，節(jié)點D的鄰居節(jié)點中可行走的節(jié)點數(shù)為0，因此把節(jié)點D從染色體頭部刪除。繼而考察節(jié)點C，因為之前考察過節(jié)點D，已經(jīng)對節(jié)點D做了標(biāo)記，故節(jié)點C的鄰居節(jié)點中可行走的節(jié)點數(shù)也為0，繼續(xù)刪除，直到考察節(jié)點A，從而退出“死胡同”。

圖2 死路現(xiàn)象

由于染色體生成過程比較復(fù)雜，這里用流程圖表示(圖3)。

圖3 染色體的生成過程流程

重復(fù)過程，直到達到式(1)計算出的種群規(guī)模為止。

2.4 選擇操作

精英主義可以加快收斂速度[14]，因此，只對種群中的優(yōu)秀個體進行變異和交叉操作。為避免由此帶來的可能陷入局部最優(yōu)的危險，設(shè)計了一種既可以保留優(yōu)秀個體又可以增加種群多樣性的選擇算子，即，保留種群中80 %的優(yōu)秀個體，其余20 %的個體用隨機生成的個體代替。

2.5 變異操作

由于傳統(tǒng)的變異操作采用的是隨機變異的形式，收斂速度慢，多位學(xué)者對其進行了改進。文獻[7]在染色體中隨機選擇一個基因作為變異點，從起點到變異點的基因保持不變，由變異點開始，隨機選擇當(dāng)前節(jié)點的可通過鄰居節(jié)點加入到染色體，直到找到目標(biāo)節(jié)點為止。文獻[8]是在染色體中隨機選擇一個基因作為變異點，再從該變異點的鄰居節(jié)點中隨機選擇一個節(jié)點作為新染色體的中間節(jié)點，用A*算法生成一條從該中間節(jié)點到起點的路徑，再用A*算法生成一條從該中間節(jié)點到目標(biāo)點的路徑，連接兩條路徑作為新的路徑。為滿足游戲?qū)崟r性的要求，設(shè)計了一種啟發(fā)式深度優(yōu)先搜索算法，用于變異操作，具體步驟如下：

1)從待變異父代路徑Vold中隨機選擇變異節(jié)點i(不包括起點和目標(biāo)點)；

2)由節(jié)點i開始，選擇其鄰居可通過節(jié)點中距離起點最近的節(jié)點加入到染色體，直到找到起點為止，作為路徑Vfront；

3)再由節(jié)點i開始，選擇其鄰居可通過節(jié)點中距離目標(biāo)點最近的節(jié)點加入到染色體，直到找到目標(biāo)點為止，作為路徑Vback；

4)連接Vfront，Vback，并將重復(fù)的節(jié)點i從中刪除一個，形成新路徑Vnew作為子代路徑。

傳統(tǒng)變異操作的隨機性可能對優(yōu)秀個體造成破壞[15]?？紤]到從優(yōu)秀個體中選取的變異節(jié)點i更有可能在最短路徑上，算法只對40 %的優(yōu)秀個體使用啟發(fā)式深度優(yōu)先搜索算法進行變異，使路徑達到“拉直”的效果，進而讓優(yōu)秀個體更優(yōu)秀。需要說明的是，啟發(fā)式深度優(yōu)先搜索算法速度非?？?，并且在沒有障礙物時，得到的路徑是最短路徑；但是遇到障礙物尤其是U形障礙物時，會繞彎路。如圖4所示，實線是將A作為變異點得到的路徑，虛線是將B作為變異點得到的路徑。通過后續(xù)的交叉操作，有很大的概率得到更短的路徑。

圖4 啟發(fā)式深度優(yōu)先搜索算法效果示意

2.6 交叉操作

為配合變異操作，算法只對40 %的優(yōu)秀個體進行交叉操作，具體步驟如下：

1)列舉出父代個體V1和V2中共同含有的節(jié)點集合Nc(不包括起始節(jié)點和目標(biāo)節(jié)點)；

2)從Nc集中隨機選擇一個節(jié)點i，i∈Nc，作為交叉點；

3)判斷可能得到的子代個體中是否至少有一個其長度均小于V1和V2，如果是，則進行步驟(4)，否則,放棄交叉；

4)交換交叉點后的所有節(jié)點。

3 環(huán)路處理

雖然在初始種群的生成中避免了環(huán)路，但是交叉操作和變異操作又會產(chǎn)生環(huán)路。所以，每當(dāng)交叉和變異之后都要對環(huán)路進行處理。處理環(huán)路的方式采用文獻[16]方法，即處理最大的環(huán)路如圖5。

圖5 環(huán)路處理方法

4 實驗與結(jié)果分析

實驗程序使用C++語言基于Cocos2d-x游戲引擎編寫。在Layer類的init()方法中，將地圖信息映射到一個二維數(shù)組。基因用指針表示，使用p=new int[2]命令為指針分配內(nèi)存，其中p[0]為節(jié)點的橫坐標(biāo)，p[1]為節(jié)點的縱坐標(biāo)。染色體用STL中的list〈int*〉數(shù)據(jù)類型，適應(yīng)度用size()方法計算，交叉使用splice()方法實現(xiàn)。

實驗從隨機選取的幾款地圖類游戲中隨機選取了10張地圖(其中含節(jié)點總數(shù)為169的地圖6張，節(jié)點總數(shù)為240的地圖4張；若地圖中有多個起點或目標(biāo)點，則隨機選取一對起點和目標(biāo)點)，然后用Tiled地圖編輯器模仿這10張實際游戲地圖建立了10張實驗所用地圖，并用Dijkstra算法計算出每張地圖的最短路徑的長度作為最短路徑長度的標(biāo)準(zhǔn)。

需要說明的是，文獻[4]的改進算法是通過節(jié)點復(fù)雜度算子確定交叉率與變異率，故在本實驗中不為其預(yù)先指定交叉率和變異率。為做到各參數(shù)與本文的改進算法一致，將傳統(tǒng)遺傳算法、文獻[7]及文獻[8]所用的選擇操作優(yōu)秀個體置換比例設(shè)為20 %，交叉率設(shè)置為0.4，變異率設(shè)置為0.4。除本文改進算法通過式(1)動態(tài)確定外，其余算法均固定種群規(guī)模為15。

由于在實際游戲開發(fā)中，都是預(yù)先指定遺傳算法的進化代數(shù)。故實驗也采用指定進化代數(shù)的方法，并讓算法在每張地圖上運行100次，將平均運行時間定義為算法在該地圖上的運行時間；并將運行結(jié)果與標(biāo)準(zhǔn)最短路徑長度做對比，將等于標(biāo)準(zhǔn)最短長度的運行次數(shù)在總次數(shù)中占的比例定義為算法在該地圖上的正確率。

實驗對比了本文的算法、傳統(tǒng)遺傳算法、文獻[4]的算法、文獻[7]的算法以及文獻[8]的算法，進化代數(shù)取4，10，20進行了3組實驗，通過記錄的每張地圖的運行時間及正確率，計算出了10張地圖的平均運行時間與平均正確率，結(jié)果如表1、表2、表3所示。

表1 進化代數(shù)為4的實驗結(jié)果

表2 進化代數(shù)為10的實驗結(jié)果

可以看出，本文的算法較傳統(tǒng)遺傳算法、文獻[4]的算法以及文獻[7]的算法在運行速度及正確率上均有大幅提升。正確率雖然不及文獻[8]，但是平均運行時間較之縮短了很多，而游戲NPC決策的實時性是游戲開發(fā)中首要考慮的性能，所以設(shè)計的改進遺傳算法更適用于游戲NPC路徑規(guī)劃。

表3 進化代數(shù)為20的實驗結(jié)果

5 在多目標(biāo)環(huán)境下的應(yīng)用

多目標(biāo)環(huán)境是指游戲地圖中含多種因素，要求NPC不但要以路徑最短為目標(biāo)，而且要有避開危險區(qū)域的能力。與此同時，多目標(biāo)遺傳算法也取得了長足的發(fā)展[17,18]。有學(xué)者將其用到游戲NPC路徑規(guī)劃中來[6]。將路徑中每個節(jié)點與危險區(qū)域的距離總和作為路徑安全參數(shù)，再將路徑長度、路徑安全、路徑耗費按照重要性加權(quán)求和，作為適應(yīng)度函數(shù)。但是這種做法會加大計算量，影響游戲NPC行為決策的實時性。本文在將地圖信息映射到二維數(shù)組時，通過計算每一個瓦片與危險源的距離，判斷該瓦片是否位于危險區(qū)域，并在數(shù)組中用特殊的字符標(biāo)記。在生成染色體及變異時，不考察位于危險區(qū)域的節(jié)點。將上述方法與文獻[6]中的方法進行對比實驗，實驗結(jié)果如圖6所示(其中黑色區(qū)域為障礙物，灰色為危險區(qū)域)。不難看出，使用本文的算法同樣能使NPC具有避開危險區(qū)域的能力，且速度更快，簡便易實現(xiàn)。

圖6 將本文算法與文獻[6]中的方法進行對比的實驗結(jié)果

6 結(jié)束語

針對游戲NPC路徑規(guī)劃中傳統(tǒng)遺傳算法計算速度慢、正確率低等問題，設(shè)計了一種改進遺傳算法，提出了一種最佳種群規(guī)模估計方法，設(shè)計了一種啟發(fā)式深度優(yōu)先搜索變異方式，并使用了精英主義思想優(yōu)化遺傳算子。實驗表明：算法能夠在保證正確率的前提下，縮短運行時間，而且在多目標(biāo)環(huán)境下同樣適用。

[1] 饒衛(wèi)平,楊任農(nóng),雷曉義,等.基于多智能體遺傳算法的戰(zhàn)術(shù)航段優(yōu)化[J].傳感器與微系統(tǒng),2016,35(3):41-43,48.

[2] 王海英,蔡向東,尤 波,等.基于遺傳算法的移動機器人動態(tài)路徑規(guī)劃研究[J].傳感器與微系統(tǒng),2007,26(8):32-34.

[3] 唐義龍,潘 煒,李念強,等.基于量子遺傳算法的無線傳感器網(wǎng)絡(luò)路由研究[J].傳感器與微系統(tǒng),2011,30(12):68-70,74.

[4] 黎忠文,覃志東,王全宇,等.游戲引擎最短路徑搜索優(yōu)化遺傳算法設(shè)計[J].計算機應(yīng)用研究,2014,31(1):76-79.

[5] 付朝暉,丁 夢,喻 昕.游戲編程中的尋路算法研究[J].湖南工業(yè)大學(xué)學(xué)報,2007,21(4):84-87.

[6] 劉大瑞,馮 鎳.基于多目標(biāo)遺傳算法的游戲路徑規(guī)劃研究[J].軟件導(dǎo)刊,2014,13(1):49-51.

[7] 孫寶林,李臘元,陳 華.基于遺傳算法的最短路徑路由優(yōu)化算法[J].計算機工程,2005,31(6):142-144，162.

[8] 李 擎,謝四江,童新海,等.一種用于車輛最短路徑規(guī)劃的自適應(yīng)遺傳算法及其與Dijkstra和A*算法的比較[J].北京科技大學(xué)學(xué)報,2006,28(11):1082-1086.

[9] Chang Wook Ahn,Ramakrishna R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J].IEEE Transactions on Evolutionary Computation,2002,6(6):566-579.

[10] 康曉軍,王茂才.基于遺傳算法的最短路徑問題求解[J].計算機工程與應(yīng)用,2008,44(23):22-23,35.

[11] Hong Qu,Ke Xing,Takacs Alexander.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing,2013(120):509-517.

[12] Lee Jaesung,Kim Dae-Won.An effective initialization method for genetic algorithm based robot path planning using a directed acyclic graph[J].Information Sciences,2016(332):1-18.

[13] 段俊花,李孝安.基于改進遺傳算法的機器人路徑規(guī)劃[J].微電子學(xué)與計算機,2005,22(1):70-72,76.

[14] Tsai Ching-Chih,Huang Hsu-Chih,Chan Cheng-Kai.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J].IEEE Transactions on Industrial Electronics,2011,58(10):4813-4821.

[15] 王友釗,彭宇翔,潘芬蘭.基于貪心算法和遺傳算法的倉儲車輛調(diào)度算法[J].傳感器與微系統(tǒng),2012,31(10):125-128.

[16] Wu Wei,Ruan Qiuqi.A gene-constrained genetic algorithm for solving shortest path Problem[C]∥Proceedings of the 7th International Conference on Signal Processing,Beijing,China:2004:2510-2513.

[17] Mohamed Cheikh,Bassem Jarboui,Taicir Loukil.A genetic algorithms to solve the bicriteria shortest path problem[J].Electronic Notes in Discrete Mathematics,2010(36):851-858.

[18] Liu Linzhong,Mu Haibo,Yang Xinfeng,et al.An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems[J].Applied Soft Computing,2012(12):506-515.

Improved genetic algorithm for path planning in games NPC*

LI Jing-song1, QIAN Qian1,3, SUN Ming-hui2,3

(1.Yunnan Key Laboratory of Computer Technology Applications,Kunming University of Science and Technology,Kunming 650500,China; 2.College of Computer Science and Technology, Jilin University,Changchun 130012，China; 3.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China)

To improve the performance of genetic algorithms for path planning in games,an improved genetic algorithm is proposed.A way to estimate the optimal population size is used.New genetic operators based on elitist strategy is designed.A mutation method based on heuristic depth-first search is introduced.The proposed algorithm is compared with the traditional genetic algorithm and the improved algorithms proposed by other researchers to show the validity of the algorithm.Experimental results prove that the proposed algorithm can shorten the running speed of the algorithm while assuring success rate and it is also effective in multi-objective environment condition.

artificial intelligence(AI); path planning; genetic algorithm; population size; elitist strategy; heuristic depth-first search

2016—06—15

國家自然科學(xué)基金資助項目(31300938,61300145)；吉林大學(xué)符號計算與知識工程教育部重點實驗室開放課題項目(93K172016K10)

10.13873/J.1000—9787(2017)06—0114—05

TP 18

A

1000—9787(2017)06—0114—05

李井頌(1989-)，男，碩士研究生，研究方向為人工智能。

錢 謙(1981-)，男，通訊作者，博士，副教授，從事視覺認(rèn)知科學(xué)工作,E—mail:qianqianyn@126.com。