[發(fā)明專利]跳點(diǎn)搜索方法、裝置、設(shè)備及存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 202110371042.6
• 申請(qǐng)日: 2021-04-07
• 公開（公告）號(hào): CN112915541B
• 公開（公告）日: 2022-09-23
• 發(fā)明（設(shè)計(jì)）人: 錢海江;費(fèi)翔
• 申請(qǐng)（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號(hào): G06F16/29
• 分類號(hào): G06F16/29;A63F13/56;A63F13/52;G06F16/9535
• 代理公司: 北京三高永信知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11138
• 代理人: 祝亞男

1.一種跳點(diǎn)搜索方法，其特征在于，所述方法包括：

在網(wǎng)格地圖中確定非行走節(jié)點(diǎn)的節(jié)點(diǎn)位置，所述非行走節(jié)點(diǎn)包括阻擋節(jié)點(diǎn)以及動(dòng)態(tài)阻擋節(jié)點(diǎn)中的至少之一，所述阻擋節(jié)點(diǎn)是無法通行的節(jié)點(diǎn)，所述動(dòng)態(tài)阻擋節(jié)點(diǎn)是可通行狀態(tài)隨變化因素變化的節(jié)點(diǎn)，所述可通行狀態(tài)用于指示所述動(dòng)態(tài)阻擋節(jié)點(diǎn)能否通行；

根據(jù)所述非行走節(jié)點(diǎn)的節(jié)點(diǎn)位置，確定所述網(wǎng)格地圖的預(yù)處理數(shù)據(jù)，在所述網(wǎng)格地圖為正四邊形網(wǎng)格地圖的情況下，所述預(yù)處理數(shù)據(jù)包括所述網(wǎng)格地圖中的每個(gè)節(jié)點(diǎn)在軸方向以及對(duì)角方向上到所述非行走節(jié)點(diǎn)的距離；在所述網(wǎng)格地圖為正六邊形網(wǎng)格地圖的情況下，所述預(yù)處理數(shù)據(jù)包括所述網(wǎng)格地圖中的每個(gè)節(jié)點(diǎn)在軸方向上到所述非行走節(jié)點(diǎn)的距離；

根據(jù)所述預(yù)處理數(shù)據(jù)，在當(dāng)前節(jié)點(diǎn)的兩側(cè)節(jié)點(diǎn)中確定目標(biāo)非行走節(jié)點(diǎn)，所述兩側(cè)節(jié)點(diǎn)的排布方向與所述當(dāng)前節(jié)點(diǎn)的第一搜索方向平行，所述兩側(cè)節(jié)點(diǎn)與待確認(rèn)節(jié)點(diǎn)相鄰，所述待確認(rèn)節(jié)點(diǎn)是處于所述第一搜索方向上的節(jié)點(diǎn)；

響應(yīng)于所述目標(biāo)非行走節(jié)點(diǎn)滿足阻擋條件，將所述目標(biāo)非行走節(jié)點(diǎn)確定為目標(biāo)阻擋節(jié)點(diǎn)，所述阻擋條件包括所述目標(biāo)非行走節(jié)點(diǎn)為所述阻擋節(jié)點(diǎn)，或，所述目標(biāo)非行走節(jié)點(diǎn)為所述動(dòng)態(tài)阻擋節(jié)點(diǎn)，且所述動(dòng)態(tài)阻擋節(jié)點(diǎn)的可通行狀態(tài)為無法通行；

根據(jù)所述目標(biāo)阻擋節(jié)點(diǎn)的節(jié)點(diǎn)位置，沿所述第一搜索方向進(jìn)行搜索，得到所述第一搜索方向上的跳點(diǎn)，所述跳點(diǎn)是路徑前進(jìn)方向發(fā)生改變的節(jié)點(diǎn)。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述目標(biāo)阻擋節(jié)點(diǎn)的節(jié)點(diǎn)位置，沿所述第一搜索方向進(jìn)行搜索，得到所述第一搜索方向上的跳點(diǎn)，包括：

根據(jù)所述目標(biāo)阻擋節(jié)點(diǎn)的節(jié)點(diǎn)位置，在所述待確認(rèn)節(jié)點(diǎn)中確定具有強(qiáng)迫鄰居的目標(biāo)待確認(rèn)節(jié)點(diǎn)，所述強(qiáng)迫鄰居是所述目標(biāo)待確認(rèn)節(jié)點(diǎn)和所述目標(biāo)阻擋節(jié)點(diǎn)共同相鄰的節(jié)點(diǎn)，所述強(qiáng)迫鄰居位于所述第一搜索方向的前方；

將所述目標(biāo)待確認(rèn)節(jié)點(diǎn)確定為所述跳點(diǎn)。

3.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

響應(yīng)于所述當(dāng)前節(jié)點(diǎn)與所述跳點(diǎn)之間存在所述非行走節(jié)點(diǎn)，且所述非行走節(jié)點(diǎn)為所述阻擋節(jié)點(diǎn)，或，所述非行走節(jié)點(diǎn)為所述動(dòng)態(tài)阻擋節(jié)點(diǎn)，且所述動(dòng)態(tài)阻擋節(jié)點(diǎn)的可通行狀態(tài)為無法通行，舍棄所述跳點(diǎn)，并終止在所述第一搜索方向上搜索跳點(diǎn)；

根據(jù)所述預(yù)處理數(shù)據(jù)沿所述當(dāng)前節(jié)點(diǎn)的第二搜索方向進(jìn)行搜索，所述第二搜索方向與所述第一搜索方向不同。

4.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

響應(yīng)于在所述第一搜索方向上搜索到至少兩個(gè)跳點(diǎn)，將與所述當(dāng)前節(jié)點(diǎn)距離最短的跳點(diǎn)確定為所述跳點(diǎn)。

5.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

在所述第一搜索方向上搜索終止節(jié)點(diǎn)，所述終止節(jié)點(diǎn)是尋路路徑的終點(diǎn)；

響應(yīng)于在所述第一搜索方向上搜索到所述終止節(jié)點(diǎn)，結(jié)束執(zhí)行根據(jù)所述預(yù)處理數(shù)據(jù)沿所述當(dāng)前節(jié)點(diǎn)的所述第一搜索方向進(jìn)行搜索的步驟。

6.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

響應(yīng)于所述網(wǎng)格地圖中靜態(tài)節(jié)點(diǎn)的可通行狀態(tài)產(chǎn)生變化，基于更新后的所述網(wǎng)格地圖中所述非行走節(jié)點(diǎn)的節(jié)點(diǎn)位置更新所述預(yù)處理數(shù)據(jù)，所述靜態(tài)節(jié)點(diǎn)為所述網(wǎng)格地圖中除所述動(dòng)態(tài)阻擋節(jié)點(diǎn)以外的節(jié)點(diǎn)。

7.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

將節(jié)點(diǎn)集合中權(quán)重值最低的待搜索節(jié)點(diǎn)確定為所述當(dāng)前節(jié)點(diǎn)，所述權(quán)重值是起始節(jié)點(diǎn)到所述待搜索節(jié)點(diǎn)的路徑的距離和所述待搜索節(jié)點(diǎn)到終止節(jié)點(diǎn)的預(yù)估路徑的距離之和；

其中，所述節(jié)點(diǎn)集合用于存儲(chǔ)所述待搜索節(jié)點(diǎn)，所述起始節(jié)點(diǎn)是尋路路徑的起點(diǎn)。

8.根據(jù)權(quán)利要求7所述的方法，其特征在于，所述方法還包括：

將所述跳點(diǎn)加入所述節(jié)點(diǎn)集合，以更新所述節(jié)點(diǎn)集合。