2D猎宝行动（类扫雷小游戏）DAY 7

迈不过友情╰ 2022-05-13 14:20 97阅读 0赞

1.创建AStar寻路算法所需要的数据结构类

新建AstarStructure类用来写AStar算法的结构体

public class Point
    {
        public int x, y;
    
        public Point(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
    
        public new bool Equals(object obj)
        {
            return (obj != null) && (obj is Point) && (((Point)obj).x == x && ((Point)obj).y == y);
        }
    }
    
    public class PointData
    {
        public Point point;
        public double g, h;
        public PointData parent;
    
        public PointData(Point point,double g,double h,PointData parent)
        {
            this.point = point;
            this.g = g;
            this.h = h;
            this.parent = parent;
        }
    
        public double F()
        {
            return g + h;
        }
    }

2.设计寻路所需的地图的形式及挑选H函数

1、首先将起始点添加进“开启列表”。

2、重复如下步骤：  
   　  
   　a) 寻找开启列表中F值最低的节点。我们称其为“当前节点”。

b) 把它从“开启列表”中移除，并添加进“关闭列表”。

c) 检查“当前节点”是否是“目标节点”

\* 如果是，停止搜索，跳到第 3 步；

\* 如果不是，继续下面步骤；

d) 寻找“当前节点”邻近的节点

\* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

\* 如果它不在开启列表中，把它添加进开启列表。把当前节点作为这一节点的父节点。记录这一格的F,G和H值。

\* 如果它已经在开启列表中，检查新路径对它G值的产生的影响  
          　  
          　a. 如果它的G值因为新路径变大，那么保持原来的状态，不作任何改变；

b. 如果G值变小，说明新路径更好，将其父结点改为“当前结点”，更新G和F值。

e) 检查列表是否为空，如果为空，说明路径未找到，直接返回，不继续任何步骤。

3、保存路径。从目标节点开始，沿着每一节点的父节点移动直到回到起始节点。这就是我们要找的路径。

根据上述，来写AStar的寻路算法。

using System;
    
    public class AStarPathfinding
    {
    
        //	1、首先将起始点添加进“开启列表”。
        //  2、重复如下步骤：
        //   　a) 寻找开启列表中F值最低的节点。我们称其为“当前节点”。
        //   　b) 把它从“开启列表”中移除，并添加进“关闭列表”。
        //   　c) 检查“当前节点”是否是“目标节点”
        //      　* 如果是，停止搜索，跳到第 3 步；
        //      　* 如果不是，继续下面步骤；　
        //   　d) 寻找“当前节点”邻近的节点
        //      * 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
        //      　* 如果它不在开启列表中，把它添加进开启列表。把当前节点作为这一节点的父节点。记录这一格的F,G和H值。
        //      　* 如果它已经在开启列表中，检查新路径对它G值的产生的影响
        //          a.如果它的G值因为新路径变大，那么保持原来的状态，不作任何改变；
        //          b.如果G值变小，说明新路径更好，将其父结点改为“当前结点”，更新G和F值。
        //   e) 检查列表是否为空，如果为空，说明路径未找到，直接返回，不继续任何步骤。
        //  3、保存路径。从目标节点开始，沿着每一节点的父节点移动直到回到起始节点。这就是我们要找的路径。
    
        //地图元素
        private const char START = 'S';      //起点
        private const char END = 'E';        //终点
        private const char SPACE = '.';      //空地
        private const char WALL = 'W';      //墙
        private const char VISTIED = '-';      //被访问过
        private const char ON_PATH = '@';      //在结果路径上
    
        //地图字符串
        public static char[,] MAP = null;
        //地图最大尺寸
        public static Point MAX_PNT = null;
        //起点
        public static Point START_PNT = null;
        //终点
        public static Point END_PNT = null;
    
        //TODO 翻译地图的方法
    
        /// <summary>
        /// 曼哈顿距离，小于等于实际值
        /// </summary>
        /// <param name="pnt">当前评估点</param>
        /// <returns>按照曼哈顿距离所评估的H值</returns>
        private static double HManhattanDistance(Point pnt)
        {
            return Math.Abs(pnt.x - END_PNT.x) + Math.Abs(pnt.y - END_PNT.y);
    
        }
    
        /// <summary>
        /// 欧式距离距离，小于等于实际值
        /// </summary>
        /// <param name="pnt">当前评估点</param>
        /// <returns>按照欧式距离所评估的H值</returns>
        private static double HEuclidianDistance(Point pnt)
        {
            return Math.Sqrt(Math.Pow(pnt.x - END_PNT.x, 2) + Math.Pow(pnt.y - END_PNT.y, 2));
    
        }
    
        /// <summary>
        /// 欧式距离平方，大于等于实际值
        /// </summary>
        /// <param name="pnt">当前评估点</param>
        /// <returns>按照欧式距离平方所评估的H值</returns>
        private static double HPowEuclidianDistance(Point pnt)
        {
            return Math.Pow(pnt.x - END_PNT.x, 2) + Math.Pow(pnt.y - END_PNT.y, 2);
        }
    
        /// <summary>
        /// H函数
        /// </summary>
        /// <param name="pnt">当前评估点</param>
        /// <returns>按照指定方法评估的H值</returns>
        private static double HFun(Point pnt)
        {
            return HManhattanDistance(pnt);
        }
    
        /// <summary>
        /// 寻路函数
        /// </summary>
        private void Search()
        {
    
        }
    }

3.编写AStar寻路算法（上）

4.编写AStar寻路算法（下）

/// <summary>
        /// 寻路函数
        /// </summary>
        private void Search()
        {
            //用List集合做“开启列表”来记录扩展的点
            List<PointData> openList = new List<PointData>();
            //八个扩展方向
            int[,] directs = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
            //把起始点放入堆
            openList.Add(new PointData(START_PNT, 0, 0, null));
            //找到最后一个点的数据，用来反推路径
            PointData endData = null;
            //找到终点或“开启列表”为空时退出循环
            for(bool finish = false; !finish && openList.Count > 0;)
            {
                //取出f值最小的点
                openList.Sort((x, y) => { return x.F().CompareTo(y.F()); });
                PointData data = openList[0];
                openList.RemoveAt(0);
                Point point = data.point;
                //将取出的点标记为已访问点
                if(MAP[point.x,point.y] == SPACE)
                {
                    MAP[point.x, point.y] = VISTIED;
                }
                //遍历八个方向的点，Rank返回维数
                for (int i = 0; i < directs.Rank; i++)
                {
                    Point newPoint = new Point(point.x + directs[i, 0], point.y + directs[i, 1]);
                    if(newPoint.x >= 0 && newPoint.x <= MAX_PNT.x && newPoint.y >= 0 && newPoint.y < MAX_PNT.y)
                    {
                        //如果是终点，则跳出循环，不用再找
                        char e = MAP[newPoint.x, newPoint.y];
                        if(e == END)
                        {
                            endData = data;
                            finish = true;
                            break;
                        }
                        //如果不是空地，就不需要扩展
                        if (e != SPACE)
                        {
                            continue;
                        }
                        //如果在“开启列表”里，则更新g值
                        PointData tempData = openList.Find((x) => { return x.point.Equals(newPoint); });
                        if(tempData != null)
                        {
                            //更新G值
                            float goffset;
                            if (Math.Abs(directs[i, 0]) + Math.Abs(directs[i, 1]) > 1)
                            {
                                goffset = 1.4f;
                            }
                            else
                            {
                                goffset = 1.0f;
                            }
                            if(tempData.g > data.g + goffset)
                            {
                                tempData.g = data.g + goffset;
                                tempData.parent = data;
                            }
                        }
                        //如果不在“开启列表”里，则放入“开启列表”中，并计算g,h值
                        else
                        {
                            float goffset;
                            if (Math.Abs(directs[i, 0]) + Math.Abs(directs[i, 1]) > 1)
                            {
                                goffset = 1.4f;
                            }
                            else
                            {
                                goffset = 1.0f;
                            }
                            double h = HFun(newPoint);
                            PointData newData = new PointData(newPoint, data.g + goffset, h, data);
                            openList.Add(newData);
                        }
                    }
                }
            }
            //反向找出路径
            for(PointData pathData = endData;pathData != null;)
            {
                Point point = pathData.point;
                if (MAP[point.x, point.y] == VISTIED)
                {
                    MAP[point.x, point.y] = ON_PATH;
                }
                pathData = pathData.parent;
            }
        }

5.将游戏地图翻译为寻路地图

//翻译地图的方法
        private static bool GenerateMap(Point s,Point e)
        {
            if (MAP[END_PNT.x, END_PNT.y] == WALL)
            {
                return false;
            }
            if (s.Equals(e))
            {
                return false;
            }
            MAX_PNT = new Point(GameManager._instance.w, GameManager._instance.h);
            START_PNT = s;
            END_PNT = e;
            MAP = new char[MAX_PNT.x, MAX_PNT.y];
            for(int i = 0; i < MAX_PNT.x; i++)
            {
                for(int j = 0; j < MAX_PNT.y; j++)
                {
                    if(GameManager._instance.mapArray[i,j].elementContent == ElementContent.Door||
                       GameManager._instance.mapArray[i, j].elementContent == ElementContent.Enemy ||
                       GameManager._instance.mapArray[i, j].elementContent == ElementContent.BigWall ||
                       GameManager._instance.mapArray[i, j].elementContent == ElementContent.SmallWall ||
                       GameManager._instance.mapArray[i, j].elementState == ElementState.Marked ||
                       (GameManager._instance.mapArray[i, j].elementContent == ElementContent.Trap && GameManager._instance.mapArray[i,j].elementState == ElementState.Uncovered))
                    {
                        MAP[i, j] = WALL;
                    }
                    else if(GameManager._instance.mapArray[i,j].elementState == ElementState.Uncovered ||
                        (GameManager._instance.mapArray[i,j].elementContent == ElementContent.Tool && ((ToolElement)GameManager._instance.mapArray[i,j]).isHide == false) ||
                        (GameManager._instance.mapArray[i, j].elementContent == ElementContent.Gold && ((GoldElement)GameManager._instance.mapArray[i, j]).isHide == false))
                    {
                        MAP[i, j] = SPACE0;
                    }
                    else
                    {
                        MAP[i, j] = SPACE1;
                    }
                }
            }
            MAP[START_PNT.x, START_PNT.y] = START;
            MAP[END_PNT.x, END_PNT.y] = END;
            return true;
        }