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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

4 倪樂波;戚鵬;遇麗娜;王婧;;Unity3d產(chǎn)品虛擬展示技術(shù)的研究與應(yīng)用[J];數(shù)字技術(shù)與應(yīng)用;2010年09期

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

6 蔡方方;楊士穎;張小鳳;劉東平;;雙層A~*算法在游戲?qū)ぢ贩矫娴难芯縖J];微型電腦應(yīng)用;2010年01期

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

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

9 張仁平;周慶忠;熊偉;王紅旗;;A~*算法改進(jìn)算法及其應(yīng)用[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2009年09期

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

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

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

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

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

本文編號：2796818