我已经在 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| | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
是否有一种正式接受的方法可以使路径看起来更合理,而不仅仅是在数学上正确?