A*（A-star）是一種圖遍歷和尋路算法，由于其完整性、最優性和最佳效率，它被用于計算機科學的許多領域。給定一個加權圖、一個源節點和一個目標節點，該算法將找到從源到目標的最短路徑（相對于給定的權重）。

算法過程：遍歷方向為從豎直向上沿順時針方向。

1.首先計算開始節點的G,H,F值，將開始節點放入檢測列表中。

2.將檢測列表中的所有點按到目標所需的成本的估計值F排序，選擇F最小的節點作為當前節點。

3.將當前點從檢測列表中移除，加入到已檢測列表中。

4.計算當前點周圍的八個點G,H,F值，將不包含在檢測列表中的點加入到檢測列表。

5.重復2，3，4,直到找到目標點。

注：

F = g （n）+ h（n）

g（n）?是從起始節點到?n?的路徑的成本，h（n）?是一個啟發式函數，用于估計從?n?到目標的最便宜路徑的成本。

代碼實現：

改造路徑點數據類：

public class DataNode
{public Vector2Int pos;public DataNode parent;//A*使用public int gCost = 999999999;public int hCost;public int fCost;public DataNode(Vector2Int pos, DataNode parent){this.pos = pos;this.parent = parent;}//A*使用計算Fpublic void CalculateFCost(){fCost = gCost + hCost;}
}

算法類：

public class AStar : FindPathAlgorithm
{public AStar(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override List<Vector2Int> FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode = this.AStarFind(startPos, goalPos);if (dataNode == null){Debug.LogError("尋路有誤，請檢查參數是否正確");return null;}return Utils.GetPath(dataNode);}DataNode AStarFind(Vector2Int startPos, Vector2Int goalPos){//存儲要檢測的點List<DataNode> frontier = new List<DataNode>();//存儲已經檢測的點List<Vector2Int> reached = new List<Vector2Int>();DataNode startNode = new DataNode(startPos,null);startNode.gCost = 0;startNode.hCost = CalculateDistanceCost(startPos, goalPos);startNode.CalculateFCost();frontier.Add(startNode);while (frontier.Count > 0){DataNode currentNode = GetLowestFCostNode(frontier);if (currentNode.pos == goalPos){return new DataNode(goalPos, currentNode.parent);}frontier.Remove(currentNode);reached.Add(currentNode.pos);List<DataNode> neighbors = GetNeighbors(currentNode.pos, reached);foreach (DataNode neighbourNode in neighbors){int tentativeGCost = currentNode.gCost + CalculateDistanceCost(currentNode.pos, neighbourNode.pos);if (tentativeGCost < neighbourNode.gCost){neighbourNode.parent = currentNode;neighbourNode.gCost = tentativeGCost;neighbourNode.hCost = CalculateDistanceCost(neighbourNode.pos, goalPos);neighbourNode.CalculateFCost();if (!frontier.Contains(neighbourNode)){frontier.Add(neighbourNode);}}}}return null;}List<DataNode> GetNeighbors(Vector2Int current, List<Vector2Int> reached){List<DataNode> neighbors = new List<DataNode>();for (int i = 0; i < Utils.pointDir.Count; i++){Vector2Int neighbor = current + Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){neighbors.Add(new DataNode(neighbor,null));}}return neighbors;}bool IsCanAdd(Vector2Int current, List<Vector2Int> reached){if (reached.Contains(current))return false;if (current.x >= 0 && current.y >= 0 && current.x < xCount && current.y < zCount){//如果是障礙物，則不能被Addif (this.mapData[current.y, current.x] == 1){return false;}return true;}return false;}private int CalculateDistanceCost(Vector2Int a, Vector2Int b){return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);}private DataNode GetLowestFCostNode(List<DataNode> pathNodeList){DataNode lowestFCostNode = pathNodeList[0];for (int i = 1; i < pathNodeList.Count; i++){if (pathNodeList[i].fCost < lowestFCostNode.fCost){lowestFCostNode = pathNodeList[i];}}return lowestFCostNode;}
}

結果：

參考鏈接：

A* 算法簡介 (redblobgames.com)

A* 搜索算法 - 維基百科，自由的百科全書 (wikipedia.org)

A* Pathfinding (E01: algorithm explanation) - YouTube