algorithm - 大型 RTS map 上的 FlowField 寻路

Question

在构建大型 map RTS 游戏时，我的团队在寻路方面遇到了一些性能问题。

A* 显然效率低下，原因不仅在于寻找路径时的卡顿，还在于大量单元同时移动的处理成本。

经过研究，显而易见的解决方案是使用 FlowField 寻路，这是目前 RTS 游戏的行业标准。

我们在创建基本算法后遇到的问题是 map 非常大，需要大约 766 x 485 的网格。这会在计算要遵循的单位的流场时造成明显的处理卡住或滞后。

有没有人以前经历过这种情况，或者有任何关于如何使流场更有效率的解决方案？我尝试了以下方法:

• 在列表创建时将流场添加到列表中并在以后引用(创建后即可工作，但创建时明显滞后。)
• 在游戏开始前处理流场并引用列表(由于单元格数量过多，这根本行不通。)
• 根据最远的选定单位和目标点之间的距离创建网格(适用于短距离，不适用于从 map 的一端移动到另一端)。

我正在考虑将 map 拆分成多个流场，但我正在尝试弄清楚如何让它们从一个场移动到另一个场。

对此有什么建议吗？

提前致谢!

Answer 1

也许这个回答有点晚了。既然你提到这是一个大型的RTS游戏，那么计算不应该局限于一个CPU核心。有一些建议可以帮助您更有效地使用流场。

1. 使用多线程为每个单元移动命令计算新的流场

2. 分组单元，使同一命令组中的所有单元共享相同的流场

3. 对流场网格进行分区，因此您只需更新路径中有修改的任何分区(新建筑/移动单元)

4. 预烘焙流场网格槽成本:您预烘焙网格的基本成本(基于环境或其他在游戏过程中不会改变的静态值)。

5. 划分，例如你有 766 x 485 的 map ，将其设置为 800 * 500，按照建议 3 将其分成 100 * 80 * 50 个分区。

   您有一个包含 10 * 10 = 100 个槽的网格，使用初始流场图(不考虑任何游戏单元)创建有向图 ( https://en.wikipedia.org/wiki/Graph_theory )，并使用 A* 算法在游戏开始前搜索流场网格，让您知道所有分区之间的联系。

   对于每个新的流场，仅使用在图表中通过简单的 A* 搜索标记的分区构建流场。然后如果 A* 给出的路由的一个节点完全被阻止而无法到达下一个节点，则使用替代路由(将节点标记为被阻止并在此 graph 中再次执行 A*)

6.缓存，保存step.5的流场结果以供进一步使用(相同的单位从家里生成并前往敌方基地。相同的分区路线。如果路径有任何变化则使缓存无效，并且仅使缓存无效首先改变分区，检查这个分区是否仍然连接到其他边，然后只在分区内进行微小的更改)

1. 运行时延迟更新单位的命令。如果 map 足够大。立即将单元移动到下一个分区，而不使用流场，(先使用 A* 搜索 10*10 图以获得下一个分区)。在此移动期间，在后台使用前面的步骤 1-6 构建流场。 (事实上​​ ，如果优化得当，您只需要几毫秒即可进行计算，然后单位会相应地更改路线。大多数时候没有区别，玩家也不会注意到任何事情。在最坏的情况下，我们最终有搜索所有patitions以获取唯一可能的路径，这只是第一次会有任何延迟，并且缓存将最小化时间，因为它是唯一的路径并且缓存将被重复使用)

2. 每隔几秒为每个命令组(在后台)重新执行一次上述构建过程，以防中间发生任何变化。

我可以使用更大的随机 map (2000*2000) 来实现这一点，而 fps 根本不会下降。

希望这对以后的任何人都有帮助。