[發明專利]跳點搜索方法、裝置、設備及存儲介質

有效

• 申請號: 202110371042.6
• 申請日: 2021-04-07
• 公開（公告）號: CN112915541B
• 公開（公告）日: 2022-09-23
• 發明（設計）人: 錢海江;費翔
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;A63F13/56;A63F13/52;G06F16/9535
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 祝亞男

本申請公開了一種跳點搜索方法、裝置、設備及存儲介質，屬于路徑規劃技術領域。所述方法包括：在網格地圖中確定非行走節點的節點位置；根據非行走節點的節點位置，確定網格地圖的預處理數據，預處理數據用于反映網格地圖中的可行走節點與非行走節點的相對位置；根據預處理數據沿當前節點的第一搜索方向進行搜索，得到第一搜索方向上的跳點，跳點是路徑前進方向發生改變的節點。在搜索跳點時，無需對當前節點周圍的節點挨個進行搜索，而是基于預處理數據直接確定出無法通行的節點的位置，從而搜索到跳點。能夠提升搜索跳點的效率，從而減少路徑規劃時消耗的時間，提升了路徑規劃的效率。

技術領域

本申請涉及路徑規劃技術領域，特別涉及一種跳點搜索方法、裝置、設備及存儲介質。

背景技術

在基于網格地圖實現控制尋路對象進行移動的場景下(例如控制虛擬角色在虛擬環境中移動的游戲以及控制機器人移動)，由于網格地圖中存在阻擋(也稱阻擋節點，例如虛擬環境中的石頭所在節點)，因此需要進行路徑規劃。

為提升路徑規劃效率，避免在路徑規劃時搜索網格地圖中的全部節點，客戶端通常采用跳點搜索(Jump Point Search，JPS)算法實現上述路徑規劃。客戶端會從起始節點開始沿搜索方向(包括軸方向以及對角方向)搜索網格地圖中的跳點，并在搜索到跳點后，沿搜索到的該跳點的搜索方向繼續搜索下一個跳點，直至搜索到終止節點。客戶端會基于搜索到的跳點(包括起始節點、終止節點以及起始節點與終止節點間的跳點)實現規劃路徑，規劃的尋路路徑會經過搜索到的跳點。其中，跳點是導致路徑前進方向發生改變的節點，具體是根據網格地圖中阻擋節點的位置確定的。基于上述方式可以確定一條避開阻擋的尋路路徑。

當網格地圖中節點數量較多時，在進行路徑規劃時仍需要對大量節點周圍的節點挨個進行搜索才能確定出跳點，會導致路徑規劃的消耗時間較長，效率較低的問題。

發明內容

本申請提供了一種跳點搜索方法、裝置、設備及存儲介質，可以提升路徑規劃的效率。所述技術方案如下：

根據本申請的一方面，提供了一種跳點搜索方法，所述方法包括：

在網格地圖中確定非行走節點的節點位置；

根據所述非行走節點的節點位置，確定所述網格地圖的預處理數據，所述預處理數據用于反映所述網格地圖中的可行走節點與所述非行走節點的相對位置；

根據所述預處理數據沿當前節點的第一搜索方向進行搜索，得到所述第一搜索方向上的跳點，所述跳點是路徑前進方向發生改變的節點。

根據本申請的另一方面，提供了一種跳點搜索裝置，所述裝置包括：

確定模塊，用于在網格地圖中確定非行走節點的節點位置；

處理模塊，用于根據所述非行走節點的節點位置，確定所述網格地圖的預處理數據，所述預處理數據用于反映所述網格地圖中的可行走節點與所述非行走節點的相對位置；

搜索模塊，用于根據所述預處理數據沿當前節點的第一搜索方向進行搜索，得到所述第一搜索方向上的跳點，所述跳點是路徑前進方向發生改變的節點。

在一個可選的設計中，所述搜索模塊，用于：

根據所述預處理數據，在所述當前節點的兩側節點中確定目標阻擋節點，所述兩側節點的排布方向與所述第一搜索方向平行，所述兩側節點與待確認節點相鄰，所述待確認節點是處于所述第一搜索方向上的節點；

根據所述目標阻擋節點的節點位置，沿所述第一搜索方向進行搜索，得到所述跳點。

在一個可選的設計中，所述非行走節點包括阻擋節點以及動態阻擋節點中的至少之一，所述阻擋節點是無法通行的節點，所述動態阻擋節點是可通行狀態隨變化因素變化的節點，所述可通行狀態用于指示所述動態阻擋節點能否通行；所述搜索模塊，用于：