5

在所有类型的游戏中都使用了哪些寻路算法？（无论如何，在角色移动的所有类型中）Dijkstra 曾经使用过吗？我并不是真的想编写任何代码。只是做一些研究，但如果你粘贴伪代码或其他东西，那很好（我能理解 Java 和 C++）。

我知道 A* 就像在 2D 游戏中使用的算法。这很好，但不是基于网格的 2D 游戏呢？诸如帝国时代或林克的觉醒之类的东西。没有不同的方形空间可供导航，那么它们是做什么的？

3D游戏有什么作用？我读过这个东西http://www.ai-blog.net/archives/000152.html，我听说这是这个主题的一个伟大的权威，但它并没有真正解释如何，一旦网格被设置，路径查找完成。如果他们使用的是 A*，那么在 3D 环境中如何完成类似的操作？样条曲线究竟如何用于圆角？

4

1 回答 1

8

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

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

最后，A* 实际上是 3D 游戏和 2D 游戏中使用的算法。让我们看看 A* 是如何工作的：

  1. 开始时，您知道当前位置和目标位置的坐标。您对到目的地的距离做出了乐观的估计，例如起始位置和目标之间的直线长度。
  2. 考虑图中的相邻节点。如果其中一个是您的目标（或包含它，在导航网格的情况下），您就完成了。
  3. 对于每个相邻节点（在导航网格的情况下，这可能是多边形的几何中心或某种其他类型的中点），估计沿着那里行驶的相关成本作为两个度量的总和：路径的长度你已经走了这么远，另一个乐观的估计仍然必须走完的距离。
  4. 将上一步中的选项按其估计成本以及您之前考虑过的所有选项进行排序，然后选择估计成本最低的选项。从第 2 步开始重复。

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

有一些密切相关的算法可以处理标准 A* 搜索中的某些问题。例如，递归最佳优先搜索 (RBFS) 和简化的内存有界 A* (SMA*) 需要较少的内存，而实时学习 A* (LRTA*) 允许代理在计算完整路径之前移动。我不知道这些算法是否真的用在现在的游戏中。

至于拐角的圆角，这可以通过距离线（其中拐角被圆弧替换）或任何类型的样条函数来实现全路径平滑。

此外，算法可能依赖于搜索空间上的梯度（空间中的每个点都与一个值相关联），而不是图。这些可能不适用于大多数游戏，因为它们需要更多的时间和内存，但无论如何可能会很有趣。示例包括各种爬山算法（默认为实时）和势场方法。

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

资料来源：

于 2012-04-25T23:36:31.257 回答