algorithm - 单位有惯性怎么寻路？

Question

我目前正在为一个单位正在移动但具有惯性的游戏寻找路径。大多数典型的寻路算法(A*、Djikastra 等)的设计只是为了最小化路径的长度。

但是，据我所知，这些技术不适用于单位具有惯性的情况。如果单位有惯性，那么根据你想去的方向，在特定方向上离开瓷砖的成本会有很大差异。

例如，如果您从东方进入方 block ，则离开北方方 block 的成本明显高于从南方进入方 block 的成本。 (在前一个示例中，您必须减速才能停止东西方向的速度，而在后一个示例中，您可以直接通过。)

系统具有惯性这一事实意味着为了转弯，您可能必须在转弯之前减速。迄今为止我最好的想法是计算减速所需的额外时间，然后将其添加到移动的启发式成本中。然而，这似乎意味着您永远无法将图 block 添加到封闭列表中，因为从另一个方向进入可能会从根本上改变移动成本。

那么，有什么办法可以解决寻路中的惯性问题吗？

Answer 1

创建一个图，其顶点是 tile+inertia 的各种组合，然后在该图中执行正常的寻路算法。