如何找到最“自然”的直接使用A星（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

您需要一个僵局添加到您的启发作用。这里的问题是，有具有相同的成本许多路径。

有关一个简单的同分有利于直接路由可以使用叉积。即如果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 *优异的教程。

Answer 2

如果你想看起来自然路径，你需要确保你的成本对应长度在笛卡尔坐标系。这意味着对角线移动的成本应SQRT垂直或水平移动的（2）倍的成本。

Answer 3

您可以添加“控制工作”的成本计算为每平方米。演员会尽量不转或改变方向太多，因为这将成本的路径添加到：

http://angryee.blogspot.com/2009/03/better -pathfinding.html

Answer 4

如果正确地记得特技到这是一个额外的参数添加到成本函数（针对你的情况相邻节点，或正方形之间的每一步），其惩罚匝比正常略多（例如，具有大于sqrt(2)为二角移动的相对成本）。现在，有可能是不过平滑路径，实际上降低了线路的最优（延长它），一线之隔，而你不会是能够避免这种以任何方式。有一定的权衡，你需要去发现具体到自己的应用程序，而这只能通过真正的测试来实现。

有是在游戏开发网站的一篇文章，我相信，详细似乎究竟如何可以这样做，但我不能在此刻找到它。与你的成本函数围绕发挥无论如何，看看有什么结果，你得到的 - 我敢肯定这是要走的路。

Answer 5

更重要的是“明智”？直？您需要正确量化它，如果算法是打算做任何事情。

由于斜向移动是水平/垂直移动作为廉价，所有的路径根据所有可用到A *的标准是等效的。如果您想更多的“明智”的路径，你需要告诉算法一些路径比其他人更可取的，有效的加权水平/垂直为比对角线“更好”。据我所看到的，这将是改变环境的参数。