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

有效

• 申請號: 201711279409.1
• 申請日: 2017-12-06
• 公開（公告）號: CN108268971B
• 公開（公告）日: 2021-12-07
• 發明（設計）人: 王杰
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F16/29;G06F16/9537;A63F13/56
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 趙囡囡

1.一種路徑的搜索方法，其特征在于，包括：

檢測待尋路區域中用于表示路徑起點的當前節點以及用于表示路徑終點的目標節點；

以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合；

在第一方向上查找跳點，得到第二節點集合，其中，目標節點處于所述第一方向，所述多個方向包括所述第一方向；

從所述第一節點集合和所述第二節點集合的所有跳點中查找目標跳點，其中，所述當前節點到所述目標跳點之間的第一路徑以及所述目標跳點到所述目標節點之間的第二路徑的路徑組合的路徑最短；

將路徑最短的所述路徑組合確定為所述路徑起點到所述路徑終點的路徑；

在以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合之前，所述方法還包括：對所述待尋路區域內的所有節點進行編碼，其中，所述編碼的數據位用于表示可行進節點和不可行進節點；利用指令從所述編碼中查找所述所有節點中的跳點和阻擋節點；

在后續尋找某個方向的節點時，直接獲取編碼已經查找到的所述所有節點中的跳點和阻擋節點。

2.根據權利要求1所述的方法，其特征在于，在第一方向上查找跳點，得到第二節點集合包括：

在所述第一方向上查找中間跳點和所述中間跳點的下一級跳點；

將所述下一級跳點的父節點設置為所述當前節點；

將父節點為所述當前節點的所有所述下一級跳點作為所述第二節點集合。

3.根據權利要求1所述的方法，其特征在于，從所述第一節點集合和所述第二節點集合中查找目標跳點包括：

在所述目標跳點為所述目標節點的情況下，判斷從所述當前節點到所述目標節點是否為直線路徑可到達；

在所述當前節點與所述目標節點之間通過直線路徑不可到達的情況下，查找拐點，其中，所述當前節點與所述拐點之間為直線路徑，且所述拐點與所述目標節點之間為直線路徑；

將查找到的拐點作為所述目標跳點。

4.根據權利要求3所述的方法，其特征在于，在所述當前節點與所述目標節點之間通過直線路徑不可到達的情況下，查找拐點包括：

獲取所述目標節點的坐標和所述當前節點的坐標在橫坐標上的第一坐標差和在縱坐標上的第二坐標差；

將所述第一坐標差和所述第二坐標差為坐標的節點作為所述拐點。

5.根據權利要求1所述的方法，其特征在于，以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合包括：

以所述當前節點為中心，沿多個方向查找每個方向上離所述當前節點最近的跳點，其中，所述跳點包括邊界節點和阻擋節點；

將所述每個方向上的所有所述跳點集合確定為所述第一節點集合。

6.根據權利要求1所述的方法，其特征在于，

在以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合之前，所述方法還包括：檢測所述當前節點所在的當前區域和所述目標節點所在的目標區域是否在同一連通區域；

以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合包括：在檢測出所述當前區域和所述目標區域在所述同一連通區域的情況下，以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點，得到第一節點集合。

7.根據權利要求6所述的方法，其特征在于，在檢測所述當前節點所在的當前區域和所述目標節點所在的目標區域是否在同一連通區域之后，所述方法還包括：

在檢測出所述當前區域和所述目標區域不在所述同一連通區域的情況下，不再執行以所述當前節點為中心，沿多個方向查找每個方向上最長路徑的終點對應的跳點。

8.根據權利要求6所述的方法，其特征在于，在檢測所述當前節點所在的當前區域和所述目標節點所在的目標區域是否在同一連通區域之前，所述方法還包括：

在所述待尋路區域中查找連通區域，其中，所述連通區域中的每個節點與所述連通區域中的至少一個節點相鄰。