注意：

本文是對基于下方文章鏈接的理論，并最終代碼實現(xiàn)，感謝作者大大的描述，非常詳細(xì)，流程稍微做了些改動，文末有工程網(wǎng)盤鏈接，感興趣的可以下載。

A*算法詳解(個人認(rèn)為最詳細(xì),最通俗易懂的一個版本)-CSDN博客

1、效果演示：

2、A*算法流程：

（1）? ? ? ? ?把起點加入?open list?。

（2）? ? ? ? ?重復(fù)如下過程：

? ? ? ? ? ? ? ? ? ? ? ? a.?????????遍歷?open list?，查找?F?值最小的節(jié)點，把它作為當(dāng)前要處理的節(jié)點。

? ? ? ? ? ? ? ? ? ? ? ? b.?????????對當(dāng)前方格的?8連通的每一個方格? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?◆?????如果它是不可抵達的或者它在?close list?中，忽略它。否則，做如下操作。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?◆?????如果它不在?open list?中，把它加入?open list?，并且把當(dāng)前方格設(shè)置為它的父親，記錄該方格的?F?，?G?和?H?值。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?◆?????如果它已經(jīng)在?open list?中，檢查這條路徑?(?即經(jīng)由當(dāng)前方格到達它那里?)?是否更好，用?G?值作參考。更小的?G?值表示這是更好的路徑。如果是這樣，把它的父親設(shè)置為當(dāng)前方格，并重新計算它的?G?和?F?值。

? ? ? ? ? ? ? ? ? ? ? ? ?c.?????????把這個節(jié)點移到?close list?。

? ? ? ? ? ? ? ? ? ? ? ? ?d.?????????停止，當(dāng)你

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?◆?????把終點加入到了?open list?中，此時路徑已經(jīng)找到了，或者

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?◆?????查找終點失敗，并且?open list?是空的，此時沒有路徑。

（3）? ? ? ? ?保存路徑。從終點開始，每個方格沿著父節(jié)點移動直至起點，這就是你的路徑。

3、代碼：

邏輯層Node結(jié)點定義：

using UnityEngine;public enum GridState
{Empty,Block,
}
public class Node
{public GridState curState;public int X;public int Y;public int F;public int G;public int H;public Node parentNode;public Node(int x, int y){X = x;Y = y;ResetNode();}public void ResetNode(){curState = GridState.Empty;F = 0;G = 0;H = 0;parentNode = null;}public void CalculateValue(Node endNode){if (parentNode == null) return;//計算GG = GetPredictGValue(parentNode);//曼哈頓距離計算HH = Mathf.Abs(endNode.X - X) + Mathf.Abs(endNode.Y - Y);F = G + H;}public int GetPredictGValue(Node targetNode){int predictG = 0;//四連通if (targetNode.X == X || targetNode.Y == Y){predictG = targetNode.G + 10;}//八連通else{predictG = targetNode.G + 14;}return predictG;}}

尋路算法：

using System.Collections.Generic;public partial class PathFind
{private List<Node> openList;private List<Node> closeList;private Node[,] allNodeList;public void AStarInit(Node[,] allNodes){openList = new List<Node>();closeList = new List<Node>();allNodeList = allNodes;}public void FindRoad(Node startNode, Node endNode){openList.Add(startNode);LoopFindRoad(endNode);}private void LoopFindRoad(Node endNode){//找到終點或者不存在路徑if (openList.Count == 0||openList.Contains(endNode)){return;}//找到F值最小的Node smallestFNode = null;for (int i = 0; i < openList.Count; i++){if (smallestFNode == null){smallestFNode = openList[i];continue;}if (openList[i].F<=smallestFNode.F){smallestFNode = openList[i];}}//獲得八連通格子List<Node> eightAdjacent = GetRoundNode(smallestFNode);//更新代價for (int i = 0; i < eightAdjacent.Count; i++){//不在openList里面if (!openList.Contains(eightAdjacent[i])){eightAdjacent[i].parentNode = smallestFNode;eightAdjacent[i].CalculateValue(endNode);openList.Add(eightAdjacent[i]);}else{//判斷是否需要更新F,G,Hif (eightAdjacent[i].GetPredictGValue(smallestFNode) <= eightAdjacent[i].G){eightAdjacent[i].parentNode = smallestFNode;eightAdjacent[i].CalculateValue(endNode);}}}//轉(zhuǎn)移結(jié)點openList.Remove(smallestFNode);closeList.Add(smallestFNode);LoopFindRoad(endNode);}/// <summary>/// 獲得八連通格子中可達到并且不在closeList中的格子/// </summary>/// <returns></returns>private List<Node> GetRoundNode(Node targetNode){int x = targetNode.X;int y = targetNode.Y;List<Node> tempList = new List<Node>();if (IsReachableNode(x, y + 1)) tempList.Add(allNodeList[x, y + 1]);if (IsReachableNode(x + 1, y + 1)) tempList.Add(allNodeList[x + 1, y + 1]);if (IsReachableNode(x + 1, y)) tempList.Add(allNodeList[x + 1, y]);if (IsReachableNode(x + 1, y - 1)) tempList.Add(allNodeList[x + 1, y - 1]);if (IsReachableNode(x, y - 1)) tempList.Add(allNodeList[x, y - 1]);if (IsReachableNode(x - 1, y - 1)) tempList.Add(allNodeList[x - 1, y - 1]);if (IsReachableNode(x - 1, y)) tempList.Add(allNodeList[x - 1, y]);if (IsReachableNode(x - 1, y + 1)) tempList.Add(allNodeList[x - 1, y + 1]);return tempList;}/// <summary>/// 判斷格子是否可到達/// </summary>/// <param name="x"></param>/// <param name="y"></param>/// <returns></returns>private bool IsReachableNode(int x, int y){if (x >= allNodeList.GetLength(0) || x <= 0){return false;}if (y >= allNodeList.GetLength(1) || y <= 0){return false;}if (allNodeList[x, y].curState == GridState.Block){return false;}if (closeList.Contains(allNodeList[x, y])){return false;}return true;}
}

4、補充：

如果希望過障礙時，不允許他斜向過障礙，可以額外加個判斷，原理很簡單，對于8連通的角落點，判斷角落點的4連通是否有障礙，如果有障礙就不算入可到達格子。

代碼如下：

演示：

5、工程網(wǎng)盤鏈接：

通過網(wǎng)盤分享的文件：AStarDemo.unitypackage
鏈接: https://pan.baidu.com/s/1L_f1DIkqe9Oqm_dnFSSVew 提取碼: 1212