[發明專利]路徑生成方法及裝置、電子設備、存儲介質

有效

• 申請號: 201811260893.8
• 申請日: 2018-10-26
• 公開（公告）號: CN109432777B
• 公開（公告）日: 2021-11-12
• 發明（設計）人: 吳昊泰
• 申請（專利權）人: 網易（杭州）網絡有限公司
• 主分類號: A63F13/56
• 分類號: A63F13/56
• 代理公司: 北京律智知識產權代理有限公司 11438
• 代理人: 袁禮君;闞梓瑄

1.一種路徑生成方法，其特征在于，包括：

確定終點可行路點，并以所述終點可行路點為起點創建目標路樹；

通過起點估值函數對所述目標路樹上除所述起點之外的所有節點進行估值，并將估值結果最大的節點確定為起始路點；

在所述目標路樹上確定所述起始路點到所述起點的最短路徑；

通過終點估值函數對所述最短路徑上除所述起始路點之外的所有節點進行再次估值，將再次估值的估值結果最大的節點作為終止路點，以根據所述起始路點和所述終止路點生成尋路路徑；

其中，通過起點估值函數對所述目標路樹上除所述起點之外的所有節點進行估值包括：

確定所述起點到所述目標路樹上除所述起點之外的節點之間的第一距離；

確定所述起點到節點的第一向量以及所述節點到所述節點關聯的下一節點的第二向量之間的第一夾角；

根據所述第一距離以及所述第一夾角對所述目標路樹上除起點之外的所有節點進行估值，以得到估值結果；

通過終點估值函數對所述最短路徑上除所述起始路點之外的所有節點進行再次估值包括：

確定節點到所述最短路徑的終點之間的第二距離；

確定所述節點關聯的上一節點到所述節點的第三向量以及確定所述節點到所述終點的第四向量之間的第二夾角；

根據所述第二距離以及所述第二夾角對所述最短路徑上除所述起始路點之外的所有節點進行再次估值，以得到再次估值的估值結果。

2.根據權利要求1所述的路徑生成方法，其特征在于，確定終點可行路點包括：

遍歷所有路點，將離目標點距離最近的路點作為所述終點可行路點。

3.根據權利要求1所述的路徑生成方法，其特征在于，以所述終點可行路點為起點創建目標路樹包括：

以所述終點可行路點為起點，確定所述起點到其他節點的多個最短路徑，并根據所述多個最短路徑構建所述目標路樹。

4.根據權利要求1所述的路徑生成方法，其特征在于，在所述目標路樹上確定所述起始路點到所述起點的最短路徑包括：

在所述目標路樹上從所述起始路點開始查詢父節點，直至查詢到所述起點為止，以確定所述起始路點到所述起點之間的最短路徑。

5.一種路徑生成裝置，其特征在于，包括：

目標路樹構建模塊，用于確定終點可行路點，并以所述終點可行路點為起點創建目標路樹；

起始路點確定模塊，用于通過起點估值函數對所述目標路樹上除所述起點之外的所有節點進行估值，并將估值結果最大的節點確定為起始路點；

最短路徑確定模塊，用于在所述目標路樹上確定所述起始路點到所述起點的最短路徑；

尋路路徑生成模塊，用于通過終點估值函數對所述最短路徑上除所述起始路點之外的所有節點進行再次估值，將再次估值的估值結果最大的節點作為終止路點，以根據所述起始路點和所述終止路點生成尋路路徑；

其中，通過起點估值函數對所述目標路樹上除所述起點之外的所有節點進行估值包括：

確定所述起點到所述目標路樹上除所述起點之外的節點之間的第一距離；

確定所述起點到節點的第一向量以及所述節點到所述節點關聯的下一節點的第二向量之間的第一夾角；

根據所述第一距離以及所述第一夾角對所述目標路樹上除起點之外的所有節點進行估值，以得到估值結果；

通過終點估值函數對所述最短路徑上除所述起始路點之外的所有節點進行再次估值包括：

確定節點到所述最短路徑的終點之間的第二距離；

確定所述節點關聯的上一節點到所述節點的第三向量以及確定所述節點到所述終點的第四向量之間的第二夾角；

根據所述第二距離以及所述第二夾角對所述最短路徑上除所述起始路點之外的所有節點進行再次估值，以得到再次估值的估值結果。

6.一種電子設備，其特征在于，包括：

處理器；以及

存儲器，用于存儲所述處理器的可執行指令；

其中，所述處理器配置為經由執行所述可執行指令來執行權利要求1-4任意一項所述的路徑生成方法。

7.一種計算機可讀存儲介質，其上存儲有計算機程序，其特征在于，所述計算機程序被處理器執行時實現權利要求1-4任意一項所述的路徑生成方法。