深刻理解js A*寻路算法的原理和具体实现过程

本文结合实例阐述了js A*寻路算法的原理和实现过程。分享给大家参考，如下：

这两天学习了A*寻路算法，主要学习了这篇文章，但是这篇文章的翻译不是很好。我花了很长时间才理解文章中的各种参考文献。我以这个博客为特色，总结写了寻路算法的代码，让觉得有用的同学可以看看。另外，因为制作图片比较麻烦，所以用了原文中的图片。

当然，路由算法不仅仅是A*，还有递归、非递归、广度优先、深度优先、使用栈等等。有兴趣可以研究一下~ ~

简单地图

图中显示了一个简单的地图，其中绿色方块是起点(用A表示)，中间的蓝色是障碍，红色方块(用B表示)是终点。为了用二维数组表示地图，我们将地图分成小方块。

二维数组在游戏中被广泛使用。比如《蛇》和《俄罗斯方块》的基本原理是移动方块，而大型游戏的地图则是在这样的小方块上散布各种‘地貌’。

寻路步骤

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，看看结果是否和你想的一样。

从“开放列表”(绿色起始方块a右侧的方块)中选择f值最低的方块c，然后按照：进行处理

4.将其从“开放列表”中删除，并将其放入“封闭列表”。

5.检查所有相邻的和可到达的方块(不考虑“封闭列表”中的障碍物和方块)。如果这些方块不在“开放列表”中，将它们添加到“开放列表”中，计算这些方块的G，H和F值，并将它们的“父方块”设置为c .

6.如果相邻的方块D已经在“开放列表”中，检查如果有新路径(即通过C的路径)到达，G值是否会更低。如果新的G值较低，则将其“父方块”更改为当前选定的方块C，然后重新计算其F值和G值(H值不需要重新计算，因为对于每个方块，H值都是常数)。如果新的G值比较高，说明先经过C再到达D不是一个明智的选择，因为需要更长的路，然后我们什么都不做。

如图所示，我们选择C是因为它的F值最小，所以我们从‘开放列表’中删除了它，并将其添加到‘封闭列表’中。它右边的上下三个是墙，所以我们不考虑。它左边的起始方块已经被添加到“封闭列表”中，我们也不考虑它。所以周围只有四个候选方块。让我们看看C下面的网格，它的电流G是14。如果我们通过C到达它，G将是10 ^ 10，大于14，所以我们什么也不做。

然后我们继续从‘开放列表’中寻找最小的f值，但是我们发现c的顶部和底部同时都是54。这个时候我们该怎么办？这时，你可以随意拿走任何一个。例如，我们选择了c下面的正方形D .

D右边和右上角的墙都被忽略了，但是为什么右下角的墙没有被添加到‘开放列表’中呢？因为如果C下面的街区也去不了，要想到达C右下角的街区，就需要从‘街区的角落’出发。设置程序中是否允许这样做。(图中的例子不允许这样。)

这样，我们从“开放列表”中找到最小的f值，将其从“开放列表”中移除，并将其添加到“封闭列表”中。然后继续找出它周围可接近的方块，以此类推.

那么什么时候会停止呢？——当我们在‘开始列表’中找到目标结束框时，意味着路径已经找到。

如何检索路径

如上图所示，除了起始框之外，以前或现在仍在“打开列表”中的每个框都有一个“父框”，通过它可以对初始的“起始框”进行索引，这就是路径。

抽象整个过程

将起始网格添加到“打开列表”

{在开放列表中寻找f值最低的网格，我们称之为当前网格。切换到关闭列表。对当前网格相邻的8个网格中的每个if(不能通过| |并且已经在“封闭列表”中)不执行任何操作。} if(不在打开列表中){将其添加到“打开列表”中，并将当前网格作为该网格的父节点。计算该格的FGH if(已经在开放列表中){if(以g值为参考，检查新路径是否更好，g值越低表示路径越好){将该格的父节点改为当前格，重新计算该格的GF值。}} while(找到路径时，目标点阵已经在“打开列表”中)

如果打开的列表为空，则路径不存在。

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

主代码

程序中的打开列表和关闭列表

列表点关闭列表；列表点开放列表；点类

公共类Point { public Point ParentPoint { get；设置；} public int F { get设置；} //F=G H公共int G { get设置；} public int H { get设置；} public int X { get设置；} public int Y { get设置；} public Point(int x，int y) { this。X=x这个。Y=y} public void CalcF() { this。F=这个。这个。h；}}寻路过程

公共点查找路径(点开始，点结束，bool isignorcorner){ OpenList。添加(开始)；while (OpenList。数数！=0) {//找出f值最小的点var tempStart=OpenList。minPoint()；OpenList。remove at(0)；关闭列表。添加(TempStart)；//找出它的相邻点var环绕点=surrroundpoints (tempstart，isignorcorner)；Foreach(环绕点中的点){if(打开列表。exists(point))//计算G的值，如果比原来大，什么都不做，否则将其父节点设置为当前点，并更新G和F找到的点(tempstart，point)；Else //如果它们不在开始列表中，则添加它们，设置父节点并计算ghf未找到点(tempstart，end，point)；} if (OpenList。Get(end)！=null)返回OpenList。get(end)；}返回OpenList。get(end)；}单击此处下载完整的示例代码。

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》和0103010

希望本文对JavaScript编程有所帮助。