7

在星际争霸之类的游戏中，您可以在一张地图中拥有多达 200 个单位（针对玩家）。

有小地图，也有大地图。

例如，当你抓住 50 个单位并告诉他们去地图的另一边时，一些算法会启动，他们会找到穿过障碍物（河流、山丘、岩石和其他）的路径。

我的问题是您是否知道游戏不会因为您有 50 条路径要计算而变慢。与此同时，还会发生其他事情，比如制造无人机收集矿物等。如果地图很大，它应该更难更慢。

所以即使算法很好，100个单位也需要一些时间。

你知道这是如何工作的，也许算法与其他游戏相似。

正如我所说，当您告诉单位移动时，您没有看到计算路径的任何延迟 - 它们立即开始运行到目的地。

问题是它们如何使单位通过最短路径但又快。

大部分游戏没有延迟（星际争霸、魔兽争霸等）

谢谢你。

4

2 回答 2

7

我想它只需要细分问题并记住结果。示例：2 个单位。Unit1 从 A 到 C，但最短路径经过 B。 Unit2 从 B 到 C。B 到 C 只需计算一次，两者都可以重用。见https://en.m.wikipedia.org/wiki/Dynamic_programming

在这个 wikipedia 页面中，它特别提到了 dijkstra 的路径查找算法，该算法通过细分问题并存储要重用的结果来工作。

这里还有一个非常漂亮的替代方案http://www.gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php它考虑了障碍物等动态因素并且仍然表现良好（视频演示：https： //www.youtube.com/watch?v=z4W1zSOLr_g）。

另一种有趣的技术，采用完全不同的方法：计算从目标位置到地图上每个点的最短路径：请参阅此处的完整说明：https ://www.youtube.com/watch?v=Bspb9g9nTto - 虽然这个对于大地图效率低下

于 2018-12-05T23:46:49.023 回答
5

首先，100 个单位并不是一个很大的数字，现代计算机上的寻路速度足够快，它不是一个大的资源汇。即使在较旧的游戏中，也进行了优化以使其更快，并且您可以看到该单元有时会丢失或卡住，而像 A* 这样的通用算法不应该真正发生这种情况。

如果地图没有改变地图，您可以对其进行预处理以构建一组表示地图区域的节点。例如，如果地图是由一座窄桥连接的两个岛屿，则将存在三个“区域”——岛屿 1、岛屿 2、桥梁。实际上，您可能会使用一些图形算法而不是手动执行此操作。例如：

  1. 用距离最近的不可通过的瓷砖对每块瓷砖进行评分。
  2. 将分数高于阈值的所有相邻图块放在同一区域中。
  3. 完成后，逐渐从所有区域向外扩展以包含低分图块。
  4. 制作一个新图，其中每个区域-区域交叉点都是一个节点，并计算它们之间的最短路径。

那么你的寻路算法就变成了两个阶段：

  1. 找出单位所在的地区。
  2. 找出目标所在的区域。
  3. 如果区域不同，首先使用上面的区域图计算到目标区域的最短路径。
  4. 一旦进入同一区域，在平铺网格上正常计算路径。

在遥远的位置之间移动时，这应该会更快，因为您现在正在搜索少数节点（在区域图上）加上相对较少数量的图块，而不是组成这些区域的数百个图块。例如，如果我们有 3 个岛 A、B、C，分别有桥 1 和 2 连接 AB 和 BC，那么从 A 移动到 C 的单元并不需要每次都搜索 B，它们只关心最短路径从桥 1 到桥 2。如果你有很多岛屿，这真的可以加快速度。

当然，问题是区域可能会由于例如建筑物阻塞路径或单元暂时阻塞通道而发生变化。解决方案取决于您的想象力。如果地图在您的游戏中很少更改，您可以尝试在每次更改地图时仔细更新区域图。或者你可以让单位天真地信任区域图，直到他们遇到障碍。在某些游戏中，您会看到后者特别糟糕的情况，因为即使在被围墙关闭后，单位仍会继续向山谷奔跑，并且只有在撞到墙后才会转身并绕行。我认为当单位阻挡狭窄的路径时，最初的星际争霸会出现这个问题。他们会尝试绕一段很长的弯路，而不是等待人群腾出一座桥。

还有一些算法可以在不显式构建区域图的情况下完成类似的优化，例如JPS大致以这种方式工作。

于 2018-12-06T21:04:54.520 回答