A星寻路算法

一、A星寻路算法介绍

          当你在制作一款游戏的时候是否想过让你的角色避开道路上的障碍物从而抵达终点呢？

          如果有的话，那么这篇文章你要认真看下去，至少可以帮助你初步建立一个利用A星算法的思路实现它！

          本篇文章将从算法最基本的思路讲起，让我们开始吧！

二、一张棋盘格

让我们来看这张图，你创造的主角小红，想要到达小黄所在的位置，这条线路我们应该怎么找。

显然图片中黑色的部分不像是小红能直接穿过的地方，我们需要绕一绕，也许你有很多条路可以走，但我现在告诉你，我们赶时间，我们需要找出最短的路！

如何解决这个问题呢，A星算法来了。

三、基本思路

我们将每个位置默认为一个正方格，他的目的是便于我们之后的计算

不要质疑为什么你的主角变了颜色，这并不影响我们的讲解。

我们创造了一个简单的搜索区域，八个方向，并且我们用小本本记下了两个列表：open列表（记录下所有被考虑来寻找最短路径的方块）     和      close列表（记录下不会再被考虑的方块）

首先我们将起点添加入close列表中（我们将起点设为“A”，深绿色方框），再将A附近所有可行方块添加入open列表中（绿色描边方框）

路径增量

我们给每一个方块一个G＋H和值

G为从起点A到当前点的移动量（代表本文中的方块数量），所以从A开始到相邻点的G值为1，这个值会随着角色的移动（或者说距离开始点）越来越远而增大。

H为从当前所在点到终点（我们将它设为B！）的移动估算量，这个常被成为探视，因为我们不确定它的移动量的准确数值，所以这个H仅仅只是一个估算值。

（值得一提的是，这个H的估算值我们有多种办法算取，你可以使用“曼哈顿距离算法”，或是欧拉公式等，它只是计算出点B剩下的水平垂直方块的数量，忽略掉中途的任何障碍物）

在A星算法中移动量这个值是由你来决定的，你可以仅仅允许主角进行上下左右四个方向的移动，或者你可以将移动量针对地形调整到大一点。

四、算法原理

既然你已经知道G和F，我们来认识一下这个算法最核心的值——F值，它有一个公式：F=G+H，它的意义是方块的移动总代价（或称为和值）

在算法中，角色将重复下列几个步骤来寻找最短路径：

1，将方块添加到open列表中,且该方块拥有最小的F和值，我们暂且将它称为S。

2、将其从open列表中移除，然后添加入close列表中。

3、对于S相邻的每一个方块，都有：

                      若该方块在close列表中，我们不管它。

                      若改方块不在open列表中，计算它的F和值并将其添加入open列表中。

                      若该方块已经在open列表中，当我们沿着当前路径到达它时，计算它的F和值是否更小，如果是，前进并更新它的和值和它的前继。

为了帮助你理解它的原理，我们来举个例子吧：

 在接下来的每一步中，绿色方框代表我们可以选择的方块，而已选择的方块我们会用红色边框将它点亮。

第一步，我们要确定起点附近的每一个方块，计算他们的F值并将其添加入open列表中，在图片中，方框左下方的数字代表G值，为了确保你学会了怎么使用“截取距离算法（忽略障碍物由A到B的位移量）”H值，我们不打算将其标入方框中，最终，将G与你计算出的H值相加便得到左上角的F和值。

第二步，选择其中F值最小的方块并将其添加入close列表中，再次检索它相邻的可行方块，我们发现有两个一模一样的方块可选，而根据刚才讲到的第三条定理，我们发现上下两个方块都已经在open列表中，且我们通过计算发现，第一步时它的G值为1，但当我们经由当前已在的“4,1”方格在到达那里时，它的G值将变为2（因为我们绕了一下，所以移动了两步），显然2比1大，因此从“4,1”再走到“5,1”并不是最优路径，我相信你是一个有远见的人，所以你会从第一步就选择“5,1”方块。

第三步、当你选择走最优路径时，你会发现一个问题，“5,1”方块有两个，也就是说有两条一模一样的路可以走，但真的是这样吗，我们保留这个疑问，随便选择一个，比如我选择走上边的“5,1”方块。

再次检索周围方块，并忽略掉障碍物。我们得到如下图的信息。

 我们发现有好几个F值都为6的，没关系，我们都考虑上并计算他附近的F值，在这里我们也顺便将刚才未选择的下方“5,1”方块周围的F值计算一下

 可以看到其实左边的方块其实是不用考虑的，我们人眼一看就知道接着刚才的路继续寻找就好了，但是程序并不知道，他只会老老实实运行你给他规定的步骤，这算是必踩的坑。

但是有一种比较简便的方法是，规定一直沿着最近被添加入open列表的方块。

好了现在你已经训练有素了，经过几次重复你得到了下图这样的路径

 你成功到达了终点，他已经在open列表中了，当你迈出最后一步时，程序会将它从open中移除并添加入close列表中。

最后，算法，算法需要做的是就是沿着路径返回并计算出最优路径。

 让我们将最终路径用蓝色方框强调出来。

代码部分

（我们在该代码中使用的是勾股定理来计算，实际上与街区算法原理）

这便是所有代码部分了，其中都包含有对每部分的注释讲解，读者可自行阅读理解。

运行结果

 我在这里插入一个比较优秀的A星算法演示链接，方便各位理解算法思路。

http://qiao.github.io/PathFinding.js/visual/

成品展示链接

链接：https://pan.baidu.com/s/1Y4OaovodEtBeXUCRdOKDIg
提取码：dt68

小组成员：杨豪杰 刘益 谢君 杨千禧