[發(fā)明專利]一種基于A*算法的路徑搜索方法、設(shè)備及計算終端

有效

• 申請?zhí)枺?/td>: 201710534025.3
• 申請日: 2014-12-02
• 公開（公告）號: CN107247805B
• 公開（公告）日: 2020-11-06
• 發(fā)明（設(shè)計）人: 羅響
• 申請（專利權(quán)）人: 廈門飛游信息科技有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/9537;G06F16/901;G06Q10/04
• 代理公司: 北京思睿峰知識產(chǎn)權(quán)代理有限公司 11396
• 代理人: 謝建云;趙愛軍

1.一種基于A*算法的路徑搜索方法，適于在計算設(shè)備中執(zhí)行，路徑搜索的地圖包括具有多個節(jié)點的陣列，該計算設(shè)備包括列表存儲器，該列表存儲器中存儲有開啟列表及刪除列表，該開啟列表包括待尋路檢測的節(jié)點，該刪除列表包括從開啟列表中刪除的節(jié)點，其中，每個節(jié)點是具有一定面積的方格狀的區(qū)域，該方法包括步驟：

判斷所述陣列中節(jié)點的數(shù)量是否小于預(yù)定值，如果確定該陣列中節(jié)點的數(shù)量小于預(yù)定值，則將所述開啟列表建成雙向鏈表，否則將所述開啟列表建成二叉堆，所述預(yù)定值根據(jù)計算設(shè)備的處理能力進行確定；

監(jiān)控所述陣列，獲取路徑搜索的開始節(jié)點及目標(biāo)節(jié)點，并將所述開始節(jié)點加入所述雙向鏈表；

刪除該雙向鏈表表頭的節(jié)點，且將所刪除的雙向鏈表表頭的節(jié)點加入刪除列表；以及

判斷所刪除的雙向鏈表表頭的節(jié)點是否為目標(biāo)節(jié)點，

如果所述刪除的雙向鏈表表頭的節(jié)點為目標(biāo)節(jié)點，則繼續(xù)監(jiān)控所述陣列，

如果該刪除的雙向鏈表表頭的節(jié)點不是目標(biāo)節(jié)點，則獲取該刪除的雙向鏈表表頭的節(jié)點周圍滿足預(yù)定條件的節(jié)點，并將所獲取滿足所述預(yù)定條件的節(jié)點加入所述雙向鏈表；以及

繼續(xù)刪除該雙向鏈表表頭的節(jié)點，且將所刪除的雙向鏈表表頭的節(jié)點加入刪除列表,

其中，將所獲取滿足預(yù)定條件的節(jié)點加入所述雙向鏈表的操作包括：

重新計算雙向鏈表中每個節(jié)點的實際代價，以更新每個節(jié)點的估價函數(shù)值，所述估價函數(shù)值為所述實際代價與節(jié)點的估計代價之和，所述估計代價是直接沿著該節(jié)點到目標(biāo)節(jié)點之間的矩形區(qū)域邊緣的節(jié)點移動后的移動消耗值，

根據(jù)更新后的估價函數(shù)值對所述雙向鏈表的節(jié)點進行排序，將估價函數(shù)值最小的節(jié)點存儲在雙向鏈表的表頭位置，將該滿足所述預(yù)定條件的節(jié)點以插入排序方式加入到所述雙向鏈表，以使雙向鏈表中新的表頭節(jié)點為向目標(biāo)節(jié)點尋路所選擇的前進節(jié)點。

2.如權(quán)利要求1所述的路徑搜索方法，其中所述獲取所述刪除的雙向鏈表表頭的節(jié)點周圍滿足所述預(yù)定條件的節(jié)點的步驟包括：

獲取所述刪除的所述雙向鏈表表頭的節(jié)點能直接到達、不屬于所述刪除列表且非障礙的節(jié)點。

3.如權(quán)利要求1所述的路徑搜索方法，還包括步驟：

當(dāng)確定所述刪除的雙向鏈表表頭的節(jié)點為目標(biāo)節(jié)點時，根據(jù)所述刪除列表中的節(jié)點獲取所述開始節(jié)點與所述目標(biāo)節(jié)點之間的最短路徑。

4.如權(quán)利要求1所述的路徑搜索方法，其中所述預(yù)定值的范圍為1000。