9

我正在开发一个简单的基于 2d 网格的 sim 游戏，并且具有功能齐全的寻路功能。

我使用在上一个问题中找到的答案作为实现 A* 路径查找的基础。（寻路 2D Java 游戏？）。

为了真正向您展示我的要求，我需要向您展示我制作的视频屏幕截图。我只是在测试这个人将如何移动到一个位置并再次返回，这就是结果......

http://www.screenjelly.com/watch/Bd7d7pObyFo

根据方向选择不同的路径，结果出人意料。有任何想法吗？

4

9 回答 9

3

如果您正在寻找一个简单的解决方案，我可以建议一些随机化吗？

我的意思是：在 cokeandcode 代码示例中，存在生成“后继状态”（使用 AI 术语）的嵌套循环。我指的是它围绕“当前”状态在 3x3 方格上循环的点，在桩上添加新的位置来考虑。

一个相对简单的修复将（应该:)）稍微隔离该代码，并让它在处理步骤的其余部分之前生成一个节点链表。然后 Containers.Shuffle（或者是 Generics.Shuffle？）那个链表，并在那里继续处理。基本上，有一个例程说“createNaiveNeighbors(node)”，它返回一个 LinkedList = {(node.x-1,node.y), (node.x, node.y-1)...} （请原谅pidgin Java，我正在尝试（但总是失败）简短。

然而，一旦你建立了链表，你应该能够做一个“for (Node n : myNewLinkedList)”而不是

for (int x=-1;x<2;x++) {

    for (int y=-1;y<2;y++) {

并且仍然使用完全相同的正文代码！

理想情况下，这样做会“改变”考虑的节点顺序，并创建更接近对角线的路径，但不必更改启发式。这些路径仍然是最有效的，但通常更接近对角线。

当然，不利的一面是，如果您多次从 A 到 B，则可能会采取不同的路径。如果这是不可接受的，您可能需要考虑进行更彻底的修改。

希望这可以帮助！-阿戈尔

于 2009-07-25T18:57:36.843 回答
2

两条路径的长度相同，因此该算法的工作正常——它正在寻找一条最短路径。但是 A* 算法没有指定它将采用哪条最短路径。实现通常采用“第一”最短路径。如果没有看到你的，就不可能知道确切的原因，但是如果你每次都想要相同的结果，你将不得不添加某种优先级规则（这样你想要的路径首先出现在搜索中）。

于 2009-07-25T16:52:36.237 回答
2

原因是您希望算法走的路径。
我不知道您的 A* 使用的启发式方法，但在第一种情况下，它必须先到达隧道的尽头，然后规划从隧道尽头到目标的方式。

在第二种情况下，最简单的移动到目标是向下直到它撞到墙壁，然后它计划从墙壁到目标的路径。

在方块世界的情况下，我所知道的大多数 A* 都使用视线启发式或曼哈顿距离。这种启发式方法为您提供了最短的方式，但如果障碍物迫使您走不同于视线的方式，则方式取决于您的起点。
该算法将尽可能长时间地进入视线。

于 2009-07-25T16:53:12.897 回答
2

原因实际上很简单：路径将始终尝试具有最低的启发式，因为它以贪婪的方式进行搜索。更接近目标是最佳路径。

如果您允许对角线移动，则不会发生这种情况。

于 2009-07-25T17:20:02.000 回答
1

最有可能的答案是，直接向南走最接近目标。相反，这不是一个选择，因此它分段优化子路径，结果是交替向上/交叉移动被认为是最好的。

如果您希望它沿着对角线返回，您将必须确定沿路径的一些兴趣点（例如隧道口）并在您的启发式中考虑这些点。或者，您可以通过重新计算通过兴趣点的任何子路径，在您的算法中考虑它们。

过去，他们过去常常对地图进行预编译的静态分析，并在阻塞点放置寻路标记。根据您的最终目标是什么，这也可能是一个好主意。

如果您真的有兴趣了解正在发生的事情，我建议您渲染 A* 搜索的步骤。鉴于您的问题，这可能会让您大开眼界。

于 2009-07-25T17:08:35.283 回答
1

在每种情况下，它都更喜欢更快地接近其目标节点的路径，这就是 A* 的设计目的。

于 2009-07-25T18:27:08.387 回答
0

如果我没看错，球体首先直线向右移动，因为它不能直接朝向目标（路径被阻挡）。然后，它朝着目标直线前进。它只看起来对角线。

于 2009-07-25T16:53:46.483 回答
0

您的搜索是否首先朝“向下”方向寻找？这可以解释算法。尝试将其更改为首先查找“向上”，我敢打赌您会看到相反的行为。

于 2009-07-25T17:08:32.867 回答
0

正如许多人所提到的，根据您的 astar 的实施，您将使用相同的启发式方法看到不同的结果。这是因为有关联，当两条或更多路径关联时，您订购开放集的方式将决定最终路径的外观。如果您有一个可接受的启发式算法，您将始终获得最佳路径，但是访问的节点将随着您拥有的联系数而增加（相对于产生较少联系的启发式算法）。

如果您不认为访问更多节点是一个问题，我建议您使用随机化（这是您当前接受的答案）建议。如果您认为搜索更多节点是一个问题并且想要优化我会建议使用某种决胜局。似乎您正在使用曼哈顿距离，如果您在两个节点作为决胜局平局时使用欧几里德距离，您将获得更多通往目标的直线路径，并且您将访问更少的节点。这当然没有给目标设置陷阱或阻挡视线。

为了避免在视线路径中访问具有阻塞元素的节点，我建议找到一种考虑到这些阻塞元素的启发式方法。当然，新的启发式算法不应该比普通的 A 星搜索做更多的工作。

I would suggest looking at my question as it might produce some ideas and solutions to this problem.

于 2010-04-06T14:45:03.577 回答