本文關(guān)鍵詞：游戲AI中的路徑搜索算法的研究與應(yīng)用，由筆耕文化傳播整理發(fā)布。

【摘要】：路徑搜索是游戲AI(人工智能)的重要組成部分,在大型的商業(yè)游戲中,路徑搜索經(jīng)常受限于存儲(chǔ)空間以及CPU處理能力,且路徑搜索的性能直接決定用戶對(duì)游戲的滿意程度。論文通過(guò)對(duì)傳統(tǒng)路徑搜索算法的深入研究與分析,提出了幾種改進(jìn)與優(yōu)化策略,并通過(guò)實(shí)驗(yàn)對(duì)比,分析了算法改進(jìn)的效果。論文首先探討了課題的研究背景與意義,分析了國(guó)內(nèi)外研究現(xiàn)狀。路徑搜索是影響游戲整體效果的因素之一,因?yàn)槁窂剿阉髻x予NPC感知周圍環(huán)境的能力,在一定程度上標(biāo)志著NPC智能水平的高低并直接影響游戲角色的行為。接著,論文對(duì)比研究了傳統(tǒng)的各種路徑搜索算法,描述了搜索空間表示方法。傳統(tǒng)的Dijkstra算法、A*算法時(shí)間復(fù)雜度高,難以滿足大規(guī)模地圖中路徑搜索的要求;HPA*等分層尋路算法對(duì)地圖進(jìn)行均勻分區(qū),未考慮地圖中地形的分布信息,適應(yīng)能力差。針對(duì)以上問(wèn)題,論文在三方面進(jìn)行了改進(jìn)與優(yōu)化:(1)提出了一種對(duì)A*算法Open表優(yōu)化的方法。利用Multiset關(guān)聯(lián)容器作為A*算法Open表的數(shù)據(jù)結(jié)構(gòu)。深入分析了順序容器和關(guān)聯(lián)容器的性質(zhì),以及RB-Tree(紅黑樹)的增加、刪除以及查找操作。經(jīng)實(shí)驗(yàn)對(duì)比,Open表優(yōu)化的A*算法在搜索效率方面優(yōu)于標(biāo)準(zhǔn)A*算法、索引數(shù)組優(yōu)化的A*算法以及盲目式搜索算法。(2)提出一種基于地圖影響因子的MF-A*路徑搜索算法。首先,根據(jù)地形分布信息,定義三種地圖影響因子,進(jìn)而得出單個(gè)地圖區(qū)域的權(quán)值,同時(shí)設(shè)計(jì)MF-A*算法的啟發(fā)函數(shù);然后,利用Floyd平滑處理方法篩選路徑上的結(jié)點(diǎn),并利用Catmull-Rom算法對(duì)路徑進(jìn)行平滑處理。實(shí)驗(yàn)證明,MF-A*算法99%以上的搜索結(jié)果優(yōu)于A*算法,且改善了路徑出現(xiàn)鋸齒狀的現(xiàn)象,MF-A*算法能夠達(dá)到預(yù)期的效果。(3)提出了一種基于地圖聚類的分層路徑搜索算法K-HPA*。首先對(duì)地圖進(jìn)行預(yù)處理,其中包括篩選障礙物區(qū)域、最大距離法尋找初始聚類中心、利用K-Means算法對(duì)地圖進(jìn)行聚類;然后,定義關(guān)鍵結(jié)點(diǎn)并構(gòu)建虛擬地圖,在障礙物區(qū)域采用MF-A*搜索算法,在非障礙物區(qū)域采用Bresenham處理方法。經(jīng)實(shí)驗(yàn)對(duì)比,K-HPA*算法搜索效率高于MF-A*算法,且擴(kuò)展結(jié)點(diǎn)數(shù)目少于MF-A*算法。論文最后結(jié)合實(shí)際,對(duì)論文研究工作進(jìn)行了總結(jié)與展望。
【關(guān)鍵詞】：游戲AI A*算法 紅黑樹 影響因子 分層搜索
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 緒論11-15
• 1.1 研究背景與意義11-12
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀12-13
• 1.3 本文的主要研究?jī)?nèi)容與結(jié)構(gòu)13-15
• 第二章 路徑搜索算法概述15-25
• 2.1 路徑搜索算法15-19
• 2.1.1 盲目式搜索算法15-16
• 2.1.2 啟發(fā)式搜索算法16-18
• 2.1.3 分層路徑搜索算法18-19
• 2.2 搜索空間表示19-23
• 2.2.1 導(dǎo)航網(wǎng)格法19-22
• 2.2.2 可見點(diǎn)法22
• 2.2.3 柵格法22-23
• 2.3 Cocos2d-x簡(jiǎn)介23-24
• 2.4 本章小結(jié)24-25
• 第三章 基于Open表優(yōu)化的A*算法25-40
• 3.1 引言25-26
• 3.2 Multiset數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介26-30
• 3.2.1 關(guān)聯(lián)容器簡(jiǎn)介26-27
• 3.2.2 Multiset數(shù)據(jù)結(jié)構(gòu)27-30
• 3.3 Open表數(shù)據(jù)操作30-37
• 3.3.1 Insertion插入節(jié)點(diǎn)30-33
• 3.3.2 Erasure刪除節(jié)點(diǎn)33-37
• 3.4 實(shí)驗(yàn)設(shè)計(jì)與分析37-39
• 3.4.1 實(shí)驗(yàn)設(shè)計(jì)37-38
• 3.4.2 實(shí)驗(yàn)數(shù)據(jù)分析38-39
• 3.5 本章小結(jié)39-40
• 第四章 MF-A*路徑搜索算法40-56
• 4.1 MF-A*算法的提出40
• 4.2 MF-A*算法思想40-41
• 4.3 地圖預(yù)處理41-46
• 4.3.1 地圖空間劃分41-43
• 4.3.2 設(shè)計(jì)地圖影響因子43-46
• 4.3.2.1 通過(guò)性影響因子43-44
• 4.3.2.2 坡度影響因子44-45
• 4.3.2.3 實(shí)時(shí)性影響因子45-46
• 4.4 MF-A*路徑搜索46-49
• 4.4.1 標(biāo)準(zhǔn)估價(jià)函數(shù)46-47
• 4.4.2 MF-A*算法估價(jià)函數(shù)47-49
• 4.5 路徑平滑處理49-51
• 4.6 實(shí)驗(yàn)數(shù)據(jù)分析51-55
• 4.6.1 實(shí)驗(yàn)設(shè)計(jì)51-52
• 4.6.2 實(shí)驗(yàn)數(shù)據(jù)分析52-55
• 4.6.2.1 MF-A*算法與標(biāo)準(zhǔn)A*算法實(shí)驗(yàn)分析52-53
• 4.6.2.2 MF-A*算法平滑處理實(shí)驗(yàn)分析53-55
• 4.7 本章小結(jié)55-56
• 第五章：K-HPA*路徑搜索算法56-68
• 5.1 K-HPA*算法的提出56
• 5.2 K-HPA*算法思想56-58
• 5.3 地圖預(yù)處理58-60
• 5.3.1 篩選障礙物區(qū)域58
• 5.3.2 地圖分類58-60
• 5.3.2.1 選取K-Means聚類中心59-60
• 5.3.2.2 K-Means地圖聚類60
• 5.4 K-HPA*路徑搜索60-64
• 5.5 實(shí)驗(yàn)數(shù)據(jù)分析64-66
• 5.5.1 實(shí)驗(yàn)設(shè)計(jì)64
• 5.5.2 實(shí)驗(yàn)數(shù)據(jù)分析64-66
• 5.6 本章小結(jié)66-68
• 第六章 總結(jié)與展望68-70
• 6.1 總結(jié)68-69
• 6.2 展望69-70
• 致謝70-71
• 參考文獻(xiàn)71-74
• 詳細(xì)摘要74-78

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 馮玉翔,唐韶華;利用證書路徑搜索實(shí)現(xiàn)交叉認(rèn)證[J];計(jì)算機(jī)工程與應(yīng)用;2003年36期

2 李得偉;韓寶明;韓宇;;一種逆向改進(jìn)型A*路徑搜索算法[J];系統(tǒng)仿真學(xué)報(bào);2007年22期

3 李艷軍;李智勇;陳思遠(yuǎn);;一種面向3D場(chǎng)景的實(shí)時(shí)自動(dòng)路徑搜索方法[J];計(jì)算機(jī)應(yīng)用;2010年01期

4 王天順;張莉;;一種基于導(dǎo)航網(wǎng)格的路徑搜索技術(shù)[J];電腦知識(shí)與技術(shù);2010年12期

5 柯健;李帥;郝沅君;張倩倩;;虛擬場(chǎng)景中路徑搜索技術(shù)的研究[J];蘇州市職業(yè)大學(xué)學(xué)報(bào);2012年02期

6 符光梅;王紅;;基于節(jié)點(diǎn)可達(dá)度的公交多路徑搜索算法[J];計(jì)算機(jī)應(yīng)用研究;2012年12期

7 繆成;吳啟迪;許維勝;;突發(fā)災(zāi)害下可靠路徑搜索模型與算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年28期

8 夏云龍;王正武;王杰;;考慮可靠性的降級(jí)路網(wǎng)最優(yōu)路徑搜索方法[J];交通科學(xué)與工程;2013年04期

9 何國(guó)輝;陳家琪;;游戲開發(fā)中智能路徑搜索算法的研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2006年13期

10 陸悠;華澤;張妮;;基于二維有向集合擴(kuò)散的公交網(wǎng)路徑搜索算法研究[J];計(jì)算機(jī)與現(xiàn)代化;2009年12期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條

1 陳思遠(yuǎn);史廣順;李剛;;實(shí)時(shí)3D游戲中的智能體路徑搜索與動(dòng)作控制[A];中國(guó)計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國(guó)計(jì)算機(jī)圖形學(xué)大會(huì)論文集[C];2008年

2 文聰;徐紅兵;鄧罡;;任意多邊形排樣和最短切割路徑搜索的算法及實(shí)現(xiàn)[A];2006中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2006年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 馬堯;在線社會(huì)網(wǎng)絡(luò)的信任網(wǎng)絡(luò)發(fā)現(xiàn)與信任融合研究[D];華中科技大學(xué);2014年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 沈良;考慮出行時(shí)間相關(guān)性的最優(yōu)路徑搜索算法及應(yīng)用[D];中國(guó)礦業(yè)大學(xué);2016年

2 閻立忠;室內(nèi)多目的地導(dǎo)航路徑搜索系統(tǒng)的研究[D];哈爾濱工業(yè)大學(xué);2015年

3 張加一;游戲AI中的路徑搜索算法的研究與應(yīng)用[D];杭州電子科技大學(xué);2016年

4 陳彩;游戲地圖中的分層和動(dòng)態(tài)路徑搜索[D];河北大學(xué);2012年

5 李文亮;基于決策樹劃分的分層路徑搜索[D];河北大學(xué);2011年

6 左振華;基于ArcGIS API for Flex的人性化路徑搜索算法研究及實(shí)現(xiàn)[D];內(nèi)蒙古師范大學(xué);2010年

7 徐菲云;3D游戲場(chǎng)景中路徑搜索的研究與實(shí)現(xiàn)[D];電子科技大學(xué);2007年

8 武s，

本文編號(hào)：345177