为什么 A* 寻路有时是直线，有时是对角线？ （爪哇）
我正在开发一个简单的基于二维网格的模拟游戏，并且具有功能齐全的寻路功能。
我使用上一个问题中找到的答案作为实现 A* 路径查找的基础。 （寻路 2D Java 游戏？）。
为了向您展示我真正要问的内容，我需要向您展示我制作的视频屏幕截图。 我只是测试一下这个人如何移动到一个位置并再次返回，这就是结果...
http://www.screenjelly.com/watch/Bd7d7pObyFo
根据方向不同选择路径，得到意想不到的结果。 有任何想法吗？
I'm in the process of developing a simple 2d grid based sim game, and have fully functional path finding.
I used the answer found in my previous question as my basis for implementing A* path finding. (Pathfinding 2D Java game?).
To show you really what I'm asking, I need to show you this video screen capture that I made.
I was just testing to see how the person would move to a location and back again, and this was the result...
http://www.screenjelly.com/watch/Bd7d7pObyFo
Different choice of path depending on the direction, an unexpected result. Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
如果您正在寻找一个简单的解决方案，我可以建议一些随机化吗？
我的意思是：在 cokeandcode 代码示例中，有嵌套的 for 循环生成“后继状态”（使用 AI 术语）。 我指的是它在“当前”状态周围的 3x3 正方形上循环的点，在堆上添加要考虑的新位置。
一个相对简单的修复将（应该:)）稍微隔离该代码，并让它在处理步骤的其余部分之前生成节点的链接列表。 然后Containers.Shuffle（或者是Generics.Shuffle？）那个链表，并在那里继续处理。 基本上按惯例说，
“创建NaiveNeighbors（节点）”
返回一个 LinkedList = {(node.x-1,node.y), (node.x, node.y-1)... } （请原谅 pidgin Java，我正在尝试（但总是失败） 理想
但是，一旦构建了链接列表，您应该能够执行“for (Node n : myNewLinkedList)”而不是
执行完全相同的主体代码！
情况下，这将 “调整”所考虑的节点的顺序，并创建更接近对角线的路径，但无需更改启发式。路径仍然是最有效的，但通常更接近对角线。
当然，缺点是，如果您多次从 A 到 B，则可能会采取不同的路径，如果这是不可接受的，您可能需要考虑更彻底的修改
希望这会有所帮助！
-阿戈尔
If you're looking for a simple-ish solution, may I suggest a bit of randomization?
What I mean is this: in the cokeandcode code example, there is the nested-for-loops that generate the "successor states" (to use the AI term). I refer to the point where it loops over the 3x3 square around the "current" state, adding new locations on the pile to consider.
A relatively simple fix would (should :)) be isolate that code a bit, and have it, say, generated a linkedlist of nodes before the rest of the processing step. Then Containers.Shuffle (or is it Generics.Shuffle?) that linked list, and continue the processing there. Basically, have a routine say,
"createNaiveNeighbors(node)"
that returns a LinkedList = {(node.x-1,node.y), (node.x, node.y-1)... } (please pardon the pidgin Java, I'm trying (and always failing) to be brief.
Once you build the linked list, however, you should just be able to do a "for (Node n : myNewLinkedList)" instead of the
And still use the exact same body code!
What this would do, ideally, is sort of "shake up" the order of nodes considered, and create paths closer to the diagonal, but without having to change the heuristic. The paths will still be the most efficient, but usually closer to the diagonal.
The downside is, of course, if you go from A to B multiple times, a different path may be taken. If that is unnacceptable, you may need to consider a more drastic modification.
Hope this helps!
-Agor
两条路径的长度相同，因此算法可以很好地完成其工作 - 它正在寻找最短路径。 然而，A* 算法没有指定它将采用哪条最短路径。 实现通常采用“第一”最短路径。 如果没有看到你的，就不可能确切地知道为什么，但是如果你每次都想要相同的结果，则必须添加某种优先级规则（以便你所需的路径在搜索中首先出现）。
Both of the paths are of the same length, so the algorithm is doing its job just fine - it's finding a shortest path. However the A* algorithm doesn't specify WHICH shortest path it will take. Implementations normally take the "first" shortest path. Without seeing yours, it's impossible to know exactly why, but if you want the same results each time you're going to have to add priority rules of some sort (so that you're desired path comes up first in the search).
原因实际上非常简单：路径将始终尝试尽可能采用最低的启发式，因为它以贪婪的方式进行搜索。 离目标越来越近，才是最优路径。
如果你允许对角线移动，这种情况就不会发生。
The reason why is actually pretty simple: the path will always try to have the lowest heuristic possible because it searches in a greedy manner. Going closer to the goal is an optimal path.
If you allowed diagonal movement, this wouldn't happen.
原因是您希望算法走的路径。
我不知道你的 A* 使用的启发式，但在第一种情况下，它必须先到达隧道的尽头，然后规划从隧道的尽头到目标的路线。
在第二种情况下，到达目标的最简单的移动是向下移动直到撞到墙壁，然后规划从墙壁到目标的路径。
据我所知，大多数 A* 都使用视线启发法或曼哈顿距离（在以下情况）一个方块世界。 这种启发式方法为您提供最短路线，但如果遇到障碍物迫使您走与视线不同的路线，则路线取决于您的起点。
该算法将尽可能长时间地运行视线。
The reason is the path you want the algorithm to go.
I don't know the heuristic your A* uses but in the first case it has to go to the end of the tunnel first and then plans the way from the end of the tunnel to the target.
In the second case the simplest moves to the targets are going down till it hits the wall and then it plans the way from the wall to the target.
Most A* I know work with a line of sight heuristic or a Manhattan Distance in the case of a block world. This heuristics give you the shortest way but in case of obstacles that force to go a way that is different from the line of sight the ways depend on your starting point.
The algorithm will go the line of sight as long as possible.
最可能的答案是，径直向南走，首先最接近目标； 反之，这不是一个选择，因此它分段优化子路径，结果是交替向上/横向移动被认为是最好的。
如果您希望它沿着对角线返回，您将必须识别沿路径的一些兴趣点（例如隧道口），并在您的启发式中考虑这些点。 或者，您可以通过重新计算经过兴趣点的任何子路径来将它们考虑到您的算法中。
过去，他们常常对地图进行预编译的静态分析，并在阻塞点放置寻路标记。 根据您的最终目标是什么，这也可能是一个好主意。
如果您确实有兴趣了解正在发生的情况，我建议您呈现 A* 搜索的步骤。 鉴于你的问题，这可能会让你大开眼界。
The most likely answer is that going straight south gets it closest to its goal first; going the opposite way, this is not a choice, so it optimizes the sub-path piecewise with the result that alternating up/across moves are seen as best.
If you want it to go along the diagonal going back, you are going to have to identify some points of interest along the path (for example the mouth of the tunnel) and take those into account in your heuristic. Alternatively, you could take them into account in your algorithm by re-computing any sub-path that passes through a point of interest.
Back in the day they used to do a pre-compiled static analysis of maps and placed pathfinding markers at chokepoints. Depending on what your final target is, that might be a good idea here as well.
If you're really interested in learning what's going on, I'd suggest rendering the steps of the A* search. Given your question, it might be very eye-opening for you.
在每种情况下，它都会优先选择能够更快地接近目标节点的路径，这就是 A* 的设计目的。
In each case it's preferring the path that takes it closer to its goal node sooner, which is what A* is designed for.
如果我看对了，球体首先以直线向右移动，因为它无法直接到达目标（路径被阻挡）。
然后，它沿着直线向目标前进。 它看起来只是对角线。
If I saw right, the sphere is moving first to the right in a straigt line, because it cannot got directly toward the goal (path is blocked).
Then, it goes in a straight line toward the goal. It only looks diagonal.
您的搜索首先是“向下”方向吗？ 这可以解释该算法。 尝试将其更改为首先查找“向上”，我敢打赌您会看到相反的行为。
Does your search look in the 'down' direction first? This might explain the algorithm. Try changing it to look 'up' first and I bet you would see the opposite behavior.
正如许多人提到的，根据您的 astar 的实现，您将看到相同启发式的不同结果。 这是因为存在平局，当两条或更多路径平局时，您的开放集排序方式将决定最终路径的外观。 如果您有一个可接受的启发式方法，您将始终获得最佳路径，但访问的节点将随着您拥有的联系数的增加而增加（相对于产生较少联系的启发式方法）。
如果您认为访问更多节点不是问题，我建议使用随机化（这是您当前接受的答案）建议。 如果您认为搜索更多节点是一个问题并且想要优化，我建议使用某种决胜局。 看来您正在使用曼哈顿距离，如果您在两个节点平局作为决胜局时使用欧几里德距离，您将获得更多到达目标的直接路径，并且您将访问更少的节点。 当然，这没有考虑到目标的陷阱或视线阻挡。
为了避免访问视线路径中具有阻挡元素的节点，我建议找到一种考虑这些阻挡元素的启发式方法。 当然，新的启发式搜索不应该比普通的 A 星搜索做更多的工作。
我建议查看我的问题，因为它可能会为这个问题产生一些想法和解决方案。
Depending on the implementation of your astar you will see different results with the same heuristic, as many people have mentioned. This is because of ties, when two or more paths tie the way you order your open set will determine the way the final path will look. You will always get the optimal path if you have an admissible heuristic, but the nodes visited will increase with the number of ties you have(relative to a heuristic producing not as many ties).
If you dont think visiting more nodes is a problem i would suggest using the randomization (which is your current accepted answer) suggestion. If you think searching more nodes is a problem and want to optimize i would suggest using some sort of tiebreaker. It seems you are using manhattan distance, if you use euclidian distance when two nodes tie as a tiebreaker you will get more straight paths to the goal and you will visit fewer nodes. This is ofcourse given no traps or block of line of sight to the goal.
To avoid visiting nodes with blocking elements in the line of sight path i would suggest finding a heuristic which takes into account these blocking elements. Ofcourse a new heuristic shouldnt do more work than a normal A star search would do.
I would suggest looking at my question as it might produce some ideas and solutions to this problem.