Unity | A*寻路算法

A*(A-Star)简介在游戏开发的过程中，不免需要涉及到怪物AI的寻路或让玩家自动导航到目标点位置，当在没有障碍的场景中，直接让怪物/玩家向目标点移动即可，但在有障碍物的场景中（如迷宫，房间，围墙等等），寻路算法就变得尤为重要。A*是目前主流的寻路算法之一，它的作用就是寻找开始点与目标点之间，避开障碍的最短路径。

苔原小鱼人

2895人浏览 · 2024-01-28 15:06:21

苔原小鱼人 · 2024-01-28 15:06:21 发布

前言

仅个人学习的记录，旨在分享我的学习笔记和个人见解。

**一、A*(A-Star)简介**

在游戏开发的过程中，不免需要涉及到怪物AI的寻路或让玩家自动导航到目标点位置，当在没有障碍的场景中，直接让怪物/玩家向目标点移动即可，但在有障碍物的场景中（如迷宫，房间，围墙等等），寻路算法就变得尤为重要。

A*是目前主流的寻路算法之一，它的作用就是寻找开始点与目标点之间，避开障碍的最短路径。它结合了Dijkstra算法的最短路径搜索和贪心算法的启发式搜索，通过综合考虑已经搜索到的路径以及预测的路径长度，选择下一个要探索的节点，以加快搜索速度。
A*计算某点代价的核心思路就是 F=G+H
总代价=初始点到该点的最小代价+该点到目标点的预估代价

二、效果展示

三、实现步骤

1、定义节点类

包含空间信息，代价等等，其中parent为当前节点的父节点，当B点的最小G值是通过A点G值+路径长度得到的时候，A为B的父节点。主要用于计算从开始点出发到该节点的最小代价。在后续回溯路径时，终点不断访问父节点即可找到最佳路径。

public class Point
{
    public int X;
    public int Y;
    public float F;//总代价 F=G+H;
    public float G;//开始点到该点的最小代价
    public float H;//该点到目的地的预计代价（曼哈顿街区）
    public Point parent = null;

    public bool isObstacle = false;

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public void SetParent(Point parent, float g)
    {
        this.parent = parent;
        G = g;
        F = G + H;
    }
}

2、定义地图

定义了3个二维数组，其中
map 为存储节点的数组，主要用于计算。
sprites 为存储SpriteRenderer的数组，用于方块显示。
blockLayout 为方块布局数组，用于在脚本中编辑地图。

public GameObject blockPrefab;   //方块预制体
public Point[,] map;
public SpriteRenderer[,] sprites;//生成的方块的二维数组

// 定义二维数组来表示方块的布局
private int[,] blockLayout = new int[,]
    {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        { 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
        { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    };

方块预制体的结构为
G、H用于显示初始点到该点的代价与该点到目标点的预估代价。

3、初始化地图

通过地图布局来对map与sprites数组赋值。

需要注意的是unity世界坐标是x正向为右，y正向为上，而在代码中定义的二维数组，x正向为下，y正向为右。如果想要生成与二维数组形态、方向一致的墙壁，需要做一点转换。

即二维数组的X=世界坐标的-Y; 二维数组的Y=世界坐标的X;
世界坐标的X=二维数组的Y;世界坐标Y=二维数组-X;
所以在生成方块时需要注意生成的坐标点与二维数组下标的转换。

public void InitMap()//初始化地图
    {
        bool isFirst = false;
        height = blockLayout.GetLength(0);
        width = blockLayout.GetLength(1);
        start = null;
        end = null;
        map = new Point[height, width];
        if(sprites == null)
        {
            sprites = new SpriteRenderer[height, width];
            isFirst = true;
        }
        else
        {
            isFirst = false;
        }
        
        for (int x = 0; x < height; x++)
        {
            for (int y = 0; y < width; y++)
            {
                Vector3 position = new Vector3(y, -x, 0);
                if (isFirst)
                {
                    sprites[x, y] = Instantiate(blockPrefab, position, Quaternion.identity).GetComponent<SpriteRenderer>();
                }
                
                sprites[x, y].transform.Find("Canvas/G").GetComponent<Text>().text = "0";
                sprites[x, y].transform.Find("Canvas/H").GetComponent<Text>().text = "0";
                if (blockLayout[x, y] == 1)
                {
                    map[x, y] = new Point(x, y);
                    map[x, y].isObstacle = true;
                    sprites[x, y].color = Color.black;
                }
                else
                {
                    map[x, y] = new Point(x, y);
                    sprites[x, y].color = Color.white;
                }
            }
        }
    }

4、寻路算法的实现

为了演示寻路的过程所以用了协程。
主要思路：定义2个集合，openList为未确定最小代价点的集合，close为已确定最小代价点的集合。在开始时，添加start点到openList中，当openList中有点时保持循环。将openList中最小的点取出并放入close集合中，获取该点8领域的点并加入openList中，并计算更新周围点的总代价。直到获取到终点时，结束循环并回溯路径。

具体已在代码中写明注释

 IEnumerator FindPath()
    {
        List<Point> openList = new List<Point>();//未确定最小代价点的集合
        List<Point> closeList = new List<Point>();//已确定最小代价点的集合
        openList.Add(start);
        //还有未确定代价点时 一直循环
        while (openList.Count > 0)
        {
            //选出open集合中代价最小的点
            Point point = GetMinFPoint(openList);

            //该点已经确定最小代价，从open中移出并放入close中。
            openList.Remove(point);
            closeList.Add(point);
            sprites[point.X, point.Y].color = Color.gray;
            
            //获取该点周围的点
            List<Point> SurroundPoints = GetSurroundPoint(point.X, point.Y);

            //剔除周围已经确定最小代价的点
            foreach (Point p in closeList)
            {
                if (SurroundPoints.Contains(p))
                {
                    SurroundPoints.Remove(p);
                }
            }
            //遍历周围的点
            //若已被访问过，则对比G代价，更新初始点到该点的最小代价。
            //若未被访问过，则基于当前点计算周围点的代价，并更新G代价。

            foreach (Point p in SurroundPoints)
            {
                if (openList.Contains(p))
                {
                    float _G = 0;
                    //若不处于斜角，则距离+1，若处于斜角则距离+1.4(根号2)
                    if (point.X==p.X || point.Y == p.Y)
                    {
                        _G = 1f + point.G;
                    }
                    else
                    {
                        _G = 1.4f + point.G;
                    }
                   
                    if (_G < p.G)
                    {
                        p.SetParent(point, _G);
                    }
                }
                else
                {
                    //基于当前点计算周围点的代价
                    SetPoint(p, point);
                    openList.Add(p);
                }

                //在方块上显示G与H
                sprites[p.X, p.Y].transform.Find("Canvas/G").GetComponent<Text>().text = (Mathf.Round(p.G * 10.0f) / 10.0f).ToString();
                sprites[p.X, p.Y].transform.Find("Canvas/H").GetComponent<Text>().text = p.H.ToString();
            }
            //找到终点后，回溯路径
            if (openList.Contains(end))
            {
                StartCoroutine(ShowPath());
                break;
            }
            yield return new WaitForSeconds(0.05f);
        }
    }

主方法中用到的方法

 /// <summary>
    /// 获取map[x,y]的八邻域点的集合
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <returns></returns>
    public List<Point> GetSurroundPoint(int x, int y)
    {
        List<Point> PointList = new List<Point>();

        int oriX;
        int oriY;
        int[] dx = new int[8] { 0, 1, 1, 1, 0, -1, -1, -1 };
        int[] dy = new int[8] { -1, -1, 0, 1, 1, 1, 0, -1 };
        for (int i = 0; i < 8; i++)
        {
            oriX = x + dx[i];
            oriY = y + dy[i];
            if (oriX > 0 && oriX < height && oriY > 0 && oriY < width && map[oriX, oriY].isObstacle == false)
            {
                PointList.Add(map[oriX, oriY]);
            }
        }
    
        return PointList;
    }

    /// <summary>
    /// 基于parentPoint 计算point的代价。
    /// </summary>
    /// <param name="point"></param>
    /// <param name="parentPoint"></param>
    public void SetPoint(Point point,Point parentPoint)
    {
        point.parent = parentPoint;
        float G = 0;
        float H = Mathf.Abs(end.X - point.X) + Mathf.Abs(end.Y - point.Y);
        if (point.parent != null)
        {
            if (point.parent.X == point.X || point.parent.Y == point.Y)
            {
                G = 1f + point.parent.G;
            }
            else
            {
                G = 1.4f + point.parent.G;
            }
        }
        
        float F = H + G;
        point.H = H;
        point.G = G;
        point.F = F;
    }

    /// <summary>
    /// 获取list中最小总代价的点
    /// </summary>
    /// <param name="list"></param>
    /// <returns></returns>
    public Point GetMinFPoint(List<Point> list)
    {
        float min = float.MaxValue;
        Point point = null;
        foreach (Point p in list)
        {
            if (p.F < min)
            {
                min = p.F;
                point = p;
            }
        }
        return point;
    }

路径回溯方法

不断访问end点的父节点，直到回到start点。

    IEnumerator ShowPath()//显示路径
    {
        Point temp = end.parent;
        while (temp != start)
        {
            sprites[temp.X, temp.Y].color = Color.blue;
            temp = temp.parent;
            yield return new WaitForSeconds(0.1f);
        }
    }

5、点击选取初始点与目标点。

按C重置地图，按D+鼠标左键，选取起点，按D+鼠标右键，设置终点并寻路。

private void Update()
    {
        if (Input.GetKeyDown(KeyCode.C))
        {
            InitMap();
        }
        if (Input.GetKey(KeyCode.D) && Input.GetMouseButtonDown(0))
        {
            Vector2 vector2 = Camera.main.ScreenToWorldPoint(Input.mousePosition);
            int MapX = -Mathf.FloorToInt(vector2.y);
            int MapY = Mathf.FloorToInt(vector2.x);
            if(0<MapX && MapX < height && 0< MapY &&MapY<width && !map[MapX, MapY].isObstacle)
            {
                start = map[MapX, MapY];
                sprites[MapX, MapY].color = Color.green;
                Debug.Log("设置起点");
            }
        }
        if (Input.GetKey(KeyCode.D) && Input.GetMouseButtonDown(1))
        {
            Vector2 vector2 = Camera.main.ScreenToWorldPoint(Input.mousePosition);
            int MapX = -Mathf.FloorToInt(vector2.y);
            int MapY = Mathf.FloorToInt(vector2.x);
            if (0 < MapX && MapX < height && 0 < MapY && MapY < width && !map[MapX, MapY].isObstacle)
            {
                end = map[MapX, MapY];
                sprites[MapX, MapY].color = Color.red;
                Debug.Log("设置终点");
                if (start != null)
                {
                    StartCoroutine(FindPath());
                }
            }
        }
    }