【摘要】：隨著硬件和圖像渲染引擎的發(fā)展,虛擬現實技術得以長足的發(fā)展。通過圖像渲染引擎營造出的虛擬現實場景,可以給用戶營造出一種身臨其境的感覺,也是這個原因,虛擬場景在各個領域都有廣泛的應用。路徑規(guī)劃則是虛擬場景中的一項基本功能。而且由于虛擬場景中存在復雜的交互和頻繁的路線導航,如何在交互型的虛擬場景下進行準確、高效的路徑規(guī)劃則成為一個關鍵性問題。本論文以交互型虛擬現實場景為背景,討論了如何在此場景下進行人物的路徑規(guī)劃。以路徑規(guī)劃中的尋路算法為切入點,深入討論了智能尋路算法在虛擬現實場景下的應用。本論文重點介紹了智能尋路中常用的A*算法,分析了標準的A*算法在實現時存在的問題,并針對這些問題對算法實現進行改進。改進主要有兩個方向,第一,針對A*算法中耗時較大的問題,采用最小堆存儲A*算法的開啟列表,從而可以快速的找出代價值最小的相鄰節(jié)點;第二,針對虛擬場景改進A*算法的啟發(fā)函數,給啟發(fā)函數添加更多適用于虛擬場景的啟發(fā)信息,在保證準確性的同時讓算法盡量少的遍歷地圖節(jié)點,從而提高算法的效率。本論文基于Unity3D引擎設計并制作出了以公園漫游為背景的虛擬場景,并為場景中的人物添加了多種交互的機制。然后重點研究了尋路算法在此場景下的應用,調整算法使其更適用于虛擬場景。首先,在尋路之前對場景地圖進行預處理,使用K-means算法對場景中的障礙進行分類,進而對障礙進行模塊化處理,從而減少尋路過程中需要遍歷的節(jié)點數;然后,在尋路之后對計算出的路徑進行平滑處理,這樣人物在最優(yōu)路徑上的行走會更加自然,避免不必要的轉向;最后,通過Unity3D引擎的碰撞檢測機制對動態(tài)障礙物進行位置的預判,用來達到對動態(tài)障礙物智能避障的目的。通過改進后的A*算法在虛擬公園場景中的應用,表明改進后的A*算法在經過調整之后,更適用于交互型虛擬場景下人物的動態(tài)路徑規(guī)劃。
【學位授予單位】：中國地質大學(北京)
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP301.6;TP391.9
【圖文】：

點都是試探性的，稱每一次訪問過的節(jié)點為當前節(jié)點，那么在算法開始時的第一個當前節(jié)點就是起始節(jié)點。在搜索的過程中，假設訪問到的當前節(jié)點為 V，首先將此節(jié)點的訪問標志 visited[v]的值置為“1”，表示此節(jié)點已經被探查過。然后順序訪問與 V 相鄰的所有節(jié)點，其中沒有被訪問過的節(jié)點當做下一次探查的當前節(jié)點。如果節(jié)點 V 的所有相鄰節(jié)點的訪問標志全都是“1”，則說明該節(jié)點的所有相鄰節(jié)點都被訪問過，就向上回溯，把當前節(jié)點設置為上一次探查過的當前節(jié)點。一直重復上述過程一直到整個連通圖的所有節(jié)點全都被訪問過。圖 2-1 展示了深度優(yōu)先搜索的一個經典示例。以頂點 A 為起始頂點進行深度優(yōu)先搜索，能夠遍歷這個連通圖的所有頂點。圖 2-1 左側是深度優(yōu)先搜索的過程，每個頂點旁邊的數字表示該頂點在遍歷時被訪問的次序。圖 2-1 右側是深度優(yōu)先搜索結果，此結果由搜索過程中所有訪問過的頂點以及搜索過程中經過的邊組成，從而構成一個連通的無向圖，實際上就是構成了樹，而這種由深度優(yōu)先搜索生成的樹稱為深度優(yōu)先生成樹（DFS 樹），包括原圖的 n 個頂點以及 n-1 條邊。

2.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索是一個逐層遍歷的過程，其搜索過程有些類似于樹的層序遍歷。搜索過程中，圖中有幾個頂點就需要重復多少步，當然，每一步還是有一個當前頂點，最初的當前頂點為起始頂點。在訪問當前頂點 v 時，首先設置該頂點訪問標志visited[v]的值為“1”，接著訪問頂點 v的每個未被訪問過的鄰接頂點1w ，2w ，…，tw ，接下來再順序訪問1w ，2w ，…，tw 的所有還沒被訪問過的鄰接頂點，然后再從這些訪問過的頂點出發(fā)，進一步訪問他們仍沒有被訪問過的領結頂點。按這種方式搜索直到圖中所有的頂點都已經被訪問過了為止。圖 2-2 展示了廣度優(yōu)先搜索的一個經典示例。以頂點 A 為起始頂點進行廣度優(yōu)先搜索。圖 2-2 左側是廣度優(yōu)先搜索的過程，每個頂點旁邊的數字表示該頂點在遍歷時被訪問的次序。圖 2-2 右側是廣度優(yōu)先搜索的結果，又稱為廣度優(yōu)先生成樹，包括原圖的 n 個頂點以及 n-1 條邊。

Dijkstra 算法適用于解決非負權值的單源最短路徑問題。這類問題可描述為給定一個有向帶權圖 D 與源點 v，各邊上的權值均非負。要求找出從 v 到 D 中其他各頂點的最短路徑。Dijkstra 算法采用的是一種貪心的策略，按照路徑長度的遞增次序，逐步生成最短路徑。首先，求出從起始頂點開始的一條最短路徑然后在最短路徑的基礎上求出長度次短的一條路徑，按照這種方式尋找，一直到從起始頂點到其他各頂點的最短路徑全部求出為止。圖 2-3 為一個帶權有向圖，以此為例介紹 Dijkstra 算法的具體做法。設圖中的起始頂點為 v0，此時，集合 S 中只有一個頂點。設 W=V-S，那么 W 中的頂點為圖中還未計算最短路徑的頂點。規(guī)定 W 中頂點到起始頂點0v 的距離為0v 到該頂點的邊上的權值，如果兩頂點之間不存在權值，則距離為無窮大。以此距離為基礎，接下來每計算出一條最短路徑（0v ，…，kv ），就將kv 加入到集合 S 中直到所有的頂點都加入到了集合 S 中。表 2-1 為 Dijkstra 算法逐步求解的過程。

【參考文獻】

相關期刊論文 前10條

1 邱磊;;利用跳點搜索算法加速A*尋路[J];蘭州理工大學學報;2015年03期

2 劉大瑞;錢程;林濤;;基于多目標A~*算法的游戲NPC路徑規(guī)劃[J];計算機應用研究;2014年08期

3 王紅衛(wèi);馬勇;謝勇;郭敏;;基于平滑A~*算法的移動機器人路徑規(guī)劃[J];同濟大學學報(自然科學版);2010年11期

4 倪樂波;戚鵬;遇麗娜;王婧;;Unity3d產品虛擬展示技術的研究與應用[J];數字技術與應用;2010年09期

5 王天順;張莉;;一種基于導航網格的路徑搜索技術[J];電腦知識與技術;2010年12期

6 蔡方方;楊士穎;張小鳳;劉東平;;雙層A~*算法在游戲尋路方面的研究[J];微型電腦應用;2010年01期

7 李艷軍;李智勇;陳思遠;;一種面向3D場景的實時自動路徑搜索方法[J];計算機應用;2010年01期

8 史輝;曹聞;朱述龍;朱寶山;;A~*算法的改進及其在路徑規(guī)劃中的應用[J];測繪與空間地理信息;2009年06期

9 張仁平;周慶忠;熊偉;王紅旗;;A~*算法改進算法及其應用[J];計算機系統應用;2009年09期

10 王同喜;孫淑霞;;基于A~*和Bresenham相結合的網絡游戲尋路算法設計與實現[J];成都理工大學學報(自然科學版);2007年04期

相關碩士學位論文 前3條

1 楊杰;具有端點方向約束的快速航跡規(guī)劃方法研究[D];華中科技大學;2013年

2 周小鏡;基于改進A*算法的游戲地圖尋徑的研究[D];西南大學;2011年

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

本文編號：2796818