A*算法的具体实现

上次简单的介绍完了A* 的应用场景。那么这次我们来介绍A* 的具体实现方法。

1.了解A* 寻路的基本原理

A* 寻路算法的基本原理就是不停的寻找自己周围的点，选出一个新的点作为下一次的起点，然后再次重复上面的步骤，直到找到终点为止

2.了解A* 寻路的详细原理

1.A* 的寻路消耗公式
f（寻路消耗） = g（离起点的距离） + h（离终点的距离）
2.开启列表
将起始点的周围的点计算并且加入到开启列表当中，但是每次从新的点找周围的点时，如果周围的点已经在开启列表或者关闭列表中了，我们就不去管他了。并且将这些点中父级相同的点中消耗最小的点加入到关闭列表当中
3.关闭列表
每次往关闭列表中放点时，我们都应该判断这个点是不是和终点一样。如果是一样的则证明路径已经找到。如果不一样，则继续找
4.格子对象的父对象
当我们已经找到终点的时候，我们就可以通过回溯这些点的父对象的坐标的方法，来找出一条路径。

3.具体实现A星算法

我们先来实现格子类

/// <summary>
/// 格子类型
/// </summary>
public enum E_Node_Type
{
    canWalk,
    dontWalk,
}
/// <summary>
/// A星格子类
/// </summary>
public class AStarNude
{
    //格子对象的坐标
    public int x;
    public int y;
    
    
    //寻路消耗
    public float f;
    //离起点的距离
    public float g;
    //离重点的距离
    public float h;
    //父对象
    public AStarNude father;
    //格子的类型
    public E_Node_Type type;
/// <summary>
/// 构造函数 传入坐标和格子类型
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <param name="type"></param>
    public AStarNude(int x, int y, E_Node_Type type)
{
    this.x = x;
    this.y = y;
    this.type = type;
}
}

然后实现A* 的本体

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

/// <summary>
/// A星寻路管理器 单例模式
/// </summary>
public class AStarMgr
{
	//这里我们使用单例模式来方便外部进行调用，其实最好使用泛型单例模式
    private static AStarMgr instance;

    public static AStarMgr Instance
    {
        get
        {
            if (instance == null)
            {
                instance = new AStarMgr();
            }

            return instance;
        }
    }

    //地图宽高
    public int mapW;

    public int mapH;
    //地图相关所有的格子对象容器
    public AStarNude[,] nodes;
    //开启列表
    private List<AStarNude> openList =new List<AStarNude>();
    //关闭列表
    private List<AStarNude> closeList = new List<AStarNude>();
/// <summary>
/// 初始化地图信息
/// </summary>
/// <param name="w"></param>
/// <param name="h"></param>
    public void InitMapInfo(int w, int h)
    {
        //根据宽高 创建格子 阻挡的问题  我们可以随机阻挡
        //因为我们现在没有地图相关的数据
        //记录宽高
        this.mapW = w;
        this.mapH = h;
        //声明容器可以装多少个格子
        nodes = new AStarNude[w, h];
        //申明格子 装进去
        
        for (int i = 0; i < w; ++i)
        {
            for (int j = 0; j < h; ++j)
            {
                //随机生成障碍  单纯作为逻辑讲解，实际操作中应该读取地图配置文件
                AStarNude node = new AStarNude(i, j,
                    Random.Range(0, 100) < 20 ? E_Node_Type.dontWalk : E_Node_Type.canWalk);
                nodes[i, j] = node;
            }
        }
        
    }
/// <summary>
/// 寻路方法 提供给外部使用
/// </summary>
/// <param name="startPos"></param>
/// <param name="endPos"></param>
/// <returns></returns>

    public List<AStarNude> FindPath(Vector2 startPos,Vector3 endPos)
    {    
        
        //实际项目中传入的点往往是坐标系中的位置
        //我们这里省略换算的步骤 直接认为他是传进来的格子坐标
        
        
        //首先判断传入的俩点是否合法
        
        //要在地图内
        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;
        }
        //要不是阻挡
        AStarNude start = nodes[(int)startPos.x, (int)startPos.y];
        AStarNude end = nodes[(int)endPos.x, (int)endPos.y];

        if (start.type == E_Node_Type.dontWalk ||
            end.type == E_Node_Type.dontWalk)
        {
            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)
        {
            //如果不合法应该直接返回NULL意味着不能寻路
            //应该得到起点和终点  对应的格子
            //从起点开始 找周围的点 并放入开启列表中
            //左上
            FindNearlyNodeToOpenList(start.x-1,start.y -1,1.4f,start,end);
            //上
            FindNearlyNodeToOpenList(start.x,start.y -1,1f,start,end);
            //右上
            FindNearlyNodeToOpenList(start.x+1,start.y -1,1.4f,start,end);
            //左
            FindNearlyNodeToOpenList(start.x-1,start.y ,1f,start,end);
            //右
            FindNearlyNodeToOpenList(start.x+1,start.y ,1f,start,end);
            //左下
            FindNearlyNodeToOpenList(start.x-1,start.y +1,1.4f,start,end);
            //下
            FindNearlyNodeToOpenList(start.x,start.y +1,1f,start,end);
            //右下
            FindNearlyNodeToOpenList(start.x+1,start.y +1,1.4f,start,end);
       
            //死路判断 开启列表为空  都还没有找到终点  就认为是死路
            if (openList.Count == 0)
            {
                return null;
            }
        
            //选出开启列表中徐璐消耗最小的点
            openList.Sort(SortOpenList);
            //放入关闭列表中 然后再从开启列表中移除
            closeList.Add(openList[0]);
            //找到和这个点又变成新的起点 进行下一次寻路计算
            start = openList[0];
            openList.RemoveAt(0);
            //如果这个点已经是终点了 那么得到最终结果返回出去
            //如果这个点不是终点 那么继续寻路
            if (start == end)
            {
                //找完了 找到路径了
                List<AStarNude> path = new List<AStarNude>();
                path.Add(end);
                while (end.father != null)
                {
                    path.Add(end.father);
                    end = end.father;
                }
                //列表翻转的api
                path.Reverse();
                return path;
            }
            
        }
    
     

    }
/// <summary>
/// 排序函数
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private int SortOpenList(AStarNude a, AStarNude b)
{
    if (a.f > b.f)
    {
        return 1;
    }
    else
    {
        return -1;
    }
}

private void FindNearlyNodeToOpenList(int x, int y, float g, 
    AStarNude fater, AStarNude end)
{
    //边界判断
    if (x < 0 || x >= mapW ||
        y < 0 || y >= mapH)
    {
        return;
    }

    //在范围内 再去取点
    AStarNude node = nodes[x, y];
    //判断这些点是否为边界 是否是阻挡 是否已经在开启或者关闭列表 如果都不是 才放入开启列表中
    if (node == null || node.type == E_Node_Type.dontWalk ||
        closeList.Contains(node) ||
        openList.Contains(node)
       )
    {
        return;
    }

    // 计算f值
    //f =g +h
    //记录父对象
    node.father = fater;
    //计算g  我离起点的距离就是我离父亲的距离加上父亲离起点的距离
    node.g = fater.g + g;
    node.h = Mathf.Abs((end.x - node.x) + Mathf.Abs(end.y - node.y));
    node.f = node.g + node.h;
    //如果通过了上面的合法验证就存到开启列表中
    openList.Add(node);

}
}

后记

还记得我们上次说的为什么A-Star所选的路线并不一定是最短路径吗。因为A-Star算法是求出最低通过成本的算法，在不同条件下获得的效果也不尽相同。