本文關(guān)鍵詞：游戲地圖尋路及其真實(shí)性研究，，由筆耕文化傳播整理發(fā)布。

《西南大學(xué)》 2013年

游戲地圖尋路及其真實(shí)性研究

韓瑋  

【摘要】：隨著社會(huì)的發(fā)展,人們物質(zhì)水平的不斷提高,同時(shí)得益于計(jì)算機(jī)的普及和軟件技術(shù)的快速發(fā)展,游戲產(chǎn)業(yè)得到了快速的發(fā)展,尤其是在進(jìn)入21世紀(jì)后,游戲產(chǎn)業(yè)迅速成為了朝陽產(chǎn)業(yè)。 游戲中路徑搜索系統(tǒng)是游戲系統(tǒng)中非常重要的一部分,好的路徑搜索算法對(duì)于游戲的重要性不可言喻。常見的路徑搜索算法主要有深度優(yōu)先搜索,廣度優(yōu)先搜索,Dijkstra, Floyd算法,A*算法等,其中A*算法是當(dāng)前游戲開發(fā)中使用最為廣泛的算法,也是游戲人工智能路徑搜索中的研究重點(diǎn)。A*算法作為一種啟發(fā)式搜索算法,在路徑搜索時(shí),相對(duì)其它搜索算法相當(dāng)高效,它的評(píng)估函數(shù)是：F(n)=G(n)+H(n),其中G(n)表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際距離,H(n)表示從當(dāng)前節(jié)點(diǎn)到下一步節(jié)點(diǎn)的估價(jià)值。A*算法總是尋找估價(jià)值最小的節(jié)點(diǎn),因此能夠找到最短路徑,但是由于在游戲地圖中,算法是基于節(jié)點(diǎn)搜索,所以在生成最終路徑的時(shí)候,雖然是最優(yōu)解,但是最終路徑經(jīng)常出現(xiàn)不符合現(xiàn)實(shí)情形,如何解決路徑真實(shí)性問題,是一個(gè)非常重要的問題。 本文首先對(duì)A*算法進(jìn)行深入研究,分析其產(chǎn)生問題的原因,然后針對(duì)A*尋路存在的問題,提出以了一種基于Floyd算法和Bezier曲線的改進(jìn)A*算法,去掉了A*算法尋路中存在的拐點(diǎn)和多余的共線節(jié)點(diǎn),避免了存在直線可走情況下走蛇型線路的問題,同時(shí)平滑了繞過障礙物時(shí)的生硬路徑,較好的解決了A*算法路徑真實(shí)性問題。最后,通過仿真實(shí)驗(yàn)對(duì)傳統(tǒng)A*算法,基于二叉堆的A*算法和改進(jìn)算法進(jìn)行最終線路效果和時(shí)間效率的對(duì)比。實(shí)驗(yàn)中采用30*30的矩形方格來模擬地圖,生成了固定地圖和隨機(jī)地圖,固定地圖主要是對(duì)比算法的時(shí)間效率方面,也比較最終的路徑效果,隨機(jī)地圖主要觀察在復(fù)雜的環(huán)境中,算法的路徑效果。通過多次實(shí)驗(yàn)對(duì)比,得出的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了改進(jìn)算法的有效性,改進(jìn)算法在時(shí)間消耗上優(yōu)于傳統(tǒng)A*算法,略低于二叉堆優(yōu)化的A*算法,尋路效果更符合現(xiàn)實(shí)。

【關(guān)鍵詞】：
【學(xué)位授予單位】：西南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP301.6
【目錄】：

下載全文 更多同類文獻(xiàn)

CAJ全文下載

(如何獲取全文？ 歡迎：購買知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【參考文獻(xiàn)】

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

1 李擎,宋頂立,張雙江,李哲,劉建光,王志良;兩種改進(jìn)的最優(yōu)路徑規(guī)劃算法[J];北京科技大學(xué)學(xué)報(bào);2005年03期

2 單偉;孟正大;;基于改進(jìn)A~*算法的平滑路徑設(shè)計(jì)[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年S1期

3 王海梅;周獻(xiàn)中;;直線優(yōu)化A~*算法在最短路徑問題中的改進(jìn)與實(shí)現(xiàn)[J];工程圖學(xué)學(xué)報(bào);2009年06期

4 李艷;陳彩;李鐵松;蘇蘭明;;游戲地圖中的分層動(dòng)態(tài)路徑搜索算法[J];計(jì)算機(jī)工程;2012年02期

5 王士同;啟發(fā)式圖搜索算法RA~*的改進(jìn)算法IRA~*及IRA′[J];計(jì)算機(jī)學(xué)報(bào);1991年03期

6 陳剛;付少鋒;周利華;;A~*算法在游戲地圖尋徑中的幾種改進(jìn)策略研究[J];科學(xué)技術(shù)與工程;2007年15期

7 申麟;何明耘;陳雷霆;;基于灰度圖像邊緣檢測(cè)的3D游戲路徑搜索[J];計(jì)算機(jī)應(yīng)用研究;2009年06期

8 劉娜;王玉芳;;A*尋路算法在游戲中的應(yīng)用[J];數(shù)字技術(shù)與應(yīng)用;2012年06期

9 張海濤;程蔭杭;;基于A*算法的全局路徑搜索[J];微計(jì)算機(jī)信息;2007年17期

10 邱磊;;基于A~*算法的游戲地圖尋路實(shí)現(xiàn)及性能比較[J];陜西科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年06期

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

1 王萬青;張曉輝;;改進(jìn)的A~*算法的高效實(shí)現(xiàn)[A];2009全國(guó)測(cè)繪科技信息交流會(huì)暨首屆測(cè)繪博客征文頒獎(jiǎng)?wù)撐募痆C];2009年

【共引文獻(xiàn)】

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

1 單方,陳璞;注塑機(jī)鎖模機(jī)構(gòu)CAD的研究與開發(fā)[J];工程塑料應(yīng)用;2001年09期

2 田曉艷;;計(jì)算智能主要算法研究[J];安防科技;2009年12期

3 陳帥,廖曉緯,王永禮,王霞,鄭嘵東,朱士永;多功能智能監(jiān)測(cè)插座研究[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年02期

4 樊孝忠,柳林,任鋒;漢字智能輸入芻議[J];兵工自動(dòng)化;1995年04期

5 高恒振;靳肖閃;李軍;郭玉華;景寧;;多星成像任務(wù)規(guī)劃的決策支持技術(shù)[J];兵工自動(dòng)化;2006年12期

6 陳永科;王樹坤;劉俊友;凌用銀;李鵬輝;鮑忠寶;;基于動(dòng)漫技術(shù)的炮兵模擬訓(xùn)練系統(tǒng)[J];兵工自動(dòng)化;2011年10期

7 楊志剛;馬云鵬;胡春梅;;一個(gè)智力游戲的計(jì)算機(jī)求解方法與討論[J];北京機(jī)械工業(yè)學(xué)院學(xué)報(bào);2006年01期

8 李國(guó)和,趙沁平;信息系統(tǒng)的一種分塊特征選取方法[J];北京航空航天大學(xué)學(xué)報(bào);2003年03期

9 李國(guó)和,趙沁平,王喜;一種頻繁復(fù)合項(xiàng)目集的混合求解方法[J];北京航空航天大學(xué)學(xué)報(bào);2004年08期

10 寧文如,申海軍;飛行員導(dǎo)航專家系統(tǒng)[J];北京航空航天大學(xué)學(xué)報(bào);1997年06期

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

1 李萍;薛克敏;劉小旦;;人工智能技術(shù)在汽車覆蓋件成形過程的應(yīng)用[A];2004“安徽制造業(yè)發(fā)展”博士科技論壇論文集[C];2004年

2 姜帆;潘方勝;李紅云;;一個(gè)基于FCR算法的推理機(jī)的設(shè)計(jì)[A];第三屆全國(guó)軟件測(cè)試會(huì)議與移動(dòng)計(jì)算、柵格、智能化高級(jí)論壇論文集[C];2009年

3 劉忠菁;霍小江;黃訓(xùn)誠(chéng);陳學(xué)廣;;節(jié)能電力調(diào)度中分布式仿生優(yōu)化策略發(fā)生器的研究[A];中國(guó)電子學(xué)會(huì)第十六屆信息論學(xué)術(shù)年會(huì)論文集[C];2009年

4 孫兆豪;李昂;劉坤起;解建軍;;論代數(shù)、邏輯和智能系統(tǒng)之間的對(duì)應(yīng)關(guān)系[A];邏輯學(xué)及其應(yīng)用研究——第四屆全國(guó)邏輯系統(tǒng)、智能科學(xué)與信息科學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

5 孫涌;詹云;;停車誘導(dǎo)系統(tǒng)中最短路徑的探索[A];江蘇省系統(tǒng)工程學(xué)會(huì)第十一屆學(xué)術(shù)年會(huì)論文集[C];2009年

6 劉奇;唐金國(guó);李榮新;黃傳毅;;基于框架的CGF實(shí)體行為建模研究[A];'2008系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2008年

7 蔣序平;;一種面向網(wǎng)絡(luò)管理的語義網(wǎng)絡(luò)模型[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（下）[C];2008年

8 尚文倩;王永濱;黃厚寬;;本科階段《人工智能》課程教學(xué)改革初探[A];2008年中國(guó)高校通信類院系學(xué)術(shù)研討會(huì)論文集（上冊(cè)）[C];2009年

9 王應(yīng);;基于時(shí)間屬性的多源日志因果關(guān)聯(lián)算法[A];2008'中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

10 陳立鵬;;基于Win32的單機(jī)游戲架構(gòu)設(shè)計(jì)[A];2008'中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

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

1 陳飛;基于Agent船載危險(xiǎn)品應(yīng)急管理資源協(xié)同分配機(jī)制研究[D];大連海事大學(xué);2010年

2 趙進(jìn)慧;膜計(jì)算仿生優(yōu)化算法及應(yīng)用研究[D];浙江大學(xué);2010年

3 遲雷;基于過程控制優(yōu)化的重組大腸桿菌高密度發(fā)酵研究[D];西北大學(xué);2011年

4 馬馳;松遼平原土地鹽堿化監(jiān)測(cè)機(jī)理及方法研究[D];吉林大學(xué);2011年

5 田瑞;應(yīng)急交通保障輔助決策支持系統(tǒng)相關(guān)模型與方法研究[D];吉林大學(xué);2011年

6 馮啟高;農(nóng)業(yè)機(jī)械化系統(tǒng)分析及智能決策支持系統(tǒng)研究[D];江蘇大學(xué);2011年

7 劉慧;基于PLS-SEM的中國(guó)高等教育學(xué)生滿意度測(cè)評(píng)研究[D];江蘇大學(xué);2011年

8 馮肖維;基于多傳感器信息融合的移動(dòng)機(jī)器人位姿計(jì)算方法研究[D];上海大學(xué);2011年

9 趙明;組織因素對(duì)核電廠人因可靠性的影響研究[D];南華大學(xué);2011年

10 俞斌;不確定條件下散裝液體化學(xué)品船安全評(píng)價(jià)方法及應(yīng)用研究[D];上海海事大學(xué);2011年

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

1 崔靜怡;基于車載導(dǎo)航系統(tǒng)的大區(qū)域路徑規(guī)劃算法的設(shè)計(jì)與實(shí)現(xiàn)[D];山東科技大學(xué);2010年

2 常春艷;礦山土地復(fù)墾方案論證管理系統(tǒng)研究[D];山東農(nóng)業(yè)大學(xué);2010年

3 梁永生;坦克戰(zhàn)場(chǎng)景模擬仿真研究[D];哈爾濱工程大學(xué);2010年

4 王濤;社保審計(jì)專家系統(tǒng)關(guān)鍵技術(shù)研究[D];哈爾濱工程大學(xué);2010年

5 柴紅霞;移動(dòng)機(jī)器人在SLAM中數(shù)據(jù)關(guān)聯(lián)方法的研究[D];大連理工大學(xué);2010年

6 楊克強(qiáng);LVQ神經(jīng)網(wǎng)絡(luò)在齒輪箱故障診斷中的研究[D];安徽農(nóng)業(yè)大學(xué);2010年

7 金璐鈺;基于框架的事件抽取關(guān)鍵技術(shù)研究[D];蘇州大學(xué);2010年

8 蘇瑞;基于多代理技術(shù)的多功能IED在數(shù)字化變電站中的應(yīng)用[D];中國(guó)電力科學(xué)研究院;2010年

9 陳政;一種改進(jìn)的遺傳算法優(yōu)化BP網(wǎng)絡(luò)的研究及應(yīng)用[D];暨南大學(xué);2011年

10 徐衡;汽車性能檢測(cè)線及其故障自動(dòng)診斷系統(tǒng)[D];南昌大學(xué);2010年

【二級(jí)參考文獻(xiàn)】

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

1 王海梅;周獻(xiàn)中;;網(wǎng)絡(luò)系統(tǒng)中的最短路徑分析及其應(yīng)用研究[J];兵工學(xué)報(bào);2006年03期

2 彭飛,柳重堪,張其善;車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J];北京航空航天大學(xué)學(xué)報(bào);2002年01期

3 王同喜;孫淑霞;;基于A~*和Bresenham相結(jié)合的網(wǎng)絡(luò)游戲?qū)ぢ匪惴ㄔO(shè)計(jì)與實(shí)現(xiàn)[J];成都理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

4 陸鋒;最短路徑算法:分類體系與研究進(jìn)展[J];測(cè)繪學(xué)報(bào);2001年03期

5 王海霞;王春蓮;;淺析計(jì)算機(jī)人工智能啟發(fā)式搜索函數(shù)[J];電腦知識(shí)與技術(shù);2008年08期

6 蘇永云,晏克非,黃翔,朱培康;車輛導(dǎo)航系統(tǒng)的動(dòng)態(tài)最優(yōu)路徑搜索方法研究[J];系統(tǒng)工程;2000年04期

7 高博;徐德民;張福斌;;動(dòng)態(tài)目標(biāo)的Field D~*算法及路徑的提取計(jì)算[J];火力與指揮控制;2010年08期

8 趙偉華,章復(fù)嘉,梁紅兵;車輛導(dǎo)航系統(tǒng)最優(yōu)路徑規(guī)劃的研究與實(shí)現(xiàn)[J];杭州電子工業(yè)學(xué)院學(xué)報(bào);2003年01期

9 段莉瓊,朱建軍,王慶社,馬玲;改進(jìn)的最短路徑搜索A*算法的高效實(shí)現(xiàn)[J];海洋測(cè)繪;2004年05期

10 周艷霞;唐新春;;基于A~*算法的海底地形等深線模型構(gòu)建方法研究[J];海洋測(cè)繪;2010年03期

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

1 靳旭棟;游戲領(lǐng)域中啟發(fā)式尋徑算法的運(yùn)用和優(yōu)化[D];華東師范大學(xué);2007年

2 張穎;基于D~*思想的ASON動(dòng)態(tài)均衡恢復(fù)策略研究[D];江蘇大學(xué);2007年

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫 前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 何國(guó)輝;陳家琪;;游戲開發(fā)中智能路徑搜索算法的研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2006年13期

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

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

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

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

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年

3 徐萍;馬齊爽;;復(fù)雜供電系統(tǒng)的一種潛通路分析方法[A];第六屆全國(guó)信息獲取與處理學(xué)術(shù)會(huì)議論文集（1）[C];2008年

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

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

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

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

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

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

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

5 武玥;礦山巷道路徑搜索及可視化[D];西安科技大學(xué);2014年

6 靳旭棟;游戲領(lǐng)域中啟發(fā)式尋徑算法的運(yùn)用和優(yōu)化[D];華東師范大學(xué);2007年

7 楊春曉;基于MapX的最優(yōu)路徑搜索理論與實(shí)施技術(shù)研究[D];吉林大學(xué);2004年

8 李楠;信任網(wǎng)絡(luò)中路徑搜索的優(yōu)化研究[D];河北科技大學(xué);2012年

9 李鐵松;游戲地圖中分層路徑搜索與地圖復(fù)雜性度量研究[D];河北大學(xué);2012年

10 史娟;基于地形分析的路徑搜索算法研究[D];華中科技大學(xué);2005年

  本文關(guān)鍵詞：游戲地圖尋路及其真實(shí)性研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：187180