前言
在使用Unity开发游戏项目时，经常会遇到一些角色的导航需求，然而Unity提供给我们的NavMesh+NavMeshAgent并不能很好帮我们实现，且寻路网格的烘焙，以及在导航过程中寻路网格的检测，都是非常消耗性能的，因此在很多企业项目中，会自己写一下高效的寻路算法来完成需求，其中有一种就是A*寻路算法。A*寻路算法是一种启发式算法，从所有可以行走的路径中找出估量代价最小的，递归每步这样的操作，最终到达目标点。
- A*寻路算法的估量代价
在A*算法中核心的寻路依据就是估量代价，在A*中通常用 F 表示。F = G + H
其中G表示当前点到起始点的估量代价，H表示当前点到终点的代价。
FGH示意图
|
1 |
图中格子左下角为G值，右下角为H值，左上角为F值 |
因此从当前格子周边的八个格子中找到下一步所走的格子，依据F值，当F值相同时随机选择。
当然在寻路过程中，会有障碍，不能通过，通过可以行走的格子走到终点。下图中绿色为起点，红色为终点，蓝色是障碍，浅蓝边框是参与计算的格子，A*就是通过这样的一系列计算完成的最优寻路。
A*行走路线
下面我写了一个小例子，方便大家学习。
- 简单效果
简单效果 - 首先需要创建一个格子类Grid
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
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类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 |
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 ()); } } |
- 最后是参考预设体方块的简单实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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*只是游戏算法中的凤毛麟角，其中的逻辑也相对简单，所以想要提升编码质量，想要写出高效的游戏逻辑，还需要更多的算法学习。还是那个道理，编程 = 数据结构 + 算法，不带班的这段时间我会尽量分享一些东西给大家，同仁们加油。本文项目下载链接: https://pan.baidu.com/s/1hrVwBcw 密码: cfas
- 本文固定链接: http://www.u3d8.com/?p=1212
- 转载请注明: 网虫虫 在 u3d8.com 发表过
