c# - 如何在物理引擎中有效地模拟静态矩形网格？

Question

我正在制作一个发生在大地牢中的太空射击游戏，地牢由用来定义墙壁的大矩形组成。游戏中的一切都是使用 Farseer Physics 进行物理模拟的。但是有一个问题:我希望地牢看起来足够大，但这要求我的网格中至少有 80x80 的矩形，这意味着在最坏的情况下我有 6400 个物理模拟的 body ，这不完全是性能友好，如您所料。

我的临时解决方案是将网格划分为垂直切片，这样，对于每一列，所有矩形都使用 bool 添加操作添加，然后使用生成的凹多边形创建一个主体。它稍微提高了性能，但多边形往往会变得困惑、变得不存在、阻塞通常应该可穿越的路径，甚至变得无效并导致 Farseer 崩溃。

我一直在考虑制作某种算法，以某种方式找到墙壁的最大区域并将它们合并成一个大矩形，并对较小的矩形继续这样做，直到所有孔都被填满，但我不知道如何实现这一点。这似乎是完美的解决方案，因为它可以解决性能问题以及我现在遇到的凹多边形问题。有没有人知道如何实现这样的事情？

完全停止使用物理引擎并不是解决方案，因为我游戏中的很多东西都依赖它。

编辑:这里有一个小例子，说明 body 现在的样子:(每个数字都是一个 body )

这就是我希望他们成为的样子:

Answer 1

我可能没有正确理解这个问题，但让我提出一个我认为有点暗示可以解决您的问题的算法。

您的问题始于矩形贪婪，其中正方形是自由 和非自由。从一开始，自由方 block 就是我们要用来 build 墙壁的方 block ，非自由方 block 是空心空间。

1. 为每个自由方 block 做一个围绕那个方 block 的扩展，看看那个方 block 可以属于的最大区域是多少。通过扩展，我的意思是从那个方 block 向各个方向延伸，同时可以用自由方 block build 一个区域。将这个最大的区域与给定的自由方 block 相关联。
2. 选择关联面积最大的方 block ，并通过围绕该方 block 扩展来构建合并墙。属于此合并的方 block 被标记为非自由。如果没有更多的空闲方 block ，您就完成了，否则转到第 1 步。

完成后，您应该将尽可能大的墙 block 组合在一起。

澄清一下，通过围绕一个自由正方形展开，我的意思是从给定的正方形开始，在所有可用方向上获取可以构建的假设最大矩形。

对于矩形 n*m 矩阵，此算法的复杂度直观地约为 O(n*n*m*m)。实际上，我认为您的数据会很快。请注意，此算法不提供最少数量的对象，而是最大化所有区域的总和(根据您的问题)。我觉得最小化物体总数的问题在复杂性方面要困难得多。