• <menu id="6c44a"></menu>
  • 關閉
    理論原理

    A*尋路算法詳解

    A*(A-star)算法是一種靜態網路中求解最短路徑最有效的直接搜索算法。在電子游戲中最主要的應用是尋找地圖上兩點間的最佳路線。在機器人領域中,A*算法常用于移動機器人路徑規劃。 為了便于理解,本文將以正...

    admin

    admin

    發布于 2017-04-18 閱讀:135

           A*(A-star)算法是一種靜態網路中求解最短路徑最有效的直接搜索算法。在電子游戲中最主要的應用是尋找地圖上兩點間的最佳路線。在機器人領域中,A*算法常用于移動機器人路徑規劃。
           為了便于理解,本文將以正方形網格地圖為例進行講解。如圖,藍色格子是障礙物,灰色格子是可通過區域,綠色格子是起點(S),紅色格子是終點(D)。我們要做的是找到一條從起點到終點的最佳路線。
           為了順利地解決問題,我們先要設定一些約束條件:
          1. 從一個格子可以朝周圍 8 個方向移動。其中朝上、下、左、右移動的成本為 1,朝左上、右上、左下、右下移動的成本為 1.4(√2 近似值);
          2. 不能朝障礙物所在格子移動(顯然啦?。?;
          3. 如果右邊和上邊兩個格子都是障礙物,則不能朝右上方的格子移動(如圖:不能朝右上和右下兩個格子移動,太窄擠不過去呀~)。
           好,下面開始找路!首先,我們把起點 S 加入一個待檢查節點的列表(Open List)。接下來,找出 S 周圍所有可移動的格子(鄰居),算出從 S 移動到該格子的總成本(記為 G),并將 S 設為其父節點。
           好,這樣我們已經完成了對 S 的檢查。把上一步找到的鄰居都加入 Open List。從 Open List 中移除 S,并將其加入另一個已檢查節點的列表(Closed List)。如圖,橙色邊框代表待檢查節點,黑色邊框代表已檢查節點。
           這下問題來了,Open List 一下有了 8 個待檢查節點,先檢查哪一個呢?每一個待檢查節點都有一個 G 值,代表從起點 S 移動到這個節點的成本。我們再計算出每一個待檢查節點與終點 D 之間的曼哈頓距離(只通過朝上、下、左、右四個方向的移動,抵達終點 D 的最短距離。例如,在平面上,坐標(x1, y1)的i點與坐標(x2, y2)的j點的曼哈頓距離為d(i,j)=|x1-x2|+|y1-y2|),作為從該節點移動到終點 D 的估算成本(記為 H)。注意!這里計算曼哈頓距離時要忽略所有障礙物。最后把 G 和 H 相加(記為 F)。
           現在,從 Open List 中選出 F 值最小的節點(上圖中應該是 S 右邊 F 值為 4 的格子),對它執行前面的檢查。不過這一次搜索鄰居時需要注意以下幾點:
          1. 如果鄰居已經在 Closed List 中,直接忽略;
          2. 如果鄰居不在 Open List 中,計算 G、H、F,設置父節點,并將其加入 Open List;
          3. 這一點非常重要!如果鄰居已經在 Open List 中(即該鄰居已有父節點),計算從當前節點移動到該鄰居是否能使其得到更小的 G 值。如果能,則把該鄰居的父節點重設為當前節點,并更新其 G 和 F 值。
           完成檢查后,把當前節點從 Open List 中移除,放入 Closed List。
           繼續處理其他待檢查節點。




           注意!在下面這一次檢查中,S 下方兩格的節點(星標)更新了 G 值和父節點。




           在下面這一步中,我們注意到終點 D 已經進入了 Open List,并且是其中 F 值最小的。
           我們從 Open List 取出的 F 值最小的節點后,發現它的 H 值為 0,這意味著我們已經找到了終點 D,搜索到此就可以告一段落。
           從終點 D 開始,依次向父節點移動,直到回到起點 S,途經即最佳路線,總長 5.6。
    補充幾點:
           1. 最佳路線可能有多條,比如本文的示例,下圖也是一條總長為 5.6 的路線。這取決于當 Open List 存在多個 F 值最小的節點時,先選取哪一個進行搜索;
           2. 曼哈頓距離只是估算 H 值最簡單的一種方法,常用的方法還有歐幾里德距離、切比雪夫距離等。估算方法的優劣是影響算法效率的重要因素;
           3. Open List 的數據結構也是算法實現的改良點。通常為了從中取出 F 值最小的節點,我們需要遍歷整個 Open List,對其排序。因此,維護一個好的 Open List 結構,減少遍歷,也能夠提高算法的效率;
           4. 實際應用中,為提高效率,還可以進行雙向搜索。從起點和終點分別發起搜索,一方搜索到另一方的已檢查節點時,即找到最佳路線。地圖較復雜時,雙向搜索可以顯著減少尋路過程中檢查的節點數量。
           5. 除了正方形網格地圖,A* 算法也能處理其他正多邊形鑲嵌和復雜甚至不規則多邊形鑲嵌的地圖。其區別在于對鄰居的處理和計算;
           6. A* 算法并不保證得到的路線是平滑的。為了解決這個問題,我們可以對轉向進行懲罰。即當移動方向發生變化時,增加額外的 G 值,以此提高轉向的成本,從而得到更平滑(轉向少、轉角?。┑淖罴崖肪€;
           7. A* 算法的在游戲中的實際應用可能會復雜得多。比如不同種族或技能的單位在同一地形上的移動成本各有差異,同一單位在草地、泥地、砂石、沼澤等各種地形上移動的成本也不盡相同(對應不同的 G 值增量),甚至允許以較高的成本翻越障礙(翻墻、過河等);
           8. 在機器人路徑規劃中,你可能還需要處理與障礙物和其他移動物體的碰撞。
           算法講解完畢,請各位自己動手嘗試實現吧。查看在線演示。
    admin
    admin

    他很懶,什么都沒有留下~