JS实现的A*寻路算法详解

本文描述了用JS实现的A*寻路算法。分享给大家参考，如下：

这两天一直在做百度前端理工的话题，涉及到寻路，所以找了相关的博客看。

看了Create Chen写的理解A*路由算法的具体过程，很快就明白了A*算法的原理。不得不说，作者写得好，熟悉易懂，画得好，说明作者重视了。如果你让我写，我写不好。

唯一的不足是，因为我学的是js，所以最终不能使用给我的源代码.所以我有计划自己写一篇文章，向js人学习。不过，我借用他的描述，因为如果我的表达能力太差。

简单地图

图中显示了一个简单的地图，其中绿色方块是起点(用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(找到路径时，目标点阵已经在“打开列表”中)

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

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

Js代码：

//其中的地图是二维数组函数searchRoad(start_x，start_y，end_x，end_y){ var openList=[]，//开启列表closeList=[]，//关闭列表结果=[],//结果数组结果_索引；//结果数组在开启列表中的序号openList.push({x:start_x，y:start_y，g :0 })；//把当前点加入到开启列表中，并且G是0 do { var CurrentPoint=OpenList。pop()；关闭列表。推送(当前点)；var surroundPoint=surroundPoint(当前点)；for(var I in surroundPoint){ var item=surroundPoint[I]；//获得周围的八个点if (item.x=0 //判断是否在地图上项目。y=0项。xmap。行项目。伊马普。科尔斯地图。arr[项目。x][项目。y]！=1 //判断是否是障碍物！现有列表（项目，关闭列表)//判断是否在关闭列表中地图。arr[项目。x][当前点。y]！=1 //判断之间是否有障碍物，如果有障碍物是过不去的地图。arr[CurrentPoint。x][项目。y]！=1) { //g到父节点的位置//如果是上下左右位置的则g等于10,斜对角的就是14 var g=currentPoint .(当前点。x项目。x)*(当前点。y型物品。y)=0？10 : 14);if(！existList(item，openList)) { //如果不在开启列表中//计算h，通过水平和垂直距离进行确定项目[' H ']=数学。ABS(end _ x-item。x)* 10数学。ABS(end _ y-item。y)* 10；项目[' G ']=G；项目['F']=项目h .项g .item[' parent ']=当前点；openlist。推送(项目)；} else { //存在在开启列表中，比较目前的g值和之前的g的大小var index=existList(item，openList)；//如果当前点的g更小if (g openList[index]).G) { openList[index].parent=currentPointopenList[索引]。g=GoPrevent[索引]。f=g OpenList[索引]。h；} } } } //如果开启列表空了，没有通路，结果为空if(OpenList。长度==0){ break；} OpenList。sort(sortF)；//这一步是为了循环回去的时候，找出F值最小的，将它从'开启列表' 中移掉}while(！(result _ index=exist list({ x : end _ x，y:end_y}，OpenList))；//判断结果列表是否为空if(！result _ index){ result=[]；} else { var CurrentoBj=OpenList[result _ index]；do{ //把路劲节点添加到结果当中结果。unshift({ x : current obj。x，y : currenttobj。y })；电流tobj=电流tobj。父母；} while(CurrentBoj。x！=start _ x | | currentObj.y！=start _ y)；}返回结果；}//用F值对数组排序函数排序(a，b){返回b . F-a . F；}//获取周围八个点的值函数SurroundPoint(CurPoint){ var x=CurPoint。x，y=curPoint.y返回[ {x:x-1，y:y-1}、{x:x，y:y-1}、{ x :y-1 }、{x:x 1，y:y}、{x:x 1，y:y 1}、{ x 3: x，y:y 1}、{ x 33: x-1，y 3:1判断点是否存在在列表中，是的话返回的是序列号函数existList(点，列表){ for(var I in list){ if(点。x==list[I]).x点。y==list[i].y){ 0返回我；} }返回false}更多关于Java脚本语言相关内容感兴趣的读者可查看本站专题： 《JavaScript数学运算用法总结》 、 《JavaScript数据结构与算法技巧总结》 、 《JavaScript数组操作技巧总结》 、 《JavaScript排序算法总结》 、 《JavaScript遍历算法与技巧总结》 、 《JavaScript查找算法技巧总结》 及《JavaScript错误与调试技巧总结》

希望本文所述对大家Java脚本语言程序设计有所帮助。