[發(fā)明專利]路徑找尋方法、終端及計算機可讀存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 202110066005.4
• 申請日: 2021-01-18
• 公開（公告）號: CN112807682B
• 公開（公告）日: 2023-06-27
• 發(fā)明（設計）人: 魏新宇;吳春琳;陳啟晗;鄧冬生;邱登輝
• 申請（專利權）人: 尚娛軟件（深圳）有限公司
• 主分類號: A63F13/56
• 分類號: A63F13/56
• 代理公司: 深圳市恒程創(chuàng)新知識產(chǎn)權代理有限公司 44542
• 代理人: 苗廣冬

本發(fā)明提出的一種路徑找尋方法、終端及計算機可讀存儲介質(zhì)，所述方法包括步驟：獲取地圖數(shù)據(jù)中的起點和終點；根據(jù)所述起點和終點以A?STAR算法執(zhí)行尋路操作；在以所述A?STAR算法執(zhí)行尋路操作時，若迭代次數(shù)達到預設次數(shù)，則根據(jù)所述起點和終點以單源最短路徑算法執(zhí)行尋路操作。通過在A?STAR算法計算到一定時間仍未求出尋路路徑時，通過單源最短路徑算法進行尋路操作，使得在地圖較小時，直接通過A?STAR算法計算，而在地圖較大時，則轉換為快速算法計算，在保證了尋路準確度的基礎上，提升了尋路效率。

技術領域

本發(fā)明涉及終端控制領域，尤其涉及一種路徑找尋方法、終端及計算機可讀存儲介質(zhì)。

背景技術

尋路一直是很多游戲中一個重要的計算環(huán)節(jié)，游戲需要根據(jù)需求的起點和終點生成一條路徑出來。目前2D網(wǎng)格游戲的主流使用尋路算法為A-STAR算法，雖然通過A-STAR算法能夠計算出準確地尋路路徑，但其運算所需的時間較長，尤其對于一些較大的地圖而言，尋路時間會因為尋路地圖成幾何增大。

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

本發(fā)明的主要目的在于提出一種路徑找尋方法、終端及計算機可讀存儲介質(zhì)，旨在解決現(xiàn)有技術中通過A-STAR算法計算尋路路徑所需的時間較長的問題。

為實現(xiàn)上述目的，本發(fā)明提供一種路徑找尋方法，所述方法包括步驟：

獲取地圖數(shù)據(jù)中的起點和終點；

根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作；

在以所述A-STAR算法執(zhí)行尋路操作時，若迭代次數(shù)達到預設次數(shù)，則根據(jù)所述起點和終點以單源最短路徑算法執(zhí)行尋路操作。

可選地，所述根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作的步驟包括：

將所述起點加入到第一列表中；

獲取所述第一列表中標記距離最小的節(jié)點，獲取該節(jié)點與所述起點之間的前置節(jié)點，將該節(jié)點與所述前置節(jié)點關聯(lián)后移動至第二列表中，并對迭代次數(shù)進行累加；

獲取所述標記距離最小的節(jié)點對應的后繼節(jié)點，判斷所述后繼節(jié)點中是否存在終點；

若存在終點，則以終點進行回溯操作得到所述起點至所述終點的路徑，尋路操作完成；

若不存在終點，則將未在所述第一列表中的后繼節(jié)點加入到第一列表中，并執(zhí)行步驟：獲取所述第一列表中標記距離最小的節(jié)點。

可選地，所述判斷所述后繼節(jié)點中是否存在終點的步驟之后還包括：

若不存在終點，則獲取已在所述第一列表中的后繼節(jié)點與所述起點的當前距離，并判斷后繼節(jié)點的當前距離是否小于標記距離；

若后繼節(jié)點的當前距離小于標記距離，則將該后繼節(jié)點的標記距離更新為所述當前距離，并執(zhí)行步驟：獲取所述第一列表中標記距離最小的節(jié)點；

若后繼節(jié)點的當前距離大于或等于標記距離，則執(zhí)行步驟：獲取所述第一列表中標記距離最小的節(jié)點。

可選地，所述獲取所述第一列表中標記距離最小的節(jié)點的步驟之前包括：

判斷所述第一列表中是否存在節(jié)點；

若不存在節(jié)點，則以A-STAR算法執(zhí)行尋路操作失敗；

若存在節(jié)點，則執(zhí)行步驟：獲取所述第一列表中標記距離最小的節(jié)點。

可選地，所述標記距離的計算步驟包括：

獲取所述起點至節(jié)點的移動距離，并獲取節(jié)點與終點的曼哈頓距離；

將所述移動距離與所述曼哈頓距離之和作為該節(jié)點的標記距離。