前言

在使用Unity开发游戏项目时，经常会遇到一些角色的导航需求，然而Unity提供给我们的NavMesh+NavMeshAgent并不能很好帮我们实现，且寻路网格的烘焙，以及在导航过程中寻路网格的检测，都是非常消耗性能的，因此在很多企业项目中，会自己写一下高效的寻路算法来完成需求，其中有一种就是A*寻路算法。A*寻路算法是一种启发式算法，从所有可以行走的路径中找出估量代价最小的，递归每步这样的操作，最终到达目标点。

• A寻路算法的估量代价*
  在A*算法中核心的寻路依据就是估量代价，在A*中通常用 F 表示。

F = G + H
其中G表示当前点到起始点的估量代价，H表示当前点到终点的代价。

• G的计算方式：最开始，以起点为中心开始计算周边的八个格子，然后在以这算出来的八个格子为中心，继续计算他们周围的八个格子的G值。以此类推，直到找到终端，或遍历完所有的格子。G值的计算结果为：中心点的G值+距离值【10 or 14】
  

  FGH示意图

                图中格子左下角为G值，右下角为H值，左上角为F值
  

因此从当前格子周边的八个格子中找到下一步所走的格子，依据F值，当F值相同时随机选择。

当然在寻路过程中，会有障碍，不能通过，通过可以行走的格子走到终点。下图中绿色为起点，红色为终点，蓝色是障碍，浅蓝边框是参与计算的格子，A*就是通过这样的一系列计算完成的最优寻路。

A*行走路线

• AStar寻路步骤

  1. 设置开放列表OpenList和关闭列表CloseList
  2. 将起点放置到OpenList
  3. 开启循环While(OpenList.count > 0)
     3.1 将OpenList排序【F值从小到大】
     3.2 OpenList[0]必定是F值最小的，命名为Center
     3.2.1 发现Center就是终点，回溯找到导航路径
     3.3 以这个点为中心，去发现它周围的8个格子
     3.4 计算发现的每个格子G H F三个值
     3.5 如果这个格子没有被计算过或原来G值，比这次计算出来的G要大
     3.5.1 此时，设置新的FGH值给这个格子，并设置该格子的发现者是Center
     3.6 如果这个格子被计算过，且原G值，比这次计算出来的G要小
     3.6.1 此时，就不能替换原来FGH值
     3.7 将发现的每个格子放入到OpenList
     3.7.1 放入的时候要做检测【该格子不在OpenList、该格子不在CloseList】
     3.8 将此次循环的发现者Center放入到CloseList
     3.8 判断OpenList空了
     3.8.1 说明所有的可发现的格子都被遍历过了，始终没有找到中，说明无法到达终点

下面我写了一个小例子，方便大家学习。

• 简单效果

  
  
  简单效果

• 首先需要创建一个格子类Grid

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

/// <summary>
/// 格子类型
/// </summary>
public enum GridType
{
    //正常类型
    Normal,
    //障碍物类型
    Obstacle,
    //起点类型
    Start,
    //终点类型
    End
}

/// <summary>
/// 格子类（实现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;
    //构造赋值
    public Grid (int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    /// <summary>
    /// 实现排序接口方法
    /// </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;
    //格子数组
    public Grid[,] grids;
    //格子数组对应的参考物（方块）对象
    public GameObject[,] objs;
    //开启列表
    public ArrayList openList;
    //关闭列表
    public ArrayList closeList;
    //目标点坐标
    public int targetX;
    public int targetY;
    //起始点坐标
    public int startX;
    public int startY;

    //格子行列数
    private int row;
    private int colomn;
    //结果栈
    private Stack<string> parentList;
    //基础物体
    private Transform plane;
    private Transform start;
    private Transform end;
    private Transform obstacle;
    //流颜色参数
    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 ()
    {
        //计算行列数
        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;
        //循环遍历路径最小F的点
        while (openList.Count > 0 && currentGrid.type != GridType.End) {
            //获取此时最小F点
            currentGrid = openList [0] as Grid;
            //如果当前点就是目标
            if (currentGrid.type == GridType.End) {
                Debug.Log ("Find");
                //生成结果
                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>
    /// 生成结果
    /// </summary>
    /// <param name="currentGrid">Current grid.</param>
    void GenerateResult (Grid currentGrid)
    {
        //如果当前格子有父格子
        if (currentGrid.parent != null) {
            //添加到父对象栈（即结果栈）
            parentList.Push (currentGrid.x + "|" + currentGrid.y);
            //递归获取
            GenerateResult (currentGrid.parent);
        }
    }

    /// <summary>
    /// 显示结果
    /// </summary>
    /// <returns>The result.</returns>
    IEnumerator ShowResult ()
    {
        //等待前面计算完成
        yield return new WaitForSeconds (0.3f);
        //计算每帧颜色值增量
        incrementPer = 1 / (float)parentList.Count;
        //展示结果
        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 ());
    }
}

• 最后是参考预设体方块的简单实现

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

public class Reference : MonoBehaviour
{
    //颜色材质区分
    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;
    }
}

• 多障碍效果图

  
  
  多障碍效果图

• 遍历流程监测
  其实A*遍历的格子还是蛮多的，因为曼哈顿计算的H值是不考虑障碍物的，所以会有很多格子的F值会很小，但不一定此时很小的F值格子就是要走的路径，最终的最优路径是通过，终点格子反推回来的，就如代码中GenerateResult递归方法所示，为了方便大家理解，我做了一个小动画，方便大家对A*的理解。（粉色是此时F值最小的格子，蓝色是最小F值格子周边正在遍历的格子，黄色格子是从未设置父物体，第一次被遍历的格子）

  
  
  遍历流程监测
  
  
  慢放版

结束语

A*只是游戏算法中的凤毛麟角，其中的逻辑也相对简单，所以想要提升编码质量，想要写出高效的游戏逻辑，还需要更多的算法学习。还是那个道理，编程 = 数据结构 + 算法，不带班的这段时间我会尽量分享一些东西给大家，同仁们加油。本文项目下载链接：http://pan.baidu.com/s/1hs13F8K 密码: rbs1