前言

在使用Unity開發(fā)游戲項目時，經(jīng)常會遇到一些角色的導航需求铅歼，然而Unity提供給我們的NavMesh+NavMeshAgent并不能很好幫我們實現(xiàn)箫措，且尋路網(wǎng)格的烘焙，以及在導航過程中尋路網(wǎng)格的檢測哎迄，都是非常消耗性能的回右，因此在很多企業(yè)項目中隆圆，會自己寫一下高效的尋路算法來完成需求，其中有一種就是A*尋路算法翔烁。A*尋路算法是一種啟發(fā)式算法渺氧，從所有可以行走的路徑中找出估量代價最小的，遞歸每步這樣的操作蹬屹，最終到達目標點侣背。

• A尋路算法的估量代價*
  在A*算法中核心的尋路依據(jù)就是估量代價，在A*中通常用 F 表示慨默。

F = G + H
其中G表示當前點到起始點的估量代價贩耐，H表示當前點到終點的代價。

• G的計算方式：最開始厦取，以起點為中心開始計算周邊的八個格子潮太，然后在以這算出來的八個格子為中心，繼續(xù)計算他們周圍的八個格子的G值虾攻。以此類推铡买，直到找到終端，或遍歷完所有的格子霎箍。G值的計算結(jié)果為：中心點的G值+距離值【10 or 14】
  

  FGH示意圖

                圖中格子左下角為G值奇钞，右下角為H值，左上角為F值
  

因此從當前格子周邊的八個格子中找到下一步所走的格子漂坏，依據(jù)F值景埃，當F值相同時隨機選擇。

當然在尋路過程中顶别，會有障礙谷徙，不能通過，通過可以行走的格子走到終點筋夏。下圖中綠色為起點蒂胞，紅色為終點，藍色是障礙条篷，淺藍邊框是參與計算的格子骗随，A*就是通過這樣的一系列計算完成的最優(yōu)尋路。

A*行走路線

• AStar尋路步驟

  1. 設置開放列表OpenList和關閉列表CloseList
  2. 將起點放置到OpenList
  3. 開啟循環(huán)While(OpenList.count > 0)
     3.1 將OpenList排序【F值從小到大】
     3.2 OpenList[0]必定是F值最小的赴叹，命名為Center
     3.2.1 發(fā)現(xiàn)Center就是終點鸿染，回溯找到導航路徑
     3.3 以這個點為中心，去發(fā)現(xiàn)它周圍的8個格子
     3.4 計算發(fā)現(xiàn)的每個格子G H F三個值
     3.5 如果這個格子沒有被計算過或原來G值乞巧，比這次計算出來的G要大
     3.5.1 此時涨椒，設置新的FGH值給這個格子，并設置該格子的發(fā)現(xiàn)者是Center
     3.6 如果這個格子被計算過，且原G值蚕冬，比這次計算出來的G要小
     3.6.1 此時免猾，就不能替換原來FGH值
     3.7 將發(fā)現(xiàn)的每個格子放入到OpenList
     3.7.1 放入的時候要做檢測【該格子不在OpenList、該格子不在CloseList】
     3.8 將此次循環(huán)的發(fā)現(xiàn)者Center放入到CloseList
     3.8 判斷OpenList空了
     3.8.1 說明所有的可發(fā)現(xiàn)的格子都被遍歷過了囤热，始終沒有找到中猎提，說明無法到達終點

下面我寫了一個小例子，方便大家學習旁蔼。

• 簡單效果

  
  
  簡單效果

• 首先需要創(chuàng)建一個格子類Grid

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

/// <summary>
/// 格子類型
/// </summary>
public enum GridType
{
    //正常類型
    Normal,
    //障礙物類型
    Obstacle,
    //起點類型
    Start,
    //終點類型
    End
}

/// <summary>
/// 格子類（實現(xiàn)IComparable方便排序）
/// </summary>
public class Grid : IComparable
{
    //格子坐標x-y
    public int x;
    public int y;
    //格子A*三屬性f-g-h
    public int f;
    public int g;
    public int h;
    //格子類型
    public GridType type;
    //格子的歸屬（父格子）
    public Grid parent;
    //構(gòu)造賦值
    public Grid (int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    /// <summary>
    /// 實現(xiàn)排序接口方法
    /// </summary>
    /// <returns>The to.</returns>
    /// <param name="obj">Object.</param>
    public int CompareTo (object obj)
    {
        Grid grid = (Grid)obj;
        if (this.f < grid.f) {
            //升序
            return -1;
        }
        if (this.f > grid.f) {
            //降序
            return 1;
        }
        return 0;
    }
}

• 然后主邏輯AStar類

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

public class MyAStar : MonoBehaviour
{
    /// <summary>
    /// 單例腳本
    /// </summary>
    public static MyAStar instance;

    //參考物體預設體
    public GameObject reference;
    //格子數(shù)組
    public Grid[,] grids;
    //格子數(shù)組對應的參考物（方塊）對象
    public GameObject[,] objs;
    //開啟列表
    public ArrayList openList;
    //關閉列表
    public ArrayList closeList;
    //目標點坐標
    public int targetX;
    public int targetY;
    //起始點坐標
    public int startX;
    public int startY;

    //格子行列數(shù)
    private int row;
    private int colomn;
    //結(jié)果棧
    private Stack<string> parentList;
    //基礎物體
    private Transform plane;
    private Transform start;
    private Transform end;
    private Transform obstacle;
    //流顏色參數(shù)
    private float alpha = 0;
    private float incrementPer = 0;

    void Awake ()
    {
        instance = this;
        plane = GameObject.Find ("Plane").transform;
        start = GameObject.Find ("Start").transform;
        end = GameObject.Find ("End").transform;
        obstacle = GameObject.Find ("Obstacle").transform;
        parentList = new Stack<string> ();
        openList = new ArrayList ();
        closeList = new ArrayList ();
    }

    /// <summary>
    /// 初始化操作
    /// </summary>
    void Init ()
    {
        //計算行列數(shù)
        int x = (int)(plane.localScale.x * 20);
        int y = (int)(plane.localScale.z * 20);
        row = x;
        colomn = y;
        grids = new Grid[x, y];
        objs = new GameObject[x, y];
        //起始坐標
        Vector3 startPos = 
            new Vector3 (plane.localScale.x * -5, 0, plane.localScale.z * -5);
        //生成參考物體（Cube）
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                grids [i, j] = new Grid (i, j);
                GameObject item = (GameObject)Instantiate (reference, 
                                      new Vector3 (i * 0.5f, 0, j * 0.5f) + startPos, 
                                      Quaternion.identity);
                item.transform.GetChild (0).GetComponent<Reference> ().x = i;
                item.transform.GetChild (0).GetComponent<Reference> ().y = j;
                objs [i, j] = item;
            }
        }
    }

    /// <summary>
    /// A*計算
    /// </summary>
    IEnumerator Count ()
    {
        //等待前面操作完成
        yield return new WaitForSeconds (0.1f);
        //添加起始點
        openList.Add (grids [startX, startY]);
        //聲明當前格子變量锨苏，并賦初值
        Grid currentGrid = openList [0] as Grid;
        //循環(huán)遍歷路徑最小F的點
        while (openList.Count > 0 && currentGrid.type != GridType.End) {
            //獲取此時最小F點
            currentGrid = openList [0] as Grid;
            //如果當前點就是目標
            if (currentGrid.type == GridType.End) {
                Debug.Log ("Find");
                //生成結(jié)果
                GenerateResult (currentGrid);
            }
            //上下左右，左上左下棺聊，右上右下伞租，遍歷
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i != 0 || j != 0) {
                        //計算坐標
                        int x = currentGrid.x + i;
                        int y = currentGrid.y + j;
                        //如果未超出所有格子范圍，不是障礙物限佩，不是重復點
                        if (x >= 0 && y >= 0 && x < row && y < colomn
                            && grids [x, y].type != GridType.Obstacle
                            && !closeList.Contains (grids [x, y])) {
                            //計算G值
                            int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10);
                            //與原G值對照
                            if (grids [x, y].g == 0 || grids [x, y].g > g) {
                                //更新G值
                                grids [x, y].g = g;
                                //更新父格子
                                grids [x, y].parent = currentGrid;
                            }
                            //計算H值
                            grids [x, y].h = Manhattan (x, y);
                            //計算F值
                            grids [x, y].f = grids [x, y].g + grids [x, y].h;
                            //如果未添加到開啟列表
                            if (!openList.Contains (grids [x, y])) {
                                //添加
                                openList.Add (grids [x, y]);
                            }
                            //重新排序
                            openList.Sort ();
                        }
                    }
                }
            }
            //完成遍歷添加該點到關閉列表
            closeList.Add (currentGrid);
            //從開啟列表中移除
            openList.Remove (currentGrid);
            //如果開啟列表空葵诈，未能找到路徑
            if (openList.Count == 0) {
                Debug.Log ("Can not Find");
            }
        }


    }

    /// <summary>
    /// 生成結(jié)果
    /// </summary>
    /// <param name="currentGrid">Current grid.</param>
    void GenerateResult (Grid currentGrid)
    {
        //如果當前格子有父格子
        if (currentGrid.parent != null) {
            //添加到父對象棧（即結(jié)果棧）
            parentList.Push (currentGrid.x + "|" + currentGrid.y);
            //遞歸獲取
            GenerateResult (currentGrid.parent);
        }
    }

    /// <summary>
    /// 顯示結(jié)果
    /// </summary>
    /// <returns>The result.</returns>
    IEnumerator ShowResult ()
    {
        //等待前面計算完成
        yield return new WaitForSeconds (0.3f);
        //計算每幀顏色值增量
        incrementPer = 1 / (float)parentList.Count;
        //展示結(jié)果
        while (parentList.Count != 0) {
            //出棧
            string str = parentList.Pop ();
            //等0.3秒
            yield return new WaitForSeconds (0.3f);
            //拆分獲取坐標
            string[] xy = str.Split (new char[]{ '|' });
            int x = int.Parse (xy [0]);
            int y = int.Parse (xy [1]);
            //當前顏色值
            alpha += incrementPer;
            //以顏色方式繪制路徑
            objs [x, y].transform.GetChild (0).GetComponent<MeshRenderer> ().material.color
            = new Color (1 - alpha, alpha, 0, 1);
        }
    }

    /// <summary>
    /// 曼哈頓方式計算H值
    /// </summary>
    /// <param name="x">The x coordinate.</param>
    /// <param name="y">The y coordinate.</param>
    int Manhattan (int x, int y)
    {
        return (int)(Mathf.Abs (targetX - x) + Mathf.Abs (targetY - y)) * 10;
    }

    void Start ()
    {
        Init ();
        StartCoroutine (Count ());
        StartCoroutine (ShowResult ());
    }
}

• 最后是參考預設體方塊的簡單實現(xiàn)

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

public class Reference : MonoBehaviour
{
    //顏色材質(zhì)區(qū)分
    public Material startMat;
    public Material endMat;
    public Material obstacleMat;
    //顯示信息Text
    private Text text;
    //當前格子坐標
    public int x;
    public int y;

    void Awake ()
    {
        text = GameObject.Find ("Text").GetComponent<Text> ();
    }
    //判斷當前格子的類型
    void OnTriggerEnter (Collider other)
    {
        if (other.name == "Start") {
            GetComponent<MeshRenderer> ().material = startMat;
            MyAStar.instance.grids [x, y].type = GridType.Start;
            MyAStar.instance.openList.Add (MyAStar.instance.grids [x, y]);
            MyAStar.instance.startX = x;
            MyAStar.instance.startY = y;
        } else if (other.name == "End") {
            GetComponent<MeshRenderer> ().material = endMat;
            MyAStar.instance.grids [x, y].type = GridType.End;
            MyAStar.instance.targetX = x;
            MyAStar.instance.targetY = y;
        } else if (other.name == "Obstacle") {
            GetComponent<MeshRenderer> ().material = obstacleMat;
            MyAStar.instance.grids [x, y].type = GridType.Obstacle;
        }
    }

    /// <summary>
    /// 鼠標點擊顯示當前格子基礎信息
    /// </summary>
    void OnMouseDown ()
    {
        text.text = "XY(" + x + "," + y + ")" + "\n" +
        "FGH(" + MyAStar.instance.grids [x, y].f + "," +
        MyAStar.instance.grids [x, y].g + "," +
        MyAStar.instance.grids [x, y].h + ")";
        text.color = GetComponent<MeshRenderer> ().material.color;
    }
}

• 多障礙效果圖

  
  
  多障礙效果圖

• 遍歷流程監(jiān)測
  其實A*遍歷的格子還是蠻多的，因為曼哈頓計算的H值是不考慮障礙物的犀暑，所以會有很多格子的F值會很小驯击，但不一定此時很小的F值格子就是要走的路徑烁兰，最終的最優(yōu)路徑是通過耐亏，終點格子反推回來的，就如代碼中GenerateResult遞歸方法所示沪斟，為了方便大家理解广辰，我做了一個小動畫，方便大家對A*的理解主之。（粉色是此時F值最小的格子择吊，藍色是最小F值格子周邊正在遍歷的格子，黃色格子是從未設置父物體槽奕，第一次被遍歷的格子）

  
  
  遍歷流程監(jiān)測
  
  
  慢放版

結(jié)束語

A*只是游戲算法中的鳳毛麟角几睛，其中的邏輯也相對簡單，所以想要提升編碼質(zhì)量粤攒，想要寫出高效的游戲邏輯所森，還需要更多的算法學習。還是那個道理夯接，編程 = 數(shù)據(jù)結(jié)構(gòu) + 算法焕济，不帶班的這段時間我會盡量分享一些東西給大家，同仁們加油盔几。本文項目下載鏈接：http://pan.baidu.com/s/1hs13F8K 密碼: rbs1