爱思达完成新一轮3亿元人民币融资，由中新融创
06-18
【警告】本文不是针对零基础知识的人，而是针对面向黄金级的LOL高手。本文也适合没有导航找不到家的孩子。
在英雄联盟中，当你和你的队友努力达到18级时，你仍然与敌方阵营打成平手。就在你刚刚购买装备并装备好时，你看到消息框有队友发来的消息：“男爵聚集”。
这时候你把鼠标移到男爵身上，右键，然后你像吃瓜群众一样盯着你的英雄，看着他走进丛林小路，因为你买了阳火斗篷。当你经过那三只狼时，它们追着你咬了几口。
你的英雄忽略了他们。三狼这才松了口气。
他们太棒了！然后你一路上摘了几个蘑菇，因为烧了被蓝buff追了。连河里的螃蟹都想咬你，为你报仇，杀了它三级的爷爷。
然而，你临死前还是来到了大龙身边。还没来得及动大龙一根汗毛，他就被大龙一甩尾击倒了。
这时候，旁边的女孩还一头雾水，你要显示器做什么？突然，它破裂了，变成了黑色和白色。那么问题来了，为什么丛林套路这么深，你的英雄却不选择走沿河的大路去男爵呢？因为每次你确定目标时，你的英雄都会走最短路线。
那么你的英雄如何找到最近的路线呢？如果你觉得很简单，你可以自己去找。你能像你的英雄一样快地找到它吗？当你确定了目标之后，你的英雄不会环顾四周就开始行走，更不会中途发现不对劲就回去重新开始。
您可能对这个问题感兴趣，游戏中的英雄是如何做到的？如果你不玩游戏，那么你一定用过导航软件，你可能会好奇它是怎么做的。如果你能读懂这篇文章，那么你一定会写代码。
能用代码实现这个功能吗？其实我一直很好奇这是怎么做到的。最多只能写一些增删改查的常规操作。
直到我接到一个实现 A-star 算法的任务，我才想通了。 A-star 算法 我们假设一个人想要从 A 点到达 B 点，并且一堵墙将两点分开。
如下图所示，绿色部分代表起点A，红色部分代表终点B，蓝色方块部分代表中间的墙壁。您会注意到的第一件事是我们将搜索区域划分为正方形。
简化搜索区域是寻找路径的第一步。这种方法将我们的搜索区域缩小为常规的二维数组。
数组中的每个元素代表一个对应的方格，该方格的状态被标记为可通行或不可通行。通过找到从A点到B点所经过的方格，就可以得到AB之间的路径。
找到路径后，人就可以从一个网格的中心移动到另一个网格的中心，直到到达目的地。 这些网格的中点称为节点。
当您在其他地方看到有关寻路的内容时，您经常会发现人们在讨论节点。为什么不直接称它们为正方形呢？因为您不必将搜索区域划分为正方形、矩形、六边形或任何其他形状。
如果节点可以位于这些形状内的任何位置怎么办？在中间，在两侧，或者其他什么地方。我们将使用此设置，因为它毕竟是最简单的情况。
当我们将搜索区域简化为一些易于操作的节点后，下一步就是构造一个搜索来寻找最短路径。在A*算法中，我们从A点开始，依次检查它的邻居节点，然后继续这样向外扩展，直到找到目的地。
我们按照以下方式开始搜索：从A点开始，将A点添加到一个专门存储待测试方块的“开放列表”中。这个开放清单有点像购物清单。
目前该列表中只有一个元素，但很快就会有更多。列表中包含的方格可能是也可能不是您想要通过的方格。
总而言之，这是一个需要检查的列表。 2.检查与起点A相邻的所有可进入或可通行的方格，无论其是否有墙壁、水或其他无效地形，并将其添加到开放列表中。
对于每个相邻的方块，将 A 点保存为它们的“父方块”。当我们想要回溯路径时，父方块是一个非常重要的元素。
我们稍后会详细解释。 3. 从打开列表中删除方格 A，并将 A 添加到“关闭列表”中。
关闭列表存储了您现在不需要考虑的方块。此时您将得到如下图所示的内容。
在这张图片中，中间的深绿色方块是您的起始方块，所有相邻的方块当前都在打开列表中，并以亮绿色勾勒出轮廓。每个相邻的方块都有一个灰色指针指向其父方块，即起始方块。
接下来，我们在打开列表中选择一个相邻的方块，并重复上述过程几次。但我们应该选择哪个方格呢？对F值最小的路径进行排序。
确定哪些方格将形成路径的关键是以下等式： F = G + HG = 沿生成路径从起点 A 移动到给定方格的成本 H = 从给定方格开始 从给定方格估计的移动成本到目的地广场。这种方法通常被称为测试，这对人们来说有点混乱。
事实上，它被称为启发式，因为它只是一种猜测。在找到路径之前，我们实际上并不知道实际距离，因为任何东西都可能出现在中途（墙壁、水等）。
这篇文章给出了计算H值的方法，网上还有很多其他文章介绍了不同的方法。我们想要的路径是通过迭代遍历 open list 并选择 F 值最小的方格来生成的。
本文稍后将详细讨论此过程。让我们仔细看看如何计算该方程。
如前所述，G 是从起点 A 沿着生成的路径移动到给定方格的成本。在这个例子中，我们指定每次水平或垂直移动的成本为10，对角线移动的成本为10。
为14。因为对角线的实际距离是2的平方根（不要害怕），或水平和垂直移动成本的 1 倍。
为了简单起见，我们使用了值 10 和 14。比例大致正确，并且我们避免了计算平方根和小数。
这并不是因为我们愚蠢或者不喜欢数学，而是因为计算机计算这些数字的速度要快得多。否则你会发现寻路会很慢。
我们想要计算给定正方形沿特定路径的 G 值，方法是找到该正方形的父正方形的 G 值，并根据其与父正方形的相对位置（倾斜或非倾斜方向）给出该值。 G 值加上 14 或 10。
在这种情况下，随着越来越多的正方形被计算得远离起始正方形，该方法将被越来越多地使用。估计 H 值的方法有很多种。
我们使用的方法称为曼哈顿法，通过水平和垂直平移计算到达目的地所行驶的方格数，并将其乘以10即可得到H值。它被称为曼哈顿方法，因为它就像计算从一个地方移动到另一个地方所需的城市街区数量，而且通常你不能对角地穿过街区。
重要的是，计算 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 值的总和。
继续搜索 要继续搜索，我们只需从 open 列表中选择 F 值最小的方格，然后对所选方格执行以下操作： 4. 将其从 open 列表中删除，并将其添加到 close 列表中。 5. 检查所有相邻的方格，忽略那些无法通过或已在关闭列表中的方格。
如果相邻的方块不在打开列表中，则将其添加。并将当前选中的方块设置为新添加的方块的父方块。
6. 如果相邻的方格已在打开列表中（意味着它已被探索并且父方格已被设置 - 翻译器），请查看是否有更好的路径到达该方格。也就是说，如果从当前选择的方格走到那个方格，那个方格的G值会更小吗？如果不是，则不采取任何行动。
反之，如果新路径的G值较小，则将相邻方格的父方格重置为当前选择的方格。 （上图中，指针的方向改变为指向选中的方格，最后重新计算相邻方格的F和G值，如果你感到困惑，下面有一张图，好吧，我们来看看我们来看一个具体的例子，在最初的9个方格中，将起始方格添加到关闭列表后，打开列表中还剩下8个方格，即起始方格右边的那个方格。
具有最小的 F 值 40。因此我们选择该方块作为下一个中心方块，它在下图中以蓝色突出显示。
首先，我们从打开列表中删除选定的方块并将其添加到关闭列表中。用亮蓝色标记）然后检查它的相邻节点，所以它右边的方块是墙，所以它左边的方块是起始方块，并且起始方块已经在关闭列表中，所以我们不这样做。
关心它。其他四个方块已经在打开的列表中，所以我们必须检查路径是否通过当前选定的方块到达这些方块。
当然，如果能以G值作为参考就更好了。我们来看看所选方块右上角的方块。
它当前的G值为14。如果通过当前节点到达该方格，则G值为20（当前方格的G值为10，向上移动一格时加10）。
G值20比14大，所以这条路不会更好。你可以看到图片。
理解。显然，从起点沿对角线方向移动到该方格比水平移动一个方格然后垂直移动一个方格更直接。
当我们按照上面的过程依次检查open列表中的所有四个方块时，我们会发现。如果没有更好的路径通过当前广场，那么我们将保持当前情况不变。
现在我们已经处理了所有相邻的方格，是时候继续处理下一个方格了。让我们再次浏览一下打开的列表。
只剩下7个方格了。我们选择 F 值最小的那个。
有趣的是，在这种情况下，有两个F值为54的方格。那么我们该如何选择呢？事实上，您选择哪一个并不重要。
如果要考虑速度，选择最近添加到打开列表中的会更快。当你越来越接近目的地时，你倾向于选择最后发现的方块。
事实上，这确实无关紧要（对此处理的差异导致两个版本的A*算法获得不同长度的路径）。然后我们选择下面的那个，也就是起始方块右边的那个。
这次，当我们检查相邻的方块时，我们发现右边的那个是一堵墙，所以我们忽略它。旁边的那个也被忽略了。
我们也不关心右墙下的正方形。为什么？因为你无法穿过拐角直接到达那个网格。
其实你得先下去，然后再经过那个广场。在这个过程中，你会绕过拐角。
（注意：这条穿过拐角的规则是可选的，具体取决于节点的放置方式。）这会留下其他五个相邻的方块。
当前方块下方的两个方块尚未在打开列表中，因此我们添加它们并使用当前方块作为其父方块。另外三个中的两个已经在关闭列表中（图中已经用亮蓝色标记了两个，起始方块，上面的方块），所以不用担心。
对于最后一个，即当前方格左边的那一个，需要检查从当前节点到那里是否会减少其G值。结果不行，所以我们再次完成处理，然后检查打开列表中的下一个网格。
重复此过程，直到我们将目标方块添加到打开列表中，如下图所示。你注意到了吗？起始方块下方的两个方块的位置与上一张不同。
之前它的 G 值为 28，并指向右上角的方块。现在它的G值为20，它指向正上方的正方形。
当在搜索过程中检查其G值并发现它在某些新路径下可以变小时，就会发生这种变化。然后其父方格被重置并重新计算其G和F值。
在此示例中，此更改可能看起来不太重要，但在许多情况下，此更改可能会使实现目标的最佳路径变得非常不同。那么我们如何自动获取实际路径呢？这很简单。
只要从红色目标方格开始，沿着每个方格的指针方向移动，依次到达它们的父方格，最终就会到达起始方格。这就是你的路！如下图所示。
从方格A到方格B的移动基本上就是沿着这条路径从每个方格的中心（节点）移动到另一个方格的中心，直到到达终点。代码示例：这是一个 python3 代码，读取类似于下图的文件。
第一行是地图的大小。在其他地方，0表示可行，1表示不可能移动。
为了简单给出编程思路，这里假设角色只能上下左右移动。命令行参数分别为地图文件、起点坐标x、y、终点坐标x、y。
地图文件名：testgrid_small.txt 代码语言：txt copy 5 30 0 1 0 01 0 1 0 00 0 0 0 1 代码文件名：astar.py 代码语言：txt copy import sys#map（从file Array) maze=[]#开始 start=None#终点 end=None#打开列表（即要探索的位置） open_list={}#关闭列表（已探索过的位置和不可行走的位置） close_list={ } #地图边框（二维数组的大小，用于判断一个节点的相邻节点是否超出范围） map_border=()#方向orientation=[]class Node(object): def __init__(self,father, x,y) ：如果 x<0 或 x>=map_border[0] 或 y<0 或 y>=map_border[1]：引发异常（'坐标错误'） self.father=father self.x=x self. y=y 如果父亲 !=None: self.G=father.G self.H=距离(self,end) self.F=self.G+self.H else: self.G=0 self.H=0 self .F=0 def reset_father(self,father,new_G): iffather!=None: self.G=new_G self.F=self.G+self.H self.father=father#计算距离 def distance(cur,end ): 返回abs(cur.x-end.x)+abs(cur.y-end.y)#查找open_list中F值最小的节点 def min_F_node(): global open_list if len(open_list)==0: raise Exception('路径不存在') _min= _k=(start.x,start.y) #以列表的形式遍历open_list字典 for k,v in open_list.items(): if _min>v.F: _min=v.F _k=k return open_list[_k]#将相邻节点添加到open_list中，如果结束点找到，则表示找到终点 def addAdjacentIntoOpen(node): global open_list,close_list #首先将节点从打开列表移动到关闭列表 open_list.pop((node.x,node.y)) close_list[( node.x,node.y) ]=node相邻=[] #添加相邻节点时注意边界 #尝试上面：adjacent.append(Node(node,node.x,node.y-1)) except Exception as err: pass #尝试以下：adjacent.append(Node(node,node.x,node.y)) except Exception as err: pass #左尝试：adjacent.append(Node(node,node.x-1,node) .y)) except Exception as err : pass #右尝试:adjacent.append(Node(node,node.x,node.y)) except Exception as err: pass #检查每个相邻点for a in相邻: #如果是终点，则结束 if (a.x,a.y)==(end.x,end.y): new_G=node.G end.reset_father(node,new_G) return True #如果是位于close_list中，忽略他 if (a.x,a.y) in close_list: continue #如果不在open_list中，则添加 if (a.x,a.y) not in open_list: open_list[(a.x,a.y)]=a #如果存在在 open_list 中，使用 G 值来判断该点是否更近 else: exit_node=open_list[(a.x,a.y)] new_G=node.G if new_G
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-18
06-18
06-17
06-18
06-21
06-21
06-06
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用