[游戏开发]【算法可视化-Unity】A*寻路算法

开新坑了开新坑了~（这应该是个长期坑，现在的想法是把学过的或者有点难度的算法都做一个可视化）

正如标题所说的那样，现在我打算来做一个算法的可视化，除了帮助自己更好的理解算法之外，也帮助其它小伙伴们更好的理解。

那么话不多说，进入今天的主角，A*寻路算法。

A*寻路算法的核心原理说起来十分简单：
每一次都选择综合代价最小的格子，以此实现一定方向的遍历

算法的具体实现思路也很简单：

整个代码部分是我自己编写的，就一个脚本，注释十分详细，但同时也有很多问题（结构有点冗余，而且有个重载操作符的问题还没解决）

现在有想法是把它做成逐帧的，按一个键一跳的那种，看看之后优化一下

其他细节：
脚本导入之后自己建几个物体赋值一下就好了
计算距离使用的是街区距离（之后会开放自选）
你可能需要自己开启是否启用斜向遍历
地图大小和障碍物的比例自定义
斜向和横向移动花费自定义

注意一下自己控制别越界了（目标和起始点的最大值为地图最大值-1）
有一个Coord类和自己循环判空的问题还没有解决，目前是使用函数替代了操作符重载

C#脚本

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


public class QuadGenerate : MonoBehaviour
{
    public GameObject MyQuadPrefab;//瓦片的预制体
    public GameObject MyMapHolder;//瓦片挂载的父节点
    public GameObject RoadHolder;//路径挂载点
    public int MapSizeX;//地图大小自己指定
    public int MapSizeZ;

    public int TargetX;//目标地砖
    public int TargetZ;//目标地砖
    public int StartX;//起始地点X
    public int StartZ;//起始地点Z
    public float LineCost = 1;//横向移动花费
    public float ObliqueCost = 2;//斜向移动花费
    public bool isOblique;//是否斜向行走
    [Range(0, 1)] public float obsPercent;//障碍物比例
   

    private List<Coord> MyMaps;//记录所有地砖
    private bool[,] mapObstacles;//判断任意一个坐标上是否有障碍物

    private float QuadLength;//瓦片长度
    private Coord TargetQuad;//目标地砖
    private Coord StartQuad;//起始地砖




    void Awake()
    {
        MyMaps = new List<Coord>();//列表必须初始化
        Vector3 QuadScale = MyQuadPrefab.transform.localScale;
        QuadLength = QuadScale.x;
        TargetQuad = new Coord(TargetX, TargetZ);
        StartQuad = new Coord(StartX, StartZ);
        mapObstacles = new bool[(int)MapSizeX, (int)MapSizeZ];//创建障碍物的二维矩阵

    }
    // Start is called before the first frame update
    void Start()
    {
        //首先先生成一张地图
        Vector3 StartPos = new Vector3(-MapSizeX / 2, 0, -MapSizeZ / 2);//计算起始位置
        for(int i = 0; i < MapSizeX; i++)
        {
            for(int j = 0; j < MapSizeZ; j++)
            {
                Vector3 SetPos = new Vector3(i * QuadLength, 0, j * QuadLength);//偏置位置
                GameObject Quad = Instantiate(MyQuadPrefab, StartPos + SetPos, Quaternion.Euler(90, 0, 0));
                Quad.transform.SetParent(MyMapHolder.transform);
                Coord coord = new Coord(i, j);

                if (Random.Range(0f,1f) < obsPercent && !coord.Equal(StartQuad) && !coord.Equal(TargetQuad))//使用概率构建障碍物,需要人为添加f来选择返回浮点数的重载
                {
                    coord.setIsObs(true);//表明这个点是障碍物
                    mapObstacles[i, j] = true;
                }

                if (coord.Equal(StartQuad) || coord.Equal(TargetQuad) || coord.getIsObs())//对目标做相应处理
                {
                    MeshRenderer meshRenderer = Quad.GetComponent<MeshRenderer>();
                    Material material = meshRenderer.material;
                    if (coord.Equal(StartQuad))
                    {
                        material.color = new Color(0, 0, 255);
                    }
                    else if(coord.Equal(TargetQuad))
                    {
                        material.color = new Color(255, 0, 0);
                    }
                    else
                    {
                        material.color = new Color(0, 255, 0);
                    }
                    meshRenderer.material = material;
                }


                MyMaps.Add(coord);
            }
        }

        List<Coord> closeList = new List<Coord>();
        if (isOblique)//允许斜向
        {
            closeList = FindRoadAStarisOblique();//斜向遍历
        }
        else
        {
            closeList = FindRoadAStar();
        } 

        //先试着让整条路线出来，通过parent访问
        Coord CurNode = closeList[closeList.Count - 1];
        int count = 0;
        if(CurNode!=null)
        {
            CurNode = CurNode.parent;
        }

        while (CurNode!=null && CurNode.parent != null)
        {
            Debug.Log("生成路径中：" + count + "当前瓦片的X和Y为：" + CurNode.x + " " + CurNode.z);
            Vector3 SetPos = new Vector3(CurNode.x * QuadLength, 0.1f, CurNode.z * QuadLength);//偏置位置
            GameObject Quad = Instantiate(MyQuadPrefab, StartPos + SetPos, Quaternion.Euler(90, 0, 0));
            Quad.transform.SetParent(RoadHolder.transform);
            MeshRenderer meshRenderer = Quad.GetComponent<MeshRenderer>();
            Material material = meshRenderer.material;
            material.color = new Color(0, 0, 0);
            meshRenderer.material = material;

            CurNode = CurNode.parent;
            count++;
        }
    }

    // Update is called once per frame
    void Update()
    {
        
    }


    List<Coord> FindRoadAStar()//移动方式为上下左右，我想让它每按下一个按键调用一次,即前进一步  公式为f = g(移动花费) + h(预计花费)
    {
        List<Coord> openList = new List<Coord>();//A*使用的开放列表
        List<Coord> closeList = new List<Coord>();//A*使用的封闭列表
        List<Coord> dir = new List<Coord>() { new Coord(0, 1), new Coord(1, 0), new Coord(-1, 0), new Coord(0, -1) };
        StartQuad.setCost(CalcuCost(StartQuad));
        openList.Add(StartQuad);
        while (openList.Count != 0)
        {
            Coord supCoord = findFmin(openList); //找到当前花费值最小的那个
            closeList.Add(supCoord);
            if (supCoord.Equal(TargetQuad))//到达终点则跳出
            {
                Debug.Log("找到了终点");
                break;
            }
            for (int i = 0; i < dir.Count; i++)
            {
                int newx = supCoord.x + dir[i].x;
                int newz = supCoord.z + dir[i].z;
                if (newx >= 0 && newz >= 0 && newx < MapSizeX && newz < MapSizeZ)
                {
                    if (!mapObstacles[newx, newz] && !InList(new Coord(newx, newz), closeList))
                    {
                        //设置新瓦片并加入openList中
                        openList.Add(new Coord(newx, newz, false, CalcuCost(new Coord(newx, newz)), supCoord));
                    }
                }
            }
            Debug.Log("一直在循环");
        }
        return closeList;
    }

    List<Coord> FindRoadAStarisOblique()//开启斜向遍历并且启动花费
    {
        List<Coord> openList = new List<Coord>();//A*使用的开放列表
        List<Coord> closeList = new List<Coord>();//A*使用的封闭列表
        List<Coord> dir1 = new List<Coord>() { new Coord(0, 1), new Coord(1, 0), new Coord(-1, 0), new Coord(0, -1) };//上下左右
        List<Coord> dir2 = new List<Coord>() { new Coord(1, 1), new Coord(-1, -1), new Coord(1, -1), new Coord(-1, 1) };//斜向移动
        StartQuad.setCost(CalcuCost(StartQuad));
        openList.Add(StartQuad);
        while(openList.Count!=0)
        {
            Coord supCoord = findFmin(openList);
            closeList.Add(supCoord);
            if (supCoord.Equal(TargetQuad))//到达终点则跳出
            {
                Debug.Log("找到了终点");
                break;
            }

            for (int i=0;i<dir1.Count;i++)//先遍历横向
            {
                int newx = supCoord.x + dir1[i].x;
                int newz = supCoord.z + dir1[i].z;
                Coord nextCoord = new Coord(newx, newz);//预计算减小开销
                if (newx >= 0 && newz >= 0 && newx < MapSizeX && newz < MapSizeZ)
                {
                    if (!mapObstacles[newx, newz] && !InList(nextCoord, closeList))
                    {
                        //设置新瓦片并加入openList中
                        if (!InList(nextCoord, openList))//如果不在开放列表里面
                        {
                            //直接计算加入即可
                            float Gcost = supCoord.Gcost + LineCost;//横向移动Gcost花费为1
                            openList.Add(new Coord(newx, newz, false, CalcuCost(nextCoord), supCoord, Gcost));

                        }
                        else
                        {
                            float Gcost = supCoord.Gcost + LineCost;//计算新的Cost花费和原本的比较
                            checkGcost(nextCoord, Gcost,openList,supCoord);//检查是不是比以前的要小，是的话则更改父节点
                        }
                    }
                }
            }


            for (int i = 0; i < dir2.Count; i++)//再遍历斜向
            {
                int newx = supCoord.x + dir2[i].x;
                int newz = supCoord.z + dir2[i].z;
                Coord nextCoord = new Coord(newx, newz);//预计算减小开销
                if (newx >= 0 && newz >= 0 && newx < MapSizeX && newz < MapSizeZ)
                {
                    if (!mapObstacles[newx, newz] && !InList(nextCoord, closeList))
                    {
                        //设置新瓦片并加入openList中
                        if (!InList(nextCoord, openList))//如果不在开放列表里面
                        {
                            //直接计算加入即可
                            float Gcost = supCoord.Gcost + ObliqueCost;//斜向移动Gcost花费为2
                            openList.Add(new Coord(newx, newz, false, CalcuCost(nextCoord), supCoord, Gcost));

                        }
                        else
                        {
                            float Gcost = supCoord.Gcost + ObliqueCost;//计算新的Cost花费和原本的比较
                            checkGcost(nextCoord, Gcost, openList, supCoord);//检查是不是比以前的要小，是的话则更改父节点
                        }
                    }
                }
            }

        }
        return closeList;

    }


    void checkGcost(Coord nextCoord,float Gcost,List<Coord> List,Coord parentCoord)
    {
        for (int i = 0; i < List.Count; i++)
        {
            if (nextCoord.Equal(List[i]))
            {
                if(Gcost<List[i].Gcost)
                {
                    List[i].setGCost(Gcost);//SetGCost自带重新计算
                    List[i].setParent(parentCoord);
                }
            }
        }
    }
    Coord findFmin(List<Coord> openList)//遍历好还是排序好？我选择排序
    {
        openList.Sort((x, y) => { return x.RealCost.CompareTo(y.RealCost); });
        Coord ans = openList[0];
        openList.RemoveAt(0);//删掉第一个元素
        return ans;
    }

    int CalcuCost(Coord myQuad)
    {
        return Mathf.Abs(TargetX - myQuad.x) + Mathf.Abs(TargetZ - myQuad.z);
    }

    bool InList(Coord myQuad,List<Coord> List)//判断在不在列表里面
    {
        for(int i=0;i< List.Count;i++)
        {
            if(myQuad.Equal(List[i]))
            {
                return true;
            }
        }
        return false;
    }


}


public class Coord//这里如果是结构体则不能循环套用，因为C#的结构体是值类型而不是引用类型
{
    public Coord(int _x, int _z,bool _isObs = false,float _cost = 0f,Coord _parent=null,float _Gcost = 0)
    {
        this.x = _x;
        this.z = _z;
        this.isObs = _isObs;
        this.cost = _cost;
        this.parent = _parent;

        //以下字段在启用斜向的时候才有用
        this.Gcost = _Gcost;
        this.RealCost = this.cost + this.Gcost;
    }

    //public static bool operator ==(Coord _c1,Coord _c2)//求助：这里绕不开这个判空了，只能换种方式
    //{
    //    return (_c1.x == _c2.x) && (_c1.z == _c2.z);
    //}

    //public static bool operator !=(Coord _c1, Coord _c2)//别忘了强制重载
    //{
    //    return !(_c1 == _c2);
    //}

    public bool Equal(Coord _c)
    {
        return (this.x == _c.x) && (this.z == _c.z);
    }


    public void setIsObs(bool _isObs)
    {
        this.isObs = _isObs;
    }

    public bool getIsObs()
    {
        return this.isObs;
    }

    public void setCost(float _cost)
    {
        this.cost = _cost;
    }

    public void setParent(Coord _Parent)
    {
        this.parent = _Parent;
    }

    public void reCalRealCost()
    {
        this.RealCost = this.cost + this.Gcost;
    }

    public void setGCost(float _gcost)
    {
        this.Gcost = _gcost;
        reCalRealCost();//重新计算RealCost
    }

    public int x;
    public int z;
    public bool isObs;//用一个值来记录是不是障碍物，会比较轻松省力
    public float cost;//动态记录Hcost值
    public Coord parent;
    //以下字段在打开斜向之后才有用
    public float Gcost;//动态记录Gcost的值
    public float RealCost;//真实值
}

效果展示：（只允许横向移动）

开启斜向移动