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

有效

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

本公開是關于一種路徑生成方法及裝置、電子設備、存儲介質(zhì)，涉及計算機技術領域，該方法包括：確定終點可行路點，并以所述終點可行路點為起點創(chuàng)建目標路樹；對所述目標路樹上的多個節(jié)點進行估值，并根據(jù)估值結(jié)果從所述多個節(jié)點中確定起始路點；在所述目標路樹上確定所述起始路點到所述起點的最短路徑；對所述最短路徑上的多個節(jié)點進行再次估值，并根據(jù)再次估值的估值結(jié)果確定終止路點，以根據(jù)所述起始路點和所述終止路點生成尋路路徑。本公開能夠得到準確的起始路點和終止路點，減少了計算量且能夠生成準確的路徑。

技術領域

本公開涉及計算機技術領域，具體而言，涉及一種路徑生成方法、路徑生成裝置、電子設備以及計算機可讀存儲介質(zhì)。

背景技術

在游戲應用中，一般有兩類尋路方式，一類是基于RecastDetour的尋路系統(tǒng)，另一類是路點尋路。

相關技術中，在進行路點尋路時，大多采用和起點最近的路點作為起始路點，采用和終點最近的路點作為終止路點；或者多找?guī)讉€路點，進而根據(jù)路點的路徑距離選擇合適的起始路點和終止路點。例如，在起點附近尋找n個路點作為起始路點，在終點附近尋找m個路點作為起始路點，計算n*m條路徑的長度，即多次計算最短路徑，從而選取最短的一條作為最終路徑。

在這種方式中，得到最終路徑前，需要計算n*m次路徑，且上述算法必須全量加載尋路圖，計算量和加載量較大，因此導致效率較低，難以快速確定最短路徑；由于最終路徑不可控，導致路徑的精度較低，導致得到的路徑較僵硬，不符合實際尋路情況；另外，由于無法加載局部尋路圖，可能導致路徑無法到達，路徑準確性較低。

需要說明的是，在上述背景技術部分公開的數(shù)據(jù)僅用于加強對本公開的背景的理解，因此可以包括不構(gòu)成對本領域普通技術人員已知的現(xiàn)有技術的數(shù)據(jù)。

發(fā)明內(nèi)容

本公開的目的在于提供一種路徑生成方法及裝置、電子設備、存儲介質(zhì)，進而至少在一定程度上克服由于相關技術的限制和缺陷而導致的不能快速準確地得到路徑的問題。

本公開的其他特性和優(yōu)點將通過下面的詳細描述變得顯然，或部分地通過本公開的實踐而習得。

根據(jù)本公開的一個方面，提供一種路徑生成方法，包括：確定終點可行路點，并以所述終點可行路點為起點創(chuàng)建目標路樹；對所述目標路樹上的多個節(jié)點進行估值，并根據(jù)估值結(jié)果從所述多個節(jié)點中確定起始路點；在所述目標路樹上確定所述起始路點到所述起點的最短路徑；對所述最短路徑上的多個節(jié)點進行再次估值，并根據(jù)再次估值的估值結(jié)果確定終止路點，以根據(jù)所述起始路點和所述終止路點生成尋路路徑。

在本公開的一種示例性實施例中，確定終點可行路點包括：遍歷所有路點，將離目標點距離最近的路點作為所述終點可行路點。

在本公開的一種示例性實施例中，以所述終點可行路點為起點創(chuàng)建目標路樹包括：以所述終點可行路點為起點，確定所述起點到其他節(jié)點的多個最短路徑，并根據(jù)所述多個最短路徑構(gòu)建所述目標路樹。

在本公開的一種示例性實施例中，對所述目標路樹上的多個節(jié)點進行估值，并根據(jù)估值結(jié)果從多個節(jié)點中確定起始路點包括：通過起點估值函數(shù)對所述目標路樹上除所述起點之外的所有節(jié)點進行估值；將估值結(jié)果最大的節(jié)點確定為所述起始路點。

在本公開的一種示例性實施例中，通過起點估值函數(shù)對所述目標路樹上除所述起點之外的所有節(jié)點進行估值包括：確定所述起點到所述目標路樹上除所述起點之外的節(jié)點之間的第一距離；確定所述起點到節(jié)點的第一向量以及所述節(jié)點到所述節(jié)點關聯(lián)的下一節(jié)點的第二向量之間的第一夾角；根據(jù)所述第一距離以及所述第一夾角對所述目標路樹上除起點之外的所有節(jié)點進行估值，以得到估值結(jié)果。

在本公開的一種示例性實施例中，在所述目標路樹上確定所述起始路點到所述起點的最短路徑包括：在所述目標路樹上從所述起始路點開始查詢父節(jié)點，直至查詢到所述起點為止，以確定所述起始路點到所述起點之間的最短路徑。