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

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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

4 曾秀;魏振華;;猴群算法及其改進綜述[J];電腦知識與技術;2017年32期

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

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

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

8 覃遠年;梁仲華;;蟻群算法研究與應用的新進展[J];計算機工程與科學;2019年01期

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

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

相關會議論文 前10條

1 苗強;劉曉琳;王仲奇;;隨機球重疊判斷算法改進研究工作進展[A];中國原子能科學研究院年報 2013[C];2014年

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

3 王蓬;宋明玉;張林芳;王新遠;;廣義自適應相干累積算法改進及其在線譜增強中的應用[A];中國聲學學會2007年青年學術會議論文集（上）[C];2007年

4 郝紅星;吳玲達;宋漢辰;;一種殘損圖像修補算法改進與實現[A];第18屆全國多媒體學術會議（NCMT2009）、第5屆全國人機交互學術會議（CHCI2009）、第5屆全國普適計算學術會議（PCC2009）論文集[C];2009年

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

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

7 鄒錦峰;;水面仿真研究及算法改進[A];全國首屆數字（虛擬）科技館技術與應用學術研討會論文集[C];2007年

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

9 李國棟;;定點DSP實現均衡的算法改進與仿真[A];系統仿真技術及其應用（第7卷）——'2005系統仿真技術及其應用學術交流會論文選編[C];2005年

10 吳鐵洲;鄭丹丹;;藍牙的密鑰算法改進[A];湖北省電工技術學會、武漢電工技術學會2008年學術年會暨理事會換屆大會論文集[C];2008年

相關重要報紙文章 前2條

1 記者 宛霞;風云衛(wèi)星云導風算法改進[N];中國氣象報;2018年

2 記者 陳姝;深企為大橋定制人臉識別方案[N];深圳商報;2018年

相關博士學位論文 前10條

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

2 鐘林峰;復雜網絡中關鍵節(jié)點的挖掘算法研究[D];電子科技大學;2018年

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

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

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

6 胡銦;基于單目視覺的運動目標檢測與跟蹤算法研究[D];南京理工大學;2008年

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

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

9 安琦;信號偵收中的識別與分類理論與算法研究[D];電子科技大學;2017年

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

相關碩士學位論文 前10條

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

2 劉曉紅;改進的AP-SVM算法研究及其在字母識別的應用[D];廈門大學;2017年

3 何逸凡;基于深度學習的視頻動作時空檢測算法研究[D];北京郵電大學;2019年

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

5 董靜;基于主題模型和聚類算法的網絡熱點話題發(fā)現[D];河北大學;2019年

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

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

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

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

10 趙斯琦;基于Spark的大規(guī)模復雜網絡的社區(qū)發(fā)現算法的研究與改進[D];吉林大學;2018年

本文編號：2641797