A* 搜索演算法在 Unity 中的簡易實現

尋路系統：尋路是尋找最短路徑並避開障礙物。

比如說王者榮耀，你用手點擊一個點，你所操縱的英雄會根據最短路徑到達你所指的位置，會自動避開在行走過程中的障礙物。

在所有尋路演算法中最好用也是最常用的是A* 搜索演算法。

A* 搜索演算法：俗稱 A 星演算法。這是一種在圖形平面上，由多個節點的路徑，求出最低成本的演算法。該演算法綜合了 Best-First Search 和 Dijkstra 演算法的優點：在進行啟發式搜索提高演算法效率的同時，可以保證找到一條最有路徑。

在此演算法中，如果以 g(n) 表示從起點到任意定點 n 的實際距離，h(n) 表示任意定點到目標定點的估算距離（根據所採用的評估函數的不同而變化），那麼 A* 演算法的估算函數為：

這個公式遵循以下特性：

• 如果 g(n) 為0，即只計算任意頂點 n 到目標的評估函數 h(n)，而不計算起點到頂點 n 的距離，則演算法轉換為使用貪心策略的 Best-First Search，速度最快，但可能得不出最優解；
• 如果 h(n) 不高於實際到目標頂點的距離，則一定可以求出最優解。而且 h(n) 越小，需要計算的節點越多，演算法效率越低。
• 如果 h(n) 為0，即只需求出起點到任意頂點 n 的最短路徑 g(n)，而不是計算任何評估函數 h(n)，則轉換為單源最短路徑問題。

以一個簡單的 Demo 為例：

簡易地圖：

如圖所示，綠色方塊 A 是起點，紅色方塊 B 是終點，中間的藍色方塊表示障礙物。我們這裡將地圖分成了一個一個的小方塊，這樣可以用二維坐標來表示。

首先，A 周圍有8個點。

我們設置兩個列表，周圍還沒有處理的方格我們存到「開啟列表」中，已經處理的方格存到「關閉列表」中。

1. 從起點 A 開始，把它作為待處理的方格存入一個「開啟列表」，開啟列表是一個等待檢查的方格的列表。
2. 尋找 A 周圍可以到達的方格（也就是周圍的八個方格），將它們加入「開啟列表」，並設置它們的父方格為 A。
3. 我們已經計算了可以從 A 到達的點，所以從「開啟列表」中刪除起點 A ，並將起點 A 加入「關閉列表」，「關閉列表」都是不需要再次檢查的方格。

此時我們要從「開啟列表」中找到最靠譜的方塊，通過公式來計算：

• G 表示從起點 A 移動到網路上指定方格的移動耗費（可沿斜方向移動）
• H 表示從指定的方格移動到終點 B 的預計耗費（H 有很多計算方法，這裡我們設定只可以上下左右移動）

假設橫向移動一個格子的耗費為 10，沿斜方向移動一個格子就是 10√2，約等於14。其中 G 是可以確定的，但是 H 計算出來的值是理想情況下的，忽略了障礙物造成的影響。

通過計算，我們發現 F 值在 C 點的時候是最小的，它最有可能在最短路徑上。我們對 C 作如下操作：

1. 把 C 從「開啟列表」中刪除，並放到「關閉列表」中。
2. 檢查它所有相鄰並且可以到達（障礙物和「關閉列表」的方格都不考慮）的方格，如果這些方格還不在「開啟列表」裡面的話，將它們加入「開啟列表」，計算這些方格的 G,H,F 的值各是多少，並設置它們的「父方格」為 C。
3. 如果某個相鄰方格 D 已經在「開啟列表」里了，檢查如果用新的路徑（就是經過 C 的路徑）到達它的話，G 值是否會更低一些，如果新的 G 值更低，那就把它的「父方格」改為目前選中的方格 C，然後重新計算它的 F 值和 G 值（H 值不需要重新計算，因為對於每個方塊，H 值是不變的）。如果新的 G 值比較高，就說明經過 C 在到達 D 不是最優解，這時我們什麼也不做。

如上圖，我們選中了 C 因為它的 F 值最小，我們把它從「開啟列表」中刪除，並把它加入「關閉列表」，它右邊上中下三個都是障礙物，不考慮。它左邊是起始方塊，已經加入到「關閉列表」中了，也不考慮。這樣它周圍的候選方塊就只剩下四個。我們看下上面標註的 D 的方格。它目前的 F 值是14，如果通過 C 到達它的話，就是10+10 = 20 要大於14，不是最優解，所以什麼也不做。

第二輪循環結束，沒有發現一個是 F 值更低的。我們智能從綠色方塊其餘的七個在「開啟列表」的方塊里找 F 值最小的，發現綠色方塊右上角和右下角的 F 值相同，那麼兩個方塊隨便找一個方塊，比如 D 方塊。

D 右邊右上方都是障礙物，不考慮。上方和左上都在「關閉列表」，不考慮。？號石表示不確定由於障礙物的存在是否可以從 D 斜著走，這裡默認不可以。我們將 D 的下方和左下方加入新的「開啟列表」，並計算 F,H,G 值。D 左方的方格由於新的路徑的 G 值更大，所以不做任何處理。第三輪循環結束， D 被加入到關閉列表中。

第四輪循環的時候，「開啟列表」還有被上圖綠框標識的8個方塊。我們從這 8 個方塊裡面選取 F 值最小的，那麼就是 C 上方的方格。F 值為 54。

如上圖所示，依此循環，如果有方格重新計算後 G 值更小的，需要改變 G 值，且改變父節點。當我們發現「開啟列表」中出現紅色方塊的時候，結束循環。

從紅色方塊開始，一直找尋它的父節點，連成的路線就是最短路徑。

在 Unity 中實現：

先創建一個 Point 類：

public class Point { public Point Parent { get; set; } public float F { get; set; } public float G { get; set; } public float H { get; set; } public int X { get; set; } public int Y { get; set; } //表示是否是障礙物 public bool isWall { get; set; } public Point (int x, int y, Point parent = null){ this.X = x; this.Y = y; this.Parent = parent; isWall = false; } public void UpdateParent(Point parent, float g){ this.Parent = parent; this.G = g; F = G + H; }}

在場景中創建一個空物體，加上 Astar 腳本：

public class Astar : MonoBehaviour { private int mapWidth = 8; private int mapHeight = 6; private Point[,] map = new Point[8,6]; void Start () { InitMap (); } //初始化地圖 private void InitMap(){ for (int x = 0; x < mapWidth; x++) { for (int y = 0; y < mapHeight; y++) { map [x, y] = new Point (x, y); } } map [4, 2].isWall = true; map [4, 3].isWall = true; map [4, 4].isWall = true; }}

這裡主要是對地圖進行一個初始化。有三個點是障礙物。

下面是核心演算法：

private void FindPath(Point start, Point end){ //核心演算法 List<Point> openList = new List<Point>(); List<Point> closeList = new List<Point> (); openList.Add (start); while (openList.Count > 0) { Point point = FindMinFOfPoint (openList); openList.Remove (point); closeList.Add (point); List<Point> surroundPoints = GetSurroundPoints (point); PointsFilter (surroundPoints, closeList); foreach (Point surroundPoint in surroundPoints) { if (openList.IndexOf (surroundPoint) > -1) { float nowG = CalcG (surroundPoint, point); if (nowG < surroundPoint.G) { surroundPoint.UpdateParent (point, nowG); } } else { surroundPoint.Parent = point; CalcF (surroundPoint, end); openList.Add (surroundPoint); } } //判斷 end 是否在「開啟列表」中 if(openList.IndexOf(end) > -1){ break; } } } //對集合進行過濾，因為添加到「關閉列表」中的點不需要被「開啟列表」考慮 private void PointsFilter(List<Point> src, List<Point> closeList){ foreach (Point p in closeList) { if (src.IndexOf (p) > -1) { src.Remove (p); } } } //得到周圍的點 private List<Point> GetSurroundPoints(Point point){ Point up = null, down = null, left = null, right = null; Point lu = null, ru = null, ld = null, rd = null; //添加上下左右四個點 if (point.Y < mapHeight - 1){ up = map [point.X, point.Y + 1]; } if (point.Y > 0) { down = map [point.X, point.Y - 1]; } if (point.X > 0) { left = map [point.X - 1, point.Y]; } if (point.X < mapWidth - 1) { right = map [point.X + 1, point.Y]; } //添加四個左上，左下，右上，右下四個點 if(up != null && left != null){ lu = map [point.X - 1, point.Y + 1]; } if(up != null && right != null){ ru = map [point.X + 1, point.Y + 1]; } if(down != null && left != null){ ld = map [point.X - 1, point.Y - 1]; } if(down != null && right != null){ rd = map [point.X + 1, point.Y - 1]; } List<Point> list = new List<Point> (); if (down != null && down.isWall == false) { list.Add (down); } if (up != null && up.isWall == false) { list.Add (up); } if (left != null && left.isWall == false) { list.Add (left); } if (right != null && right.isWall == false) { list.Add (right); } if (lu != null && lu.isWall == false && left.isWall == false && up.isWall == false) { list.Add (lu); } if (ld != null && ld.isWall == false && left.isWall == false && down.isWall == false) { list.Add (ld); } if (ru != null && ru.isWall == false && right.isWall == false && up.isWall == false) { list.Add (ru); } if (rd != null && rd.isWall == false && right.isWall == false && down.isWall == false) { list.Add (rd); } return list; } //從「開啟列表」中查找 F 值最小的 private Point FindMinFOfPoint(List<Point> openList){ float f = float.MaxValue; Point temp = null; foreach (Point p in openList) { if (p.F < f) { temp = p; f = p.F; } } return temp; } private float CalcG(Point now, Point parent){ return Vector2.Distance (new Vector2 (now.X, now.Y), new Vector2 (parent.X, parent.Y)) + parent.G; } //計算 F 值 private void CalcF(Point now, Point end){ //F = G + H float h = Mathf.Abs(end.X - now.X) + Mathf.Abs(end.Y - now.Y); float g = 0; //沒有父節點，只有開始節點沒有父節點 if (now.Parent == null) { g = 0; } else { g = Vector2.Distance (new Vector2 (now.X, now.Y), new Vector2 (now.Parent.X, now.Parent.Y)) + now.Parent.G; } float f = g + h; now.F = f; now.G = g; now.H = h; }

Unity 控制台輸出結果：

學習資料：

Unity 遊戲開發人工智慧編程

A* 搜索演算法-維基百科

Unity3D人工智慧編程精粹