网站运营者网址,wordpress 点餐主题,榆社县济南网站建设公司 大学,新手制作网站工具2019独角兽企业重金招聘Python工程师标准 ■在A *方法总结 Summary of the A* Method 好了#xff0c;现在你通过解释已经走了#xff0c;让我们奠定了一步一步的方法#xff0c;在同一个地方#xff1a; Okay, now that you have gone through the explanat… 2019独角兽企业重金招聘Python工程师标准 ■在A *方法总结 Summary of the A* Method 好了现在你通过解释已经走了让我们奠定了一步一步的方法在同一个地方 Okay, now that you have gone through the explanation, lets lay out the step-by-step method all in one place: 添加开始方块或节点到开启列表。 Add the starting square (or node) to the open list. 重复以下操作 Repeat the following: a 寻找开启列表上最小F值的方块。我们将此作为当前方块。 Look for the lowest F cost square on the open list. We refer to this as the current square b 切换到关闭列表。 Switch it to the closed list. c 对于当前方块的8个方块的每一个... c) For each of the 8 squares adjacent to this current square … 如果不能走或者如果它是关闭的名单上忽略它。否则请执行以下操作。 If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following. 如果不在开启列表中将其添加到开启列表。使当前方块成为这个方块的父。记录的方块F值G值和H值。 If it isnt on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square. 如果在开启列表了检查看看这个路径该方块是否是更好的采用G值作为衡量。更低的G值意味着这是一个更好的路径。如果是这样把方格的父改变当前方块并重新计算方块的G值和F值。如果你保持开启列表排序F值由于这个变化你可能需重存列表。 If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change. d当你停止 d) Stop when you: 目标方块添加到关闭列表在这种情况下路径已经被发现见下面的注或无法找到目标方块并且开启列表是空的。在这种情况下不存在路径。 Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path. 保存路径。从目标方块往回走从每个方块移到其父直到你到达开始方块。这是你的路径。 Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path. 注在早期版本的文章中有人建议当目标方块或节点已经添加到开启列表而不是关闭的列表你可以停下来。这样做会更快它几乎总是会给你的最短路径但并非总是如此。有些情况下这样做可能产生差异当从第二移动到最后一个节点到最后的目标节点的运动成本可能有明显变化 -例如如果在河流交叉在两个节点之间的情况下。 Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list. Doing this will be faster and it will almost always give you the shortest path, but not always. Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example. ■小咆哮 Small Rant 请原谅我的题外话但值得指出的是当你在网上阅读的A *路径搜索并在各类论坛上的各种讨论时你偶尔会看到有人提到某些代码不是A *。对于A *使用方法你需要包含上面讨论到的元素 -- 特别是开放列表和关闭列表和路径采用F值G值和H值。有很多其他的路径搜索算法但是其它的通常被认为是最好的方法不是A *。在这篇文章的末尾有布莱恩斯托特讨论包括他们的一些利弊引用的文章很多。有时替代品在某些情况下更好但你应该明白你正在进入。好了爽了。回到话题。 Forgive me for digressing, but it is worth pointing out that when you read various discussions of A* pathfinding on the web and in assorted forums, you will occasionally see someone refer to certain code as A* when it isnt. For the A* method to be used, you need to include the elements just discussed above -- specifically open and closed lists and path scoring using F, G, and H. There are lots of other pathfinding algorithms, but those other methods are not A*, which is generally considered to be the best of the lot. Bryan Stout discusses many of them in the article referenced at the end of this article, including some of their pros and cons. Sometimes alternatives are better under certain circumstances, but you should understand what you are getting into. Okay, enough ranting. Back to the article. 待续 转载于:https://my.oschina.net/dubenju/blog/464443
