[發(fā)明專利]一種高效分級(jí)尋路方法、裝置、介質(zhì)和設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 202210345629.4
• 申請(qǐng)日: 2022-04-02
• 公開（公告）號(hào): CN114470776B
• 公開（公告）日: 2022-07-08
• 發(fā)明（設(shè)計(jì)）人: 張佳亮;董偉;黃正雨;李鑒
• 申請(qǐng)（專利權(quán)）人: 北京優(yōu)锘科技有限公司
• 主分類號(hào): A63F13/56
• 分類號(hào): A63F13/56
• 代理公司: 北京安度修典專利代理事務(wù)所(特殊普通合伙) 11424
• 代理人: 楊方成;馬歡萍

本發(fā)明涉及一種高效分級(jí)尋路方法，包括基于路徑點(diǎn)序列和德洛內(nèi)三角化算法，生成標(biāo)準(zhǔn)尋路網(wǎng)格數(shù)據(jù)；在路徑點(diǎn)序列中選取N個(gè)路徑點(diǎn)作為宏觀路徑點(diǎn)，基于四個(gè)極值點(diǎn)數(shù)據(jù)與和宏觀路徑點(diǎn)生成宏觀尋路網(wǎng)格數(shù)據(jù)；根據(jù)Astar尋路算法在宏觀尋路網(wǎng)格數(shù)據(jù)上計(jì)算得到從起始查詢點(diǎn)與目標(biāo)查詢點(diǎn)之間的初步宏觀尋路路徑數(shù)據(jù)；對(duì)初步宏觀尋路路徑數(shù)據(jù)進(jìn)行處理得到最終宏觀尋路路徑數(shù)據(jù)；根據(jù)最終宏觀尋路路徑數(shù)據(jù)，分段進(jìn)行微觀標(biāo)準(zhǔn)尋路；合并分段微觀標(biāo)準(zhǔn)尋路結(jié)果，得到最終標(biāo)準(zhǔn)尋路路徑數(shù)據(jù)。本發(fā)明通過(guò)降低AStar算法的試錯(cuò)成本，使得尋路網(wǎng)格尋路計(jì)算時(shí)間被極大壓縮，提高了程序的響應(yīng)速度，使用戶體驗(yàn)得到顯著提升。本發(fā)明還涉及高效分級(jí)尋路裝置、介質(zhì)和設(shè)備。

技術(shù)領(lǐng)域

本發(fā)明涉及導(dǎo)航技術(shù)領(lǐng)域，尤其涉及一種高效分級(jí)尋路方法、裝置、介質(zhì)和設(shè)備。

背景技術(shù)

根據(jù)對(duì)目前游戲和GIS行業(yè)中主流軟件應(yīng)用的觀察，我們發(fā)現(xiàn)大家在尋路算法的選擇上基本都是使用AStar算法，或者是基于AStar算法的簡(jiǎn)單修改；但是由于AStar在計(jì)算尋路路徑時(shí)，會(huì)根據(jù)可尋路點(diǎn)依次逐個(gè)向前探索，如果當(dāng)前線路不通，則需要退回上一可尋路點(diǎn)重新探索，即AStar算法本身的計(jì)算過(guò)程存在試錯(cuò)成本，并且其試錯(cuò)成本會(huì)隨著起止點(diǎn)之間的尋路網(wǎng)格數(shù)量的增加而增加。于是在進(jìn)行跨越大量尋路網(wǎng)格的超長(zhǎng)路程的尋路計(jì)算中，試錯(cuò)成本會(huì)隨之增加，程序的響應(yīng)時(shí)間會(huì)被拉長(zhǎng)，進(jìn)而導(dǎo)致用戶體驗(yàn)下降。

為此本領(lǐng)域迫切需要開發(fā)出一種能夠降低試錯(cuò)成本的尋路網(wǎng)絡(luò)數(shù)據(jù)索引方法。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問(wèn)題是針對(duì)現(xiàn)有技術(shù)的不足，提供一種高效分級(jí)尋路方法、裝置、介質(zhì)和設(shè)備。

本發(fā)明解決上述技術(shù)問(wèn)題的技術(shù)方案如下：

一種高效分級(jí)尋路方法，所述方法包括：

基于數(shù)據(jù)源提供的路徑點(diǎn)序列和德洛內(nèi)三角化算法，生成標(biāo)準(zhǔn)尋路網(wǎng)格數(shù)據(jù)；

遍歷數(shù)據(jù)源路徑點(diǎn)數(shù)量M，計(jì)算M個(gè)路徑點(diǎn)在x,y方向上的四個(gè)極值點(diǎn)數(shù)據(jù)，并且將所述路徑點(diǎn)數(shù)量M通過(guò)開方運(yùn)算得到數(shù)量閾值N，在所述路徑點(diǎn)序列中均勻選取N個(gè)路徑點(diǎn)作為宏觀路徑點(diǎn)，基于四個(gè)極值點(diǎn)數(shù)據(jù)與宏觀路徑點(diǎn)通過(guò)德洛內(nèi)三角化算法，生成宏觀尋路網(wǎng)格數(shù)據(jù)；

根據(jù)Astar尋路算法在所述宏觀尋路網(wǎng)格數(shù)據(jù)上計(jì)算得到初步宏觀尋路路徑數(shù)據(jù)，所述初步宏觀尋路路徑數(shù)據(jù)為從起始查詢點(diǎn)與目標(biāo)查詢點(diǎn)之間的路徑數(shù)據(jù)；

對(duì)所述初步宏觀尋路路徑數(shù)據(jù)進(jìn)行處理得到最終宏觀尋路路徑數(shù)據(jù)；

根據(jù)所述最終宏觀尋路路徑數(shù)據(jù)，結(jié)合所述標(biāo)準(zhǔn)尋路網(wǎng)格數(shù)據(jù)，分段進(jìn)行微觀標(biāo)準(zhǔn)尋路；

合并分段微觀標(biāo)準(zhǔn)尋路結(jié)果，得到最終標(biāo)準(zhǔn)尋路路徑數(shù)據(jù)。

進(jìn)一步地，基于數(shù)據(jù)源提供的路徑點(diǎn)序列和德洛內(nèi)三角化算法，生成標(biāo)準(zhǔn)尋路網(wǎng)格數(shù)據(jù)，具體包括：

將所述數(shù)據(jù)源提供的路徑點(diǎn)序列輸入至德洛內(nèi)三角化算法中，得到所述尋路網(wǎng)格數(shù)據(jù)；

其中，所述尋路網(wǎng)格數(shù)據(jù)包括三角網(wǎng)序列Mesh，所述三角網(wǎng)序列Mesh中包括多個(gè)三角形Triangle，所述三角形的三個(gè)頂點(diǎn)分別對(duì)應(yīng)三個(gè)路徑點(diǎn)。

進(jìn)一步地，所述根據(jù)Astar尋路算法在所述宏觀尋路網(wǎng)格數(shù)據(jù)上計(jì)算得到從起始查詢點(diǎn)與目標(biāo)查詢點(diǎn)之間的初步宏觀尋路路徑數(shù)據(jù)，具體包括：

根據(jù)起始查詢點(diǎn)位置，判斷所述起始查詢點(diǎn)處于所述宏觀尋路網(wǎng)格數(shù)據(jù)中的哪個(gè)三角形中，并計(jì)算得到所述起始查詢點(diǎn)距離該三角形中最近的首個(gè)路徑點(diǎn)；

根據(jù)目標(biāo)查詢點(diǎn)位置，判斷所述目標(biāo)查詢點(diǎn)處于所述宏觀尋路網(wǎng)格數(shù)據(jù)中的哪個(gè)三角形中，并計(jì)算得到所述目標(biāo)查詢點(diǎn)距離該三角形中最近的末尾路徑點(diǎn)；

根據(jù)AStar尋路算法，在所述宏觀尋路網(wǎng)格數(shù)據(jù)中計(jì)算得到從所述首個(gè)路徑點(diǎn)到末尾路徑點(diǎn)之間的初步宏觀尋路路徑數(shù)據(jù)。

進(jìn)一步地，所述對(duì)所述初步宏觀尋路路徑數(shù)據(jù)進(jìn)行處理得到最終宏觀尋路路徑數(shù)據(jù)，具體包括：