大型RTS地图上的FlowField路径查找

Question

在构建一个大型地图RTS游戏时，我的团队在路径查找方面遇到了一些性能问题。

A*显然是低效的，因为不仅是简陋的路径查找，而且大组单元同时移动的处理成本。

经过研究，最明显的解决方案是使用FlowField搜索，这是RTS游戏的行业标准。

在创建基本算法之后，我们现在面临的问题是，地图相当大，需要一个大约766x485的网格。这会在计算单元要遵循的流场时造成明显的处理冻结或滞后。

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

在创建列表时将流场添加到列表中并在稍后引用(一旦创建就可以了，但在游戏开始和引用列表之前显然会滞后于creation.)

• Processing流场(由于单元格的数量巨大，这就不能根据所选单元与目标点之间的距离work.)

• Creating work.)

• Creating)(在很短的距离内工作，而不是从地图的一端移动到另一端)。

我想也许把地图分割成多个流场，但我想弄清楚如何让它们从一个领域转移到另一个领域。

对此有什么建议吗？

提前感谢！

Answer 1

也许这是个有点晚的回答。由于您已经提到这是一个大型的RTS游戏，那么计算不应局限于一个CPU核心。有一些建议，让您更有效地使用流场。

1. 使用多线程为每个单元移动命令

计算新的流场。

1. 组单元，以便同一命令组中的所有单元共享相同的流场

1. 划分流场网格，因此只需更新路径(新建/移动单元)中的任何分区(

)

1. 预先烘焙的流场网格槽成本:预先计算网格的基本成本(基于游戏期间不会改变的环境或其他静态值)。

1. 除法，例如，您有766 x 485映射，将其设置为800 * 500，将其划分为100 * 80 *50个分区，如建议3所述。

网格为10 * 10 =100个槽，使用初始流场映射(不考虑任何游戏单元)创建有向图 (https://en.wikipedia.org/wiki/Graph_theory)，并在游戏开始前使用A* algorihtm搜索流场网格，以便了解分区之间的所有连接。

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

6.缓存，保存第5步产生的流场以供进一步使用(同一单位从家中产卵并前往敌人基地)。相同的分区路线。如果路径中有任何更改，则使缓存失效，并且只首先使已更改的分区的缓存失效，检查此分区是否仍然连接到其他侧，然后只在分区内进行小的更改)

1. 运行时延迟更新单元的命令。如果地图够大的话。在不使用流场的情况下，立即将单元移动到下一个分区(首先使用A*搜索10*10图以获得下一个分区)。在运动的这段时间里，在背景中，使用前面的步骤1-6构建流场。(事实上，如果优化得当，您只需要几毫秒就能完成计算，那么单元就会相应地改变路线。大多数情况下没有区别，球员不会注意到任何事情。在最坏的情况下，我们最终必须搜索所有的位置才能得到唯一可能的路由，这只是第一次出现延迟，而缓存将使时间最小化，因为它是唯一的方法，缓存将被使用repeatitively)

。

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

我可以用更大的随机地图(2000*2000)来工作，而不需要fps下降。

希望这对未来的任何人都有帮助。