如何找到最“自然”的东西？ 使用 A 星 (A*) 的直达航线
我已经在 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| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
有一种正式接受的方法可以使路径看起来更合理而不仅仅是数学上正确？
I have implemented the A* algorithm in AS3 and it works great except for one thing.
Often the resulting path does not take the most “natural” or smooth route to the target.
In my environment the object can move diagonally as inexpensively as it can move horizontally or vertically.
Here is a very simple example; the start point is marked by the S, and the end (or finish) point by the F.
| | | | | | | | | |
|S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
As you can see, during the 1st round of finding, nodes [0,2], [1,2], [2,2] will all be added to the list of possible node as they all have a score of N.
The issue I’m having comes at the next point when I’m trying to decide which node to proceed with. In the example above I am using possibleNodes[0] to choose the next node. If I change this to possibleNodes[possibleNodes.length-1] I get the following path.
| | | | | | | | | |
|S| | | | | | | | |
| |x| | | | | | | |
| | |x| | | | | | |
| | | |x| | | | | |
| | |x| | | | | | |
| |x| | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
And then with possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1]
| | | | | | | | | |
|S| | | | | | | | |
|x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
All these paths have the same cost as they all contain the same number of steps but, in this situation, the most sensible path would be as follows...
| | | | | | | | | |
|S| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|x| | | | | | | | |
|F| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
Is there a formally accepted method of making the path appear more sensible rather than just mathematically correct?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您需要在启发式函数中添加决胜局。 这里的问题是有许多路径具有相同的成本。
对于有利于直接路线的简单决胜局，您可以使用叉积。 即，如果 S 是开始，E 是结束，X 是算法中的当前位置，您可以计算 SE 和 XE 的叉积，并在启发式中偏离 0 进一步增加惩罚（= 直接路线）。
在代码中：
另请参阅 http://theory.stanford.edu/~amitp/ GameProgramming/Heuristics.html#S12，这是关于 A* 的优秀教程。
You need to add a Tie-breaker to your heuristic function. The problem here is that there are many paths with the same costs.
For a simple Tie-breaker that favors the direct route you can use the cross-product. I.e. if S is the start and E is the end, and X is the current position in the algorithm, you could calculate the cross-products of S-E and X-E and add a penalty to the heuristic the further it deviates from 0 (= the direct route).
In code:
See also http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12, which is an excellent tutorial about A* in general.
如果您希望路径看起来自然，则需要确保您的成本与笛卡尔坐标系上的长度相对应。 这意味着对角移动的成本应该是垂直或水平移动成本的 sqrt(2) 倍。
If you want paths that look natural, you need to make sure that your costs correspond to the length on a cartesian coordinate system. That means the cost of moving diagonally should be sqrt(2) times the cost of moving vertically or horizontally.
您可以将“控制工作量”添加到每个方格的成本计算中。 演员会尽量不要过度转动或改变方向，因为这会增加路径的成本：
http://angryee.blogspot.com/2009/03/better-pathfinding.html
You can add 'control effort' to the cost calculations for each square. The actor will try not to turn or change direction too much as that will add a cost to the path:
http://angryee.blogspot.com/2009/03/better-pathfinding.html
如果我没记错的话，这样做的诀窍是向成本函数添加一个额外的参数（对于相邻节点之间的每一步，或者您的情况下的方块），惩罚转动比正常情况稍多一些（例如，对于二边形移动来说，相对成本大于
sqrt(2)）。 现在，平滑路径和实际降低路径的最优性（延长路径）之间可能存在一条微妙的界限，但是，您将无法以任何方式避免这种情况。 您需要针对自己的应用程序发现某种权衡，而这只能通过测试才能真正实现。我相信，游戏开发网站上有一篇文章详细说明了如何做到这一点，但我目前似乎找不到它。 无论如何，尝试一下你的成本函数，看看你会得到什么结果 - 我很确定这就是要走的路。
If I remember correctly, the trick to this is to add an extra parameter to the cost function (for every step between adjacent nodes, or squares in your case) that penalises turns slightly more than normal (for example, having a relative cost of greater than
sqrt(2)for digonal moves). Now, there's probably a fine line between smoothing out the path and actually decreasing the optimality of the route (elongating it), however, and you're not going to be able to avoid this in any way. There's a certain trade-off you'll need to discover specific to your own application, and this can only really be achieved by testing.There was an article on a game dev site, I believe, that detailed exactly how this could be done, but I can't seem to find it at the moment. Have a play around with your cost function anyway and see what results you get - I'm pretty sure that's the way to go.
什么更“明智”？ 直一点？ 如果算法要对此采取任何措施，您需要对其进行正确的量化。
由于对角移动与水平/垂直移动一样便宜，因此根据 A* 可用的所有标准，所有路径都是等效的。 如果您想要一条更“合理”的路径，您需要告诉算法某些路径比其他路径更理想，有效地将水平/垂直权重设置为比对角线“更好”。 据我所知，这将改变您的环境参数。
What is more 'sensible'? Straighter? You need to quantify it properly if the algorithm is going to do anything about it.
Since moving diagonally is as inexpensive as moving horizontally/vertically, all the paths are equivalent according to all the criterion available to A*. If you want a more 'sensible' path, you need to tell the algorithm that some paths are more desirable than others, effectively weighting horizontal/vertical as 'better' than diagonal. As far as I can see, that would be altering the parameters of your environment.