Unity学习笔记——A*寻路算法的应用

时间:2022-12-28 12:25:39

初步了解了一些寻路算法后,本以为dijstra是比较合适的寻路算法,今天仔细看了关于A星寻路算法的教程和视频后,我认为A星寻路算法很适合战棋游戏。由于我的项目是仿照小小合金的玩法,所以是只需要上下左右寻路的正方形格子地图。

A星寻路的原理和教程我就不班门弄斧了,百度前几个都是大神写的。对着前辈的教程,我简单修改了一部分代码后做了一个简单的demo,又花了一个晚上将跑通的demo的脚本移植到项目了,在博客里就只贴出demo里的脚本了,作为我的学习记录。

其中有一部分不是很懂,写的注释(理解)可能是错的,以后有时间会重新学习和修改的。

Point类,存储着每一个点的各种属性,父点、F、G、H值,x、z坐标

public class Point  {
    public Point ParentPoint { get; set; }
    public float F { get; set; }
    public float G { get; set; }
    public float H { get; set; }
    public int X { get; set; }
    public int Z { get; set; }

    public bool IsObstacle { get; set; }
    public Point(int x, int z, Point parent = null)
    {
        this.X = x;
        this.Z = z;
        this.ParentPoint = parent;
    }
    public void UpdateParent(Point parent,float g)
    {
        this.ParentPoint = parent;
        this.G = g;
        F = G + H;
    }
}

AStar类,根据需要能得到移动路径点列表、移动所需要的步数、障碍物(不能走的格子)

public class AStar : MonoBehaviour {
    private const int mapWith = 5;
    private const int mapHeight = 5;
    private Point[,] map;
    Point start;
    Point end;
    public GameObject player;
    List<Point> pointList = new List<Point>();
    Vector3 targetPos;
    int step;
    void Update () {
        if (pointList.Count == 0)
            return;
        Move();
    }
    void InitPath(int row,int column)
    {
        map = new Point[row, column];
        InitMap();
        start = map[0, 0];//起始坐标
        end = map[1, 2];//目标点坐标
        FindPath(start, end);
        SetPathByParent(start, end);
    }
    //移动方法
    void Move()
    {
        for (int i = pointList.Count; i > 0; i--)
        {
            Vector3 pointPos = new Vector3(pointList[i - 1].X, player.transform.position.y, pointList[i - 1].Z);
            if (player.transform.position == pointPos)
            {
                pointList.Remove(pointList[i - 1]);
                break;
            }
            if (i == pointList.Count)
            {
                targetPos = pointPos;
                break;
            }
        }
        player.transform.position = Vector3.MoveTowards(player.transform.position, targetPos, 1 * Time.deltaTime);
    }
    //将通过父点,将路径点添加进列表
    private void SetPathByParent(Point start, Point end)
    {
        Point temp = end;
        pointList.Add(temp);
        while (true)
        {
            if (temp.ParentPoint == null)
                break;
            temp = temp.ParentPoint;
            step++;
            pointList.Add(temp);
        }
        Debug.Log(step);
    }
    //点过滤方法,关闭列表里存在的点——其本身,在周围能走的点列表里移除该点
    private void PointsFilter(List<Point> src, List<Point> closeList)
    {
        foreach (Point p in closeList)
        {
            if (src.IndexOf(p) > -1)
            {
                src.Remove(p);
            }
        }
    }
    //初始化格子坐标和属性
    private void InitMap()
    {
        for (int x = 0; x < mapWith; x++)
        {
            for (int z = 0; z < mapHeight; z++)
            {
                map[x, z] = new Point(x, z);
            }
        }
        //设置某点为障碍物
        map[0, 1].IsObstacle = true;
    }
    //寻找路径方法,传入起始点和结束点,
    private void FindPath(Point start, Point end)
    {
        //声明开启列表和结束列表,将起始点添加进开启列表
        List<Point> openList = new List<Point>();
        List<Point> closeList = new List<Point>();
        openList.Add(start);
        //如果开启列表数量不为0
        while (openList.Count > 0)
        {
            //找到开启列表里最小F值的点,将该点移除开启列表,添加进关闭列表
            Point point = FindMinFOfPoint(openList);
            openList.Remove(point);
            closeList.Add(point);
            //得到该点的周围的点,并将关闭列表里最小F值的点从中移除
            List<Point> surroundPoints = GetSurroundPoints(point);
            PointsFilter(surroundPoints, closeList);
            //遍历周围能走的点列表,第一次循环结束后,开启列表里最小F值的点为所以周围的点的父点,并且周围的点都添加进了开启列表
            foreach (Point surroundPoint in surroundPoints)
            {
                //如果周围的点在开启列表里,计算当前遍历到的周围的点的G值
                if (openList.IndexOf(surroundPoint) > -1)
                {
                    float nowG = CalcG(surroundPoint, point);
                    if (nowG < surroundPoint.G)
                    {
                        surroundPoint.UpdateParent(point, nowG);
                    }
                }
                //不在开启列表里,将当前点设为周围能走的点的父点,计算周围点的F、H、G值,将其添加进开启列表
                else
                {
                    surroundPoint.ParentPoint = point;
                    CalcF(surroundPoint, end);
                    openList.Add(surroundPoint);
                }
            }
            
            //如果开启列表为空,跳出循环
            if (openList.IndexOf(end) > -1)
            {
                break;
            }
        }
    }
    //得到周围点方法
    private List<Point> GetSurroundPoints(Point point)
    {
        //默认点有四个方向,上下左右四个点,由地图大小判断四个点是否存在
        Point up = null, down = null, left = null, right = null;
        //Point lu = null, ru = null, ld = null, rd = null;
        if (point.Z < mapHeight - 1)
        {
            up = map[point.X, point.Z + 1];
        }
        if (point.Z > 0)
        {
            down = map[point.X, point.Z - 1];
        }
        if (point.X > 0)
        {
            left = map[point.X - 1, point.Z];
        }
        if (point.X < mapWith - 1)
        {
            right = map[point.X + 1, point.Z];
        }
        //判断上下左右点是否为障碍物点,返回存储能走的点的list
        List<Point> list = new List<Point>();
        if (down != null && down.IsObstacle == false)
        {
            list.Add(down);
        }
        if (up != null && up.IsObstacle == false)
        {
            list.Add(up);
        }
        if (left != null && left.IsObstacle == false)
        {
            list.Add(left);
        }
        if (right != null && right.IsObstacle == false)
        {
            list.Add(right);
        }
        return list;
    }
    //在开启列表里寻找最小F值的点,并返回该点
    private Point FindMinFOfPoint(List<Point> openList)
    {
        //初始化f值为最大值,遍历开启列表,判断开启列表里F值最小的点,即为最合适的点
        float f = float.MaxValue;
        Point temp = null;
        foreach (Point p in openList)
        {
            if (p.F < f)
            {   
                temp = p;
                f = p.F;
            }
        }
        return temp;
    }
    //返回由父点计算得到的当前点的G值
    private float CalcG(Point now, Point parent)
    {
        return Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(parent.X, parent.Z))+parent.G;
    }
    //计算F值,传入当前点和结束点
    private void CalcF(Point now,Point end)
    {
        //得到当前点和结束点的x、z两坐标值之差的绝对值之和为h值,g初始化为0
        float h = Mathf.Abs(end.X-now.X) + Mathf.Abs(end.Z-now.Z);
        float g = 0;
        //如果当前点没有父点,说明为起始点,g值为0
        if (now.ParentPoint == null)
            g = 0;
        //如果有父点,则计算当前点到父点的距离加上父点的g值就为当前点的g值
        else
            g = Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(now.ParentPoint.X, now.ParentPoint.Z))+ now.ParentPoint.G;
        float f = g + h;
        now.F = f;
        now.G = g;
        now.H = h;
    }
}