游戏中的路径规划

Question

5

在各种类型的游戏中，都使用了哪些寻路算法？（任何角色移动类型的游戏）是否会使用Dijkstra算法？我不想编写任何代码，只是做一些研究，如果你能粘贴一些伪代码之类的东西，那就太好了（我能理解Java和C++）。

我知道A*是在2D游戏中使用的算法。这很棒，但是对于不基于网格的2D游戏呢？像帝国时代或者塞尔达传说的觉醒。没有明显的方形空间来导航，那么他们该怎么做呢？

3D游戏怎么办？我读过这个东西http://www.ai-blog.net/archives/000152.html，听说它是这个主题的绝佳权威，但它并没有真正解释路径规划是如何完成的，如果是使用A*，那么在3D环境中如何实现？曲线怎么处理转角？

- Pojo

2

这个问题可以在游戏开发网站上提问。 - Matthias

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Julian · Accepted Answer

Dijkstra算法计算从起始位置可到达的图中所有节点的最短路径。对于现代游戏来说，这既是不必要的，也是非常昂贵的。

您区分了2D和3D，但值得注意的是，对于任何基于图的算法，搜索空间的维度数量并没有影响。您链接的网页讨论了航点图和导航网格；两者都是基于图的，原则上可以在任意维度中工作。虽然没有“不同的正方形空间可供移动”，但是在AI可以移动到并由游戏设计师精心布置的空间中存在离散的“插槽”。

总之，在3D游戏中，A*实际上与在2D游戏中使用的一样。让我们看看A*如何工作：

开始时，你知道当前位置和目标位置的坐标。你对到达目的地的距离进行了乐观的估计，例如从起点到目标的直线长度。

考虑图中相邻的节点。如果其中一个是你的目标（或者在导航网格的情况下包含它），那么你就完成了。

对于每个相邻节点（在导航网格的情况下，这可能是多边形的几何中心或其他类型的中点），将沿着该节点旅行的相关成本估计为两个度量的总和：迄今为止已经行进路径的长度和仍需覆盖的另一个乐观估计距离。

按照先前考虑过的所有选项以及它们的估计成本对选项进行排序，并选择估计成本最低的选项。从步骤2重复。

这里有一些我没有讨论的细节，但应该足以看出A*算法基本上独立于空间维数的数量。您也应该能够看出为什么这适用于连续空间。

有一些与标准A*搜索中特定问题相关的算法。例如，递归最佳优先搜索（RBFS）和简化内存受限A*（SMA*）需要更少的内存，而学习实时A*（LRTA*）允许代理在计算完整路径之前移动。我不知道这些算法是否实际应用于当前的游戏。

至于圆角的舍入，可以使用距离线（其中角落被替换为圆弧），或者使用任何类型的spline函数进行完整路径平滑处理。

此外，还可能存在依赖于搜索空间梯度（其中空间中的每个点都与一个值相关联）而不是图形的算法。这些算法可能在大多数游戏中并未应用，因为它们需要更多的时间和内存，但了解它们仍然很有趣。例如各种爬山算法（默认情况下是实时的）和势场方法。

存在从连续空间程序化地获得图形的方法，例如单元分解、 Voronoi骨架化和概率路线图骨架化。前者将产生与导航网格兼容的东西（尽管可能很难使其与手工制作的导航网格同样有效），而后两者产生的结果将更像航路图。所有这些方法以及潜在场方法和A*搜索都与机器人相关。

来源：