基于Unity的A星尋路演算法（絕對簡單完整版本）

前言

在上一篇文章，介紹了網格地圖的實作方式，基于該文章，我們來實作一個A星尋路的演算法,最終實作的效果為：

專案原始碼已上傳Github：AStarNavigate

在閱讀本篇文章，如果你對于里面提到的一些關于網格地圖的創建方式的一些地圖不了解的話，可以先閱讀了解一下下面的這篇文章：

文章鏈接：

• Unity 制作一個網格地圖生成組件

1、簡單做一些背景介紹

在介紹A星尋路演算法前，先介紹另外一種演算法：Dijkstra尋路演算法，簡單的來說是一種A星尋路的基礎版，Dijkstra作為一種無啟發的尋路演算法，通過圍繞起始點向四周擴展遍歷，一直到找到目標點結束，簡單來說就是暴力破解，由近到遠遍歷所有可能，從而找到目標點

很明顯，這種尋路方式是很的消耗性能的，非常的不高效，有沒有更好的解決方式呢

從實際生活中出發，如果你要到達某地，卻不知道具體的路該怎么辦呢，是不是先大概確定方向，邊靠近目標點邊問路呢

A星尋路演算法也是基于這樣的思路，通過一定的邏輯找到可以靠近物體的方向，然后一步步的走進目標點，直到到達目的地，

二、A星尋路演算法的基本原理

整個理解程序是一個線性結構，只需要一步步完整的走下去，基本就可以對于A星有一個大概的了解，

確定直角斜角權重：

本質上來講，A星尋路是基于一種網格的地圖來實作的尋路的方式，在網格中，一個點可以到達的位置為周圍的八個方向，而由于水平與垂直和傾斜的方向距離不一樣，所以我們在尋路時需要設定不同的長度：

通過圖片可以看出，直線距離與斜線距離是分別等腰直角三角形直角邊與斜邊，根據勾股定理我們可以得知兩者的比例關系約為1.41：1，為了方便計算，我們就將斜邊權重為14，而直角邊權重為10，這樣的話，要得到最短的路徑，可以按照下面的思路去考慮：

遍歷移動格子可能性：

接下來需要考慮第二個問題，在對起始點周圍的可移動格子遍歷完成后，如何找到最短路徑上的那個格子呢，即下一步該走哪一個格子，這里就是整個A星尋路演算法的核心：

如圖，當我們第一步對起始點A周圍所有的格子遍歷后，從A出發有八個可以移動的方向可以到達下一個格子，如果你作為一個人類，當然一眼可以看出下一步向綠色箭頭方向移動產生的路徑是最短的，

我們人類可以根據經驗很快的判斷出方向，但是機器不能，計算機需要嚴謹的程式邏輯來實作這樣的效果，需要我們賦予他基本的執行程式，通過重復的執行這樣的邏輯，得到最終的效果，因此，接下來，需要思考如何讓計算機在一系列點位中找到方向最正確的那個點位

計算某一格子期望長度：

到目前，我們的目的就是使計算機可以找到找到所有可以走的格子中產生路徑最短的格子，接下來以你的經驗來思考，比較長短往往是依據什么，嘿嘿，別想歪，確實是數字的大小，所以我們需要給每一個格子一個數值來作為路徑通過該格子的代價，

當程式進行到現在，要解決的問題是如何求得一個數字來代表該格子，實作方式是通過計算一個通過格子路徑長度的對比來找到最短的路徑，而任一格子記錄路徑長度標記為All，并可以將其分為兩部分：已走路徑與預估路徑（不理解沒關系，接著往下看）：

如圖（靈魂畫手，順便加個防偽標志嘿嘿）求從A到B點的路徑，當前已經尋路到C點，如何求得經過該點的一個期望路徑的長度呢：

• 到達該格子已經走過的路徑長度G：G值的計算是基于遞推的思想，根據上一個格子的G再加上上一個格子到這個格子的距離即可
• 當前格子到達終點預估路徑長度H：該距離是一個估計的距離，至于如何估計的，接下來會進行介紹

然后就可以求出該點的整個期望路徑長度All，對G和H進行一個簡單的加法：

這樣我們就可以通過下一步所有可能的移動的格子中找到最短的格子

關于預估路徑長度H的計算：

• 實作對于H的計算的估計有很多，由于本來就是預估，換句話就是不是一定準確的結果，所以我們可以通過計算當前節點到目標點的直線距離或者水平加垂直距離來獲得

在本文章的后面演示案例中，是基于水平加垂直距離來計算預估路徑長度H，即在上面的圖中，從C到B的預估路徑計算方式為：

Hcb = 水平格子差 * 10 + 垂直格子差 * 10

上述步驟總結升級：

假設我們走到了C點，并且接下來只能從C點向下一步移動，可以在下面的圖中看出接下來格子的所有可能性：

下面我們來手動計算一下4號和5號的預估路徑長度來幫助你理解這個程序，開始前我們要知道一條斜邊長14，直邊長度為10：

則AC的長度為：

Lac=4*14=56

4號：

 H = Lac + 1 * 14 = 70
 G = 2 * 10 + 2 * 10 = 40
 All = H + G = 110

5號：

H = Lac + 1 * 10 = 66
G = 2 * 10 + 3 * 10 = 50
All = H + G = 116

經過對比，5號格子的期望路徑長度長于4號，在計算機運行程式時，會對1到7號都進行這樣的計算，然后求得其中的一個最小值并作為下一步的移動目標

注意：

• 如過有兩個或者多個相同的最小值，會根據程式的寫法選擇任意一個，這不影響整個程式的運行思路

進一步升級

我們發現，上述步驟是有一些問題，因為場景中沒有障礙物，所以物體會一直走直線，但是在實際情況中，假若尋路走進了死胡同，最后的C點周圍沒有可以移動的點位怎么辦呢，

事實上在前面為了便于理解，我們在A星尋路上將問題簡化了，一直以最終點作為下一次尋路的起始點，這種方式是沒有辦法保證最短的路徑的，而在實際的A星尋路中，在每一步中，都會記錄新的可以移動的路徑加入到串列中，我們命名這個串列為開放串列，找到最短的一個節點后，將該點移除，并加入另外一個節點，命名為關閉串列，具體的可以這么說

• 開放串列：用來在其中選擇預估路徑長度最短的點
• 封閉串列：用來表示已經計算過該點，以后不再進行索引

圖中資訊注解：

• 紅色格子：障礙物
• 白色格子：可以移動區域
• 黃色格子：起始點與終點
• 藍色格子：代表開放串列中的格子，用來標識下一步所有可以移動的區域
• 綠色格子：所有走過的格子，同時代表閉合串列中的格子
• 黑色格子：最終的路徑

通過反復的觀看這張動圖，相信你應該對于A星尋路有一個完整的理解，接下來，就需要通過編程來實作該尋路演算法

三、編程實作

1、制作格子預制體模板

如果你之前看過Unity 制作一個網格地圖生成組件這篇文章，你應該很清楚接下來要做什么，如果你不了解也沒有關系，我這里再演示一遍：

創建一個Cube，并調整其縮放，掛載一個腳本Grid，然后編輯該腳本：
由于是作為尋路的基本格子，因此需要其記錄一些資訊，我們定義一些變數：

	//格子的坐標位置
    public int posX;
    public int posY;
    //格子是否為障礙物
    public bool isHinder;
    public Action OnClick;

    //計算預估路徑長度三個值
    public int G = 0;
    public int H = 0;
    public int All = 0;

    //記錄在尋路程序中該格子的父格子
    public Grid parentGrid;

同時在本專案中格子模板需要一個可以改變其顏色的方法用來標識當前模板所處于的狀態（障礙、起始點、終點、路徑等等），以及一個注冊點擊事件的委托方法，所以最后完整的代碼為：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
using UnityEngine.UI;

public class Grid : MonoBehaviour
{

    public int posX;
    public int posY;
    public bool isHinder;
    public Action OnClick;

    //計算預估路徑長度三個值
    public int G = 0;
    public int H = 0;
    public int All = 0;

    //記錄在尋路程序中該格子的父格子
    public Grid parentGrid;
    public void ChangeColor(Color color)
    {
        gameObject.GetComponent<MeshRenderer>().material.color = color;
    }

    //委托系結模板點擊事件
    private void OnMouseDown()
    {
        OnClick?.Invoke();
    }

}

完成代碼的撰寫后，就可以將其拖入我們的資源管理視窗Project面板做成一個預制體，或者直接隱藏也可以

注意：

• 如果你不理解我在干什么或者不懂代碼的內容，一定要去查看這篇文章：Unity 制作一個網格地圖生成組件

2、地圖創建

為了提升代碼的通用性，在這篇文章中，對于網格地圖創建的腳本做出了一些修改，主要在于替換掉腳本中的Grid變數的定義，轉換為GameObject，由于之前對該腳本有了詳細的介紹，所以只貼出了代碼：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;



public class GridMeshCreate : MonoBehaviour 
{
    [Serializable]
    public class MeshRange
    {
        public int horizontal;
        public int vertical;
    }
    [Header("網格地圖范圍")]
    public MeshRange meshRange;
    [Header("網格地圖起始點")]
    private Vector3 startPos;
    [Header("創建地圖網格父節點")]
    public Transform parentTran;
    [Header("網格地圖模板預制體")]
    public GameObject gridPre;
    [Header("網格地圖模板大小")]
    public Vector2 scale;


    private GameObject[,] m_grids;
    public GameObject[,] grids
    {
        get
        {
            return m_grids;
        }
    }
    //注冊模板事件
    public Action<GameObject, int, int> gridEvent;
    /// <summary>
    /// 基于掛載組件的初始資料創建網格
    /// </summary>
    public void CreateMesh()
    {
        if (meshRange.horizontal == 0 || meshRange.vertical == 0)
        {
            return;
        }
        ClearMesh();
        m_grids = new GameObject[meshRange.horizontal, meshRange.vertical];
        for (int i = 0; i < meshRange.horizontal; i++)
        {
            for (int j = 0; j < meshRange.vertical; j++)
            {
                CreateGrid(i, j);

            }
        }
    }

    /// <summary>
    /// 多載，基于傳入寬高資料來創建網格
    /// </summary>
    /// <param name="height"></param>
    /// <param name="widght"></param>
    public void CreateMesh(int height, int widght)
    {
        if (widght == 0 || height == 0)
        {
            return;
        }
        ClearMesh();
        m_grids = new GameObject[widght, height];
        for (int i = 0; i < widght; i++)
        {
            for (int j = 0; j < height; j++)
            {
                CreateGrid(i, j);

            }
        }
    }

    /// <summary>
    /// 根據位置創建一個基本的Grid物體
    /// </summary>
    /// <param name="row">x軸坐標</param>
    /// <param name="column">y軸坐標</param>
    public void CreateGrid(int row, int column)
    {
        GameObject go = GameObject.Instantiate(gridPre, parentTran);
        //T grid = go.GetComponent<T>();

        float posX = startPos.x + scale.x * row;
        float posZ = startPos.z + scale.y * column;
        go.transform.position = new Vector3(posX, startPos.y, posZ);
        go.SetActive(true);
        m_grids[row, column] = go;
        gridEvent?.Invoke(go, row, column);
    }
    /// <summary>
    /// 洗掉網格地圖，并清除快取資料
    /// </summary>
    public void ClearMesh()
    {
        if (m_grids == null || m_grids.Length == 0)
        {
            return;
        }
        foreach (GameObject go in m_grids)
        {
            if (go != null)
            {
                Destroy(go);
            }
        }
        Array.Clear(m_grids, 0, m_grids.Length);
    }
}

3、實作尋路的程序：

創建一個腳本命名為AStarLookRode作為尋路的腳本

變數定義：

在正式的邏輯代碼開始前，需要定義一些基本的變數：

• 開放串列：存盤所有下一步可移動的格子
• 封閉串列：存盤所有移動過的格子
• 路徑堆疊：存盤最終尋路的路徑格子
• 起始點
• 終點
• 場景中的網格地圖

完成變數的定義后，需要在尋路程式開始，對一些變數進行賦值，同時初始化串列，所以我們定義一個初始化的方法：

    public GridMeshCreate meshMap;
    public Grid startGrid;
    public Grid endGrid;

    public List<Grid> openGrids;
    public List<Grid> closeGrids;
    public Stack<Grid> rodes;

    public void Init(GridMeshCreate meshMap, Grid startGrid, Grid endGrid)
    {
        this.meshMap = meshMap;
        this.startGrid = startGrid;
        this.endGrid = endGrid;
        openGrids = new List<Grid>();
        closeGrids = new List<Grid>();
        rodes = new Stack<Grid>();
    }

添加路徑點周圍格子至開放串列：

接下來進行一個功能的代碼邏輯設計，如何將一個點周圍的格子加入到開放串列，可以觀察場景中的格子，有下面的兩種情況：

• 位于地圖中心：周圍有八個可以移動的格子：
• 位于地圖的邊緣：左邊或者右邊，上邊或者下邊沒有格子

這就需要我們從中找到可以取值的范圍，由于格子的位置資訊是一個二維坐標，X和Y，單純的從X軸來考慮，X-1會是格子左邊的格子的坐標，但是如果X-1<0則說明其左邊沒有格子，基于這樣的計算方式，來求得當前格子item周圍格子的坐標范圍，并剔除一些不需要添加的格子，具體的選擇步驟為：

• 遍歷周圍的格子grid，如果存在于封閉串列closeGrids內，不處理
• 如果格子在開放串列openGrids中，計算該點位到目前尋路位置點的期望路徑長度，如果長度更短的話，將當前格子item的父物體替換為該格子的grid
• 接下來如果grid既不在開放串列openGrids，也不再閉合串列closeGrids內，若判斷不為障礙物，則將其加入開放串列openGrids，并設定其父物體為當前尋路位置item

簡單的從圖中理解：

假定我們現在走到了A點（A代表當前路徑點Item），那么添加其周圍的格子（用grid代表）范圍限定在紅色框，為了便于區分不同的情況，我做了一些簡單的標識：

• 紅色格子：障礙物，不處理
• 綠色格子：已經走過的路徑，在閉合串列closeList內，不處理
• 標有圓形的格子，未執行過任何操作，添加到openList里面
• 橙色小框C：最需要理解的一個格子，首先要明白，該格子已經被其上面的綠色格子遍歷過，簡單的來說是已經在開放串列內，這個時候我們就要判斷A點如果經過C點過來，路徑會不會更短，如果會，則修改該A點的父元素為C點，否則不處理

    public void TraverseItem(int i, int j)
    {
        int xMin = Mathf.Max(i - 1, 0);
        int xMax = Mathf.Min(i + 1, meshMap.meshRange.horizontal - 1);
        int yMin = Mathf.Max(j - 1, 0);
        int yMax = Mathf.Min(j + 1, meshMap.meshRange.vertical - 1);

        Grid item = meshMap.grids[i, j].GetComponent<Grid>();
        for (int x = xMin; x <= xMax; x++)
        {
            for (int y = yMin; y <= yMax; y++)
            {
                Grid grid = meshMap.grids[x, y].GetComponent<Grid>();
                if ((y == j && i == x) || closeGrids.Contains(grid))
                {
                    continue;
                }
                if (openGrids.Contains(grid))
                {
                    if(item.All > GetLength(grid, item))
                    {
                        item.parentGrid = grid;
                        SetNoteData(item);
                    }  
                    continue;
                }                    
                if (!grid.isHinder)
                {
                    openGrids.Add(grid);
                    grid.parentGrid= item;
                }               
            }
        }
    }

求任一格子的期望路徑長度：

接下來就需要計算出一個格子的期望路徑的長度，要基于的父元素的G來計算出該格子的G，同時預估出來該格子到達目標的距離H，計算方式在原理里面已經介紹過，這里直接貼出代碼的執行方式：

    public int SetNoteData(Grid grid)
    {
        Grid itemParent = rodes.Count == 0 ? startGrid : grid.parentGrid;
        int numG = Mathf.Abs(itemParent.posX - grid.posX) + Mathf.Abs(itemParent.posY - grid.posY);
        int n = numG == 1 ? 10 : 14;
        grid.G = itemParent.G + n;

        int numH = Mathf.Abs(endGrid.posX - grid.posX) + Mathf.Abs(endGrid.posY - grid.posY);
        grid.H = numH * 10;
        grid.All = grid.H + grid.G;
        return grid.All;
    }

在前面的代碼中，有一個開放串列中已經存在，對比期望長度的更改父格子的功能功能，用到了求根據一個格子求下一個格子期望路徑長度的功能，雖然與上面的代碼功能類似，但是不能直接使用，提升通用性修改起來又麻煩，所以直接再寫一個：

    public int GetLength(Grid bejinGrid,Grid grid)
    {
        int numG = Mathf.Abs(bejinGrid.posX - grid.posX) + Mathf.Abs(bejinGrid.posY - grid.posY);
        int n = numG == 1 ? 10 : 14;
        int G = bejinGrid.G + n;
        
        int numH = Mathf.Abs(endGrid.posX - grid.posX) + Mathf.Abs(endGrid.posY - grid.posY);
        int H = numH * 10;
        int All = grid.H + grid.G;
        return All;
    }

開放串列中尋找期望路徑最短的格子：

在完成對于一個格子的期望路徑長度的計算，我們就需要從開放串列中找出期望路徑長度最短的路徑加入到路徑堆疊中

但是在這一步有這樣的一個問題，在原理介紹中也有說到，尋路程序中遇到障礙會進行回溯到之前的某一個路徑點，如果在在堆疊中執行這樣的操作呢

這里就要用到格子模板Grid中存盤的父格子的資訊，通過對比堆疊中的資料，查找到父格子的位置，清除后面的資料，并將該格子插入，具體代碼為：

     /// <summary>
    /// 在開放串列選中路徑最短的點加入的路徑堆疊，同時將路徑點加入到閉合串列中
    /// </summary>
    public void Traverse()
    {
        if (openGrids.Count == 0)
        {
            return;
        }
        Grid minLenthGrid = openGrids[0];
        int minLength = SetNoteData(minLenthGrid);
        for (int i = 0; i < openGrids.Count; i++)
        {
            if (minLength > SetNoteData(openGrids[i]))
            {
                minLenthGrid = openGrids[i];
                minLength = SetNoteData(openGrids[i]);
            }
        }
        minLenthGrid.ChangeColor(Color.green);
        Debug.Log("我在尋找人生的方向" + minLenthGrid.posX + "::::" + minLenthGrid.posY);

        closeGrids.Add(minLenthGrid);
        openGrids.Remove(minLenthGrid);               
        rodes.Push(minLenthGrid);
    }

獲取最終路徑：

在完成尋路的步驟后，需要根據路徑堆疊和格子的父物體來找到最短的路徑，這里比較功能邏輯比較清晰，直接貼代碼：

    void GetRode()
    {
        List<Grid> grids = new List<Grid>();
        rodes.Peek().ChangeColor(Color.black);
        grids.Insert(0, rodes.Pop());
        while (rodes.Count != 0)
        {
            if (grids[0].parentGrid != rodes.Peek())
            {
                rodes.Pop();

            }
            else
            {
                rodes.Peek().ChangeColor(Color.black);
                grids.Insert(0, rodes.Pop());               
            }

        }      
    }

封裝方法，對外暴露：

在解決三個關鍵功能的代碼后，就需要通過一個方法來完成整個尋路的程序,在方法的最后需要通過對終點坐標與堆疊頂物體的坐標進行對比，如果相同，則跳出回圈，執行路徑查找完成后的操作

同時為了在本案例中為了使得整個尋路程序的步驟可視化，使用一個協程來完成尋路程序的方法呼叫，這樣，在每一次完成一格的尋路后，可以通過協程來延時執行下一次回圈：

    public IEnumerator OnStart()
    {

        //Item itemRoot = Map.bolls[0].item;
        rodes.Push(startGrid);
        closeGrids.Add(startGrid);

        TraverseItem(startGrid.posX, startGrid.posY);
        yield return new WaitForSeconds(1);
        Traverse();

        //為了避免無法完成尋路而跳不出回圈的情況，使用For來規定尋路的最大步數
        for (int i = 0; i < 6000; i++)
        {
            if (rodes.Peek().posX == endGrid.posX && rodes.Peek().posY == endGrid.posY)
            {
                GetRode();
                break;
            }
            TraverseItem(rodes.Peek().posX, rodes.Peek().posY);
            yield return new WaitForSeconds(0.2f);
            Traverse();
        }
    }

四、 執行代碼

接下來需要創建一個腳本明命名為MainRun 來執行整個專案，主要部分為創建場景的網格地圖，在前面反復提到的文章里面已經有這一部分的介紹，接下來就需要對A星的呼叫:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class MainRun : MonoBehaviour
{
    //獲取網格創建腳本
    public GridMeshCreate gridMeshCreate;
    //控制網格元素grid是障礙的概率
    [Range(0,1)]
    public float probability;
    bool isCreateMap=false;
    int clickNum=0;
    Grid startGrid;
    Grid endGrid;
    private void Update()
    {
        if (Input.GetKeyDown(KeyCode.Space))
        {
            Run();
            isCreateMap = false;
            clickNum = 0;
        }
        if (Input.GetKeyDown(KeyCode.Q))
        {
            AStarLookRode aStarLookRode = new AStarLookRode();
            aStarLookRode.Init(gridMeshCreate,startGrid,endGrid);
            StartCoroutine(aStarLookRode.OnStart());          
        }
    }
    private void Run()
    {        
        gridMeshCreate.gridEvent = GridEvent;
        gridMeshCreate.CreateMesh();
    }

    /// <summary>
    /// 創建grid時執行的方法，通過委托傳入
    /// </summary>
    /// <param name="grid"></param>
    private void GridEvent(GameObject go,int row,int column)
    {
        //概率隨機決定該元素是否為障礙
        Grid grid = go.GetComponent<Grid>();
        float f = Random.Range(0, 1.0f);
        Color color = f <= probability ? Color.red : Color.white;
        grid.ChangeColor(color);
        grid.isHinder = f <= probability;
        grid.posX = row;
        grid.posY = column;
        //模板元素點擊事件
        grid.OnClick = () => {
            if (grid.isHinder)
                return;
            clickNum++;
            switch (clickNum)
            {
                case 1:
                    startGrid = grid;
                    grid.ChangeColor(Color.yellow);
                    break;
                case 2:
                    endGrid = grid;
                    grid.ChangeColor(Color.yellow);
                    isCreateMap = true;
                    break;
                default:
                    break;
            }

        };

    }
}

在該腳本中，主要是用來執行網格地圖創建的方法的，同時寫入A星腳本的執行介面，

場景執行：

創建一個空物體，并掛載網格地圖創建腳本GridMeshCreate與運行腳本MainRun，然后對這兩個腳本進行賦值：

在兩個腳本中，我們可以控制一些變數來改變網創建網格地圖大小與障礙物的占比：

• MainRun中Probability：用來控制地圖中障礙物的數量占比
• GridMeshCreate中Mesh Range：用來控制網格地圖的大小范圍

在完成上面的腳本掛載與設定后，就可以運行游戲，進入游戲場景后，點擊空格即可創建地圖，

在創建地圖后，可以使用滑鼠點擊地圖中的白色格子，第一次點擊表示選擇了路徑的起始點，而第二次點擊表示選擇了目標點格子

注意：

• 這一塊Bug挺多的，我也沒有修改，所以盡量按著提示來，不要非要點擊障礙物，或者非要在場景中點擊三次

在完成對于兩個關鍵節點的選擇后，就可以點擊Q鍵開始執行尋路程序，然后就可以直接觀察整個場景中的運行流程：

4、關于A星尋路的能效問題

演算法復雜度問題：

第一張圖片：障礙物的比例比較低時，尋找的路徑接近于一條直線，同時沒有多余的尋路節點產生：

當地圖復雜度上升后，A星尋路產生巨大的代價才能獲取最后的路徑，而這些代價產生的原因是由于為了獲取最短的路徑而進行大量的回溯，而回溯又進一步造成了遍歷串列長度的增加，進一步的消耗了計算資源，

所以當地圖復雜度到達一定閾值并再次上升后，尋路的代價會急速的上升，也可以簡單的理解為指數的形式，而當這一數值超過了0.5，地圖基本就處于不可用的狀態，會有大量的死胡同，很大概率造成無路可循，

特殊情況的尋路效果：

話不多說，先看圖：

通過上圖可以看出，雖然場景中的網格地圖很簡單，但是當兩個尋路點之間存在比較大的橫截面時，也同樣會付出巨大的尋路代價

擴展：

• 看到這張圖，你知道Unity官方的NavMesh是如何實作尋路的嗎？

當我們使用NavMesh來執行尋路操作時，會事先對場景進行烘培，如果你曾經觀察過這張烘培地圖，就會發現其是由一張張三角面來構成的，而當我們進入游戲，執行尋路操作時，NavMesh就會根據這些三角面的頂點來執行可移動的路徑計算，

如圖，其實NavMesh的優勢在與烘培階段對于地圖障礙的處理，通過一些頂點來大大簡化了尋路時的計算，

如果你先學習NavMesh 的使用方式：

• 可以通過該文章：unity中Navigation實作自動尋路功能

總結

總的來說，A星是目前應用最廣的尋路方式，其特點簡單明了，整個程序以最短路徑為設計準則，逐漸的接近目標點，

但是要注意，A星雖然一直以最短為驅動，但是最終得到的路徑不一定最短（至少本篇文章的案例是這樣)，至于原因，你如果理解了代碼的實作程序應該也能明白，如果你不理解，知道原因也沒意義，嘿嘿！