🧑‍💻A星寻路简介

A*寻路就是用来计算玩家行进路径的，通过它可以计算出避开阻挡的最短路径
A星寻路算法的基本原理就是不停的找自己周围的点,选出一个新的点作为起点再循环的找
主要是应用于2D游戏上面的寻路AI算法

A星寻路原理

1.寻路消耗公式: f(寻路消耗) = g(离起点的距离) + h(终点的距离)
2.开启列表
3.关闭列表
4.格子对象的父对象

在这里插入图片描述

开启列表：每次从新的点找周围的点时，如果周围的点已经在开启列表或者关闭列表中了，我们就不用去管它
关闭列表：每次往关闭列表中放点时，我们都应该判断这个点是不是和终点一样，如果是一样证明路径找完了，如果不一样，继续找

在这里插入图片描述

👉代码基础架构

在这里插入图片描述

👍代码实现

格子类

/// <summary>
/// 格子类型枚举
/// </summary>
public enum E_AStar_Type{Walk,//可行走Stop//阻挡物
}/// <summary>
/// A星寻路 格子类
/// </summary>
public class AStarNode
{//格子对象坐标 行列(x,y)public int x;public int y;//寻路消耗public float f;//离起点的距离public float g;//离终点的距离public float h;//父对象public AStarNode father;//格子类型public E_AStar_Type type;/// <summary>/// 格子类型构造函数 /// </summary>/// <param name="x">行</param>/// <param name="y">列</param>/// <param name="type">格子类型</param>public AStarNode(int x,int y,E_AStar_Type type){this.x = x;this.y = y;this.type = type;}
}

寻路管理类

/// <summary>
/// A星寻路管理类
/// </summary>
public class AStarMgr
{//私有单例private static AStarMgr instance;//公有属性public static AStarMgr Instance{get{//保证唯一性 如果为空new一个if (instance == null){instance = new AStarMgr();}return instance;}}//地图的宽高private int mapW;private int mapH;//地图相关所有的格子对象容器public AStarNode[,] nodes;//创建开启列表private List<AStarNode> openList = new List<AStarNode>();//创建关闭列表private List<AStarNode> closeList = new List<AStarNode>();/// <summary>/// 初始化地图/// </summary>/// <param name="w">宽</param>/// <param name="h">高</param>public void InitMapInfo(int w ,int h){//记录宽高 范围this.mapW = w;this.mapH = h;//初始化AStarNodenodes = new AStarNode[w, h];//创建生成地图for (int r = 0; r < w - 1; r++){for (int c = 0; c < h - 1; c++){//随机生成阻挡格子 百分之二十概率 //注意：真正的项目中 这些阻挡信息应该是从地图配置文件中读取出来的 不应该是随机的AStarNode node = new AStarNode(r, c, Random.Range(0, 100) < 20 ? E_AStar_Type.Stop : E_AStar_Type.Walk);//赋值nodes[r, c] = node;}}}/// <summary>/// 寻路方法 提供给外部使用/// </summary>/// <param name="startPos">起点</param>/// <param name="endPos">终点</param>/// <returns></returns>public List<AStarNode> FindPath(Vector2 startPos,Vector2 endPos){//实际项目中传入的点往往是坐标系中的位置**********//这里省略换算的步骤直接认为它是传进来的格子坐标***********//有些是float类型小数 需要和世界坐标进行转换***********//1.首先要在地图范围内 x y不能越界if (startPos.x<0||startPos.x>=mapW||startPos.y<0||startPos.y>=mapH||endPos.x < 0 || endPos.x >= mapW || endPos.y < 0 || endPos.y >= mapH){Debug.Log("开始或者结束点在地图格子范围外");return null;}//2.要不是阻挡的 先取出 开始 结束 点//原Vector2 float类型需转换为世界坐标(老师没教) 先直接强制转换为intAStarNode start = nodes[(int)startPos.x, (int)startPos.y];AStarNode end = nodes[(int)endPos.x, (int)endPos.y];//判断类型是否为Walk类型if (start.type == E_AStar_Type.Stop || end.type == E_AStar_Type.Stop){Debug.Log("开始或结束点是阻挡");return null;}//得到起点和终点 对应的格子//需清空上一次相关的数据 避免他们影响 这一次的寻路计算//清空关闭和开启列表closeList.Clear();openList.Clear();//开始点信息清空start.father = null;start.f = 0;start.g = 0;start.h = 0;//把开始点 放入关闭列表中closeList.Add(start);while (true){//从起点开始 找周围的点 并放入开启列表中//左上 x-1 y-1FindNearlyNodeToOpenList(start.x - 1, start.y - 1, 1.4f, start, end);//上   x   y-1FindNearlyNodeToOpenList(start.x, start.y - 1, 1f, start, end);//右上 x+1 y-1FindNearlyNodeToOpenList(start.x + 1, start.y - 1, 1.4f, start, end);//左   x-1 yFindNearlyNodeToOpenList(start.x - 1, start.y, 1f, start, end);//右   x+1 yFindNearlyNodeToOpenList(start.x + 1, start.y, 1f, start, end);//左下 x-1 y+1FindNearlyNodeToOpenList(start.x - 1, start.y + 1, 1.4f, start, end);//下   x   y+1FindNearlyNodeToOpenList(start.x, start.y + 1, 1f, start, end);//右下 x+1 y+1FindNearlyNodeToOpenList(start.x + 1, start.y + 1, 1.4f, start, end);//死路判断开启列表为空都还没有找到终点就认为是死路if (openList.Count == 0){Debug.Log("死路");return null;}//选出开启列表中寻路消耗最小的点 列表排序.SortopenList.Sort(SortOpenList);//放入关闭列表中 然后再从 开启列表中移除closeList.Add(openList[0]);//找得这个点又编程新的起点进行下一次寻路计算了start = openList[0];//每次获取开启列表的第一个值openList.RemoveAt(0);//开启列表中移除//如果这个点已经是终点 那么得到最终结果返回出去//如果这个点 不是终点 那么继续寻路if (start == end){//找完了 已经找到路径 最终路径List<AStarNode> path = new List<AStarNode>();path.Add(start);//回溯每个点while (end.father != null){path.Add(end.father);end = end.father;}//列表反转path.Reverse();return path;}}}/// <summary>/// 排序函数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// <returns></returns>private int SortOpenList(AStarNode a,AStarNode b){if (a.f > b.f){return 1;}else if (a.f == b.f){return 1;}else{return -1;}}/// <summary>/// 把临近的点放入开启列表中的函数/// </summary>/// <param name="x">行</param>/// <param name="y">列</param>/// <param name="g">方向格子 离起点距离</param>/// <param name="father">父对象</param>/// <param name="end">终点位置</param>private void FindNearlyNodeToOpenList(int x,int y,float g,AStarNode father,AStarNode end){//边界判断if (x<0||x>=mapW||y<0||y>=mapH){return;}//在边界范围内 再去取点 AStarNode node = nodes[x, y];//判断这些点 是否为空 是否是阻挡  是否在开启或者关闭列表 如果都不是 才放入开启列表中if (node == null || node.type == E_AStar_Type.Stop||closeList.Contains(node)||openList.Contains(node))//.Contains包含的意思{return;}//计算f值 寻路消耗//f = g + h;//记录父对象node.father = father;//计算g 现在到起点的距离 = 父亲离起点的距离 + 现在离父亲的距离node.g = father.g + g;//计算h 离终点的距离 曼哈顿算法node.h = Mathf.Abs(end.x - node.x) + Mathf.Abs(end.y - node.y);node.f = node.g + node.h;//如果通过了上面的合法验证就存到开启列表中openList.Add(node);//保存}
}