A*演算法

看完視頻后理解的A*演算法
A *演算法

Node 定義小方格

public class Node
{
public bool walkable;
public int x;
public int z;
public Vector3 pos; // 當前位置
public int hCost; // 從當前節點到目標節點的距離
public int gCost; // 從起始點到當前節點的距離
public Node parent;

public int fCost { get { return gCost + hCost; } }     //   最終的距離

public Node(int x,int z,bool walkable,Vector3 pos)
{
    this.x = x;
    this.z = z;
    this.walkable = walkable;
    this.pos = pos;
}

}

Grids 繪制地圖

public class Grids : MonoBehaviour
{
public LayerMask unwalkbaleMask; // 定義障礙物
public Vector3 gridSize; // 當前網格尺寸
public float nodeRadius; // 節點的半徑
float nodeDiameter; // 節點的直徑
public int nodeNumX,nodeNumZ; // 定義每個節點的數量，分別是x和y的數量
public Node[,] grid; // 定義的節點，利用二維節點陣列來定義網格
public List path; // 定義尋路路徑串列，記錄尋路的經過的節點
public Transform Player, Target;
Node playerNode, targetNode;

// Start is called before the first frame update
void Start()
{
    nodeDiameter = nodeRadius * 2;
    nodeNumX = Mathf.RoundToInt(gridSize.x / nodeDiameter);         // Mathf.RoundToInt()   整形化
    nodeNumZ = Mathf.RoundToInt(gridSize.z / nodeDiameter);
    CreateGrid();
}

public void CreateGrid()
{
    grid = new Node[nodeNumX,nodeNumZ];
    Vector3 startPos = transform.position - new Vector3(gridSize.x / 2, 0, gridSize.z / 2);         //地圖左下角的位置坐標
    for (int x = 0; x < nodeNumX; x++)
    {
        for (int z = 0; z < nodeNumZ; z++)
        {
            Vector3 currentPos = startPos + new Vector3(x * nodeDiameter + nodeRadius, 0, z * nodeDiameter + nodeRadius);
            //  設定每個節點（小方格）的中心位置坐標
            bool walkable = !Physics.CheckSphere(currentPos, nodeRadius, unwalkbaleMask);
            //  在每個小方塊位置處檢查一個小圓球范圍內是否有物體
            //  并且這個物體的層級是unwalkbaleMask  
            //  如果是將這個節點定義為不可移動點  回傳false 如果不是回傳true
            grid[x,z]=new Node(x,z,walkable,currentPos);
            //  給每個節點小方格設定資料
        }
    }
}
public Node GetNodeFromPosition(Vector3 pos)            //  該方法從某個位置獲取節點
{
    float penrcentX = (pos.x + gridSize.x / 2) / gridSize.x;
    penrcentX = Mathf.Clamp01(penrcentX);                       //  使penrcentX范圍在0-1之間
    float penrcentZ = (pos.z + gridSize.z / 2) / gridSize.z;
    penrcentZ = Mathf.Clamp01(penrcentZ);                       //  使penrcentX范圍在0-1之間
    int x = Mathf.RoundToInt(penrcentX * (nodeNumX - 1));
    int z = Mathf.RoundToInt(penrcentZ * (nodeNumZ - 1));
    return grid[x, z];
}

private void OnDrawGizmos()         //畫出方格
{
    Gizmos.color = Color.green;
    Gizmos.DrawCube(transform.position, new Vector3(gridSize.x,1, gridSize.z ));
    if (grid!=null)
    {
        foreach (Node n in grid)
        {
            if (n.walkable)
            {
                Gizmos.color = Color.gray;
                if (GetNodeFromPosition(Player.position)==n)
                {
                    Gizmos.color = Color.red;
                }
                if (GetNodeFromPosition(Target.position) == n)
                {
                    Gizmos.color = Color.white;
                }
                if (path != null && path.Contains(n))
                {
                    Gizmos.color = Color.blue;
                }
                    
                Gizmos.DrawCube(n.pos,new Vector3(nodeDiameter*0.9f,1.2f,nodeDiameter*0.9f));
            }
        }
    }
}

}

FindPath 使用A*演算法尋路

public class PathFinding : MonoBehaviour
{
Grids myGrid;
Node startNode;
Node targetNode;
// Start is called before the first frame update
void Awake()
{
myGrid = GetComponent();
}

void FindPath(Vector3 startPos,Vector3 targetPos)
{
    startNode = myGrid.GetNodeFromPosition(startPos);       //  得到開始節點
    targetNode = myGrid.GetNodeFromPosition(targetPos);     //  得到結束節點
    List<Node> openSet = new List<Node>();                  //  開始節點串列
    HashSet<Node> closeSet = new HashSet<Node>();           //  關閉節點串列
    openSet.Add(startNode);                                 //  開始節點加入到openSet
    while (openSet.Count>0)                                 //  openSet中有節點開始回圈
    {
        Node currentNode = openSet[0];                      //  當前節點
        for (int i = 0; i < openSet.Count; i++)             //  開始回圈串列    
        {
            if (openSet[i].fCost<currentNode.fCost || (openSet[i].fCost==currentNode.fCost && openSet[i].hCost<currentNode.hCost))
            {
                currentNode = openSet[i];                   //  滿足條件重新得到當前節點是openSet[i]，
            }
            openSet.Remove(currentNode);                    //  在openSet中移除當前節點
            closeSet.Add(currentNode);                      //  在closeSet中加入當前節點
            if (currentNode==targetNode)                    //  到指定位置
            {
                print("path was found");
                RetrievePath(currentNode);                  //  呼叫 RetrievePath()方法
                return;
            }
            //print("Path");
            foreach (Node n in GetNeighbors(currentNode))           //  遍歷周圍一圈節點即遍歷 neighbor 串列 呼叫GetNeighbors
            {                                                       //  GetNeighbors(currentNode)可以得到當前節點周圍的鄰居節點
                if (!n.walkable || closeSet.Contains(n))            //  如果該節點為不能走的節點或者在關閉串列中有該節點
                    continue;                                       //  結束本次回圈，進行下一個節點的判斷
                int newgCost = currentNode.gCost + GetDistance(currentNode, n);     //  當前節點和鄰居節點之間的距離
                bool inOpenset = openSet.Contains(n);               //  如果打開串列中有該節點回傳true
                if (newgCost<n.gCost || !inOpenset)                 //  如果newgCost小于鄰居節點從起始點到當前節點的距離
                {                                                   //  或者該鄰居節點不在打開節點串列中
                    n.gCost = newgCost;                             //  此時節點n的 gCost為newgCost
                    n.hCost = GetDistance(n, targetNode);           //  求出此時節點n到終點的距離
                    n.parent = currentNode;                         //  設定父節點
                    if (!inOpenset)                                 //  如果不在打開節點串列中
                    {
                       // Debug.Log("aa");
                        openSet.Add(n);                             //  把節點n添加到打開串列中
                    }
                }
                
            }
        }
    }
}

private void RetrievePath(Node n)           //  上方呼叫該函式時傳遞的引數為當前節點
{
    List<Node> p = new List<Node>();        //  新建串列 p,p是用來存盤尋路的路徑
    while (n!=startNode)                    //  如果當前節點不是開始位置節點
    {
        p.Add(n);                           //  串列p中添加節點n,n為當前節點
        n = n.parent;                       //  n重新賦值，賦值為它的父節點，直到n為開始位置節點
    }
    p.Reverse();                            //  因為賦值節點是從后往前，所以要反轉順序
    myGrid.path = p;                        //  把路徑回傳
}

int GetDistance(Node n1,Node n2)              //  求距離(pos1和pos2之間的距離)
{
    int distanceX = (int)Mathf.Abs(n1.x - n2.x);    
    int distanceZ = (int)Mathf.Abs(n1.z - n2.z);
    if (distanceX > distanceZ)                      //  計算距離的方式，水平垂直方向一格為10，斜方向為14  
    {
        return 14 * distanceZ + 10 * (distanceX - distanceZ);
    }
    else
    {
        return 14 * distanceX + 10 * (distanceZ - distanceX);
    }
}

private List<Node> GetNeighbors(Node n)                 //  獲得周圍一圈節點，上方呼叫該函式傳遞的引數為當前節點位置 
{                                                       //  n是當前位置傳遞進來的坐標
    List<Node> neighbors = new List<Node>();            //  新建串列 neighbor 用來存放當前節點周圍一圈的節點
    int xx = n.x;                                       //  xx是當前位置的x軸上的值
    int zz = n.z;                                       //  zz是當前位置的z軸上的值
    Debug.Log(xx + "," + zz);
    Debug.Log("a="+n.pos);
    for (int x = -1; x <= 1; x++)                       //  獲取周圍一圈節點坐標的x
    {
        for (int z = -1; z <= 1; z++)                   //  獲取周圍一圈節點坐標的z
        {
            if (x == 0 && z == 0)                       //  如果x=0，z=0即位置沒發生改變，得到的是自己當前坐標，不需要
                continue;
            if (xx+x >= 0 && xx+x < myGrid.nodeNumX && zz + z >= 0 && zz + z < myGrid.nodeNumZ)     //  獲取周圍一圈節點坐標
            {
                neighbors.Add(myGrid.grid[xx + x, zz + z]);     //  把每個鄰居節點的資訊存盤到 neighbor 串列中
            }                                                   //  在Grids中從左下角第一個方格開始[x,z]是[0,0]
        }
    }
    return neighbors;               //  回傳 neighbor 串列
}

// Update is called once per frame
void Update()
{
    FindPath(myGrid.Player.position, myGrid.Target.position);
}

}