分分钟学会【A星寻路】~~~~~~~【无上天君与梦瑶的传说】

TKCB

TKCB网站
网址：www.tkcb.cc

【分分钟教程】——系列教程，共3篇

分分钟学会【A星寻路】~~~~~~~【无上天君与梦瑶的传说】

分分钟学会【AS3人脸识别】~~~~~~~【猪八戒的嫦娥梦】

分分钟学会【Flash垃圾回收机制】~~~~~~~【死神的烦恼】

教程开始了！

很多高手、大神都曾经讲过A星寻路，但小弟不才，也想献上一篇A星寻路的文章，以供观赏。本人系AS3菜鸟一枚，文章有不足之处，敬请包涵理解。

我主要会讲一些理论知识，至于具体具体的代码，可以参考、查看我上传的Flash源文件以及附带的一篇A星教程。

一提到A星寻路，或许有些初学者总觉得很高大上。但其实A星寻路的核心只是：循环（for大家都会） + 判断（if谁不会给我站出来） + 计算距离（这个也是so easy）。

无上天君与梦瑶的传说

序章，仙界天山住着一位威震仙界的大神（无上天君），我们假设我们就是这位无上天君，我们有神识亿万分身术和卫星定位系统（谁说神仙不会高科技），这可是我们寻路的资本！

第一章，传说美丽的天外仙岛有一个仙女，她叫做梦瑶，她是所有程序神猿的终极梦想，但谁也不知道这座仙岛在什么地方，只知道在仙界之外。无上天君也一直喜欢着这位未知的仙女，以致于单身数万年。

第二章，我们（无上天君）偶然得到了一张太古的天外地图，这里面记载着去天外仙道的路，但由于太古文字过于古老，我们也无法知道路在何方，但至少我们有了地图。

第三章，我们是谁？我们是拥有卫星定位系统的无上天君，这样通过地图加上系统，我们锁定了仙岛的位置和自己的位置。我们通过系统的雷达辅助，就可以实时计算我们所处位置到仙道的大致距离。

第四章，一张地图、神识亿万分身术和卫星定位系统我们拥有这些，但路依然是未知的，那么重点来了，我们需要寻路！！！

第五章，我们发明了一种算法叫做 F 算法（F = G + H），这种算法可以帮助我们确定自己和仙岛的距离，F 是我们从天山到仙岛的估算距离，G 是我们从天山到现在所处位置的实际距离，H 是我们从现在位置到仙岛的估算距离。

第六章，天外一直是禁地，各种远古萌兽、死亡绝地等等不知吞噬了多少仙界大神的神格。但我们拥有神识亿万分身术，可以用分身不断的试路，但每一个分身的死亡都会减少我们的寿命（虽然我们拥有数以万年的生命，但终究不是不死之身）。

第七章，我们按照地图将整个天界（包括天外）划分成为很多方格区域，这样方便我们寻路探索。

第八章，我们从天山派出了四（八）个分身向四面（八方）出发，但由于神力有限只能一次控制一个分身去寻路探索。

1. 如果当前分身无法到达某个地方，就会返回本体，之后我们控制其他最靠近仙岛的分身（通过F 算法）；

2. 如果分身遇到了远古萌兽或者其他危险，就会死亡，我们就知道了这个地方再也不用去了，之后我们控制其他最靠近仙岛的分身（通过F 算法）；

3. 每当分身到达一个新的方格区域，则会再次分身为四（八）个，再次向周围的区域探索，之后我们控制其他最靠近仙岛的分身（通过F 算法）；

4. 如果当前操控的分身遇到了其他分身，我们就用 F 算法 计算一下两个分身中那个分身到达这个方格区域更快一些（距离更短）；

   4.1 如果当前操作的分身比遇到的其他分身到这个方格区域快，则将其他分身返回本体，用当前操作的分身代替他继续寻路，之后我们控制其他最靠近仙岛的分身（通过F 算法）；

   4.2 如果是相反的，则将当前操作的分身返回本体，之后我们控制其他最靠近仙岛的分身（通过F 算法）；

第九章，无上天君从仙界消失了，谁也不知道他究竟是找到了仙岛，还是没有找到，但最终所有的程序神猿都将无上天君视为情敌，立誓要杀他千万遍！

第十章（番外结局一），千辛万苦我们不断地这样分身寻找，分身寻找，最终我们找到了仙岛，见到了心意的仙女梦瑶，抱得美人归！

第十章（番外结局二），千辛万苦我们不断地这样分身寻找，分身寻找，最终我们探索完了天界所有的区域（方格），都没有找到去仙岛的路，有些区域我们没有探索，是因为太古萌兽以及天外绝地将这些地方包围起来或者分隔，这些成为了我们永远的痛，永远的痛！

代码界的程序神猿

随着科技的发展，计算机来临了，程序神猿们发现，我们可以用计算机模拟寻路，他们看到了去天外仙岛的希望，他们看到了仙女梦瑶。

下面就是他们通过计算机计算的方法（这是一篇网上的教程，我做了一些小小的改动与完善）：

一、搜索区域

我们假设某个人要从A点到达B点，而一堵墙把这两个点隔开了，如下图所示，绿色部分代表起点A，红色部分代表终点B，蓝色方块部分代表之间的墙。

你首先会注意到我们把这一块搜索区域分成了一个一个的方格，如此这般，使搜索区域简单化，正是寻找路径的第一步。这种方法将我们的搜索区域简化成了一个普通的二维数组。数组中的每一个元素表示对应的一个方格，该方格的状态被标记为可通过的和不可通过的。通过找出从A点到B点所经过的方格，就能得到AB之间的路径。当路径找出来以后，这个人就可以从一个格子中央移动到另一个格子中央，直到抵达目的地。

这些格子的中点叫做节点。当你在其他地方看到有关寻找路径的东西时，你会经常发现人们在讨论节点。为什么不直接把它们称作方格呢？因为你不一定要把你的搜索区域分隔成方块，矩形、六边形或者其他任何形状都可以。况且节点还有可能位于这些形状内的任何一处呢？在中间、靠着边，或者什么的。我们就用这种设定，因为毕竟这是最简单的情况。

二、开始搜索

当我们把搜索区域简化成一些很容易操作的节点后，下一步就要构造一个搜索来寻找最短路径。在A*算法中，我们从A点开始，依次检查它的相邻节点，然后照此继续并向外扩展直到找到目的地。

我们通过以下方法来开始搜索：

1. 从A点开始，将A点加入一个专门存放待检验的方格的“开放列表”中。这个开放列表有点像一张购物清单。当前这个列表中只有一个元素，但一会儿将会有更多。列表中包含的方格可能会是你要途经的方格，也可能不是。总之，这是一个包含待检验方格的列表。

2.检查起点A相邻的所有可达的或者可通过的方格，不用管墙啊，水啊，或者其他什么无效地形，把它们也都加到开放列表中。对于每一个相邻方格，将点A保存为它们的“父方格”。当我们要回溯路径的时候，父方格是一个很重要的元素。稍后我们将详细解释它。

3. 从开放列表中去掉方格A，并把A加入到一个“封闭列表”中。封闭列表存放的是你现在不用再去考虑的方格。

此时你将得到如下图所示的样子。在这张图中，中间深绿色的方格是你的起始方格，所有相邻方格目前都在开放列表中，并且以亮绿色描边。每个相邻方格有一个灰色的指针指向它们的父方格，即起始方格。

接下来，我们在开放列表中选一个相邻方格并再重复几次如前所述的过程。但是我们该选哪一个方格呢？具有最小F值的那个。

三、路径排序

决定哪些方格会形成路径的关键是下面这个等式：

F = G + H

G＝从起点A沿着已生成的路径到一个给定方格的移动开销。

H＝从给定方格到目的方格的估计移动开销。这种方式常叫做试探，有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离，因为任何东西都有可能出现在半路上（墙啊，水啊什么的）。本文中给出了一种计算H值的方法，网上还有很多其他文章介绍的不同方法。

我们要的路径是通过反复遍历开放列表并选择具有最小F值的方格来生成的。本文稍后将详细讨论这个过程。我们先进一步看看如何计算那个等式。

如前所述，G是从起点A沿着已生成的路径到一个给定方格的移动开销，在本例中，我们指定每一个水平或者垂直移动的开销为10，对角线移动的开销为14。因为对角线的实际距离是2的平方根（别吓到啦），或者说水平及垂直移动开销的1.414倍。为了简单起见我们用了10和14这两个值。比例大概对就好，我们还因此避免了平方根和小数的计算。这倒不是因为我们笨或者说不喜欢数学，而是因为对电脑来说，计算这样的数字也要快很多。不然的话你会发现寻找路径会非常慢。

我们要沿特定路径计算给定方格的G值，办法就是找出该方格的父方格的G值，并根据与父方格的相对位置（斜角或非斜角方向）来给这个G值加上14或者10。在本例中这个方法将随着离起点方格越来越远计算的方格越来越多而用得越来越多。

有很多方法可以用来估计H值。我们用的这个叫做曼哈顿（Manhattan）方法，即计算通过水平和垂直方向的平移到达目的地所经过的方格数乘以10来得到H值。之所以叫Manhattan方法是因为这就像计算从一个地方移动到另一个地方所经过的城市街区数一样，而通常你是不能斜着穿过街区的。重要的是，在计算H值时并不考虑任何障碍物。因为这是对剩余距离的估计值而不是实际值（通常是要保证估计值不大于实际值――译者注）。这就是为什么这个方式被叫做试探法的原因了。想要了解更多些吗？

G和H相加就得到了F。第一步搜索所得到的结果如下图所示。每个方格里都标出了F、G和H值。如起点方格右侧的方格标出的，左上角显示的是F值，左下角是G值，右下角是H值。

我们来看看这些方格吧。在有字母的方格中，G＝10，这是因为它在水平方向上离起点只有一个方格远。起点紧挨着的上下左右都具有相同的G值10。对角线方向的方块G值都是14。

H值通过估算到红色目标方格的曼哈顿距离而得出。用这种方法得出的起点右侧方格到红色方格有3个方格远，则该方格H值就是30。上面那个方格有4个方格远（注意只能水平和垂直移动），H就是40。你可以大概看看其他方格的H值是怎么计算出来的。

每一个方格的F值，当然就不过是G和H值之和了。

继续搜索

为了继续搜索，我们简单的从开放列表中选择具有最小F值的方格，然后对选中的方格进行如下操作：

将其从开放列表中移除，并加到封闭列表中。

检验所有的相邻方格，忽略那些不可通过的或者已经在封闭列表里的方格。如果这个相邻方格不在开放列表中，就把它添加进去。并将当前选定方格设为新添方格的父方格。

如果某个相邻方格已经在开放列表中了（意味着已经探测过，而且已经设置过父方格――译者），就看看有没有到达那个方格的更好的路径。也就是说，如果从当前选中方格到那个方格，会不会使那个方格的G值更小。如果不能，就不进行任何操作。相反的，如果新路径的G值更小，就将该相邻方格的父方格重设为当前选中方格。（在上图中是改变其指针的方向为指向选中方格。最后，重新计算那个相邻方格的F和G值。如果你看糊涂了，下面会有图解说明。

好啦，咱们来看看具体点的例子。在初始时的9个方块中，当开始方格被加到封闭列表后，开放列表里还剩8个方格。在这八个方格当中，位于起点方格右边的那个方格具有最小的F值40。所以我们选择这个方格作为下一个中心方格。下图中它以高亮的蓝色表示。

首先，我们将选中的方格从开放列表中移除，并加入到封闭列表中（所以用亮蓝色标记）。然后再检验它的相邻节点。那么在它紧邻的右边的方格都是墙，所以不管它们。左边挨着的是起始方格，而起始方格已经在封闭列表中了，所以我们也不管它。

其他四个方格已经在开放列表中，那么我们就要检验一下如果路径经由当前选中方格到那些方格的话会不会更好，当然，是用G值作为参考。来看看选中方格右上角的那一个方格，它当前的G值是14，如果我们经由当前节点再到达那个方格的话，G值会是20（到当前方格的G值是10，然后向上移动一格就再加上10）。为20的G值比14大，因此这样的路径不会更好。你看看图就会容易理解些。显然从起始点沿斜角方向移动到那个方格比先水平移动一格再垂直移动一格更直接。

当我们按如上过程依次检验开放列表中的所有四个方格后，会发现经由当前方格的话不会形成更好的路径，那我们就保持目前的状况不变。现在我们已经处理了所有相邻方格，准备到下一个方格吧。

我们再遍历一下开放列表，目前只有7个方格了。我们挑个F值最小的吧。有趣的是，目前这种情况下，有两个F值为54的方格。那我们怎么选择呢？其实选哪个都没关系，要考虑到速度的话，选你最近加到开放列表中的那一个会更快些。当离目的地越来越近的时候越偏向于选最后发现的方格。实际上这个真的没关系（对待这个的不同造成了两个版本的A*算法得到等长的不同路径）。

那我们选下面的那个好了，就是起始方格右边的，下图所示的那个。




这一次，在我们检验相邻方格的时候发现右边紧挨的那个是墙，就不管它了。上面挨着的那个也同样忽略。还有右边墙下面那个方格我们也不管。为什么呢？因为你不可能切穿墙角直接到达那个格子。实际上你得先向下走然后再通过那个方格。这个过程中是绕着墙角走。（注意：穿过墙角的这个规则是可选的，取决于你的节点是如何放置的。）

那么还剩下其他五个相邻方格。当前方格的下面那两个还不在开放列表中，那我们把它们加进去并且把当前方格作为它们的父方格。其他三个中有两个已经在封闭列表中了（两个已经在图中用亮蓝色标记了，起始方格，上面的方格），所以就不用管了。最后那个，当前方格左边挨着的，要检查一下经由当前节点到那里会不会降低它的G值。结果不行，所以我们又处理完毕了，然后去检验开放列表中的下一个格子。

重复这个过程直到我们把目的方格加入到开放列表中了，那时候看起来会像下图这个样子。




注意到没？起始方格下两格的位置，那里的格子已经和前一张图不一样了。之前它的G值是28并且指向右上方的那个方格。现在它的G值变成了20并且指向了正上方的方格。这个改变是在搜索过程中，它的G值被核查时发现在某个新路径下可以变得更小时发生的。然后它的父方格也被重设并且重新计算了G值和F值。在本例中这个改变看起来好像不是很重要，但是在很多种情况下这种改变会使到达目标的最佳路径变得非常不同。

那么我们怎样来自动得出实际路径的呢?很简单，只要从红色目标方格开始沿着每一个方格的指针方向移动，依次到达它们的父方格，最终肯定会到达起始方格。那就是你的路径！如下图所示。从A方格到B方格的移动就差不多是沿着这个路径从每个方格中心（节点）移动到另一个方格中心，直到抵达终点。简单吧！





A*算法总结
1. 将开始节点放入开放列表(开始节点的F和G值都视为0);

2. 重复一下步骤
         I. 在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;
         II. 把当前节点从开放列表删除, 加入到封闭列表;
         III. 对当前节点相邻的每一个节点依次执行以下步骤:
                 ① 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
                 ② 如果该相邻节点没有探测过，则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和F值;
                 ③ 如果该相邻节点在开放列表中, 则判断若经由当前节点到达该相邻节点的G值是否小于原来保存的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
         IV. 循环结束条件：
                 ① 当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环；
                 ② 当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找到,此时也结束循环;
3. 从终点节点开始沿父节点遍历, 并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;


结束语
请大家原谅我的懒惰，虽然第二个里面的教程是弄别人的，但我确实下了不少功夫了~~~望大家理解！！！

代码里的注释写的还算详细，基础好点的，看了文章，再看代码估计都能懂个七七八八了。

愿大家越来越厉害，愿我早已脱离菜鸟的头衔~~~我是一只小小鸟，怎么飞也飞不高！！！

愿大家都能找到属于自己的仙女~~~送所有程序神猿~~~

源文件奉上：

游客，如果您要查看本帖隐藏内容请回复

免费是最昂贵的
银子还是要收的，因为 “免费的东西最昂贵” ，请深刻理解这句话的含义！！！


广告

QQ（TKCB）：2414268040（欢迎和我聊天交流，有朋自远方来不亦说乎）

QQ群：96759336（AS3殿堂之路，Flash Animate AS3 AIR 技术交流）

QQ群：705730359（H5天路历程，HTML5 CSS3 JaveScript  技术交流）

QQ群：463560360（King系列软件分享交流，TKCB 出品的 King 系列软件分享、使用、交流、反馈等）

TKCB网站：www.tkcb.cc

官方技术论坛：www.11ria.com

Leo

除了开头的故事是你自己编的下面都是复制别人的，这篇之前看过，现在重温一遍

TKCB

Leo 发表于 2019-2-26 15:05
除了开头的故事是你自己编的下面都是复制别人的，这篇之前看过，现在重温一遍 ...

应该说，中间是复制别人的，开头的故事，和后面的总结，以及源文件都是我写的。。
你之前看过的，就是我写在9RIA上面的。。

Leo

大哥你别糊我，因子扣了没有下载

TKCB

Leo 发表于 2019-2-26 15:15
大哥你别糊我，因子扣了没有下载

手动点击下载

Leo

TKCB 发表于 2019-2-26 15:17
手动点击下载

还要再点一次

墨海雪浪

向高手学习！

knightky

向高手学习！!!!!!!!!!!!!!

aopeng8700

112233DFSGSDGSDFGSDGF

jiaruida

11111111111111111111111111