精华内容
参与话题
问答
  • a*自动寻路算法详解

    万次阅读 2016-11-09 20:47:29
    A*算法主要是在父节点更新那个地方很容易误解,但是父节点的更新又是A*算法的核心,因为遍历到目标节点之后就是根据父节点回溯返回找到的路径的。 开始: 一只探路猫   让我们想象一下,有一款游戏,游戏中一只猫...

    这篇博文是在其他博客基础上加工的,主要原因是感觉原博客举得例子不太好,很多细节感觉没有描述。

    A*算法主要是在父节点更新那个地方很容易误解,但是父节点的更新又是A*算法的核心,因为遍历到目标节点之后就是根据父节点回溯返回找到的路径的。

    开始:

    一只探路猫

     

    让我们想象一下,有一款游戏,游戏中一只猫想要找到获取骨头的路线。

    为什么会有一只猫想要骨头?!你可能会这么想。在本游戏中,这是一只狡猾的猫,他想捡起骨头给狗,以防止被咬死!:]

    现在想像一下下图中的猫想找到到达骨头的最短路径:


    不幸的是,猫不能直接从它当前的位置走到骨头的位置,因为有面墙挡住了去路,而且它在游戏中不是一只幽灵猫!

    游戏中的猫同样懒惰,它总是想找到最短路径,这样当他回家看望它的女朋友时不会太累:-)

    但是我们如何编写一个算法计算出猫要选择的那条路径呢?A星算法拯救了我们!

     

    简化搜索区域

     

    寻路的第一步是简化成容易控制的搜索区域。

    怎么处理要根据游戏来决定了。例如,我们可以将搜索区域划分成像素点,但是这样的划分粒度对于我们这款基于方块的游戏来说太高了(没必要)。

    作为代替,我们使用方块(一个正方形)作为寻路算法的单元。其他的形状类型也是可能的(比如三角形或者六边形),但是正方形是最简单并且最适合我们需求的。

    像那样去划分,我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图,我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点,搜索区域就是一个有640000个正方形的数组了(一个方块是32*32像素)!

    现在让我们基于目前的区域,把区域划分成多个方块来代表搜索空间(在这个简单的例子中,7*6个方块 = 42个方块):

     

    OpenClosed列表

     

    既然我们创建了一个简单的搜索区域,我们来讨论下A星算法的工作原理吧。

    除了懒惰之外,我们的猫没有好的记忆力,所以它需要两个列表:

    1. 一个记录下所有被考虑来寻找最短路径的方块(称为open 列表)
    2. 一个记录下不会再被考虑的方块(成为closed列表)

    猫首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行小方块添加到open列表中。

    下图是猫在某一位置时的情景(绿色代表open列表):


    现在猫需要判断在这些选项中,哪项才是最短路径,但是它要如何去选择呢?

    A星寻路算法中,通过给每一个方块一个和值,该值被称为路径增量。让我们看下它的工作原理!

    路径增量

     

    我们将会给每个方块一个G+H和值:

    ·        G是从开始点A到当前方块的移动量。所以从开始点A到相邻小方块的移动量为1,该值会随着离开始点越来越远而增大。

    ·        H是从当前方块到目标点(我们把它称为点B,代表骨头!)的移动量估算值。这个常被称为探视,因为我们不确定移动量是多少仅仅是一个估算值。

    你也许会对移动量感兴趣。在游戏中,这个概念很简单仅仅是方块的数量。

    然而,在游戏中你可以对这个值做调整。例如:

    ·        如果你允许对角线移动,你可以针对对角线移动把移动量调得大一点。

    ·        如果你有不同的地形,你可以将相应的移动量调整得大一点例如针对一块沼泽,水,或者猫女海报:-)

    这就是大概的意思现在让我们详细分析下如何计算出GH值。

    关于G

     

    G是从开始点A到达当前方块的移动量(在本游戏中是指方块的数目)。

    为了计算出G的值,我们需要从它的前继(上一个方块)获取,然后加1。所以,每个方块的G值代表了从点A到该方块所形成路径的总移动量。

    例如,下图展示了两条到达不同骨头的路径,每个方块都标有它的G值:

     

    关于H

    H值是从当前方块到终点的移动量估算值(在本游戏中是指方块的数目)。

    移动量估算值离真实值越接近,最终的路径会更加精确。如果估算值停止作用,很可能生成出来的路径不会是最短的(但是它可能是接近的)。这个题目相对复杂,所以我们不会再本教程中讲解,但是我在教程的末尾提供了一个网络链接,对它做了很好的解释。

    为了让它更简单,我们将使用曼哈顿距离方法(也叫曼哈顿长或者城市街区距离),它只是计算出距离点B,剩下的水平和垂直的方块数量,略去了障碍物或者不同陆地类型的数量。

    例如,下图展示了使用城市街区距离,从不同的开始点到终点,去估算H的值(黑色字):


    A星算法

     

    既然你知道如何计算每个方块的和值(我们将它称为F,等于G+H),  我们来看下A星算法的原理。

    猫会重复以下步骤来找到最短路径:

    1. 将方块添加到open列表中,该列表有最小的和值。且将这个方块称为S吧。
    2. 将S从open列表移除,然后添加S到closed列表中。
    3. 对于与S相邻的每一块可通行的方块T:

    ·        如果Tclosed列表中:不管它。

    ·        如果T不在open列表中:添加它然后计算出它的和值。

    ·        如果T已经在open列表中:当我们使用当前生成的路径到达那里时,检查F和值是否更小。如果是,更新它的和值和它的前继。

    如果你对它的工作原理还有点疑惑,不用担心我们会用例子一步步介绍它的原理!:]


    如下图方格中左下角:G,方格右下角:H,左上角:F

    F=G+H (其实这个公式不用理解也行,主要是为了方便计算的)



    上图是第一步:计算起点周围邻域的代价,跨越一条边是10,对角是14,

    把周围节点的G和H计算出来之后,计算F(就是G+H)。然后再赋予父节点,其实可以想象初始的时候所有节点的F都是无穷大的,为什么要这么理解呢,主要是节点的父指针就是根据F来变化的。

    因为一开始都是无穷大,所以邻域节点的F计算出来之后都要比无穷大小,那么,这些节点的父指针就指向当前的起始节点。如上图所示。因为此时这几个邻域节点都没有在open列表中,于是就把这8个点加到open队列中,并且把当前节点也就是起始节点放到close中(也就是下次不再考虑了)。


    第二步:从open队列中选择F最小的那个节点,此时可能有F相同的(这种情况就随便选个,不影响最短路径长度),我们选择40的那个,于是,把F=40的这个节点作为当前节点,如下图所示:(此时我们把40抹去了,因为之后会把这个节点放到close队列中,close队列中的点都是不考虑的,也是为了描述方便,我们要的只是指针方向)


    关键:

    第三步:把40的那个节点周围8邻域的节点计算完F后,放到open队列中,注意,此时障碍物的节点和已经放入close队列的节点不放,那么此时没有新节点加入进来,由于把涂抹了的那个节点当成当前节点,所以需要重新计算它的8邻域节点的G值和F值,(也就是它的上方那个,坐上方节点,下方节点,左下方节点,一个4个),此时G值的计算是这样的:比如计算上方那个(54 14 40),由于从原点到当前节点的G为10,从当前节点到上方节点的G值为10,所以10+10=20(也就是所到上方节点需要先从原点到这个点,然后在从这个点到上面那个点),但是新计算的G=20<14(节点原来的G值),所以上方节点的指针方向不变,(如果计算出来小于原来的值,那么就把上方节点的指针指向当前这个节点了)!!

    同样计算剩下的三个节点的G值,发现都大于原来的G值,所以节点指针方向没有做任何改变。

    于是把当前节点放到close对列中,再从open队列中找F值最小的节点。(此时队列中有7个节点)

    于是把54那个节点(起始节点的右下方那个)当成当前节点,计算周围8邻域的G值和F值。但是障碍物下方的那个点不能加入计算,因为从当前节点到障碍物下方那个节点必须穿透墙角了!

    同样赋予节点父指针以及更新8邻域的G值和F值。



    当把起始节点下方的那个节点当成当前节点的时候,注意它下方那个节点的父指针变化了,因为它原来的G值为28,但是通过当前节点的时候G能变小到20,所以对应的F也小了,那么,它的父指针就指向当前节点,表示这样走更近。


    所以如此循环下去:不断从open队列中找最小的点作为当前节点并加入周围节点,不断更新周围8邻域的G和F,看看能不能比原来G值更小,如果小就更新,否则不更新,当前节点算完就放入close队列,然后再从open队列中找最小的点。。。。


    最后直到把终点加入open队列中,计算出父指针就完事了。

    所以最后的路径就是,从终点开始沿着父指针不断回缩,最后回到起始点,这样最短路径就找到了。




    展开全文
  • 一种高效的寻路算法 - B*寻路算法

    万次阅读 2017-04-13 10:11:48
    在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。  通过引入该算法,一定程度上...

    http://qinysong.iteye.com/blog/678941


    在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。 

    通过引入该算法,一定程度上解决了游戏服务器端无法进行常规寻路的效率问题,除非服务器端有独立的AI处理线程,否则在服务器端无法允许可能消耗大量时间的寻路搜索,即使是业界普遍公认的最佳的A*,所以普遍的折中做法是服务器端只做近距离的寻路,或通过导航站点缩短A*的范围。 

    算法原理 
    本算法启发于自然界中真实动物的寻路过程,并加以改善以解决各种阻挡问题。 
    前置定义: 
    1、探索节点: 
    为了叙述方便,我们定义在寻路过程中向前探索的节点(地图格子)称为探索节点,起始探索节点即为原点。(探索节点可以对应为A*中的开放节点) 

    2、自由的探索节点: 
    探索节点朝着目标前进,如果前方不是阻挡,探索节点可以继续向前进入下一个地图格子,这种探索节点我们称为自由探索节点; 

    3、绕爬的探索节点: 
    探索节点朝着目标前进,如果前方是阻挡,探索节点将试图绕过阻挡,绕行中的探索节点我们成为绕爬的探索节点; 
    算法过程 
    1、起始,探索节点为自由节点,从原点出发,向目标前进; 
    2、自由节点前进过程中判断前面是否为障碍, 
         a、不是障碍,向目标前进一步,仍为自由节点; 
         b、是障碍,以前方障碍为界,分出左右两个分支,分别试图绕过障碍,这两个分支节点即成为两个绕爬的探索节点; 
    3、绕爬的探索节点绕过障碍后,又成为自由节点,回到2); 
    4、探索节点前进后,判断当前地图格子是否为目标格子,如果是则寻路成功,根据寻路过程构造完整路径; 
    5、寻路过程中,如果探索节点没有了,则寻路结束,表明没有目标格子不可达; 


    演示如下:  
         
        



    B*与A*算法的性能比较 

    寻路次数比较(5秒钟寻路次数) 


      
    B*与A*性能比较实例 
    1、 无障碍情况 
    此种情况,根据以上测试数据,B*算法效率是普通A*的44倍(左为A*,右为B*) 

          
      

    2、线形障碍 
    此种情况,根据以上测试数据,B*算法效率是普通A*的28倍(左为A*,右为B*) 

        

       
    3、环形障碍 
    此种情况,根据以上测试数据,B*算法效率是普通A*的132倍(左为A*,右为B*) 

          


    4、封闭障碍(目标不可达) 
    此种情况,根据以上测试数据,B*算法效率是普通A*的581倍(左为A*,右为B*) 
         

    衍生算法 
    通过以上封闭障碍,可以看出,这个方法在判断地图上的两个点是否可达上,也是非常高效的,在不可达情况下,时间复杂度与封闭障碍的周长相当,而不是整个地图的面积。 

    评论
    74 楼 yiubian 2015-12-21  
    写得不错,学习了。
    73 楼 cctvwspc 2015-09-10  
    要附件啊!
    72 楼 zzz郑家兴 2015-04-30  
    71 楼 h348592532 2015-03-18  
    如果可以斜着走,很明显你这没法可以找到最佳路径,就知道不停的往前冲,说白你这个是可以分支的贪心算法的确还会出各种未知的问题,伦理验证性不强,谁敢用,呵呵



    展开全文
  • http://www.360doc.com/content/16/1201/12/99071_610999046.shtml http://blog.csdn.net/booirror/article/details/50834915 http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html

    A*算法广泛应用于寻路和图的遍历,是对Dijkstra算法的一种扩展。是一种高效的搜索算法。

    1.简易地图

    如图所示简易地图,其中绿色方块的是起点 (用 A 表示), 中间蓝色的是障碍物,红色的方块 (用 B 表示) 是目的地。为了可以用一个二维数组来表示地图, 我们将地图划分成一个个的小方块。

    二维数组在游戏中的应用是很多的,比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已。 而大型游戏的地图, 则是将各种"地貌"铺在这样的小方块上。

    2.寻路步骤

    1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表。

    2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A。

    3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格。

    图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查。 淡蓝色描边的起点 A 表示已经放入 "关闭列表" , 它不需要再执行检查。

    从 "开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算。

    F = G + H

    G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动)。

    H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动)。

    我们假设横向移动一个格子的耗费为10, 为了便于计算, 沿斜方向移动一个格子耗费是14。 为了更直观的展示如何运算 FGH, 图中方块的左上角数字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的结果一样?

    从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处理:

    4. 把它从 "开启列表" 中删除, 并放到 "关闭列表" 中。

    5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格。 如果这些方格还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 "父方格" 为 C。

    6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做。

    如图, 我们选中了 C 因为它的 F 值最小, 我们把它从 "开启列表" 中删除, 并把它加入 "关闭列表"。 它右边上下三个都是墙, 所以不考虑它们。 它左边是起始方块, 已经加入到 "关闭列表" 了, 也不考虑. 所以它周围的候选方块就只剩下 4 个。 让我们来看看 C 下面的那个格子, 它目前的 G 是14, 如果通过 C 到达它的话, G将会是 10 + 10, 这比 14 要大, 因此我们什么也不做。

    然后我们继续从 "开启列表" 中找出 F 值最小的, 但我们发现 C 上面的和下面的同时为 54, 这时怎么办呢? 这时随便取哪一个都行, 比如我们选择了 C 下面的那个方块 D。

    D 右边已经右上方的都是墙, 所以不考虑, 但为什么右下角的没有被加进 "开启列表" 呢? 因为如果 C 下面的那块也不可以走, 想要到达 C 右下角的方块就需要从 "方块的角" 走了, 在程序中设置是否允许这样走。(图中的示例不允许这样走)

    就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表"。 再继续找出它周围可以到达的方块, 如此循环下去...

    那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经被找到。

    3.如何找回路径

    如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径。

    4.将整个过程抽象

    A*算法的具体步骤:

    1. 把起点加入openlist

    2. 遍历openlist,找到F值最小的节点,把它作为当前处理的节点,并把该节点加入closelist中

    3. 对该节点的8个相邻格子进行判断,如果格子是不可抵达的或者在closelist中,则忽略它,否则如下操作:

    a. 如果相邻格子不在openlist中,把它加入,并将parent设置为该节点和计算f,g,h值

    b.如果相邻格子已在openlist中,并且新的G值比旧的G值小,则把相邻格子的parent设置为该节点,并且重新计算f值。

    4. 重复2,3步,直到终点加入了openlist中,表示找到路径;或者openlist空了,表示没有路径。

    如果开启列表已经空了,说明路径不存在。

    最后从目标格开始,沿着每一格的父节点移动直到回到起始格,这就是路径。


    5.程序实现

    类结构定义:

    #include <vector>
    #include <list>
    using namespace std;
    const int kCost1 = 10; //直移一格消耗
    const int kCost2 = 14; //斜移一格消耗
    
    struct Point
    {
    	int x, y; //点坐标,这里为了方便按照C++的数组来计算,x代表横排,y代表竖列
    	int F, G, H; //F=G+H
    	Point *parent; //parent的坐标,这里没有用指针,从而简化代码
    	Point(int _x, int _y) :x(_x), y(_y), F(0), G(0), H(0), parent(NULL) {}  //变量初始化
    };
    
    class Astar
    {
    public:
    	Astar(vector<vector<int>> &_maze) :maze(_maze){}
    	list<Point *> GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);
    private:
    	Point *findPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner);
    	vector<Point *> getSurroundPoints(const Point *point, bool isIgnoreCorner) const;
    	bool isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const; //判断某点是否可以用于下一步判断(是否可达)
    	Point *isInList(const list<Point *> &list, const Point *point) const; //判断开启/关闭列表中是否包含某点
    	Point *getLeastFpoint(); //从开启列表中返回F值最小的节点
    	//计算FGH值
    	int calG(Point *temp_start, Point *point);
    	int calH(Point *point, Point *end);
    	int calF(Point *point);
    private:
    	vector<vector<int>> maze;
    	list<Point *> openList;  //开启列表
    	list<Point *> closeList; //关闭列表
    };

    类成员函数实现:

    #include <math.h>
    #include "Astar.h"
    
    int Astar::calG(Point *temp_start, Point *point)
    {
    	int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? kCost1 : kCost2;
    	int parentG = point->parent == NULL ? 0 : point->parent->G; //如果是初始节点,则其父节点是空
    	return parentG + extraG;
    }
    
    int Astar::calH(Point *point, Point *end)
    {
    	//用简单的欧几里得距离计算H,这个H的计算是关键,还有很多算法
    	return sqrt((double)(end->x - point->x)*(double)(end->x - point->x) + (double)(end->y - point->y)*(double)(end->y - point->y))*kCost1;
    }
    
    int Astar::calF(Point *point)
    {
    	return point->G + point->H;
    }
    
    Point *Astar::getLeastFpoint()
    {
    	if (!openList.empty())
    	{
    		auto resPoint = openList.front();
    		for (auto &point : openList)
    			if (point->F<resPoint->F)
    				resPoint = point;
    		return resPoint;
    	}
    	return NULL;
    }
    
    Point *Astar::findPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner)
    {
    	openList.push_back(new Point(startPoint.x, startPoint.y)); //置入起点,拷贝开辟一个节点,内外隔离
    	while (!openList.empty())
    	{
    		auto curPoint = getLeastFpoint(); //找到F值最小的点
    		openList.remove(curPoint); //从开启列表中删除
    		closeList.push_back(curPoint); //放到关闭列表
    		//1,找到当前周围八个格中可以通过的格子
    		auto surroundPoints = getSurroundPoints(curPoint, isIgnoreCorner);
    		for (auto &target : surroundPoints)
    		{
    			//2,对某一个格子,如果它不在开启列表中,加入到开启列表,设置当前格为其父节点,计算F G H
    			if (!isInList(openList, target))
    			{
    				target->parent = curPoint;
    
    				target->G = calG(curPoint, target);
    				target->H = calH(target, &endPoint);
    				target->F = calF(target);
    
    				openList.push_back(target);
    			}
    			//3,对某一个格子,它在开启列表中,计算G值, 如果比原来的大, 就什么都不做, 否则设置它的父节点为当前点,并更新G和F
    			else
    			{
    				int tempG = calG(curPoint, target);
    				if (tempG<target->G)
    				{
    					target->parent = curPoint;
    
    					target->G = tempG;
    					target->F = calF(target);
    				}
    			}
    			Point *resPoint = isInList(openList, &endPoint);
    			if (resPoint)
    				return resPoint; //返回列表里的节点指针,不要用原来传入的endpoint指针,因为发生了深拷贝
    		}
    	}
    
    	return NULL;
    }
    
    list<Point *> Astar::GetPath(Point &startPoint, Point &endPoint, bool isIgnoreCorner)
    {
    	Point *result = findPath(startPoint, endPoint, isIgnoreCorner);
    	list<Point *> path;
    	//返回路径,如果没找到路径,返回空链表
    	while (result)
    	{
    		path.push_front(result);
    		result = result->parent;
    	}
    	return path;
    }
    
    Point *Astar::isInList(const list<Point *> &list, const Point *point) const
    {
    	//判断某个节点是否在列表中,这里不能比较指针,因为每次加入列表是新开辟的节点,只能比较坐标
    	for (auto p : list)
    		if (p->x == point->x && p->y == point->y)
    			return p;
    	return NULL;
    }
    
    bool Astar::isCanreach(const Point *point, const Point *target, bool isIgnoreCorner) const
    {
    	if (target->x<0 || target->x>maze.size() - 1
    		|| target->y<0 && target->y>maze[0].size() - 1
    		|| maze[target->x][target->y] == 1
    		|| target->x == point->x&&target->y == point->y
    		|| isInList(closeList, target)) //如果点与当前节点重合、超出地图、是障碍物、或者在关闭列表中,返回false
    		return false;
    	else
    	{
    		if (abs(point->x - target->x) + abs(point->y - target->y) == 1) //非斜角可以
    			return true;
    		else
    		{
    			//斜对角要判断是否绊住
    			if (maze[point->x][target->y] == 0 && maze[target->x][point->y] == 0)
    				return true;
    			else
    				return isIgnoreCorner;
    		}
    	}
    }
    
    vector<Point *> Astar::getSurroundPoints(const Point *point, bool isIgnoreCorner) const
    {
    	vector<Point *> surroundPoints;
    
    	for (int x = point->x - 1; x <= point->x + 1; x++)
    		for (int y = point->y - 1; y <= point->y + 1; y++)
    			if (isCanreach(point, new Point(x, y), isIgnoreCorner))
    				surroundPoints.push_back(new Point(x, y));
    
    	return surroundPoints;
    }


    参考:

    http://www.360doc.com/content/16/1201/12/99071_610999046.shtml

    http://blog.csdn.net/booirror/article/details/50834915

    展开全文
  • 深入理解游戏中寻路算法(转)

    千次阅读 2019-03-23 11:51:41
    这种看似寻常的寻路在程序实现起来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是寻路算法首先要考虑的问题。 在这篇文章中我们会循序渐进来讲解寻路算法是如何演进的,你会看到一种...

    如果你玩过MMOARPG游戏,比如魔兽,你会发现人物行走会很有趣,为了模仿人物行走的真实体验,他们会选择最近路线达到目的地,期间会避开高山或者湖水,绕过箱子或者树林,直到走到你所选定的目的地。

    这种看似寻常的寻路在程序实现起来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是寻路算法首先要考虑的问题。

    在这篇文章中我们会循序渐进来讲解寻路算法是如何演进的,你会看到一种算法从简单到高效所遇到的问题,以及精进的过程,带着问题来阅读,理解更快。

    本篇主要包含以下内容:

    1、图

    2、宽度最优搜索,

    3、Dijkstra 算法,

    4、贪心算法,

    5、A*搜索算法,

    6、B*搜索算法,

    1、游戏中的人物是如何寻路的

    你所看到的人物行走方式:

    开发人员实际所看到的方式:

    或者是这种:

     

    对于一张地图,开发人员需要通过一定的方案将其转换为数据对象,常见的就是以上这种把地图切个成网格,当然了地图的划分方式不一定非要用网格这种方式,采用多边形方式也可以,这取决于你的游戏,一般情况下,同等面积的地图采用更少的顶点,寻路算法会更快。寻路中常用的数据结构就是图,以下我们先来了解一下。

     

     2、图

    在讲寻路算法之前我们先了解一种数据结构—图,数据结构是我们进行算法运算的基础,好的数据结构除了方便我们理解算法,还会提升算法的效率。网格某种意义上也是图的演变,只是图形变了而已,理解了图的概念可以帮助我们更好理解寻路算法。

    图的基本定义:

    图的正式表达式是G=(V,E),V是代表顶点的集合,E和V是一种二元关系,可以理解为边,比如有条边从顶点U到顶点V结束,那么E可以用(u,v)来表示这条边。具体的有向图和无向图,也是边是否有方向来区分。为了方便理解,我们文中所有的数据演示都是基于网格地图来进行讲解,以下是几种关系梳理,以A为顶点,BCDE为子顶点,我们可以把每个格子也看是一个顶点。

     

    3、搜索算法

    对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。对于多图算法来说,广度优先算法和深度优先搜索算法都十分重要,因为它们提供了一套系统地访问图数据结构的方法。我们着重讲解广度优先搜索算法。

    深度优先搜索

    深度优先算法和最小路径关系不大,我们只简单介绍。

    深度优先搜索算法(简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

     

    广度优先搜索

    广度优先搜索算法(简称BFS)又称为宽度优先搜索,是一种图形搜索算法,很适合用来探讨最短路径的第一个模型,我们会顺着这个思路往下讲。

    BFS是一种盲目搜寻法,目的是系统地展开并检查中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止它的步骤如下:

    - 首先将根节点放入队列中。

    - 从队列中取出第一个节点,并检验它是否为目标。

    - 如果找到目标,则结束搜寻并回传结果。

    - 否则将它所有尚未检验过的直接子节点(邻节点)加入队列中。

    - 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

    网格:

    我们看下代码(js):

    var frontier = new Array();
    
    frontier.put(start);
    
    var visited = new Array();
    
    visited[start] = true;
    
    
    
    while(frontier.length>0){
    
        current = frontier.get();
    
         //查找周围顶点
    
        for(next in graph.neighbors(current)){
    
            var notInVisited = visited.indexOf(next)==-1;
    
            //没有访问过
    
            if(notInVisited) {
    
                frontier.put(next);
    
                visited[next] = true;
    
              }
    
           }
    }

    从上可以发现,宽度搜索就是以开始顶点为起点,访问其子节点(在网格中是访问周围节点),然后不断的循环这个过程,直到找到目标,这种算法比较符合常规逻辑,把所有的的顶点全部枚举一遍。不过这种方式也有很明显的缺点。

    缺陷:

    1、效率底下, 时间复杂度是:T(n) = O(n^2)

    2、每个顶点之间没有权值,无法定义优先级,不能找到最优路线。比如遇到水域需要绕过行走,在宽度算法里面无法涉及。

    如何解决这个问题?我们来看Dijkstra 算法。

    4、Dijkstra 算法

    宽度优先搜索算法,解决了起始顶点到目标顶点路径规划问题,但不是最优以及合适的,因为它的边没有权值(比如距离),路径无法进行估算比较最优解。为何权值这么重要,因为真实环境中,2个顶点之间的路线并非一直都是直线,需要绕过障碍物才能达到目的地,比如森林,湖水,高山,都需要绕过而行,并非直接穿过。

    比如我采用宽度优先算法,遇到如下情况,他会直接穿过障碍物(绿色部分 ),明显这个不是我们想要的结果:

    解决痛点:

    寻找图中一个顶点到另一个顶点的最短以及最小带权路径是非常重要的提炼过程。为每个顶点之间的边增加一个权值,用来跟踪所选路径的消耗成本,如果位置的新路径比先前的最佳路径更好,我们将添加它,规划到新的路线中。

    Dijkstra 算法基于宽度优先算法进行改进,把当前看起来最短的边加入最短路径树中 ,利用贪心算法计算并最终能够产生最优结果的算法。具体步骤如下:

    1、每个顶点都包含一个预估值cost(起点到当前顶点的距离),每条边都有权值v ,初始时,只有起始顶点的预估值cost为0,其他顶点的预估值d都为无穷大 ∞。

    2、查找cost值最小的顶点A,放入path队列

    3、循环A的直接子顶点,获取子顶点当前cost值命名为current_cost,并计算新路径new_cost,new_cost=父节点A的cost+v(父节点到当前节点的边权值),如果new_cost<current_cost,当前顶点的cost=new_cost

    4、重复2,3直至没有顶点可以访问.

    我们看下图例:

     

    我们看下代码(js):

    var frontier = new PriorityQueue();
    
    frontier.put(start);
    
    path = new Array();
    
    //每个顶点路径消耗
    
    cost_so_far = new Array();
    
    
    
    path[start] = 0;
    
    cost_so_far[start] = 0
    
    
    
    while(frontier.length>0){
    
       current = frontier.get();
    
    
       if current == goal:
    
          break
    
           //查找周围节点
    
        for(next in graph.neighbors(current)){
    
            var notInVisited = visited.indexOf(next)==-1;
    
            var new_cost = cost_so_far[current] + graph.cost(current, next);
    
               //没有访问过或者路径更近
    
            if(notInVisited ||  new_cost < cost_so_far[next]) {
    
                cost_so_far[next] = new_cost;
    
                priority = new_cost;
    
                frontier.put(next, priority);
    
                path[next] = current;
    
              }
    
           }
    
    }

    我们看到虽然Dijkstra 算法 虽然相对于宽度优先搜索更加智能,基于cost_so_far ,可以规避路线比较长或者无法行走的区域,但依然会存在盲目搜索的倾向,我们在地图中常见的情况是查找目标和起始点的路径,具有一定的方向性,而Dijkstra 算法从上述的图中可以看到,也是基于起点向子节点全方位扩散。

    缺点:

    1、运行时间复杂度是:T(n) = O(V^2),其中V为顶点个数。效率上并不高

    2、目标查找不具有方向性

    如何解决让搜索不是全盘盲目瞎找?我们来看Greedy Best First Search算法(贪婪最佳优先搜索)。

    5、贪婪最佳优先搜索

    在Dijkstra算法中,我已经发现了其最终要的缺陷,搜索存在盲目性。在这里,我们只针对这个痛点,采用贪婪最佳优先搜索来解决。如何解决?我们只需稍微改变下观念即可,在Dijkstra算法中,优先队列采用的是,每个顶点到起始顶点的预估值来进行排序。在贪婪最佳优先搜索中 ,

    解决痛点:

    我们采用每个顶点到目标顶点的距离进行排序。一个采用离起始顶点的距离来排序,一个采用离目标顶点距离排序(离目标的远近排序)

    哪个更快?我们看下图(左边宽度优先,右边贪婪优先):

    从上图中我们可以明显看到右边的算法(贪婪最佳优先搜索 )寻找速度要快于左侧,虽然它的路径不是最优和最短的,但障碍物最少的时候,他的速度却足够的快。这就是贪心算法的优势,基于目标去搜索,而不是完全搜索。

    我们看下算法(js):

    frontier = new PriorityQueue();
    
    frontier.put(start, 0)
    
    came_from = new Array();
    
    came_from[start] = 0;
    
    
    
    while(frontier.length>0){
    
        current = frontier.get()
    
    
    
       if current == goal:
    
          break
    
    
    
           for(next in graph.neighbors(current)){
    
               var notInVisited = visited.indexOf(next)==-1;
    
               //没有访问过
    
            if(notInVisited ) {
    
                //离目标的距离 ,距离越近优先级越高
    
                 priority = heuristic(goal, next);
    
                 frontier.put(next, priority);
    
                 came_from[next] = current;
    
              }
    
           }
    
    }
    
    
    
    function heuristic(a, b){
    
        //离目标的距离
    
       return abs(a.x - b.x) + abs(a.y - b.y)
    
    }

    缺点:

    1.路径不是最短路径,只能是较优

    如何在搜索尽量少的顶点同时保证最短路径?我们来看A*算法。

     6、A*算法

    从上面算法的演进,我们逐渐找到了最短路径和搜索顶点最少数量的两种方案,Dijkstra 算法和 贪婪最佳优先搜索。那么我们有没有可能汲取两种算法的优势,令寻路搜索算法即便快速又高效?

    答案是可以的,A*算法正是这么做了,它吸取了Dijkstra 算法中的cost_so_far,为每个边长设置权值,不停的计算每个顶点到起始顶点的距离,以获得最短路线,同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势,并持续计算每个顶点到目标顶点的距离,以引导搜索队列不断想目标逼近,从而搜索更少的顶点,保持寻路的高效。

    解决痛点:

    A*算法的优先队列排序方式基于F值:

    F=cost(顶点到起始顶点的距离 )+heuristic(顶点到目标顶点的距离 )

    我们看下算法(js):

    var frontier = new PriorityQueue();
    
    frontier.put(start);
    
    path = new Array();
    
    cost_so_far = new Array();
    
    path[start] = 0;
    
    cost_so_far[start] = 0
    
    while(frontier.length>0){
    
        current = frontier.get()
    
       if current == goal:
    
          break
    
           for(next in graph.neighbors(current)){
    
               var notInVisited = visited.indexOf(next)==-1;
    
               var new_cost = cost_so_far[current] + graph.cost(current, next);
    
               //没有访问过而且路径更近
    
            if(notInVisited ||  new_cost < cost_so_far[next]) {
    
                  cost_so_far[next] = new_cost
    
                  //队列优先级= new_cost(顶点到起始顶点的距离 )+heuristic(顶点到目标顶点的距离 )
    
                priority = new_cost + heuristic(goal, next)
    
                frontier.put(next, priority)
    
                path[next] = current
    
              }
    
           }
    
    }
    
    function heuristic(a, b){
    
        //离目标的距离
    
       return abs(a.x - b.x) + abs(a.y - b.y)
    
    }

    以下分别是Dijkstra算法,贪心算法,以及A*算法的寻路雷达图,其中格子有数字标识已经被搜索了,可以对比下三种效率:

    7、B*算法

    B*算法是一种比A*算法更高效的算法, 适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。B*算法不想介绍了,自己去google下吧,

    通过以上算法不断的演进,我们可以看出每一种算法的局限,以及延伸出的新算法中出现的解决方式,希望方便你的理解。

     原文:http://mdsa.51cto.com/art/201707/546036.htm

    展开全文
  • 之前有网友在我这里留言,问我怎样用自己的方法生成NavMesh。我也答应了有空的时候介绍一下,所以写...1、NavMesh是一种寻路的算法,我使用的是凸多边形寻路算法,你可以理解成和A星寻路差不多的算法,并不是只有U...
  • A*寻路算法python版(第二版)

    万次阅读 2018-03-26 00:04:47
    这一周的工作主要是将上一周改的python版代码调试正常。由于对python语言特定语法结构理解的还是不深,所以的遇到了很多坑,万幸最后还是一一填上了,随着不断的调试对于python的有了进一步的认识。...
  • 一、A* 寻路算法 原文地址:&nbsp;http://www.gamedev.net/reference/articles/article2003.asp 概述 虽然掌握了&nbsp;A*&nbsp;算法的人认为它容易,但是对于初学者来说,&nbsp;A*&nbsp;算法...
  • 引言:小生今日分享的是寻路系统中常用的A*寻路算法,在此特别感谢Siki学院的老师们。如果大神发现错误,请评论告知!再次感谢!开发版本:unity 2017.1.1f1适合人群:Unity有一定基础的童鞋开启学习之旅吧!寻路:...
  • A*寻路算法

    千次阅读 2019-04-25 16:38:47
    A*寻路算法是一种用于静态位置高效搜索算法。他是在平面中两点之间去寻找一条可以到达的最短路径算法。 二维平面之中两个点,寻找可以抵达的最短路径。首先明确三个概念,H值,目前点到终点的曼哈顿距离(曼哈顿...
  • 1.了解游戏中常见的驯鹿方式 2.寻路方案选择 3.NavMesh 寻路 4.任务目标追踪 5.常见的寻路方式-建模方式 寻路建模 Grid WayPoint NavMesh
  • 图的寻路算法

    千次阅读 2018-09-11 17:07:31
     图的寻路算法 前言 寻路算法的思路 核心代码详解 测试用例 完整代码获取 博客文章版权声明  图的寻路算法 前言 前面我们探讨了有关于图的“深度优先遍历”算法,知道了如何利用dfs算法查找图中联通分量...
  • 深入理解游戏中寻路算法

    万次阅读 2017-07-28 20:49:08
    摘要: 看似寻常的路径行走,在程序看来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是我们首要考虑的问题。 如果你玩过MMOARPG游戏,比如魔兽,你会发现人物行走会很有趣,为了...
  • 写了几天,搞定了贪吃蛇自动寻路……目前在20*20的格子上面可以稳定跑到100+分,200+的话……看运气吧o(╯□╰)o,总之算法还有很多可以修改的地方,而且UI部分还有部分没写的…… 总结下:这次写的话主要算法用的...
  • b* 寻路算法

    热门讨论 2012-11-20 10:58:36
    b 星 b start b* 寻路 算法
  • java寻路算法

    2014-12-09 16:07:40
    java游戏AI寻路算法(非常实用,附带源码与可视操作界面),类似于A*但又不同于A*!很实用!供参考!
  • 在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。 通过引入该算法,一定程度上解决了...
  • 寻路算法:找到NPC最好的行走路径

    千次阅读 2016-11-29 14:01:59
    理想的寻路算法需要查找所有可能的情况,然后比较出最好的路径。 本文将从搜索空间,可接受的启发式算法、贪婪最佳优先算法进行探讨。搜索空间的表示最简单的寻路算法设计就是将图作为数据结构。一个图包...
  • A*自动寻路算法demo

    2018-06-16 22:31:00
    A*自动寻路算法,一共6个java类,主类是BasePanel.java,可以直接运行这个类,就会生成swing面板,随机生成起点、终点、障碍物,然后选择最佳路线。
  • 游戏寻路算法的简单实现

    千次阅读 2013-06-19 14:53:58
    提到寻路算法,大家都会想到A*算法。 在度娘找了不少代码,看了不少教程之后,尤其是这个文章中提到的总结:http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html A*算法总结(Summary of the A* ...
  • 在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。  通过引入该算法,一定程度上...

空空如也

1 2 3 4 5 ... 20
收藏数 8,161
精华内容 3,264
关键字:

寻路算法