[發(fā)明專利]一種面向虛擬現(xiàn)實(shí)的A*尋路優(yōu)化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810839896.0
• 申請(qǐng)日: 2018-07-27
• 公開(kāi)（公告）號(hào): CN109255467A
• 公開(kāi)（公告）日: 2019-01-22
• 發(fā)明（設(shè)計(jì)）人: 何小海;宋健;卿粼波;王正勇;吳小強(qiáng);吳曉紅;滕奇志
• 申請(qǐng)（專利權(quán)）人: 四川大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06F3/01;G06T19/00
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種面向虛擬現(xiàn)實(shí)的A^*尋路優(yōu)化方法，其特征在于包括以下步驟：

(1)在尋路前對(duì)整個(gè)虛擬場(chǎng)景進(jìn)行障礙物檢測(cè)，生成一個(gè)覆蓋整個(gè)虛擬場(chǎng)景的網(wǎng)格地圖，每個(gè)網(wǎng)格不僅包含坐標(biāo)信息，還包括障礙物信息；

(2)確定路徑的代價(jià)估計(jì)函數(shù)和啟發(fā)函數(shù)；

(3)確定路徑節(jié)點(diǎn)的方向信息和約束規(guī)則；

(4)根據(jù)(3)中方向信息和約束規(guī)則進(jìn)行遞歸查找，直至得到下一個(gè)搜索節(jié)點(diǎn)；

(5)根據(jù)(2)中的代價(jià)估計(jì)函數(shù)和啟發(fā)函數(shù)對(duì)(4)中得到的待搜索節(jié)點(diǎn)進(jìn)行代價(jià)估計(jì)，并從中選取代價(jià)最小的節(jié)點(diǎn)加入最優(yōu)路徑。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于步驟(3)中使用節(jié)點(diǎn)的方向信息來(lái)修正路徑搜索策略，修正方法如下：

對(duì)于路徑節(jié)點(diǎn)E，它的每個(gè)鄰接節(jié)點(diǎn)E_i都是待搜索節(jié)點(diǎn)，E_i的方向信息是其父節(jié)點(diǎn)E至本身節(jié)點(diǎn)的方向向量，則對(duì)于節(jié)點(diǎn)N＝(x_n,y_n)至其父節(jié)點(diǎn)N_p＝(x_pn,y_pn)的方向向量為：

。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于步驟(3)中使用節(jié)點(diǎn)的約束規(guī)則來(lái)修正路徑搜索策略，修正方法如下：

假設(shè)節(jié)點(diǎn)N＝(x_n,y_n)及其方向信息路徑終點(diǎn)D＝(x_d,y_d)及其方向信息若滿足以下約束條件中的任意一種，則節(jié)點(diǎn)N＝(x_n,y_n)是下一個(gè)路徑查找節(jié)點(diǎn)；

(1)當(dāng)dx_N·dx_D≥0且dy_D≥0時(shí)，節(jié)點(diǎn)(x_n,y_n+1)是不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(x_n+1,y_n+1)是可通過(guò)節(jié)點(diǎn)；

(2)當(dāng)dx_N·dx_D≥0且dy_D≤0時(shí)，節(jié)點(diǎn)(x_n,y_n-1)是不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(x_n+1,y_n-1)是可通過(guò)節(jié)點(diǎn)；

(3)當(dāng)dx_N·dx_D≤0且dy_D≥0時(shí)，節(jié)點(diǎn)(x_n,y_n+1)是不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(x_n-1,y_n+1)是可通過(guò)節(jié)點(diǎn)；

(4)當(dāng)dx_N·dx_D≤0且dy_D≤0時(shí)，節(jié)點(diǎn)(x_n,y_n-1)是不可通過(guò)節(jié)點(diǎn)且節(jié)點(diǎn)(x_n-1,y_n-1)是可通過(guò)節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于結(jié)合尋路節(jié)點(diǎn)的方向信息，采用深度優(yōu)先搜索和約束規(guī)則，節(jié)約了存儲(chǔ)空間，提高了尋路效率。