[發明專利]一種基于AStar算法的路徑搜索方法

在審

• 申請號: 202110698514.9
• 申請日: 2021-06-23
• 公開（公告）號: CN113532458A
• 公開（公告）日: 2021-10-22
• 發明（設計）人: 姚俊峰;洪湘
• 申請（專利權）人: 廈門大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 廈門市新華專利商標代理有限公司 35203
• 代理人: 朱凌

1.一種基于AStar算法的路徑搜索方法，其特征在于：包括如下步驟：

步驟S10、利用Prime算法隨機規劃路徑，基于所述路徑生成迷宮場景；

步驟S20、將所述迷宮場景轉換為Grid地圖；

步驟S30、搜索所述Grid地圖中的死路并進行排除；

步驟S40、搜索所述Grid地圖中各地圖節點的鄰接點；

步驟S50、計算各所述鄰接點的f(n)值，基于所述f(n)值對各鄰接點進行排序；

步驟S60、將排序后的各所述鄰接點基于小根堆算法存儲至Open列表；

步驟S70、利用AStar算法，基于所述Open列表中存儲的各鄰接點進行路徑搜索。

2.如權利要求1所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述步驟S10具體包括：

步驟S11、利用Prime算法隨機規劃路徑，所述路徑由若干個方形的路徑節點組成；

步驟S12、依次隨機選取一個所述路徑節點添加進墻體隊列中；

步驟S13、判斷所述墻體隊列中路徑節點相鄰的上、下、左、右方向是否僅存在3個路徑節點，若是，則將該3個路徑節點添加進所述墻體隊列中；若否，則刪除所述墻體隊列中的路徑節點；

步驟S14、將所述墻體隊列中的路徑節點初始化為墻體，生成迷宮場景。

3.如權利要求1所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述步驟S10中，所述路徑設有一起始路徑節點以及一目標路徑節點。

4.如權利要求2所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述步驟S20具體為：

將所述迷宮場景基于路徑節點的大小均分成等大的方格，得到若干個地圖節點，基于所述迷宮場景設置各地圖節點的墻體屬性，完成Grid地圖的轉換。

5.如權利要求4所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述墻體屬性用于標識地圖節點是否為墻體。

6.如權利要求1所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述步驟S30具體為：

依次判斷所述Grid地圖中的各地圖節點，是否存在相鄰的3個地圖節點均為墻，若是，說明為死路，將所述地圖節點設為墻，并進入步驟S40；若否，說明不為死路，并進入步驟S40。

7.如權利要求1所述的一種基于AStar算法的路徑搜索方法，其特征在于：所述步驟S40具體為：

基于上、下、左、右四個方向搜索所述Grid地圖中各地圖節點的鄰接點。