A －Star演算法

來自專欄 Unity3D從入門到放棄4 人贊了文章

A*（A-Star)演算法是一種求解最短路徑最有效的直接搜索方法，也是許多其他問題的常用啟發式演算法。

一、簡介

二、尋路方式

三、運行機制

四、常用估價演算法

五、示例

一、簡介

A*（A-Star)演算法是一種求解最短路徑最有效的直接搜索方法，也是許多其他問題的常用啟發式演算法。注意——是最有效的直接搜索演算法，之後湧現了很多預處理演算法（如ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。

公式表示為： f(n)=g(n)+h(n),

其中，

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，

g(n) 是在狀態空間中從初始狀態到狀態n的實際代價，

h(n) 是從狀態n到目標狀態的最佳路徑的估計代價。

（對於路徑搜索問題，狀態就是圖中的節點，代價就是距離）

FGH示意圖如下所示（圖中格子左下角為G值，右下角為H值，左上角為F值）：

因此從當前格子周邊的八個格子中找到下一步所走的格子，依據F值，當F值相同時隨機選擇。

當然在尋路過程中，會有障礙，不能通過，通過可以行走的格子走到終點。下圖中綠色為起點，紅色為終點，藍色是障礙，淺藍邊框是參與計算的格子，A*就是通過這樣的一系列計算完成的最優尋路。

二、尋路方式

A* 演算法常用的尋路方式有三種：基於單元的導航圖、基於可視點的導航圖以及導航網格。

1) 基於單元的導航圖：將地圖劃分為由多個正方形或者六邊形組成的規則網格，網格點或往各單元的中心可以看作是尋路節點。此種方式適用於塔防、即時戰略或者其他頻繁動態更新場景的遊戲中，但此種方式易造成巨大的內存開銷，原因在於尋路過程中，對於複雜地形需要將可行走區域和不可行走區域進行標記，並且需要為單元格記錄地形信息，需要消耗大量的存儲空間，另外單元格的大小，也影響著尋路結果和內存消耗情況。如下圖所示是基於單元的導航圖：

2) 基於可視點的導航圖實現時，一般先由場景設計者在場景中手工放置一些「路徑點」， 然後由設計人員逐個測試這些「路徑點」之間的可視性。此種導航方式最大優點在於它的靈活性，分散在各處的路徑點是由場景設計者精心選擇的，能覆蓋絕大部分可行走的區域，還可以將其他一些重要位置的點包含進去。此種方式存在一定的缺點，首先，當場景很大時，手工放置路徑點是非常繁瑣的工作，也很容易出錯，其次，此種方式主要是一些點和線段的集合，角色只能沿著那些邊運動，無法表示出實際的二維可行走區域，最後，該種方式也存在組合爆炸的問題，例如：如果設置了100個路徑點，就可能需要測試99 * 100條路徑。如下圖所示，即為基於可視點的導航圖

3) 導航網格將遊戲場景中的可行走區域劃分成凸多邊形。導航網格能夠表示出可行走區域的真實幾何關係，是一個非均勻網格。Unity3D自帶的導航系統就簡歷在導航網格的基礎上。導航網格的有點是可以進行精確的點到點移動，其次，非常高效，原因在於多邊形的面積可以任意大，因此，只需要較少的多邊形，就可以表示出很大的可行走區域，不但佔用的內存較小，搜索路徑的速度也會有很大的提高。另外，導航網格的生成無需人工干預，只需要通過實現設計好的演算法，能夠自動地將可行走區域劃分成多邊形，生成導航網格。導航網格的主要缺點在於生成導航網格需要較長的時間，因此，多用於靜態場景中。如下圖所示，即為導航網格：

三、運行機制

在A*演算法中，使用了兩個狀態表，分別稱為Open表和Closed表。Open表由待考察的節點組成，Closed表由已經考察過的節點組成。

什麼樣的節點才算是已考察過的呢？對於一個節點來說，當演算法已經檢查過與它相鄰的所有節點，計算出了這些節點的fgh值，並把它們放入Open表以待考察，那麼，這節點就是「已考察過」的節點。

開始時，Closed表為空，Open表僅包括起始節點，每次迭代中，A*演算法將Open表中具有最小代價之的節點去除進行檢查，如果這個節點不是目標節點，那麼考慮該節點的所有8個相鄰節點。對於每個相鄰節點按下列規則處理；

（1） 如果相鄰節點既不在Open表中，又不在Closed表中，則將它加入Open表中；

（2） 如果相鄰節點已經在Open表中，並且新的路徑具有更低的代價值，則更新它的信息；

（3） 如果相鄰節點已經在Closed表中，那麼需要檢查新的路徑是否具有更低的代價值，如果是，那麼將它從Closed表中移出，加入到Open表中，否則忽略。

重複上述步驟，直到到達目標節點。如果在到達目標之前，Open表就已經變空，則意味著在起始位置和目標位置之間沒有可達的路徑。

四、常用估價演算法

（1）曼哈頓距離

標準的啟發式函數是曼哈頓距離（Manhattan distance）。考慮你的代價函數並找到從一個位置移動到鄰近位置的最小代價D。因此，我的遊戲中的啟發式函數應該是曼哈頓距離的D倍：

H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

你應該使用符合你的代價函數的衡量單位。

（2）對角線距離

如果在你的地圖中你允許對角運動那麼你需要一個不同的啟發函數。（4 east, 4 north）的曼哈頓距離將變成8*D。然而，你可以簡單地移動（4 northeast）代替，所以啟發函數應該是4*D。這個函數使用對角線，假設直線和對角線的代價都是D：

h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

如果對角線運動的代價不是D，但類似於D2 = sqrt(2) * D，則上面的啟發函數不準確。你需要一些更準確（原文為sophisticated）的東西：

h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))

h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))

h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

這裡，我們計算h_diagonal(n)：沿著斜線可以移動的步數；h_straight(n)：曼哈頓距離；然後合併這兩項，讓所有的斜線步都乘以D2，剩下的所有直線步(注意這裡是曼哈頓距離的步數減去2倍的斜線步數)都乘以D。

（3） 歐幾里得距離

如果你的單位可以沿著任意角度移動（而不是網格方向），那麼你也許應該使用直線距離：

h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

然而，如果是這樣的話，直接使用A*時將會遇到麻煩，因為代價函數g不會match啟發函數h。因為歐幾里得距離比曼哈頓距離和對角線距離都短，你仍可以得到最短路徑，不過A*將運行得更久一些：

（4）平方後的歐幾里得距離

我曾經看到一些A*的網頁，其中提到讓你通過使用距離的平方而避免歐幾里得距離中昂貴的平方根運算：

h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

不要這樣做！這明顯地導致衡量單位的問題。當A*計算f(n) = g(n) + h(n)，距離的平方將比g的代價大很多，並且你會因為啟發式函數評估值過高而停止。對於更長的距離，這樣做會靠近g(n)的極端情況而不再計算任何東西，A*退化成BFS：

五、示例

本案例採用基於單元的導航圖尋路方式以及曼哈頓距離估價法進行實現。首先需要創建一個格子類Grid：using UnityEngine;using System.Collections;using System.Collections.Generic;using System;/// <summary>/// 格子類型/// </summary>public enum GridType{ //正常類型 Normal, //障礙物類型 Obstacle, //起點類型 Start, //終點類型 End}/// <summary>/// 格子類（實現IComparable方便排序）/// </summary>public class Grid : IComparable{ //格子坐標x-y public int x; public int y; //格子A*三屬性f-g-h public int f; public int g; public int h; //格子類型 public GridType type; //格子的歸屬（父格子） public Grid parent; //構造賦值 public Grid (int x, int y) { this.x = x; this.y = y; } /// <summary> /// 實現排序介面方法 /// </summary> /// <returns>The to.</returns> /// <param name="obj">Object.</param> public int CompareTo (object obj) { Grid grid = (Grid)obj; if (this.f < grid.f) { //升序 return -1; } if (this.f > grid.f) { //降序 return 1; } return 0; }}然後主邏輯AStar類：using UnityEngine;using System.Collections;using System.Collections.Generic;public class MyAStar : MonoBehaviour{ /// <summary> /// 單例腳本 /// </summary> public static MyAStar instance; //參考物體預設體 public GameObject reference; //格子數組 public Grid[,] grids; //格子數組對應的參考物（方塊）對象 public GameObject[,] objs; //開啟列表 public ArrayList openList; //關閉列表 public ArrayList closeList; //目標點坐標 public int targetX; public int targetY; //起始點坐標 public int startX; public int startY; //格子行列數 private int row; private int colomn; //結果棧 private Stack<string> parentList; //基礎物體 private Transform plane; private Transform start; private Transform end; private Transform obstacle; //流顏色參數 private float alpha = 0; private float incrementPer = 0; void Awake () { instance = this; plane = GameObject.Find ("Plane").transform; start = GameObject.Find ("Start").transform; end = GameObject.Find ("End").transform; obstacle = GameObject.Find ("Obstacle").transform; parentList = new Stack<string> (); openList = new ArrayList (); closeList = new ArrayList (); } /// <summary> /// 初始化操作 /// </summary> void Init () { //計算行列數 int x = (int)(plane.localScale.x * 20); int y = (int)(plane.localScale.z * 20); row = x; colomn = y; grids = new Grid[x, y]; objs = new GameObject[x, y]; //起始坐標 Vector3 startPos = new Vector3 (plane.localScale.x * -5, 0, plane.localScale.z * -5); //生成參考物體（Cube） for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { grids [i, j] = new Grid (i, j); GameObject item = (GameObject)Instantiate (reference, new Vector3 (i * 0.5f, 0, j * 0.5f) + startPos, Quaternion.identity); item.transform.GetChild (0).GetComponent<Reference> ().x = i; item.transform.GetChild (0).GetComponent<Reference> ().y = j; objs [i, j] = item; } } } /// <summary> /// A*計算 /// </summary> IEnumerator Count () { //等待前面操作完成 yield return new WaitForSeconds (0.1f); //添加起始點 openList.Add (grids [startX, startY]); //聲明當前格子變數，並賦初值 Grid currentGrid = openList [0] as Grid; //循環遍歷路徑最小F的點 while (openList.Count > 0 && currentGrid.type != GridType.End) { //獲取此時最小F點 currentGrid = openList [0] as Grid; //如果當前點就是目標 if (currentGrid.type == GridType.End) { Debug.Log ("Find"); //生成結果 GenerateResult (currentGrid); } //上下左右，左上左下，右上右下，遍歷 for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { if (i != 0 || j != 0) { //計算坐標 int x = currentGrid.x + i; int y = currentGrid.y + j; //如果未超出所有格子範圍，不是障礙物，不是重複點 if (x >= 0 && y >= 0 && x < row && y < colomn && grids [x, y].type != GridType.Obstacle && !closeList.Contains (grids [x, y])) { //計算G值 int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10); //與原G值對照 if (grids [x, y].g == 0 || grids [x, y].g > g) { //更新G值 grids [x, y].g = g; //更新父格子 grids [x, y].parent = currentGrid; } //計算H值 grids [x, y].h = Manhattan (x, y); //計算F值 grids [x, y].f = grids [x, y].g + grids [x, y].h; //如果未添加到開啟列表 if (!openList.Contains (grids [x, y])) { //添加 openList.Add (grids [x, y]); } //重新排序 openList.Sort (); } } } } //完成遍歷添加該點到關閉列表 closeList.Add (currentGrid); //從開啟列表中移除 openList.Remove (currentGrid); //如果開啟列表空，未能找到路徑 if (openList.Count == 0) { Debug.Log ("Can not Find"); } } } /// <summary> /// 生成結果 /// </summary> /// <param name="currentGrid">Current grid.</param> void GenerateResult (Grid currentGrid) { //如果當前格子有父格子 if (currentGrid.parent != null) { //添加到父對象棧（即結果棧） parentList.Push (currentGrid.x + "|" + currentGrid.y); //遞歸獲取 GenerateResult (currentGrid.parent); } } /// <summary> /// 顯示結果 /// </summary> /// <returns>The result.</returns> IEnumerator ShowResult () { //等待前面計算完成 yield return new WaitForSeconds (0.3f); //計算每幀顏色值增量 incrementPer = 1 / (float)parentList.Count; //展示結果 while (parentList.Count != 0) { //出棧 string str = parentList.Pop (); //等0.3秒 yield return new WaitForSeconds (0.3f); //拆分獲取坐標 string[] xy = str.Split (new char[]{ | }); int x = int.Parse (xy [0]); int y = int.Parse (xy [1]); //當前顏色值 alpha += incrementPer; //以顏色方式繪製路徑 objs [x, y].transform.GetChild (0).GetComponent<MeshRenderer> ().material.color = new Color (1 - alpha, alpha, 0, 1); } } /// <summary> /// 曼哈頓方式計算H值 /// </summary> /// <param name="x">The x coordinate.</param> /// <param name="y">The y coordinate.</param> int Manhattan (int x, int y) { return (int)(Mathf.Abs (targetX - x) + Mathf.Abs (targetY - y)) * 10; } void Start () { Init (); StartCoroutine (Count ()); StartCoroutine (ShowResult ()); }}最後是參考預設體方塊的簡單實現：using UnityEngine;using System.Collections;using UnityEngine.UI;public class Reference : MonoBehaviour{ //顏色材質區分 public Material startMat; public Material endMat; public Material obstacleMat; //顯示信息Text private Text text; //當前格子坐標 public int x; public int y; void Awake () { text = GameObject.Find ("Text").GetComponent<Text> (); } //判斷當前格子的類型 void OnTriggerEnter (Collider other) { if (other.name == "Start") { GetComponent<MeshRenderer> ().material = startMat; MyAStar.instance.grids [x, y].type = GridType.Start; MyAStar.instance.openList.Add (MyAStar.instance.grids [x, y]); MyAStar.instance.startX = x; MyAStar.instance.startY = y; } else if (other.name == "End") { GetComponent<MeshRenderer> ().material = endMat; MyAStar.instance.grids [x, y].type = GridType.End; MyAStar.instance.targetX = x; MyAStar.instance.targetY = y; } else if (other.name == "Obstacle") { GetComponent<MeshRenderer> ().material = obstacleMat; MyAStar.instance.grids [x, y].type = GridType.Obstacle; } } /// <summary> /// 滑鼠點擊顯示當前格子基礎信息 /// </summary> void OnMouseDown () { text.text = "XY(" + x + "," + y + ")" + "
" + "FGH(" + MyAStar.instance.grids [x, y].f + "," + MyAStar.instance.grids [x, y].g + "," + MyAStar.instance.grids [x, y].h + ")"; text.color = GetComponent<MeshRenderer> ().material.color; }}