【摘要】：針對(duì)在三維游戲場景中游戲角色動(dòng)態(tài)尋路存在路徑搜索結(jié)點(diǎn)過多,效率低下以及避讓動(dòng)態(tài)障礙物引起的振蕩問題。本文分別在全局路徑搜索和局部動(dòng)態(tài)避免上做出了改進(jìn)。在全局路徑搜索方面,運(yùn)用八叉樹體素化法光柵化三維場景空間,然后根據(jù)體素坡度、高度等性質(zhì)生成可行走的區(qū)域,利用Delaunay三角剖分算法生成導(dǎo)航網(wǎng)格。最后針對(duì)導(dǎo)航網(wǎng)格,分別對(duì)A*算法的啟發(fā)式函數(shù)和Open列表進(jìn)行了改進(jìn),并且對(duì)生成的路徑進(jìn)行平滑處理,從而提高了A*算法的搜索效率和搜索路徑的準(zhǔn)確性。在局部動(dòng)態(tài)碰撞避免方面,引入了速度障礙的概念并分析了動(dòng)態(tài)碰撞避免過程中的振蕩原因,給出了基于目標(biāo)區(qū)域的優(yōu)先級(jí)相互速度最優(yōu)碰撞避免算法,打破了碰撞避免過程中的對(duì)稱性,有效的解決了動(dòng)態(tài)尋路中的振蕩問題。在實(shí)驗(yàn)仿真部分,基于Unity3D游戲引擎搭建了全局路徑搜索實(shí)驗(yàn)仿真,比較基于導(dǎo)航網(wǎng)格改進(jìn)A*算法與常規(guī)的基于方格地圖A*算法的性能差異。最后制作了三維游戲場景的動(dòng)態(tài)尋路仿真,模擬了在三維場景下游戲人物動(dòng)態(tài)尋路的狀態(tài)。最后通過實(shí)驗(yàn)仿真得出結(jié)論,基于導(dǎo)航網(wǎng)格改進(jìn)A*算法結(jié)合目標(biāo)區(qū)域相互速度動(dòng)態(tài)碰撞避免算法可以大幅度的提高動(dòng)態(tài)尋路中搜索效率并且解決動(dòng)態(tài)碰撞避免引起的振蕩問題。
【圖文】：

間進(jìn)行抽象化處理，生成底層數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)來表示場景中的搜索空間對(duì)要。針對(duì)不同的場景，應(yīng)該選擇合適高尋路算法的效率。目前搜索空間處，可視圖法和路徑點(diǎn)法。種簡單的場景地圖劃分方式，多用于戲地圖。使用大小的相同的柵格劃分息，每個(gè)柵格都代表著場景地圖中的。根據(jù)障礙物占柵格的百分比判斷游域。如圖 2-1，黑色部分代表障礙物可以定義柵格為障礙物，不可通過。

當(dāng)場景地圖存在不規(guī)則的障物，設(shè)置單元柵格過小會(huì)導(dǎo)致尋路結(jié)點(diǎn)能準(zhǔn)確的表示障礙物，從而導(dǎo)致尋路算用于機(jī)器人路徑規(guī)劃領(lǐng)域，主要通過人定可視頂點(diǎn)[48-50]。首先對(duì)障礙物進(jìn)行矩形點(diǎn)和終點(diǎn)的相互連接生成路線網(wǎng)絡(luò)，如果物，，則稱該直線為可視路徑，所有的可的路徑。如圖 2-2 所示，將兩個(gè)障礙物進(jìn)頂點(diǎn)分別為{N1,N2,N3,N4}和{N5,N6,N7相互連接，與障礙物不相交的連線就是可
【學(xué)位授予單位】：武漢工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

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

1 歐陽普仁,楊叔子;一種改進(jìn)的Marple算法[J];南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年01期

2 黃小蓓;隆永紅;;分布式數(shù)據(jù)庫管理系統(tǒng)中的N&發(fā)控制——算法及其性能分析[J];計(jì)算技術(shù)與自動(dòng)化;1988年02期

3 馮成進(jìn);;0—1規(guī)劃新算法的改進(jìn)[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年02期

4 曾秀;魏振華;;猴群算法及其改進(jìn)綜述[J];電腦知識(shí)與技術(shù);2017年32期

5 許燦英;;算法合謀反競爭問題初探[J];合肥工業(yè)大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版);2019年02期

6 段艷明;肖輝輝;林芳;;新授粉方式的花授粉算法[J];計(jì)算機(jī)工程與應(yīng)用;2018年23期

7 肖海軍;王芬艷;盧常景;曹穎;;一種有效的多峰優(yōu)化鳥群算法[J];中南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2018年04期

8 覃遠(yuǎn)年;梁仲華;;蟻群算法研究與應(yīng)用的新進(jìn)展[J];計(jì)算機(jī)工程與科學(xué);2019年01期

9 肖輝輝;段艷明;;基于改進(jìn)花授粉算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J];軟件導(dǎo)刊;2018年11期

10 莫海淼;趙志剛;曾敏;石靜;溫泰;;具有自適應(yīng)步長與協(xié)同尋優(yōu)的蝙蝠煙花混合算法[J];小型微型計(jì)算機(jī)系統(tǒng);2019年07期

相關(guān)會(huì)議論文 前10條

1 苗強(qiáng);劉曉琳;王仲奇;;隨機(jī)球重疊判斷算法改進(jìn)研究工作進(jìn)展[A];中國原子能科學(xué)研究院年報(bào) 2013[C];2014年

2 李超;余昭平;;基于矩陣的Apriori算法改進(jìn)研究[A];第二屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議（NCIRCS-2005）論文集[C];2005年

3 王蓬;宋明玉;張林芳;王新遠(yuǎn);;廣義自適應(yīng)相干累積算法改進(jìn)及其在線譜增強(qiáng)中的應(yīng)用[A];中國聲學(xué)學(xué)會(huì)2007年青年學(xué)術(shù)會(huì)議論文集（上）[C];2007年

4 郝紅星;吳玲達(dá);宋漢辰;;一種殘損圖像修補(bǔ)算法改進(jìn)與實(shí)現(xiàn)[A];第18屆全國多媒體學(xué)術(shù)會(huì)議（NCMT2009）、第5屆全國人機(jī)交互學(xué)術(shù)會(huì)議（CHCI2009）、第5屆全國普適計(jì)算學(xué)術(shù)會(huì)議（PCC2009）論文集[C];2009年

5 解迎剛;王志良;鄭珊山;;基于LANDMARC及其算法改進(jìn)的RFID室內(nèi)定位研究[A];第二十九屆中國控制會(huì)議論文集[C];2010年

6 王篤俠;冷晟;周燕飛;;單件小批生產(chǎn)模式下的MRP算法改進(jìn)[A];全國先進(jìn)制造技術(shù)高層論壇暨第七屆制造業(yè)自動(dòng)化與信息化技術(shù)研討會(huì)論文集[C];2008年

7 鄒錦峰;;水面仿真研究及算法改進(jìn)[A];全國首屆數(shù)字（虛擬）科技館技術(shù)與應(yīng)用學(xué)術(shù)研討會(huì)論文集[C];2007年

8 林關(guān)成;李亞安;;一種支持向量機(jī)訓(xùn)練集選取算法改進(jìn)[A];2009’中國西部地區(qū)聲學(xué)學(xué)術(shù)交流會(huì)論文集[C];2009年

9 李國棟;;定點(diǎn)DSP實(shí)現(xiàn)均衡的算法改進(jìn)與仿真[A];系統(tǒng)仿真技術(shù)及其應(yīng)用（第7卷）——'2005系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文選編[C];2005年

10 吳鐵洲;鄭丹丹;;藍(lán)牙的密鑰算法改進(jìn)[A];湖北省電工技術(shù)學(xué)會(huì)、武漢電工技術(shù)學(xué)會(huì)2008年學(xué)術(shù)年會(huì)暨理事會(huì)換屆大會(huì)論文集[C];2008年

相關(guān)重要報(bào)紙文章 前2條

1 記者 宛霞;風(fēng)云衛(wèi)星云導(dǎo)風(fēng)算法改進(jìn)[N];中國氣象報(bào);2018年

2 記者 陳姝;深企為大橋定制人臉識(shí)別方案[N];深圳商報(bào);2018年

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

1 張代雨;多學(xué)科優(yōu)化算法及其在水下航行器中的應(yīng)用[D];西北工業(yè)大學(xué);2017年

2 鐘林峰;復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的挖掘算法研究[D];電子科技大學(xué);2018年

3 邱實(shí);多光譜衛(wèi)星遙感影像云及云陰影精準(zhǔn)檢測算法研究[D];電子科技大學(xué);2018年

4 孫寧;人工免疫優(yōu)化算法及其應(yīng)用研究[D];哈爾濱工業(yè)大學(xué);2006年

5 陸楠;關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D];吉林大學(xué);2007年

6 胡銦;基于單目視覺的運(yùn)動(dòng)目標(biāo)檢測與跟蹤算法研究[D];南京理工大學(xué);2008年

7 王玨;生物地理學(xué)優(yōu)化算法的研究及應(yīng)用[D];哈爾濱工程大學(xué);2013年

8 黃松;面向多應(yīng)用場景的粒子群優(yōu)化算法研究[D];江南大學(xué);2017年

9 安琦;信號(hào)偵收中的識(shí)別與分類理論與算法研究[D];電子科技大學(xué);2017年

10 周瑞紅;基于群智能優(yōu)化理論的聚類改進(jìn)方法及應(yīng)用研究[D];吉林大學(xué);2017年

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

1 朱昌龍;面向三維游戲場景的動(dòng)態(tài)尋路算法的研究與應(yīng)用[D];武漢工程大學(xué);2018年

2 劉曉紅;改進(jìn)的AP-SVM算法研究及其在字母識(shí)別的應(yīng)用[D];廈門大學(xué);2017年

3 何逸凡;基于深度學(xué)習(xí)的視頻動(dòng)作時(shí)空檢測算法研究[D];北京郵電大學(xué);2019年

4 林婉瑩;圖書推薦系統(tǒng)中提升Top-N列表多樣性算法研究[D];北京郵電大學(xué);2019年

5 董靜;基于主題模型和聚類算法的網(wǎng)絡(luò)熱點(diǎn)話題發(fā)現(xiàn)[D];河北大學(xué);2019年

6 李佩茜;一種高效的基于教與學(xué)的社區(qū)發(fā)現(xiàn)算法的研究[D];廈門大學(xué);2018年

7 裴華欣;自適應(yīng)密度峰劃分聚類算法研究及應(yīng)用[D];浙江工業(yè)大學(xué);2018年

8 朱炎亮;基于深度學(xué)習(xí)的人員異常操作視覺檢測算法[D];浙江工業(yè)大學(xué);2018年

9 曾辰子;改進(jìn)差分進(jìn)化算法及其收斂性分析[D];武漢理工大學(xué);2018年

10 趙斯琦;基于Spark的大規(guī)模復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法的研究與改進(jìn)[D];吉林大學(xué);2018年

本文編號(hào)：2641797