4

我已经在 AS3 中实现了 A* 算法，它工作得很好，除了一件事。生成的路径通常不会采用最“自然”或最顺畅的路线到达目标。在我的环境中，对象可以像水平或垂直移动一样便宜地沿对角线移动。这是一个非常简单的例子；起点用 S 标记，终点（或终点）用 F 标记。

 | | | | | | | | | |
 |S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

如您所见，在第一轮查找过程中，节点 [0,2]、[1,2]、[2,2] 都将被添加到可能节点列表中，因为它们的得分均为 N。当我试图决定继续使用哪个节点时，我遇到的问题出现在下一点。在上面的示例中，我使用 possibleNodes[0] 来选择下一个节点。如果我将其更改为 possibleNodes[possibleNodes.length-1] 我得到以下路径。

 | | | | | | | | | |
 |S| | | | | | | | |
 | |x| | | | | | | |
 | | |x| | | | | | |
 | | | |x| | | | | |
 | | |x| | | | | | |
 | |x| | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

然后使用 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1]

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

所有这些路径都具有相同的成本，因为它们都包含相同数量的步骤，但在这种情况下，最明智的路径如下......

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

是否有一种正式接受的方法可以使路径看起来更合理，而不仅仅是在数学上正确？

4

5 回答 5

10

您需要在启发式函数中添加一个 Tie-breaker。这里的问题是有许多路径具有相同的成本。

对于有利于直接路由的简单决胜局，您可以使用叉积。即，如果 S 是开始，E 是结束，并且 X 是算法中的当前位置，您可以计算 SE 和 XE 的叉积，并在启发式中添加惩罚，它离 0 越远（= 直接路线）。

在代码中：

 dx1 = current.x - goal.x
 dy1 = current.y - goal.y
 dx2 = start.x - goal.x
 dy2 = start.y - goal.y
 cross = abs(dx1*dy2 - dx2*dy1)
 heuristic += cross*0.001

另请参阅http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12，这是一个关于 A* 的优秀教程。

于 2009-05-10T16:44:21.440 回答
4

如果您想要看起来自然的路径，您需要确保您的成本对应于笛卡尔坐标系上的长度。这意味着对角移动的成本应该是 sqrt(2) 乘以垂直或水平移动的成本。

于 2009-05-10T16:46:48.927 回答
2

您可以在每个方格的成本计算中添加“控制努力”。演员将尽量不要过度转向或改变方向，因为这会增加路径的成本：

http://angryee.blogspot.com/2009/03/better-pathfinding.html

于 2009-05-27T13:16:40.023 回答
1

如果我没记错的话，这样做的诀窍是在成本函数中添加一个额外的参数（对于相邻节点之间的每一步，或者在您的情况下为正方形），它会比正常情况稍微多一些（例如，相对成本更大比sqrt(2)对角线移动）。现在，在平滑路径和实际降低路径的最优性（延长它）之间可能有一条细线，但是您将无法以任何方式避免这种情况。您需要发现特定于您自己的应用程序的某种权衡，而这只能通过测试来实现。

我相信在游戏开发网站上有一篇文章详细说明了如何做到这一点，但我目前似乎找不到。无论如何都要玩弄你的成本函数，看看你得到了什么结果——我很确定这是要走的路。

于 2009-05-10T16:51:16.800 回答
0

什么更“明智”？更直？如果算法要对它做任何事情，你需要正确地量化它。

由于对角线移动与水平/垂直移动一样便宜，因此根据 A* 可用的所有标准，所有路径都是等效的。如果您想要一条更“合理”的路径，您需要告诉算法某些路径比其他路径更可取，有效地将水平/垂直加权为“比对角线更好”。据我所知，这将改变您的环境参数。

于 2009-05-10T16:47:26.587 回答