如何使用A-star(A*)找到最"自然"的直接路线

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.这里的问题是有许多路径具有相同的成本.

对于有利于直接路线的简单连接器,您可以使用交叉产品.即如果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*的优秀教程.