俗话说，好记性不如烂笔头，对于有了解过寻路算法的同学，对于A星算法应该不陌生；为了巩固下这个算法的理解，所以利用Unity演示了算法的过程；本文的基本构成分为 基本原理+ 算法实现+ Unity演示三个步骤。

A星算法基本原理

什么是寻路算法

寻路算法是在指定地图中，NPC可以根据起始点和目标点，计算出一条比较合理的链接路线（通常需要最短路径）；在地图中，路点可以分为两种，一种是普通路点，一种是障碍路点（墙、水、坑等），算法的目的就是要绕过障碍物，使得NPC尽可能的走最短路线到达目标点(targetPoint)。

对于最基本的A星寻路算法，是把一张地图分为一个二维数组，每一个格子代表一个路点；或者如下图如所示，将一张地图分为一个一个的格子，格子为正方形，下方的绿色格子周围有8个相邻的格子；

算法的思路

对于上述九宫格图，假设最小方格的边长是10,那么从绿色格子出发，到达红色格子的距离为$\sqrt{200}$，这里可以简化为14，因为这样可以简化算法的计算难度（浮点数比整数的计算复杂）；到达黄色格子的距离为10；
每一个路点都有一个评估值F，其中$F=G+H$，G值是起点移动到指定方格的移动代价，H是指定的方格移动到终点的估算成本，H值的计算方式有如下两种：

方式一：计算横向和纵向移动的距离，不能斜着走；

方式二：比如该点和目标点为对角顶点组成的举行的边长是a 和 b，那么H值是 $min(a,b)\times 14+abs(a-b)\times 10$

，

本文算法选择的是方式二，H值的计算需要注意的地方是，不需要考虑障碍物，只需考虑起始点和目标点即可。对于F、G、H三个评估值的什么这么命名，我也不清楚，猜测是就和我们平时用来替代临时变量用的i、j、k一样，仅仅是26英文字母中连续的三个而已，方便记忆😎;

这个算法需要两个数组，openList和closeList，openList里面存放的是当前状态可以到达的路点，closeList存放不能到达的路点和已经经过判断的路点；具体步骤如下：

1. 从当前选中路点a出发，总共有8个路点可能到达，假设可到达的节点为b，如果b是障碍点，则直接加入closeList；如果b在openList中，当且仅当b的G值小于点a的G值时，更新b的G值，并且将路点b的父节点设置为当前a；如果b在closeList中，则跳过该点的判断。否者初始化G值和H值，并将该节点b加入到openlist列表中；最后将初始路点a移出openlist。
2. 如果目标点进入了openList，则遍历停止，找到可到达路径，由于每个节点都保存着到达自己的父节点，所以拿到目标点，一直拿到它的父节点就可以找到到达路径；如果openList为空时还没找都目标路点，则不可到达，算法结束；否则进入下一个步骤；
3. 遍历openList的路点，选出F值最小的那个点，如果有多个最小值，可以选择第一个最小值，也可以选择多个最小值中的最后一个，最后的表现就是到达目标点的最短路径可能有多条；然后把这个点当做选中路点，进行步骤1；

算法实现

这里列出算法用的大部分代码，其中最关键的就是RefreshFind函数和AddOpenlistNode函数，执行的就是算法的关键部分----遍历openList然后不断的进行判断，直到找到目标路点或者openList为空，如果有不理解的地方，请留言。

脚本1————cconst.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;namespace AStar
{public static class cconst{public static int NormalTile = 0;public static int WaterTile = 1;public static int DestinationTile = 2;public static int MarkTile = 3;public static int FindTile = 4;public static int StartTile = 5;public static int RowLineNum = 16;  // 行数public static int ColLineNum = 32;  // 列数public static Vector2 startPos = new Vector2(-617, 298);public static float itemRate = 1.0f;public static float width = 40 * itemRate;public static float height = 40 * itemRate;public static int SlideDis = 14;public static int UnSlideDis = 10;public static int slideValNum = 4;public static List<Vector2> UnSlideDisVal = new List<Vector2> { new Vector2(-1, 0), new Vector2(0, 1), new Vector2(1, 0), new Vector2(0, -1) };public static List<Vector2> SlideDisVal = new List<Vector2> { new Vector2(-1, -1), new Vector2(-1, 1), new Vector2(1, 1), new Vector2(1, -1) };//障碍点类型public static int BattleNum = 5;public static int BattleTypeNum = 3;public static Dictionary<int, List<List<int>>> BattleTypeDic = new Dictionary<int, List<List<int>>>{{ 0, new List<List<int>>{ new List<int> {1,0,0 }, new List<int> { 1,1,0 }, new List<int> { 1,1,1 },new List<int> { 1,1,1 }, new List<int> { 1,1,0 }, new List<int> { 1,0,0 } } },{ 1, new List<List<int>>{ new List<int> {1,1,1,1}, new List<int> {1,1,1 }, new List<int> { 1, 1, 1,1,1 } } },{ 2, new List<List<int>>{ new List<int> {1,0, 0, 0, }, new List<int> {1,1,1,1 }, new List<int> {0,0,0,1 }, new List<int> { 0, 0, 0, 1 } } },};}
}

脚本2————AStar.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;namespace AStar
{public class GObject{public GameObject gameobject;public int objType;GameObject fValText;GameObject gValText;GameObject hValText;GameObject textPanel;public GObject(GameObject _gameobject, int _type) {gameobject = _gameobject; objType = _type;textPanel = _gameobject.transform.Find("Panel").gameObject;fValText = textPanel.transform.Find("FText").gameObject;gValText = textPanel.transform.Find("GText").gameObject;hValText = textPanel.transform.Find("HText").gameObject;textPanel.SetActive(false);}public bool IsObstacle{get { return objType == cconst.WaterTile;  }}public void UpdateDis(int g, int h){textPanel.SetActive(true);gValText.GetComponent<Text>().text = g.ToString();hValText.GetComponent<Text>().text = h.ToString();int f = g + h;fValText.GetComponent<Text>().text = f.ToString();}public bool Visible{set { gameobject.SetActive(value);if(!value){textPanel.SetActive(false);}}get { return gameobject.activeSelf; }}public void SetParent(Transform transform){gameobject.transform.SetParent(transform);}public Vector2 localPosition{set { gameobject.transform.localPosition = value; }get { return gameobject.transform.localPosition;  }}}public class Node{public Node parent;public GObject gameobject;int idx = 0;public Node(GObject obj, int _idx) { gameobject = obj; idx = _idx; }int g = 0;int h = 0;public int Idx{get { return idx; }}public int F{get { return G + H; }}public int G{get { return g; }set { g = value; }}public int H{get { return h; }set { h = value;}}public int xIdx{get { return idx / cconst.ColLineNum; }}public int yIdx{get { return idx % cconst.ColLineNum; }}public void UpdateGVal(int gVal){if(gVal < G){G = gVal;}}public void UpdateLocalPosition(){int rowIdx = xIdx;int colIdx = yIdx;float posX = cconst.startPos.x + colIdx * cconst.width;float posY = cconst.startPos.y - rowIdx * cconst.height;gameobject.localPosition = new Vector2(posX, posY);}public void UpdateDescDis(){gameobject.UpdateDis(G, H);}public void UpdateDescDis(Node node){G = node.G;H = node.H;gameobject.UpdateDis(G, H);}public void SetParrent(Node node){parent = node;}public bool Visible{set { gameobject.gameobject.SetActive(value); }get { return gameobject.gameobject.activeSelf; }}}public class AStarTest : MonoBehaviour{// Start is called before the first frame updatepublic List<int> map;public Dictionary<int, string> mapTypeDic;public Dictionary<int, GObject> mapTypeObjDic;public Dictionary<int, GObject> idxObjDic;GameObject normalTile;GameObject waterTile;GameObject destinationTile;GameObject markTile;GameObject findTile;GameObject startTile;public int startIdx;public int targetIdx;public List<int> battleList;public List<Node> openList;public Dictionary<int, Node> openListIdxDic;public List<Node> closeList;public Dictionary<int, Node> closeListIdxDic;public List<GObject> totalObjList;public Dictionary<int, Stack<GObject>> nodeDicPool;Node targetNode;Node markTargetNode;public List<Node> markNodeList;public Coroutine curCoroutine;void Start(){idxObjDic = new Dictionary<int, GObject>();nodeDicPool = new Dictionary<int, Stack<GObject>>();mapTypeDic = new Dictionary<int, string> {{0, "normalTile" },{1, "waterTile" },{2, "targetTile" },{3, "markTile" },{4, "findTile" },{5, "startTile" },};normalTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.NormalTile]);waterTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.WaterTile]);destinationTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.DestinationTile]);markTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.MarkTile]);findTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.FindTile]);startTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.StartTile]);mapTypeObjDic = new Dictionary<int, GObject>{{cconst.NormalTile,  new GObject(normalTile,cconst.NormalTile)},{cconst.WaterTile,  new GObject(waterTile,cconst.WaterTile)},{cconst.DestinationTile,  new GObject(destinationTile,cconst.DestinationTile)},{cconst.MarkTile,  new GObject(markTile,cconst.MarkTile)},{cconst.FindTile,  new GObject(findTile,cconst.FindTile)},{cconst.StartTile,  new GObject(startTile,cconst.StartTile)},};InitData();}public void InitData(){transform.DetachChildren();int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;//初始化乜有障碍物的地图map = new List<int>();for (int i = 0; i < cconst.RowLineNum; ++i)for (int j = 0; j < cconst.ColLineNum; ++j){map.Add(cconst.NormalTile);}//初始化地图障碍物battleList = new List<int>();for (int i = 0; i < cconst.BattleNum; i++){int curBattleType = Random.Range(0, 100) % cconst.BattleTypeNum;int curBattleStartIdx = Random.Range(0, _totalIdx);List<List<int>> curBattleList = cconst.BattleTypeDic[curBattleType];int curBattleRow = curBattleStartIdx / cconst.ColLineNum;int curBattleCol = curBattleStartIdx % cconst.ColLineNum;curBattleRow = Mathf.Min(curBattleRow, cconst.RowLineNum - curBattleList.Count - 1);curBattleCol = Mathf.Min(curBattleCol, cconst.ColLineNum - curBattleList[0].Count - 1);for(int j = 0; j< curBattleList.Count; ++j)for(int k=0; k<curBattleList[j].Count; ++k){if(curBattleList[j][k] > 0){int curCalIdx = (curBattleRow + j) * cconst.ColLineNum + (curBattleCol + k);map[curCalIdx] = cconst.WaterTile;battleList.Add(curCalIdx);}}}//初始化起始点startIdx = Random.Range(0, _totalIdx / 2);while (battleList.Contains(startIdx)){startIdx = Random.Range(0, _totalIdx / 2);}//初始化目标点targetIdx = Random.Range(_totalIdx / 2, _totalIdx);while (battleList.Contains(targetIdx) || startIdx == targetIdx){targetIdx = Random.Range(_totalIdx / 2, _totalIdx);}totalObjList = new List<GObject>();map[startIdx] = cconst.StartTile;map[targetIdx] = cconst.DestinationTile;InitMapRes();// ---------------- A*openList = new List<Node>();openListIdxDic = new Dictionary<int, Node>();closeList = new List<Node>();closeListIdxDic = new Dictionary<int, Node>();markNodeList = new List<Node>();targetNode = new Node(idxObjDic[targetIdx], targetIdx);markTargetNode = null;InitAStarStart();curCoroutine = StartCoroutine(FindNextPoint());}public IEnumerator FindNextPoint(){RefreshFind();yield return new WaitForSeconds(0.05f);if (!openListIdxDic.ContainsKey(targetNode.Idx)){curCoroutine = StartCoroutine(FindNextPoint());  //目标点没在dic里面，继续执行}else{markTargetNode = openListIdxDic[targetNode.Idx];curCoroutine = StartCoroutine(ShowFindPath(markTargetNode));Debug.Log("find the way to the target !!!");}}void InitMapRes(){int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;for (int i=0; i< _totalIdx; ++i){int rowIdx = i / cconst.ColLineNum;int colIdx = i % cconst.ColLineNum;var obj = GetTypeObject(map[i]);idxObjDic[i] = obj;float posX = cconst.startPos.x + colIdx * cconst.width;float posY = cconst.startPos.y - rowIdx * cconst.height;obj.localPosition = new Vector2(posX, posY);}}void InitAStarStart(){GObject startObj = idxObjDic[startIdx];Node startNode = new Node(startObj, startIdx);AddOpenlistNode(startNode);}void AddOpenlistNode(Node node)  //出发点是node，遍历其周围8个点，更细其F、G、H值{if(openListIdxDic.ContainsKey(targetNode.Idx)){Debug.Log("find the way to the target !!!");return;}int xIdx = node.xIdx;int yIdx = node.yIdx;List<Vector2> curDisVal;int curValDis;for (int i =0; i<2; i++){if(i == 0){curDisVal = cconst.UnSlideDisVal;curValDis = cconst.UnSlideDis;}else{curDisVal = cconst.SlideDisVal;curValDis = cconst.SlideDis;}for (int j = 0; j < cconst.slideValNum; ++j){var addVal = curDisVal[j];var curXIdx = xIdx + (int)addVal.x;var curYIdx = yIdx + (int)addVal.y;if (curXIdx < 0 || curXIdx >= cconst.RowLineNum || curYIdx < 0 || curYIdx >= cconst.ColLineNum) continue;int cur_Idx = curXIdx * cconst.ColLineNum + curYIdx;if (closeListIdxDic.ContainsKey(cur_Idx)) continue;Node curNode = null;if (openListIdxDic.ContainsKey(cur_Idx)){curNode = openListIdxDic[cur_Idx];int cur_G = node.G + curValDis;if (curNode.G > cur_G){curNode.SetParrent(node);curNode.UpdateGVal(cur_G);}}else{GObject gobject = GetTypeObject(cconst.FindTile);float posX = cconst.startPos.x + curYIdx * cconst.width;float posY = cconst.startPos.y - curXIdx * cconst.height;gobject.localPosition = new Vector2(posX, posY);curNode = new Node(gobject, cur_Idx);if (idxObjDic[curXIdx * cconst.ColLineNum + curYIdx].IsObstacle){closeListIdxDic[cur_Idx] = curNode;curNode.gameobject.gameobject.SetActive(false);return;}curNode.SetParrent(node);openList.Add(curNode);openListIdxDic[cur_Idx] = curNode;curNode.G = node.G + curValDis;SetHVal(curNode);}curNode.UpdateDescDis();}}closeListIdxDic[node.Idx] = node;closeList.Add(node);}// Update is called once per framevoid Update(){if(Input.GetKeyDown(KeyCode.A)){//dosomething}}void DoNextOperation(){StopCoroutine(curCoroutine);foreach (var obj in totalObjList){obj.Visible = false;Stack<GObject> tmpList;if (nodeDicPool.ContainsKey(obj.objType)){tmpList = nodeDicPool[obj.objType];tmpList.Push(obj);}else{tmpList = new Stack<GObject>();tmpList.Push(obj);}nodeDicPool[obj.objType] = tmpList;}InitData();}void RefreshFind(){Node findNode = null;int tmpMax = int.MaxValue;if(openList.Count == 0){Debug.Log("can not find the way to the target !!!");DoNextOperation();return;}foreach(var node in openList){if (node.F < tmpMax){tmpMax = node.F;findNode = node;}}if (findNode == null) return;GObject gobject = GetTypeObject(cconst.MarkTile);Node curNode = new Node(gobject, findNode.Idx);curNode.UpdateLocalPosition();curNode.UpdateDescDis(findNode);markNodeList.Add(curNode);openList.Remove(findNode);AddOpenlistNode(findNode);}IEnumerator ShowFindPath(Node targetNode){foreach (var _node in markNodeList){_node.Visible = false;}Node temp_node = targetNode;while(temp_node != null){int curTile = cconst.MarkTile;if(temp_node.Idx == startIdx){curTile = cconst.StartTile;}else if(temp_node.Idx == targetIdx){curTile = cconst.DestinationTile;}GObject gobject = GetTypeObject(curTile);Node curNode = new Node(gobject, temp_node.Idx);curNode.Visible = true;curNode.UpdateLocalPosition();temp_node = temp_node.parent;yield return new WaitForSeconds(0.2f);}yield return new WaitForSeconds(0.5f);DoNextOperation();}    void SetHVal(Node node){int xDelVal = Mathf.Abs(node.xIdx - targetNode.xIdx);int yDelVal = Mathf.Abs(node.yIdx - targetNode.yIdx);node.H =  Mathf.Min(xDelVal, yDelVal) * cconst.SlideDis + Mathf.Abs(xDelVal - yDelVal) * cconst.UnSlideDis;}GObject GetTypeObject(int objType){if(nodeDicPool.ContainsKey(objType)){var typeStack = nodeDicPool[objType];if(typeStack.Count > 0){var obj = typeStack.Pop();obj.SetParent(transform);nodeDicPool[objType] = typeStack;obj.Visible = true;totalObjList.Add(obj);return obj;}else{GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);gameObject.transform.SetParent(transform);GObject obj = new GObject(gameObject, objType);totalObjList.Add(obj);return obj;}}else{GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);gameObject.transform.SetParent(transform);GObject obj = new GObject(gameObject, objType);obj.Visible = true;totalObjList.Add(obj);return obj;}}}}

Unity演示

这里的演示样例，都是跑的同一份代码，每次循环都是随机出发点、目的点、障碍物。

演示样例一

演示样例二

演示样例三

演示样例四