[發(fā)明專利]路徑的搜索方法、裝置、處理器和電子裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201711279409.1
• 申請(qǐng)日: 2017-12-06
• 公開(kāi)（公告）號(hào): CN108268971B
• 公開(kāi)（公告）日: 2021-12-07
• 發(fā)明（設(shè)計(jì)）人: 王杰
• 申請(qǐng)（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06F16/29;G06F16/9537;A63F13/56
• 代理公司: 北京康信知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11240
• 代理人: 趙囡囡

本發(fā)明公開(kāi)了一種路徑的搜索方法、裝置、處理器和電子裝置。其中，該方法包括：檢測(cè)待尋路區(qū)域中用于表示路徑起點(diǎn)的當(dāng)前節(jié)點(diǎn)以及用于表示路徑終點(diǎn)的目標(biāo)節(jié)點(diǎn)；以當(dāng)前節(jié)點(diǎn)為中心，沿多個(gè)方向查找每個(gè)方向上最長(zhǎng)路徑的終點(diǎn)對(duì)應(yīng)的跳點(diǎn)，得到第一節(jié)點(diǎn)集合；在第一方向上查找跳點(diǎn)，得到第二節(jié)點(diǎn)集合；從第一節(jié)點(diǎn)集合和第二節(jié)點(diǎn)集合的所有跳點(diǎn)中查找目標(biāo)跳點(diǎn)；將路徑最短的路徑組合確定為路徑起點(diǎn)到路徑終點(diǎn)的路徑。本發(fā)明解決了搜索路徑的效率比較低的技術(shù)問(wèn)題。

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

本發(fā)明涉及數(shù)據(jù)處理領(lǐng)域，具體而言，涉及一種路徑的搜索方法、裝置、處理器和電子裝置。

背景技術(shù)

尋路方法用途眾多，例如在游戲和地圖中進(jìn)行尋路。在游戲中通常會(huì)用到尋路A*方法每次從有序隊(duì)列中取出優(yōu)先級(jí)最高的節(jié)點(diǎn)，然后擴(kuò)展該節(jié)點(diǎn)的八個(gè)鄰居，直到找到目標(biāo)節(jié)點(diǎn)為止。JPS方法每次從有序隊(duì)列中取出優(yōu)先級(jí)最高的點(diǎn)，然后擴(kuò)展該點(diǎn)附近的跳點(diǎn)，直到找到目標(biāo)點(diǎn)為止。

JPS又名跳點(diǎn)搜索方法(Jump Point Search)，是基于Grid格子的尋路方法。JPS根據(jù)當(dāng)前節(jié)點(diǎn)的方向、并基于跳點(diǎn)的策略來(lái)擴(kuò)展后繼節(jié)點(diǎn)，遵循確定強(qiáng)迫鄰居、跳點(diǎn)的定義，以及確定后繼節(jié)點(diǎn)的拓展原則，具體流程如下：

一，若當(dāng)前節(jié)點(diǎn)的當(dāng)前方向是直線方向：(1)如果當(dāng)前節(jié)點(diǎn)的左后方不可走且左方可走(即左方是強(qiáng)迫鄰居)，則沿當(dāng)前節(jié)點(diǎn)左前方和左方尋找不在關(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)；(2)如果當(dāng)前節(jié)點(diǎn)的當(dāng)前方向可走，則沿當(dāng)前節(jié)點(diǎn)的當(dāng)前方向?qū)ふ也辉陉P(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)；(3)如果當(dāng)前節(jié)點(diǎn)的右后方不可走且右方可走(右方是強(qiáng)迫鄰居)，則沿當(dāng)前節(jié)點(diǎn)右前方和右方尋找不在關(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)；

二，若當(dāng)前節(jié)點(diǎn)的當(dāng)前方向?yàn)閷?duì)角線方向：(1)如果當(dāng)前節(jié)點(diǎn)的當(dāng)前方向的水平分量可走(例如當(dāng)前節(jié)點(diǎn)的當(dāng)前為東北方向，則水平分量為東)，則沿當(dāng)前節(jié)點(diǎn)的當(dāng)前方向的水平分量尋找不在關(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)；(2)如果當(dāng)前節(jié)點(diǎn)的當(dāng)前方向可走，則沿當(dāng)前節(jié)點(diǎn)的當(dāng)前方向?qū)ふ也辉陉P(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)；(3)如果當(dāng)前節(jié)點(diǎn)的當(dāng)前方向的垂直分量可走(例如當(dāng)前節(jié)點(diǎn)的當(dāng)前為東北方向，則垂直分量為北)，則沿當(dāng)前節(jié)點(diǎn)的當(dāng)前方向的垂直分量尋找不在關(guān)閉節(jié)點(diǎn)集合的跳點(diǎn)。

A*方法包括如下步驟：

Step 1.將起始點(diǎn)加入開(kāi)啟節(jié)點(diǎn)集合；

Step 2.重復(fù)以下工作：

當(dāng)開(kāi)啟節(jié)點(diǎn)集合為空，則結(jié)束程序，此時(shí)沒(méi)有路徑。

尋找開(kāi)啟節(jié)點(diǎn)集合中F值最小的節(jié)點(diǎn)，設(shè)為當(dāng)前點(diǎn)關(guān)閉節(jié)點(diǎn)集合，從開(kāi)啟節(jié)點(diǎn)集合中移出當(dāng)前點(diǎn)關(guān)閉節(jié)點(diǎn)集合；關(guān)閉節(jié)點(diǎn)集合中加入當(dāng)前點(diǎn)關(guān)閉節(jié)點(diǎn)集合；若當(dāng)前節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則結(jié)束程序，此時(shí)有路徑生成，此時(shí)由目標(biāo)節(jié)點(diǎn)開(kāi)始逐級(jí)追溯路徑上每一個(gè)節(jié)點(diǎn)x的上一級(jí)父節(jié)點(diǎn)parent(x)，直至回溯到開(kāi)始節(jié)點(diǎn)，此時(shí)回溯的各節(jié)點(diǎn)即為路徑。

對(duì)當(dāng)前節(jié)點(diǎn)的八個(gè)方向的每一個(gè)相鄰節(jié)點(diǎn)來(lái)說(shuō)，如果相鄰節(jié)點(diǎn)不可通過(guò)或者已經(jīng)在關(guān)閉節(jié)點(diǎn)集合中，略過(guò)。如果相鄰節(jié)點(diǎn)不在開(kāi)啟節(jié)點(diǎn)集合中，加入開(kāi)啟節(jié)點(diǎn)集合中；如果相鄰節(jié)點(diǎn)在開(kāi)啟節(jié)點(diǎn)集合中，G值判定，若此路徑G值比之前路徑小，則相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，同時(shí)更新G值與F值。反之，則保持原來(lái)的節(jié)點(diǎn)關(guān)系與G值、F值。G值表示從起點(diǎn)到當(dāng)前點(diǎn)路徑耗費(fèi)；H值表示不考慮不可通過(guò)區(qū)域，當(dāng)前點(diǎn)到終點(diǎn)的理論路徑耗費(fèi)，其中，F(xiàn)＝G+F。