artificial-intelligence - 如何使用 A-star (A*) 找到最多 “Naturally"的直达路线

Question

我已经在 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| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

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

Answer 1

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

对于支持直接路线的简单决胜局，您可以使用交叉积。 IE。如果 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* 的优秀教程。