精华内容
参与话题
问答
  • AStar技术,浏览器插件,/出国/人士常用,是个T—Z,很稳定,分享给大家。 ---------------以下资源具体描述(cou50zi):Zipkin 是一款开源的分布式实时数据追踪系统(Distributed Tracking System),基于 Google ...
  • AStar算法

    2017-07-10 19:39:17
    我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,中间蓝色是墙。图 1 我们把要搜寻的区域划分成了正方形的格子,目的是简化搜索区域,我们的搜索区域简化为了二维...

    我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,中间蓝色是墙。

    这里写图片描述

    图 1
    我们把要搜寻的区域划分成了正方形的格子,目的是简化搜索区域,我们的搜索区域简化为了二维数组。数组的每一项代表一个格子,它的状态就是可走和不可走,通过计算出从 A 到 B需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心移动到另一个方格的中心,直至到达目的地。

    方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。

    开始搜索(Starting the Search)
    一旦我们把搜寻区域简化为一组可以量化的节点后,就像上面做的一样,我们下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。

    查找的方法如下:
    1.从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。

    2.查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,及其他障碍物的方格 ) ,把其中可走的方格也加入到 open list 中。把起点 A 设置为这些方格的父物体。当我们在追踪路径时,这些父节点的内容是很重要的。(根据当前节点的父,反推路径)

    3.把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。
    如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。

    这里写图片描述

    图 2 。

    下一步,我们需要从 open list 中选一个与起点 A 相邻的方格,选择具有最小 F 值的那个。

    路径排序(Path Sorting)

    计算出组成路径的方格的关键是下面这个等式:
    F = G + H
    这里,

    G = 从起点 A 移动到指定方格的移动代价。

    H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法,为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。

    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。

    如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单。

    既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。

    有很多方法可以估算 H 值。这里我们使用 Manhattan(曼哈顿街区算法)方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。

    把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。

    这里写图片描述

    图 3
    现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。

    H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。

    每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。

    继续搜索(Continuing the Search)
    为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:
    1.把它从 open list 里取出,放到 close list 中。

    2.检查所有与它相邻的方格,忽略其中在 close list 中或是不可走的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open list 中,则把它们加入到 open list 中。

    3.把我们选定的方格设置为这些新加入的方格的父亲。

    4.如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。
    相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。

    这里写图片描述

    图 4
    Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 open list 中,起点被放入了 close list 中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

    首先,我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他 4 个相邻的方格均在 open list 中,我们需要检查经由这个方格到达那里的路径是否更好,使用 G 值来判定。首先让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。因为直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。
    当把 4 个已经在 open list 中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。

    因此再次遍历我们的 open list ,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54(图4,上下2个) ,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待,导致两中版本的 A* 找到等长的不同路径 ) 。

    我们选择起点右下方的方格,如下图所示。

    这里写图片描述

    图 5

    这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。右上面的也一样。
    我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。
    这样还剩下 5 个(9宫格左边3个,和当前的上面和下面2个)相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。

    不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。

    这里写图片描述

    图 6

    那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。

    这里写图片描述

    图 7

    A*算法总结(Summary of the A* Method)
    1. 把起点加入 open list 。
    2. 重复如下过程:
    a. 遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。
    b. 把这个节点移到 close list 。
    c. 对当前方格的 8 个相邻方格的每一个方格,做如下处理:
    ◆ 如果它是不可抵达的或者它在 close list 中,忽略它。
    ◆ 如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。
    ◆ 如果它已经在 open list 中,检查这条路径是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。
    d. 停止
    ◆ 当你把终点加入到了 open list 中,此时路径已经找到了
    ◆ 或者查找终点失败,并且 open list 是空的,此时没有路径。
    3. 保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

    本文参考

    www.gamedev.net/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003

    展开全文
  • 自动寻路之 --AStar算法

    千次阅读 2018-06-11 23:19:15
    如图所示,为了向大家介绍AStar自动寻路算法,我先用一个二维数组作为地图的数据建立了一个如图所示的地图 privateint[,] map0 = new int[,]{ { 0,0,0,0,0,0,0}, { 0,1,1,1,1,1,0}, { 0,1,2,0,1,1,0}, { ...

    如图所示,为了向大家介绍AStar自动寻路算法,我先用一个二维数组作为地图的数据建立了一个如图所示的地图

        privateint[,] map0 = new int[,]{
    
           { 0,0,0,0,0,0,0},
    
           { 0,1,1,1,1,1,0},
    
           { 0,1,2,0,1,1,0},
    
           { 0,1,1,0,1,1,0},
    
           { 0,1,1,0,1,1,0},
    
           { 0,1,1,1,1,1,0},
    
           { 0,0,0,0,0,0,0}
    
       };

     

    二维数组用来显示地图的基本信息是最为简单的一种方式,在游戏中的应用是很多的, 例如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而一些大型游戏的地图看起来比较平滑的起始只是进行了些处理, 是将各种"地貌"铺在这样的小方块上. 为了抽象理解看如下这张较为平滑的简易地图作为理解

     

    【问题分析】

    1.    已知地图样貌信息和起始位置

    2.    从初始方格周围开始计算距离终止方格的信息并进行记录,减少信息冗余

    3.    可走动方向为棋面可走8个方向,但斜走时不可有上下左右墙阻挡(路径抽象最小化如1图可知次举动不可为,除非特殊情况的设定。本帖设定不可)

     

    【实现策略】

     

    1.    定义方格的信息(距离重点信息+移动位置点信息(包含前一位置))权值

    F = G + H

    G: 表示从某位置移动到网格上指定位置点的移动耗费 (距离)—包含前一位置耗费

    H: .表示从指定的位置点移动到终点 B 的预计耗费

    2.     定义两个容器

    (1)“开启列表”保存已检测到和未到达的方格

    (2)“关闭列表”保存已到达的过方格

    3.     先将起始位置保存到(1),从(1)得到F值最小的并设为A, 再将A从(1)中移除,记录A位置可到达方格并将他们的父亲设为A并计算他们的权值并保存到(1)中。如果从(1)中得到F值最小方格为终点则结束

    4.     线性递归 【3】

    5.     A为终点结束后只需从终点的的父节点开始向上遍历则可得到完整的路径点

     

     

     

    【抽象分析】 使用图例加强理解

    ◆   假设从绿方格到红方格,将起点加入(1);再从(1)得到F值最小从(1)中移除并设为A。在计算A可到达的方格加入(1)中并计算他们的权值,在将他们的父亲设为A

    ◆   再从(1)得到F值最小的从(1)中移除并设为A。在计算A可到达的方格加入(1)中并将他们的父亲设为A再计算他们的权值(需将G值进行累==加上其父亲的G值表示路程信息),如A上面的方格G值原本位置因为其父亲的G值为1所以就为1+1=2

    ● 从(1)得到F值最小的以第一个为先(否则只需更改算法设定)

     

     

    ◆   再从(1)得到F值最小的从(1)中移除并设为A。在计算A可到达的方格加入(1)中并将他们的父亲设为A再计算他们的权值

    ◆   再从(1)得到F值最小的从(1)中移除并设为A。在计算A可到达的方格加入(1)中并将他们的父亲设为A再计算他们的权值

    ◆   再从(1)得到F值最小的从(1)中移除并设为A。如果A为终点则结束

     【代码实现】

    Point类        --方格信息类

    public class Point
    {
        public Point Parent { get; set; }
        public float F { get; set; }
        public float G { get; set; }
        public float H { get; set; }
    
        public int mapPointX { get; set; }
        public int mapPointY { get; set; }
        public Vector2 MapVector2 { get; set; }
    
        public bool IsWall { get; set; }
        private bool _isVisi;
        public bool IsVisi { get { return _isVisi && !IsWall; } set { _isVisi = value; } }
    
        public Point(int mapX, int mapY, Point parent = null)
        {
            this.mapPointX = mapX;
            this.mapPointY = mapY;
            MapVector2 = new Vector2(mapPointX, mapPointY);
            this.Parent = parent;
            IsWall = false;
            IsVisi = true;
        }
        public Point(bool isVisi = false)
        {
            IsVisi = isVisi;
        }
        public void UpdateParent(Point parent, float g)
        {
            this.Parent = parent;
            this.G = g;
            F = G + H;
        }
    }

     

    AStar类        --实现类

     

    public class Astar :MonoBehaviour{
    
        private const float COST_HOR = 1f;
        private const float COST_VER = 1f;
        private const float COST_DIA = 2f;
        private static int mapWidth;
        private static int mapHeight;
    
        private static Point[,] map;                                           //数据地图
        //private static List<GameObject> objList = new List<GameObject>();      //最佳移动点集
        private static List<Point> closeList = new List<Point>();
    
        //得到传入的数据--初始化数据地图--计算最佳移动点集--返回最佳移动点集
        public static Vector3[] StartMake (int[,] map0,Vector3Int sPos, Vector3Int ePos)
        {
            if(sPos == ePos) return new Vector3[1] { sPos };
    
            if (sPos.x > map0.GetLength(0) || ePos.x > map0.GetLength(0) || sPos.y > map0.GetLength(1) || ePos.y > map0.GetLength(1)) {
    
                Debug.LogError("["+sPos.x + "," + sPos.y+"]["+ ePos.x+","+ ePos.y+"]");
                Debug.LogError("数组索引超出范围");
                return new Vector3[1] { sPos };
            }
            InitMap(map0, sPos, ePos);
    
            Point start = map[sPos.x, sPos.y];
            Point end = map[ePos.x, ePos.y];
    
            if (FindPath(start, end))
            {
                return GetPathPoints(start, end);                          //返回最佳移动点集
            }
            else
            {
              return new Vector3[1] { sPos };
            }
        }
    
        //初始化数据地图
        static void InitMap(int[,] map0, Vector3Int start, Vector3Int end)
        {
            mapWidth = map0.GetLength(0);
            mapHeight = map0.GetLength(1);
            //print(mapWidth + " " + mapHeight);
            map = new Point[mapWidth, mapHeight];
            for (int x = 0; x < mapWidth; x++) {
                for (int y = 0; y < mapHeight; y++) {
                    map[x,y] = new Point(x,y);
                    if(map0[x,y] == 0)
                        map[x, y].IsWall = true;
                }
            }
        }
        //计算最佳移动点集
        static bool FindPath(Point start, Point end) {
    
            List<Point> openList = new List<Point>();
            //List<Point> closeList = new List<Point>();
            closeList.Clear();
            
            openList.Add(start);
    
            while (openList.Count > 0) {
                Point point = GetMinF(openList);
                openList.Remove(point);
                closeList.Add(point);
    
                List<Point> surroundPoints = GetGroundPoint(point);
                GetSurroundPoints(surroundPoints, closeList);
    
                foreach (Point surroundPoint in surroundPoints) {
                    if (openList.IndexOf(surroundPoint) > -1)
                    {
                        float nowG = CalcG(surroundPoint, point);
                        if (nowG < point.G)
                        {
                            surroundPoint.UpdateParent(point, nowG);
                        }
                    }
                    else {
                        surroundPoint.Parent = point;
                        CalcFGH(surroundPoint, end);
                        FindAndSort(openList, surroundPoint);
                    }
                }
                if (openList.IndexOf(end) > -1)
                {
                    return true;
                }
                else if (openList.Count == 0)
                {
                    break;
                }
            }
            return false;
        }
    
        static void FindAndSort(List<Point> openList, Point point)
        {
    
            bool IsInsert = true;
            foreach (Point pointT in openList)
            {
                if (point.mapPointX == pointT.mapPointX && point.mapPointY == pointT.mapPointY)
                {
                    IsInsert = false;
                }
            }
            if (IsInsert)
            {
                openList.Add(point);
            }
        }
    
        static void GetSurroundPoints(List<Point> src, List<Point> closeList) {
            foreach (Point p in closeList) {
                if (src.IndexOf(p) > -1)
                {
                    src.Remove(p);
                }
            }
        }
    
        static List<Point> GetGroundPoint(Point point) {
    
            Point up = null, down = null, right = null, left = null;
            Point uR = null, uL = null, dR = null, dL = null;
            List<Point> tempList = new List<Point>();
    
            //上下左右
            if (point.mapPointY < mapHeight - 1) up = map[point.mapPointX, point.mapPointY + 1];
            else up = new Point();
    
            if (point.mapPointY > 0) down = map[point.mapPointX, point.mapPointY - 1];
            else down = new Point();
    
            if (point.mapPointX < mapWidth - 1) right = map[point.mapPointX + 1, point.mapPointY];
            else right = new Point();
    
            if (point.mapPointX > 0) left = map[point.mapPointX - 1, point.mapPointY];
            else left = new Point();
    
            //上右 上左 下右 下左 
            if (up.IsVisi && right.IsVisi) uR = map[point.mapPointX + 1, point.mapPointY + 1];
            else uR = new Point();
    
            if (up.IsVisi && left.IsVisi) uL = map[point.mapPointX - 1, point.mapPointY + 1];
            else uL = new Point();
    
            if (down.IsVisi && right.IsVisi) dR = map[point.mapPointX + 1, point.mapPointY - 1];
            else dR = new Point();
    
            if (down.IsVisi && left.IsVisi) dL = map[point.mapPointX - 1, point.mapPointY - 1];
            else dL = new Point();
    
    
            if (up.IsVisi) tempList.Add(up);
            if (down.IsVisi) tempList.Add(down);
            if (right.IsVisi) tempList.Add(right);
            if (left.IsVisi) tempList.Add(left);
            if (uR.IsVisi && up.IsVisi && right.IsVisi) tempList.Add(uR);
            if (uL.IsVisi && up.IsVisi && left.IsVisi) tempList.Add(uL);
            if (dR.IsVisi && down.IsVisi && right.IsVisi) tempList.Add(dR);
            if (dL.IsVisi && down.IsVisi && right.IsVisi) tempList.Add(dL);
    
            return tempList;
        }
    
        static Point GetMinF(List<Point> tempList) {
            Point point = null;
            float minPoint = float.MaxValue;
    
            for (int i = tempList.Count - 1; i >= 0; i--) {
                if (tempList[i].F <= minPoint)
                {
                    minPoint = tempList[i].F;
                    point = tempList[i];
                }
            }
            return point;
        }
    
        static void CalcFGH(Point now, Point end) {
            // F =G + H
            float h = Mathf.Abs(end.mapPointX - now.mapPointX) + Mathf.Abs(end.mapPointY - now.mapPointY);
            float g;
            if (now.Parent == null)
            {
                g = 0;
            }
            else
            {
                float disance = Vector2.Distance(now.Parent.MapVector2, now.MapVector2);
                float disanceZ = Mathf.RoundToInt(disance);
                if (disance - disanceZ != 0)
                {
                    g = disance * COST_DIA + now.Parent.G;
                }
                else
                {
                    if (now.Parent.mapPointX == now.mapPointX && now.Parent.mapPointY != now.mapPointY)
                        g = disance * COST_HOR + now.Parent.G;
                    else
                        g = disance * COST_VER + now.Parent.G;
                }
            }
            now.G = g;
            now.H = h;
            now.F = g + h;
        }
    
        static float CalcG(Point now, Point parent) {
            return Vector2.Distance(now.MapVector2, parent.MapVector2) + parent.G;
        }
    
        static Vector3[] GetPathPoints(Point start, Point end)
        {
            List<Vector3> path = new List<Vector3>();
            Vector3[] pathPoints;
    
            Point point = end;
            while (true)
            {
                path.Add(new Vector3(point.mapPointX, point.mapPointY,0));
                point = point.Parent;
                if (point == null)
                    break;
            }
            pathPoints = new Vector3[path.Count];
            for (int i = 1; i <= path.Count; i++)
            {
                pathPoints[i - 1] = path[path.Count - i];
            }
            return pathPoints;
        }
        
    }

     

    AStar 辅助方法测试用

     

        #region AStarPaint
    
        List<Vector3> GetPathPoints(Point start, Point end) {
            foreach (GameObject obj in objList) {
                Destroy(obj);
            }
            objList.Clear();
            for (int x = 0; x < mapWidth; x++)
            {
                for (int y = 0; y < mapHeight; y++)
                {
                    if (map[x, y].IsWall)
                    {
                        PaintSceneCube(x+ mapWidth, y, Color.black);
                    }
                    PaintTest(x + mapWidth, y, map[x, y]);
                }
            }
            List<Vector3> path = new List<Vector3>();
            List<Vector3> path0 = new List<Vector3>();
            Point point = end;
            while (true) {
    
                path.Add(new Vector3(point.mapPointX, 0.5f, point.mapPointY));
                Color color = Color.gray;
                if (point == start)
                {
                    color = Color.green;
                    
                }
                if (point == end)
                {
                    color = Color.red;
                }
                PaintSceneCube(point.mapPointX+ mapWidth, point.mapPointY, color,point);
                point = point.Parent;
                if (point == null)
                    break;
            }
            for (int i=1;i<= path.Count;i++) {
                path0.Add(path[path.Count - i]);
            }
            return path0;
        }
        void PaintSceneCube(int x, int y, Color color)
        {
            GameObject gameObject = GameObject.CreatePrimitive(PrimitiveType.Cube);
            gameObject.transform.position = new Vector3(x, 0, y);
            gameObject.transform.SetParent(GameObject.Find("GameFaced").transform);
            gameObject.GetComponent<Renderer>().material.color = color;
            objList.Add(gameObject);
        }
        void PaintSceneCube(int x, int y, Color color,Point point) 
        {
            GameObject gameObject = GameObject.CreatePrimitive(PrimitiveType.Cube);
            gameObject.transform.position = new Vector3(x, 0, y);
            gameObject.transform.SetParent(GameObject.Find("GameFaced").transform);
            gameObject.GetComponent<Renderer>().material.color = color;
            objList.Add(gameObject);
        }
        void PaintTest(int x, int y, Point point) {
            if (point.F <= 0)
                return;
            
            GameObject testObject = Instantiate(testObj);
            testObject.transform.position = new Vector3(x, 0.7f, y);
            testObject.transform.SetParent(GameObject.Find("GameFaced").transform);
            testObject.transform.Find("F").GetComponent<Text>().text = Mathf.RoundToInt(point.F).ToString();
            testObject.transform.Find("G").GetComponent<Text>().text = Mathf.RoundToInt(point.G).ToString();
            testObject.transform.Find("H").GetComponent<Text>().text = Mathf.RoundToInt(point.H).ToString();
            objList.Add(testObject);
    
        }
        #endregion

     

    主控制类

     

    public class GameManager : MonoBehaviour {
    
        private int[,] map0 = new int[,]{
            { 0,0,0,0,0,0,0},
            { 0,1,1,1,1,1,0},
            { 0,1,2,0,1,1,0},
            { 0,1,1,0,1,1,0},
            { 0,1,1,0,1,1,0},
            { 0,1,1,1,1,1,0},
            { 0,0,0,0,0,0,0}
        };
        
        #region AStar
        private Astar astar = new Astar();
        public GameObject testObj;
    
        #endregion
    
        public GameObject wallObject;
        public GameObject planeObject;
        public GameObject gamePlayerObject;
        private GameObject gamePlayer = null;
    
        private List<Vector3> targetPos = new List<Vector3>();
    
    
        void Start () {
            Init();
        }
    	
    	// Update is called once per frame
    	void Update () {
            if (Input.GetMouseButtonDown(0))
            {
                Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
                RaycastHit hit;
                if (Physics.Raycast(ray, out hit))
                {
                    if (hit.collider.tag == "Plane")
                    {
                        Vector3 temp = new Vector3(hit.transform.position.x,0.5f, hit.transform.position.z);
    
                        AtarGetPos(temp);
                        //targetPos.Add(temp);
                    }
                }
            }
        }
        private void FixedUpdate()
        {
            PlayerMove(targetPos);
        }
        void Init() {
    
            for (int i = 0; i < map0.GetLength(0); i++)
            {
                for (int j = 0; j < map0.GetLength(1); j++)
                {
                    switch (map0[i,j])
                    {
                        case 0:
                            Instantiate(wallObject, new Vector3(i, 0, j), Quaternion.identity, transform);
                            break;
                        case 1:
                            Instantiate(planeObject, new Vector3(i, 0, j), Quaternion.identity, transform);
                            break;
                        case 2:
                            Instantiate(planeObject, new Vector3(i, 0, j), Quaternion.identity, transform);
                            gamePlayer = Instantiate(gamePlayerObject, new Vector3(i, 0.5f, j), Quaternion.identity);
                            break;
                        default:
                            break;
                    }
                }
            }
        }
        void PlayerMove(List<Vector3> vector3) {
            if (vector3.Count > 0)
            {
                Vector3 pos = new Vector3((int)vector3[0].x, 0.5f, (int)vector3[0].z);
                gamePlayer.transform.position = pos;
                vector3.Remove(vector3[0]);
            }
        }
        void AtarGetPos(Vector3 temp) {
            targetPos.Clear();
            Vector3 pos = new Vector3((int)gamePlayer.transform.position.x, 0.5f, (int)gamePlayer.transform.position.z);
            targetPos = astar.StartMake(map0, gamePlayer.transform.position, temp, testObj);
        }
    }
    

    【效果演示】    右边为AStar 辅助方法测试用

    【工程代码】

    *提示:本博文中的脚本可能会与工程代码中的有些许不同以工程代码中的为准

    链接:  CSDN下载 

    展开全文
  • AStar算法

    千次阅读 2018-09-01 19:51:47
    什么是AStar: 是一种静态路网中求解最短路最有效的直接搜索方法,估价值跟实例值非常接近; 启发式搜索 : 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,在从这个位置进行搜索直到目标...

    什么是AStar:
    是一种静态路网中求解最短路最有效的直接搜索方法,估价值跟实例值非常接近;

    启发式搜索 :
    启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,在从这个位置进行搜索直到目标.这样可以省略大量无谓的搜索路径,提高了效率;

    在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价,可以有不同的效果;
    (估价函数就一种规则,制定的规则不同,最后的效果也就不同)<比如寻路的格子不同,最后的效果也是不同的>
    

    估价函数 :
    从当前节点移动到 目标节点的预估费用<费用简单的说就是从起点到终点的距离>(如果放到地图上就是距离,走的路越多估价越高);这个估价就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预估费用.

    A*算法特点:
    在理论上是时间最优的;
    但也有缺点:它的空间增长是指数级别的;(格子越多计算的量也就越大)<优化可以使用 二叉堆 >

    中心思想:
    通过从起始点开始,检查相邻方格的方式,向外扩展,直到找到目标;

    运用:
    把一个平面分成一个个的小方格,方格分的越细,寻路就越精准;

    为了更好的描述,和理解A*算法提出的两个概念(不存在于真实的场景中)
    

    开启列表:
    待检查方格的集合列表,寻找周围可以达到的点,加入到此列表中,
    并保存中心点为父节点

    关闭列表:列表中保存不需要再次检查的方格

    这里写图片描述

    路径评分:
    G-当前点与起始点的距离
    H-当前点与目标点的距离

    F的值是G和F的和
    F,G和H的评分被写在每个方格里.
    如图:F被打印在中间,G在左上角.H在右上角.
    <如上图>
    从一个格子到相邻格子的斜线距离(以为到斜线格子的距离为跟2,所以用1.4为单位)
    从一个格子到相格子的直线距离(因为格子为1,所以就以1为单位);
    为了方便计算查看,都乘以10作为单位;

    选择路径过程中,经过哪个方格关键是:F=G+H;
    这里写图片描述

    <如上图>以红色格子为例
    方块的中心位置42就是估价,也就是起始点到目标的距离
    左上角用G表示,也就是该格子到目标点的距离为14
    右上角用H表示,也就是该格子到起始点的距离为28
    红色格子右上角是62,是因为已经确定了当前红色的格子,路径是从当前红色格子到右上角的格子,所以值为62;
    如果选择的不是当前红色的格子,那么就会去改变其他格子的值,也就是说每个格子的值随着你的选择进行改变
    (改变成符合当前格子路径上的值).

    例如:从A到B的一个解析过程
    这里写图片描述

    开始搜索:
    1.把起始格添加到开启列表。
    从A点开始查找
    2.寻找起点周围所有可到达或者可通过的方格,把他们加入开启列表。
    遍历A所能到达的所有方格,把他们加入开启列表中
    3.从开启列表中删除点A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。
    因为A已经走过,所以把A加入关闭列表中,下次在进行遍历时把A除外
    这里写图片描述

    继续搜索:
    4把当前格子从开启列表中删除,然后添加到关闭列表中。
    因为已经到达了当前格子,所以把当前格子放到关闭列表中(已经到达了,没有必要去进行遍历)
    5检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的,把他们添加进开启列表,把选中的方格作为新的方格的父节点。
    当前中的格子周围有两个已经添加到开启列表中,上面三个为不可通过,也就是障碍物,所以只是新添加了左侧的两个格子;
    这里写图片描述
    这里写图片描述
    这里写图片描述

    6如果某个相邻格已经在开启列表里了,检查现在的这条路径G值是否会更低一些。

    如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格,重新计算F和G的值。
    一旦重新选择了一个点那么就需要重新计算一下当前的费用,上面写着只计算G和F的 值,为什么呢!
    原因:
    每个点到目标点的距离是固定的,所以H点(又上角的点)是不需要改变的,会变化的G值仅仅是因为路经改变的原因跟起始点的距离会发生改变,
    所以只需要计算G的值和F的值,其他的点也会相应的更新;
    <图一>
    因为选择的42,但是出现了3个相同的估价,那么我们该怎么选择呢?
    <图二>
    这里还有另外一个原则:那就是选择一个距离目标点最近的一个值,也就是H值最低的一个.
    也就是左侧的48这个方块 ,那么就把48这个点从开启列表中删除,送进关闭列表中.
    因为选择了48,新增了左侧两个点,那么跟新一下在开启列表中的当前48下面的两个点(在这里下面那两个点是没有变化的,因为42下面的也是48,所以路径的值是没有改变的);
    那么继续走
    当我们继续走的时候,发现遍历48所能达到的值,发现这条路径不是最优的.
    为什么不是最优的呢:(因为在它的开启列表中还有一个48)
    那么在他的开启列表中还有一个48的值,那么就把当前的这个48从开起列表中删除,送进关闭列表中。
    我们就回到上一步,选择42下方的48;
    同理,这个48也不是最优的,因为他的开启列表中还有一个48,那么我们继续选择42,右侧的这个48;
    结束
    这里写图片描述

    起始格下方格子的父节点已 经和前面不同的。 之前它的G值是,并且指向 右上方的格子。现在它的G 值是,指向它上方的格子。 这在寻路过程中的某处发生, 当应用新路径时,G值经过 检查变得低了-于是父节点 被重新指定,G和F值被重
    新计算。

    根据上述的原理得到如上图所示的路径,也就是最佳路径;

    总结

    1把起始格添加到开启列表。
    2重复如下的工作:
    寻找开启列表中F值最低的格子。我们称它为当前格。
    把它切换到关闭列表。
    /1/对相邻的格中的每一个–> 如果它不可通过或者已经在关闭列表中,略过它。反之如下。如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
    /2/如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的 G和F值。
    停止,当你 把目标格添加进了关闭列表,这时候路径被找到–>没有找到目标格,开启列表已经空了。这时候,路径不存在。
    3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。

    算法:步骤架构
    <1>开启集合
    <2>关闭集合
    <3>添加起始点到开始集合中
    <4>循环如下步骤: 当前点=开启集合中最小F_Cost的点 将当前点移出开启集合中 将当前点添加到关闭集合中
    <5>如果当前点是目标点,结束查询
    <6>遍历当前点的每个相邻点 如果相邻点不能访问或者相邻点在关闭集合中,跳过此相邻点 如果新路径到相邻点的距离更短,或者相邻点不在开启集合中 重新设置F_Cost 重新设置其父节点为当前点
    <7>如果相邻点不在开启集合中
    <8>添加相邻点到开启集合什么是AStar: 是一种静态路网中求解最短路最有效的直接搜索方法,估价值跟实例值非常接近;
    启发式搜索 : 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,在从这个位置进行搜索直到目标.这样可以省略大量无谓的搜索路径,提高了效率;

    在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价,可以有不同的效果;
    (估价函数就一种规则,制定的规则不同,最后的效果也就不同)<比如寻路的格子不同,最后的效果也是不同的>

    估价函数 :从当前节点移动到 目标节点的预估费用<费用简单的说就是从起点到终点的距离>(如果放到地图上就是距离,走的路越多估价越高);这个估价就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预估费用.

    A*算法特点:在理论上是时间最优的;
    但也有缺点:它的空间增长是指数级别的;(格子越多计算的量也就越大)<优化可以使用 二叉堆 >

    中心思想:通过从起始点开始,检查相邻方格的方式,向外扩展,直到找到目标;

    .运用
    把一个平面分成一个个的小方格,方格分的越细,寻路就越精准;

    为了更好的描述,和理解A*算法提出的两个概念(不存在于真实的场景中)
    开启列表: 待检查方格的集合列表,寻找周围可以达到的点,加入到此列表中,
    并保存中心点为父节点

    关闭列表:列表中保存不需要再次检查的方格

    路径评分:
    G-当前点与起始点的距离
    H-当前点与目标点的距离

    F的值是G和F的和
    F,G和H的评分被写在每个方格里.
    如图:F被打印在中间,G在左上角.H在右上角.
    <如上图>
    从一个格子到相邻格子的斜线距离(以为到斜线格子的距离为跟2,所以用1.4为单位)
    从一个格子到相格子的直线距离(因为格子为1,所以就以1为单位);
    为了方便计算查看,都乘以10作为单位;

    选择路径过程中,经过哪个方格关键是:F=G+H;

    <如上图>以红色格子为例
    方块的中心位置42就是估价,也就是起始点到目标的距离
    左上角用G表示,也就是该格子到目标点的距离为14
    右上角用H表示,也就是该格子到起始点的距离为28
    红色格子右上角是62,是因为已经确定了当前红色的格子,路径是从当前红色格子到右上角的格子,所以值为62;
    如果选择的不是当前红色的格子,那么就会去改变其他格子的值,也就是说每个格子的值随着你的选择进行改变
    (改变成符合当前格子路径上的值).

    例如:从A到B的一个解析过程

    开始搜索:
    1.把起始格添加到开启列表。
    从A点开始查找
    2.寻找起点周围所有可到达或者可通过的方格,把他们加入开启列表。
    遍历A所能到达的所有方格,把他们加入开启列表中
    3.从开启列表中删除点A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。
    因为A已经走过,所以把A加入关闭列表中,下次在进行遍历时把A除外

    继续搜索:
    4把当前格子从开启列表中删除,然后添加到关闭列表中。
    因为已经到达了当前格子,所以把当前格子放到关闭列表中(已经到达了,没有必要去进行遍历)
    5检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的,把他们添加进开启列表,把选中的方格作为新的方格的父节点。
    当前中的格子周围有两个已经添加到开启列表中,上面三个为不可通过,也就是障碍物,所以只是新添加了左侧的两个格子;

    6如果某个相邻格已经在开启列表里了,检查现在的这条路径G值是否会更低一些。
    如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格,重新计算F和G的值。
    一旦重新选择了一个点那么就需要重新计算一下当前的费用,上面写着只计算G和F的 值,为什么呢!
    原因:每个点到目标点的距离是固定的,所以H点(又上角的点)是不需要改变的,会变化的G值仅仅是因为路经改变的原因跟起始点的距离会发生改变,
    所以只需要计算G的值和F的值,其他的点也会相应的更新;
    <图一>
    因为选择的42,但是出现了3个相同的估价,那么我们该怎么选择呢?
    <图二>
    这里还有另外一个原则:那就是选择一个距离目标点最近的一个值,也就是H值最低的一个.
    也就是左侧的48这个方块 ,那么就把48这个点从开启列表中删除,送进关闭列表中.
    因为选择了48,新增了左侧两个点,那么跟新一下在开启列表中的当前48下面的两个点(在这里下面那两个点是没有变化的,因为42下面的也是48,所以路径的值是没有改变的);
    那么继续走
    当我们继续走的时候,发现遍历48所能达到的值,发现这条路径不是最优的.
    为什么不是最优的呢:(因为在它的开启列表中还有一个48)
    那么在他的开启列表中还有一个48的值,那么就把当前的这个48从开起列表中删除,送进关闭列表中。
    我们就回到上一步,选择42下方的48;
    同理,这个48也不是最优的,因为他的开启列表中还有一个48,那么我们继续选择42,右侧的这个48;
    结束

    起始格下方格子的父节点已 经和前面不同的。 之前它的G值是,并且指向 右上方的格子。现在它的G 值是,指向它上方的格子。 这在寻路过程中的某处发生, 当应用新路径时,G值经过 检查变得低了-于是父节点 被重新指定,G和F值被重
    新计算。

    根据上述的原理得到如上图所示的路径,也就是最佳路径;

    总结

    1把起始格添加到开启列表。
    2重复如下的工作:
    寻找开启列表中F值最低的格子。我们称它为当前格。
    把它切换到关闭列表。
    /1/对相邻的格中的每一个–> 如果它不可通过或者已经在关闭列表中,略过它。反之如下。如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
    /2/如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的 G和F值。
    停止,当你 把目标格添加进了关闭列表,这时候路径被找到–>没有找到目标格,开启列表已经空了。这时候,路径不存在。
    3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。

    算法:步骤架构
    <1>开启集合
    <2>关闭集合
    <3>添加起始点到开始集合中
    <4>循环如下步骤: 当前点=开启集合中最小F_Cost的点 将当前点移出开启集合中 将当前点添加到关闭集合中
    <5>如果当前点是目标点,结束查询
    <6>遍历当前点的每个相邻点 如果相邻点不能访问或者相邻点在关闭集合中,跳过此相邻点 如果新路径到相邻点的距离更短,或者相邻点不在开启集合中 重新设置F_Cost 重新设置其父节点为当前点
    <7>如果相邻点不在开启集合中
    <8>添加相邻点到开启集合

    展开全文
  • Astar算法

    千次阅读 2019-04-11 09:05:49
    转自:https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/ 简介:搜索区域 让我们假设我们有人想要从A点到达B点。让我们假设一条墙将这两点分开。...

    转自:https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

    简介:搜索区域

    让我们假设我们有人想要从A点到达B点。让我们假设一条墙将这两点分开。这在下面说明,绿色是起点A,红色是终点B,蓝色填充的正方形是两者之间的墙。

                                                  

    您应该注意的第一件事是我们将搜索区域划分为方形网格。正如我们在这里所做的那样,简化搜索区域是寻路的第一步。这种特殊方法将我们的搜索区域缩小为简单的二维数组。数组中的每个项目代表网格上的一个正方形,其状态记录为可通过或不可通过。通过确定从A到B应该采取哪些方格来找到路径。一旦找到路径,我们的人就从一个方格的中心移动到下一个方格的中心,直到达到目标。

    这些中心点称为“节点”。当您在其他地方阅读有关寻路的信息时,您会经常看到有人讨论节点。为什么不把它们称为方块?因为可以将寻路区域划分为方形以外的其他区域。它们可以是矩形,六边形,三角形或任何形状。节点可以放置在形状内的任何位置 - 中心或沿边缘,或其他任何地方。然而,我们正在使用这个系统,因为它是最简单的。

    开始搜索(Starting the Search)

    一旦我们把搜寻区域简化为一组可以量化的节点后,就像上面做的一样,我们下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。

    我们这样开始我们的寻路旅途:

    1.       从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。

    2.       查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,河流所占领的方格及其他非法地形占领的方格 ) ,把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。稍后解释。

    3.       把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。

    如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。

                                                                                 

    下一步,我们需要从 open list 中选一个与起点 A 相邻的方格,按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢?具有最小 F 值的那个。

    路径排序(Path Sorting)

    计算出组成路径的方格的关键是下面这个等式:

    F = G + H

    这里,

    G = 从起点 A 移动到指定方格的移动代价,沿着到达该方格而生成的路径。

    H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法,有点让人混淆。为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。本教程将教你一种计算 H 的方法,你也可以在网上找到其他方法。

    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

    如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现,如果不使用这些技巧,寻路算法将很慢。

     

    既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。

     

    有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。

     

    把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。

                                              

    好,现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。

     

    H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。

     

    每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。

    继续搜索(Continuing the Search)

    为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:

    4.       把它从 open list 里取出,放到 close list 中。

    5.       检查所有与它相邻的方格,忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open lsit 中,则把它们加入到 open list 中。

    把我们选定的方格设置为这些新加入的方格的父亲。

    6.       如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。

    相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。

                                              

    这一次,当我们检查相邻的方块时,我们发现右边的那个是一个墙方块,所以我们忽略它。对于正好在上面的那个也是如此。我们也忽略了墙下方的广场。为什么?因为你不能直接从当前的广场到达那个广场,而不会越过附近墙壁的角落。你真的需要先下去,然后转移到那个广场,在这个过程中转移。(注意:关于切角的这条规则是可选的。它的使用取决于节点的放置方式。)

    剩下五个正方形。当前方块下方的其他两个方块尚未在开放列表中,因此我们添加它们,当前方块成为其父级。在其他三个正方形中,两个已经在闭合列表中(起始正方形,正好在当前正方形上方,在图中以蓝色突出显示),因此我们忽略它们。然后检查当前正方形左边的最后一个方格,看看如果你通过当前的方格到达那里,G得分是否更低。没有骰子。所以我们已经完成并准备好检查我们的开放列表中的下一个方块。

    我们重复这个过程,直到我们将目标方块添加到关闭列表中,此时它看起来如下图所示。

                                         

    请注意,起始方块下方的正方形两个方格的父方块已从上一个插图中更改。在G得分为28之前,指向它上方和右侧的方格。现在它得分为20,并指向它上方的正方形。这发生在我们的搜索过程中的某个地方,其中G分数被检查,并且使用新路径结果显示较低 - 因此父母被切换并且重新计算了G和F分数。虽然这个变化在这个例子中似乎并不重要,但是在很多可能的情况下,这种不断的检查会在确定目标的最佳路径方面产生重大影响。

    那么我们如何确定路径呢?简单,只需从红色目标方块开始,然后按照箭头向后移动,从一个方格移动到其父级。这将最终带你回到起跑广场,这就是你的道路。它应该如下图所示。从起始广场A移动到目的地广场B只是从每个广场(节点)的中心移动到路径上的下一个广场的中心,直到到达目标。

                                          

    A*算法总结(Summary of the A* Method)

    Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

    1.         把起点加入 open list 。

    2.         重复如下过程:

    a.         遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。

    b.         把这个节点移到 close list 。

    c.         对当前方格的 8 个相邻方格的每一个方格?

    ◆     如果它是不可抵达的或者它在 close list 中,忽略它。否则,做如下操作。

    ◆     如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

    ◆     如果它已经在 open list 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。

    d.         停止,当你

    ◆     把终点加入到了 open list 中,此时路径已经找到了,或者

    ◆     查找终点失败,并且 open list 是空的,此时没有路径。

    3.         保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

     

    展开全文
  • AStar 算法 ---在Unity当中实现

    千次阅读 2018-06-11 17:46:19
    AStar算法,是一种在静态路网中求最短路径的一种算法,是一种启发式的算法.其中,算法当中起点与终点的距离,与算法当中的预估距离越接近,则搜索速度越快. 其实,在AStar算法当中,他的搜索路径的特点与迪杰斯特拉那种...
  • astar_tutorials

    2009-03-28 19:25:48
    了解和研究ASTAR 算法的必备文档 注意:本文档为英文原版文档
  • AstarPathfindingProject 4.1.12 最新版本 ! ! !
  • Astar A*算法 最短路径算法

    万次阅读 2016-10-30 16:29:06
    A*算法 astar算法
  • A -Star算法 A*(A-Star)算法是一种求解最短路径最有效的直接搜索方法,也是许多其他问题的常用启发式算法。 一、简介 二、寻路方式 三、运行机制 ...四、常用估价算法 ...A*(A-Star)算法是一种求解最短路径最有效的...
  • AStar

    2017-10-11 16:00:00
    1 POJ 1475 Pushing Boxes 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> ...q...
  • Astar

    2006-07-25 15:17:00
    题目描述:八方块移动游戏要求从一个含8个数字(用1-8表示)的方块以及一个空格方块(用0表示)的3x3矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。...
  • AStar算法

    千次阅读 2016-08-29 11:48:49
    原文地址:... 本文版权归原作者、译者所有,我只是转贴;如果侵害到您的权益,请联系我,我将删除本文。 基本上,这文章可以说是最佳A*算法文档。...这篇文章很适合A*算法的初学者,
  • Astar类包

    2013-01-22 20:15:56
    Astar类包
  • 关于AStar的算法请参见网络. 在些大体介绍一下. AStar算法的核心是估价函数,不同的估价函数可能会表现出不同的行为,因此效率也会有所不同.是一种启发式搜索.有一张open和close表,使用这两张表来确定哪些遍历过,...
  • 本文证明了A Star算法,并且给出了该算法的一个伪代码实现。
  • A星(AStar)算法的实现

    2020-08-15 12:13:47
    关于AStar的原理这里简述一下, 首先有一张地图,然后准备一个open list 和 close list,open list存放所有可能的路径,但是需要注意的是这个列表是动态怎加的,也就是每走一步就把当前可能的路径都加进去,然后...
  • A*(Astar)搜索算法的实现(C语言)

    千次阅读 2012-12-02 21:50:06
    名字创意来源于第一届百度之星比赛决赛中有题目是一道经典的8数码题目,解这道题,冠军ACRush使用了A*算法(Astar)。Astar又包含了“百度之星”的含义。 2.算法的描述 2.1 该算法可以用如下等式表示: f(n) = g(n) +...
  • JAVA-Astar算法实现

    2009-09-18 20:25:40
    JAVA实现Astar寻径算法: 此算法的演示Applet程序请连接:http://www.dotnet.pp.ru/SMQ/AppletAstar.htm 此算法的主要公式:F=G+H * G = 从起点,沿着产生的路径,移动到网格上指定方格的移动耗费。 * H = 从此...
  • 光速AStar算法实现,基于C++ 一、最终效果 可以看到,我创建了500个小动物,也有110的FPS。虽然它们并不是每一帧都在计算寻路,但是平均下来不卡顿也不错了。我是i7 6700 + GT 720,这个效果图虽然不能直观的说明...

空空如也

1 2 3 4 5 ... 20
收藏数 5,572
精华内容 2,228
关键字:

astar