js中A*尋路算法原理的示例分析

這篇文章主要為大家展示了“js中A*尋路算法原理的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“js中A*尋路算法原理的示例分析”這篇文章吧。

簡易地圖

如圖所示簡易地圖, 其中綠色方塊的是起點 (用 A 表示), 中間藍色的是障礙物, 紅色的方塊 (用 B 表示) 是目的地. 為了可以用一個二維數組來表示地圖, 我們將地圖劃分成一個個的小方塊.

二維數組在游戲中的應用是很多的, 比如貪吃蛇和俄羅斯方塊基本原理就是移動方塊而已. 而大型游戲的地圖, 則是將各種"地貌"鋪在這樣的小方塊上.

尋路步驟

1. 從起點A開始, 把它作為待處理的方格存入一個"開啟列表", 開啟列表就是一個等待檢查方格的列表.

2. 尋找起點A周圍可以到達的方格, 將它們放入"開啟列表", 并設置它們的"父方格"為A.

3. 從"開啟列表"中刪除起點 A, 并將起點 A 加入"關閉列表", "關閉列表"中存放的都是不需要再次檢查的方格

圖中淺綠色描邊的方塊表示已經加入 "開啟列表" 等待檢查. 淡藍色描邊的起點 A 表示已經放入 "關閉列表" , 它不需要再執行檢查.

從 "開啟列表" 中找出相對最靠譜的方塊, 什么是最靠譜? 它們通過公式 F=G+H 來計算.

F = G + H

    G 表示從起點 A 移動到網格上指定方格的移動耗費 (可沿斜方向移動).

    H 表示從指定的方格移動到終點 B 的預計耗費 (H 有很多計算方法, 這里我們設定只可以上下左右移動).

我們假設橫向移動一個格子的耗費為10, 為了便于計算, 沿斜方向移動一個格子耗費是14. 為了更直觀的展示如何運算 FGH, 圖中方塊的左上角數字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的結果一樣?

從 "開啟列表" 中選擇 F 值最低的方格 C (綠色起始方塊 A 右邊的方塊), 然后對它進行如下處理:

4. 把它從 "開啟列表" 中刪除, 并放到 "關閉列表" 中.

5. 檢查它所有相鄰并且可以到達 (障礙物和 "關閉列表" 的方格都不考慮) 的方格. 如果這些方格還不在 "開啟列表" 里的話, 將它們加入 "開啟列表", 計算這些方格的 G, H 和 F 值各是多少, 并設置它們的 "父方格" 為 C.

6. 如果某個相鄰方格 D 已經在 "開啟列表" 里了, 檢查如果用新的路徑 (就是經過C 的路徑) 到達它的話, G值是否會更低一些, 如果新的G值更低, 那就把它的 "父方格" 改為目前選中的方格 C, 然后重新計算它的 F 值和 G 值 (H 值不需要重新計算, 因為對于每個方塊, H 值是不變的). 如果新的 G 值比較高, 就說明經過 C 再到達 D 不是一個明智的選擇, 因為它需要更遠的路, 這時我們什么也不做.

如圖, 我們選中了 C 因為它的 F 值最小, 我們把它從 "開啟列表" 中刪除, 并把它加入 "關閉列表". 它右邊上下三個都是墻, 所以不考慮它們. 它左邊是起始方塊, 已經加入到 "關閉列表" 了, 也不考慮. 所以它周圍的候選方塊就只剩下 4 個. 讓我們來看看 C 下面的那個格子, 它目前的 G 是14, 如果通過 C 到達它的話, G將會是 10 + 10, 這比 14 要大, 因此我們什么也不做.

然后我們繼續從 "開啟列表" 中找出 F 值最小的, 但我們發現 C 上面的和下面的同時為 54, 這時怎么辦呢? 這時隨便取哪一個都行, 比如我們選擇了 C 下面的那個方塊 D.

D 右邊已經右上方的都是墻, 所以不考慮, 但為什么右下角的沒有被加進 "開啟列表" 呢? 因為如果 C 下面的那塊也不可以走, 想要到達 C 右下角的方塊就需要從 "方塊的角" 走了, 在程序中設置是否允許這樣走. (圖中的示例不允許這樣走)

就這樣, 我們從 "開啟列表" 找出 F 值最小的, 將它從 "開啟列表" 中移掉, 添加到 "關閉列表". 再繼續找出它周圍可以到達的方塊, 如此循環下去...

那么什么時候停止呢? —— 當我們發現 "開始列表" 里出現了目標終點方塊的時候, 說明路徑已經被找到.

如何找回路徑

如上圖所示, 除了起始方塊, 每一個曾經或者現在還在 "開啟列表" 里的方塊, 它都有一個 "父方塊", 通過 "父方塊" 可以索引到最初的 "起始方塊", 這就是路徑.

將整個過程抽象

把起始格添加到 "開啟列表"

do
{
       尋找開啟列表中F值最低的格子, 我們稱它為當前格.
       把它切換到關閉列表.
       對當前格相鄰的8格中的每一個
          if (它不可通過 || 已經在 "關閉列表" 中)
          {
                什么也不做.
           }
          if (它不在開啟列表中)
          {
                把它添加進 "開啟列表", 把當前格作為這一格的父節點, 計算這一格的 FGH
          if (它已經在開啟列表中)
          {
                if (用G值為參考檢查新的路徑是否更好, 更低的G值意味著更好的路徑)
                    {
                            把這一格的父節點改成當前格, 并且重新計算這一格的 GF 值.
                    }
} while( 目標格已經在 "開啟列表", 這時候路徑被找到)

如果開啟列表已經空了, 說明路徑不存在.

最后從目標格開始, 沿著每一格的父節點移動直到回到起始格, 這就是路徑.

主要代碼

程序中的 "開啟列表" 和 "關閉列表"

List<Point> CloseList;
List<Point> OpenList;

Point 類

public class Point
{
  public Point ParentPoint { get; set; }
  public int F { get; set; } //F=G+H
  public int G { get; set; }
  public int H { get; set; }
  public int X { get; set; }
  public int Y { get; set; }
  public Point(int x, int y)
  {
    this.X = x;
    this.Y = y;
  }
  public void CalcF()
  {
    this.F = this.G + this.H;
  }
}

尋路過程

public Point FindPath(Point start, Point end, bool IsIgnoreCorner)
{
  OpenList.Add(start);
  while (OpenList.Count != 0)
  {
    //找出F值最小的點
    var tempStart = OpenList.MinPoint();
    OpenList.RemoveAt(0);
    CloseList.Add(tempStart);
    //找出它相鄰的點
    var surroundPoints = SurrroundPoints(tempStart, IsIgnoreCorner);
    foreach (Point point in surroundPoints)
    {
      if (OpenList.Exists(point))
        //計算G值, 如果比原來的大, 就什么都不做, 否則設置它的父節點為當前點,并更新G和F
        FoundPoint(tempStart, point);
      else
        //如果它們不在開始列表里, 就加入, 并設置父節點,并計算GHF
        NotFoundPoint(tempStart, end, point);
    }
    if (OpenList.Get(end) != null)
      return OpenList.Get(end);
  }
  return OpenList.Get(end);
}

以上是“js中A*尋路算法原理的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！