游戏中的最短路径（星际争霸示例）
Shortest path in games (StarCraft example)
在像星际争霸这样的游戏中，一张地图中最多可以有 200 个单位（对于玩家）。
有小地图也有大地图
例如，当你抓住 50 个单位并告诉他们去地图的另一边时，一些算法会启动，他们会找到穿过障碍物（河流、山丘、岩石和其他）的路径。
我的问题是你知道游戏是如何不减慢的，因为你有 50 条路径要计算。与此同时，其他事情也发生了，比如收集矿物的无人机被制造出来等等。如果地图很大，它应该更难更慢。
所以即使算法很好，100个单位也需要一些时间。
你知道这是怎么工作的吗？也许算法和其他游戏类似。
正如我所说，当你告诉单位移动时，你没有看到计算路径的任何延迟 - 它们立即开始 运行 目的地。
问题是他们如何使单位通过最短路径但速度很快。
绝大部分游戏（星际争霸、魔兽争霸等）无延迟
谢谢。
我猜它只是需要细分问题并记住结果。示例：2 个单元。单元 1 从 A 到 C，但最短路径经过 B。单元 2 从 B 到 C。
B 到 C 只需要计算一次，并且可以被两者重复使用。
参见 https://en.m.wikipedia.org/wiki/Dynamic_programming
在此维基百科页面中，它特别提到了 dijkstra 的路径查找算法，该算法通过细分问题和存储结果以供重复使用。
这里还有一个很好看的替代品http://www.gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php where it takes into account dynamic stuff like obstacles and still performs very well (video demo: https://www.youtube.com/watch?v=z4W1zSOLr_g)。
另一个有趣的技术，采用完全不同的方法：
计算从目标位置到地图上每个点的最短路径：请参阅此处的完整说明：https://www.youtube.com/watch?v=Bspb9g9nTto - 虽然这对于大地图来说效率低下
首先 100 个单位并不是一个很大的数字，寻路在现代计算机上已经足够快了，它不是一个很大的资源池。即使在较旧的游戏中，也进行了优化以使其更快，您会看到该单元有时会丢失或卡住，这对于像 A* 这样的通用算法来说应该不会发生。
如果地图不改变地图，您可以对其进行预处理以构建一组代表地图区域的节点。例如，如果地图是由一座窄桥连接的两个岛屿，则将有三个 "regions" - 岛 1、岛 2、桥。实际上，您可能会使用某种图形算法来执行此操作，而不是手动执行。例如：
- 根据与最近的无法通行的方块的距离对每个方块进行评分。
- 将得分高于阈值的所有相邻图块放在同一区域。
- 完成后，从所有区域逐渐向外扩展以包含低分块。
- 制作一个新图，其中每个区域-区域交点是一个节点，并计算它们之间的最短路径。
那么你的寻路算法就变成了两个阶段：
- 查找单位所在的区域。
- 找到目标所在的区域。
- 如果不同区域，首先使用上面的区域图计算到目标区域的最短路径。
- 进入同一区域后，正常计算瓷砖网格上的路径。
在相距较远的位置之间移动时，这应该会快得多，因为您现在搜索的是少数节点（在区域图上）加上相对较少的图块，而不是构成这些区域的数百个图块.例如，如果我们有 3 个岛 A、B、C，桥 1 和 2 分别连接 A-B 和 B-C，那么从 A 移动到 C 的单位实际上不需要每次都搜索所有 B，他们只关心最短路线从 1 号桥到 2 号桥。如果你有很多岛屿，这真的可以加快速度。
当然问题是区域可能会因为例如建筑物挡路或单位暂时阻塞通道而发生变化。对此的解决方案取决于您的想象力。如果地图在您的游戏中很少更改，您可以尝试在每次更改地图时仔细更新区域图。或者你可以让单元天真地相信区域图，直到它们碰到障碍物。在某些游戏中，您会看到后者的情况特别糟糕，因为一个单位即使在被围墙隔离后仍会继续 运行 朝向山谷，并且只有在撞到墙壁后它才会掉头并绕行。我认为当单位挡住狭窄的路径时，最初的星际争霸有这个问题。他们会尝试绕很长的路，而不是等待人群腾出一座桥。
还有一些算法可以在不显式构建区域图的情况下完成类似的优化，例如 JPS 大致就是这样工作的。
在像星际争霸这样的游戏中，一张地图中最多可以有 200 个单位（对于玩家）。
有小地图也有大地图
例如，当你抓住 50 个单位并告诉他们去地图的另一边时，一些算法会启动，他们会找到穿过障碍物（河流、山丘、岩石和其他）的路径。
我的问题是你知道游戏是如何不减慢的，因为你有 50 条路径要计算。与此同时，其他事情也发生了，比如收集矿物的无人机被制造出来等等。如果地图很大，它应该更难更慢。
所以即使算法很好，100个单位也需要一些时间。
你知道这是怎么工作的吗？也许算法和其他游戏类似。
正如我所说，当你告诉单位移动时，你没有看到计算路径的任何延迟 - 它们立即开始 运行 目的地。
问题是他们如何使单位通过最短路径但速度很快。
绝大部分游戏（星际争霸、魔兽争霸等）无延迟
谢谢。
我猜它只是需要细分问题并记住结果。示例：2 个单元。单元 1 从 A 到 C，但最短路径经过 B。单元 2 从 B 到 C。 B 到 C 只需要计算一次，并且可以被两者重复使用。 参见 https://en.m.wikipedia.org/wiki/Dynamic_programming
在此维基百科页面中，它特别提到了 dijkstra 的路径查找算法，该算法通过细分问题和存储结果以供重复使用。
这里还有一个很好看的替代品http://www.gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php where it takes into account dynamic stuff like obstacles and still performs very well (video demo: https://www.youtube.com/watch?v=z4W1zSOLr_g)。
另一个有趣的技术，采用完全不同的方法： 计算从目标位置到地图上每个点的最短路径：请参阅此处的完整说明：https://www.youtube.com/watch?v=Bspb9g9nTto - 虽然这对于大地图来说效率低下
首先 100 个单位并不是一个很大的数字，寻路在现代计算机上已经足够快了，它不是一个很大的资源池。即使在较旧的游戏中，也进行了优化以使其更快，您会看到该单元有时会丢失或卡住，这对于像 A* 这样的通用算法来说应该不会发生。
如果地图不改变地图，您可以对其进行预处理以构建一组代表地图区域的节点。例如，如果地图是由一座窄桥连接的两个岛屿，则将有三个 "regions" - 岛 1、岛 2、桥。实际上，您可能会使用某种图形算法来执行此操作，而不是手动执行。例如：
- 根据与最近的无法通行的方块的距离对每个方块进行评分。
- 将得分高于阈值的所有相邻图块放在同一区域。
- 完成后，从所有区域逐渐向外扩展以包含低分块。
- 制作一个新图，其中每个区域-区域交点是一个节点，并计算它们之间的最短路径。
那么你的寻路算法就变成了两个阶段：
- 查找单位所在的区域。
- 找到目标所在的区域。
- 如果不同区域，首先使用上面的区域图计算到目标区域的最短路径。
- 进入同一区域后，正常计算瓷砖网格上的路径。
在相距较远的位置之间移动时，这应该会快得多，因为您现在搜索的是少数节点（在区域图上）加上相对较少的图块，而不是构成这些区域的数百个图块.例如，如果我们有 3 个岛 A、B、C，桥 1 和 2 分别连接 A-B 和 B-C，那么从 A 移动到 C 的单位实际上不需要每次都搜索所有 B，他们只关心最短路线从 1 号桥到 2 号桥。如果你有很多岛屿，这真的可以加快速度。
当然问题是区域可能会因为例如建筑物挡路或单位暂时阻塞通道而发生变化。对此的解决方案取决于您的想象力。如果地图在您的游戏中很少更改，您可以尝试在每次更改地图时仔细更新区域图。或者你可以让单元天真地相信区域图，直到它们碰到障碍物。在某些游戏中，您会看到后者的情况特别糟糕，因为一个单位即使在被围墙隔离后仍会继续 运行 朝向山谷，并且只有在撞到墙壁后它才会掉头并绕行。我认为当单位挡住狭窄的路径时，最初的星际争霸有这个问题。他们会尝试绕很长的路，而不是等待人群腾出一座桥。
还有一些算法可以在不显式构建区域图的情况下完成类似的优化，例如 JPS 大致就是这样工作的。