【摘要】：游戲地圖路徑搜索是指在盡可能短的時(shí)間內(nèi),為游戲中的虛擬角色計(jì)算出一條從當(dāng)前位置到目標(biāo)位置的最短無碰撞路徑,被稱為游戲人工智能的一塊神圣基石。游戲中的智能路徑搜索算法主要包括A*算法與遺傳算法兩種,但兩種算法在該領(lǐng)域應(yīng)用中的設(shè)計(jì)與實(shí)現(xiàn)均有不足,造成算法運(yùn)行速度不夠快,影響游戲的實(shí)時(shí)性,且搜索到最短路徑的概率不夠高,影響游戲NPC的智能性。有鑒于此,本文對它們進(jìn)行了適當(dāng)改進(jìn)與重新設(shè)計(jì)。因?yàn)锳*算法已經(jīng)非常成熟,且學(xué)術(shù)界又有多位學(xué)者對其進(jìn)行了改進(jìn)研究,故本只提出了一種簡單A*算法的啟發(fā)式的改進(jìn)方案。改進(jìn)后的啟發(fā)式可根據(jù)地圖中障礙物的多少調(diào)節(jié)簡單A*算法的搜索行為,使之兼顧搜索成功率與運(yùn)行時(shí)間。遺傳算法相對A*算法較不成熟,本文將其作為研究重點(diǎn),對其進(jìn)行的改進(jìn)與重新設(shè)計(jì)如下:1)設(shè)計(jì)了一種以地圖圖塊坐標(biāo)為基因的染色體編碼方式,以方便進(jìn)行平滑路徑等后續(xù)優(yōu)化操作;2)設(shè)計(jì)了一種不產(chǎn)生斷路與環(huán)路的染色體生成方式,提高了初代群體的整體質(zhì)量;3)提出了一種即可保留優(yōu)勝個(gè)體又可增加種群的多樣性的變異算子,減小了算法陷入局部最優(yōu)解的概率;4)提出了一種基于啟發(fā)式深度優(yōu)先搜索的變異操作,又將交叉操作的執(zhí)行順序調(diào)整于其后,加快了種群的進(jìn)化速度;5)提出了一種以指定迭代次數(shù)為算法終止條件時(shí),兼顧搜索能力與計(jì)算速度的最佳種群規(guī)模的選取方案。最后通過實(shí)驗(yàn)分析了上述改進(jìn)的有效性,并與傳統(tǒng)遺傳算法及其他學(xué)者的改進(jìn)算法進(jìn)行了對比實(shí)驗(yàn)。
【圖文】：

實(shí)現(xiàn)路徑搜索是實(shí)現(xiàn)游戲ＮＰＣ智能化的首要任務(wù)，被稱為游戲人工智能的一逡逑塊“神圣基石”。所謂游戲ＮＰＣ路徑規(guī)劃，就是在盡可能短的時(shí)間內(nèi)，為游戲ＮＰＣ逡逑計(jì)算出一條從起點(diǎn)到終點(diǎn)的無碰撞的最短路徑（圖１．１）。現(xiàn)如今依賴地圖的游戲逡逑越來越多，比如最近非常受歡迎的魔獸爭霸、英雄聯(lián)盟、王者榮耀、皇室戰(zhàn)爭等逡逑游戲，就存在大量的游戲ＮＰＣ，需要為他們計(jì)算出一條這樣的路徑。逡逑１逡逑Ｉ逡逑

２．１二維游戲地圖逡逑二維游戲地圖是由多個(gè)圖層疊加而成，而圖層又由多個(gè)圖塊拼接而成，看起逡逑來與柵格化的移動(dòng)機(jī)器人工作空間類似，如圖２．１所示。逡逑：ＣｒａｔｘＳ＾ｐ．邋ｔ？ｓ邋Ｘ邋！■邐窈邋Ｓｔ；逡逑灥！逡逑１１１＇逡逑圖２．１邋２Ｄ游戲地圖逡逑那么何為圖層，何為圖塊呢？下面就對二維游戲地圖中的這兩個(gè)重要概念作逡逑一下簡要說明：逡逑（１）圖層逡逑與Ｐｈｏｔｏｓｈｏｐ中的ｐｓｄ分成文件類似，游戲地圖也是分層的，最上層是對象逡逑層，也就是與玩家角色交互的層。中間可以是地圖層，用來表示地圖的各種地形。逡逑而最下層往往作為碰撞檢測層，用于進(jìn)行碰撞檢測，并對玩家隱藏。這樣就可以逡逑使碰撞檢測和地圖圖塊所代表的具體地形分開，，方便游戲開發(fā)。逡逑７逡逑
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 盧月品;趙陽;孟躍強(qiáng);劉佳;;基于改進(jìn)遺傳算法的狹窄空間路徑規(guī)劃[J];計(jì)算機(jī)應(yīng)用研究;2015年02期

2 劉大瑞;馮鎳;;基于多目標(biāo)遺傳算法的游戲路徑規(guī)劃研究[J];軟件導(dǎo)刊;2014年01期

3 黎忠文;覃志東;王全宇;倪仲余;;游戲引擎最短路徑搜索優(yōu)化遺傳算法設(shè)計(jì)[J];計(jì)算機(jī)應(yīng)用研究;2014年01期

4 馬超;;遺傳算法和Dijkstra算法在動(dòng)態(tài)權(quán)值系統(tǒng)中的比較[J];計(jì)算機(jī)技術(shù)與發(fā)展;2012年09期

5 沈暢;樂天;;遺傳算法中的變異算子的述評(píng)[J];科技視界;2012年23期

6 雷文杰;;基于遺傳算法的游戲地圖尋徑問題[J];電腦知識(shí)與技術(shù);2012年16期

7 肖曉明;陳志興;高平安;;動(dòng)態(tài)確定基因數(shù)的遺傳算法路徑規(guī)劃[J];計(jì)算機(jī)應(yīng)用研究;2009年07期

8 康曉軍;王茂才;;基于遺傳算法的最短路徑問題求解[J];計(jì)算機(jī)工程與應(yīng)用;2008年23期

9 李擎;馮金玲;柳延領(lǐng);周洲;尹怡欣;;自適應(yīng)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J];北京科技大學(xué)學(xué)報(bào);2008年03期

10 付朝暉;丁夢;喻昕;;游戲編程中的尋路算法研究[J];湖南工業(yè)大學(xué)學(xué)報(bào);2007年04期

相關(guān)碩士學(xué)位論文 前9條

1 唐崇;基于加速A*算法的游戲網(wǎng)格地圖尋徑研究[D];江西師范大學(xué);2015年

2 陳漢偉;基于人工智能的虛擬角色行為決策能力的研究[D];浙江理工大學(xué);2015年

3 周振華;游戲場景中分層尋路算法及地圖復(fù)雜性度量研究[D];河北大學(xué);2014年

4 韓瑋;游戲地圖尋路及其真實(shí)性研究[D];西南大學(xué);2013年

5 沈健;FPS游戲?qū)ぢ匪惴ǖ难芯颗c實(shí)現(xiàn)[D];華南理工大學(xué);2012年

6 秦思涵;Virtools三維游戲最優(yōu)路徑的遺傳算法研究[D];四川師范大學(xué);2012年

7 楊科選;人工智能尋路算法及其在游戲中的應(yīng)用研究[D];中南大學(xué);2009年

8 何文雅;3D游戲場景中虛擬角色的智能尋徑應(yīng)用研究[D];華中師范大學(xué);2009年

9 詹海波;人工智能尋路算法在電子游戲中的研究和應(yīng)用[D];華中科技大學(xué);2006年

本文編號(hào)：2551011