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

有效

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

1.一種路徑找尋方法，其特征在于，所述方法包括：

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

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

在以所述A-STAR算法執(zhí)行尋路操作時，若迭代次數(shù)達到預(yù)設(shè)次數(shù)，則根據(jù)所述起點和終點以單源最短路徑算法執(zhí)行尋路操作，其中，所述單源最短路徑算法是指基于預(yù)設(shè)點陣中的一個起點作為源，計算從源到其他所有各頂點的最短路徑長度的算法；

所述根據(jù)所述起點和終點以單源最短路徑算法執(zhí)行尋路操作的步驟包括：

獲取預(yù)設(shè)點陣，并在所述預(yù)設(shè)點陣中獲取與所述起點直線可到達距離最近的起點鄰近點，和與所述終點直線可到達距離最近的終點鄰近點；

將所述起點鄰近點作為單源最短路徑算法的源，并根據(jù)單源最短路徑算法得到所述起點鄰近點到所述終點鄰近點的最短路徑；

將所述起點至所述起點鄰近點的路徑、所述最短路徑，和所述終點鄰近點至所述終點的路徑的集合作為所述起點至所述終點的路徑。

2.如權(quán)利要求1所述的路徑找尋方法，其特征在于，所述根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作的步驟包括：

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

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

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

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

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

3.如權(quán)利要求2所述的路徑找尋方法，其特征在于，所述判斷所述后繼節(jié)點中是否存在終點的步驟之后還包括：

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

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

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

4.如權(quán)利要求3所述的路徑找尋方法，其特征在于，所述獲取所述第一列表中標(biāo)記距離最小的節(jié)點的步驟之前包括：

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

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

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

5.如權(quán)利要求2所述的路徑找尋方法，其特征在于，所述標(biāo)記距離的計算步驟包括：

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

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

6.如權(quán)利要求1所述的路徑找尋方法，其特征在于，所述在所述預(yù)設(shè)點陣中獲取與所述起點直線可到達距離最近的起點鄰近點，和與所述終點直線可到達距離最近的終點鄰近點的步驟之前包括：

判斷所述預(yù)設(shè)點陣中是否存在所述起點鄰近點和所述終點鄰近點；

若所述預(yù)設(shè)點陣中不存在所述起點鄰近點和所述終點鄰近點，則繼續(xù)根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作；

若所述預(yù)設(shè)點陣中存在所述起點鄰近點和所述終點鄰近點，則執(zhí)行步驟：在所述預(yù)設(shè)點陣中獲取與所述起點直線可到達距離最近的起點鄰近點，和與所述終點直線可到達距離最近的終點鄰近點。

7.如權(quán)利要求1～6中任一項所述的路徑找尋方法，其特征在于，所述根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作的步驟之前還包括：

獲取所述起點至所述終點的直線路徑；

判斷所述直線路徑所經(jīng)過的節(jié)點是否均為可通行節(jié)點；

若所述直線路徑所經(jīng)過的節(jié)點均為可通行節(jié)點，則將所述直線路徑作為所述起點至所述終點的路徑；

若所述直線路徑所經(jīng)過的節(jié)點存在不可通行的節(jié)點，則執(zhí)行步驟：根據(jù)所述起點和終點以A-STAR算法執(zhí)行尋路操作。