@作者： 风不停息丶
🧑💻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;
//初始化AStarNode
nodes = 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类型需转换为世界坐标(老师没教) 先直接强制转换为int
AStarNode 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-1
FindNearlyNodeToOpenList(start.x - 1, start.y - 1, 1.4f, start, end);
//上 x y-1
FindNearlyNodeToOpenList(start.x, start.y - 1, 1f, start, end);
//右上 x+1 y-1
FindNearlyNodeToOpenList(start.x + 1, start.y - 1, 1.4f, start, end);
//左 x-1 y
FindNearlyNodeToOpenList(start.x - 1, start.y, 1f, start, end);
//右 x+1 y
FindNearlyNodeToOpenList(start.x + 1, start.y, 1f, start, end);
//左下 x-1 y+1
FindNearlyNodeToOpenList(start.x - 1, start.y + 1, 1.4f, start, end);
//下 x y+1
FindNearlyNodeToOpenList(start.x, start.y + 1, 1f, start, end);
//右下 x+1 y+1
FindNearlyNodeToOpenList(start.x + 1, start.y + 1, 1.4f, start, end);
//死路判断开启列表为空都还没有找到终点就认为是死路
if (openList.Count == 0)
{
Debug.Log("死路");
return null;
}
//选出开启列表中寻路消耗最小的点 列表排序.Sort
openList.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);//保存
}
}
效果
结尾总结
这就是A星寻路的基础算法了，优化算法老师还没教，看到这篇文章的同志们可以点个赞👍支持一下，谢谢！
