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

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

回答：

你需要为你的启发式函数添加一个决胜器。这里的问题是有很多路径具有相同的成本。

对于一个简单的、倾向于直线的决胜器，你可以使用叉积。也就是说，如果 S 是起点，E 是终点，X 是算法中的当前位置，你可以计算 S-E 和 X-E 的叉积，并对启发式函数添加一个惩罚，惩罚的大小取决于它偏离 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* 的优秀教程。