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

Question

我正在制作一个太空射击游戏,它发生在一个大的地牢里,它由大的矩形组成,用来定义墙壁.使用Farseer Physics对游戏中的所有内容进行物理模拟.但是有一个问题:我希望地牢看起来足够大,但这需要我的网格中至少有80x80个矩形,这意味着在最坏的情况下,我有6400个物理模拟的物体,这不完全是性能友好,你可以猜到.

我的临时解决方案是在垂直切片中划分网格,这样,对于每一列,使用布尔添加操作添加所有矩形,然后使用生成的凹多边形创建一个主体.它会稍微提高性能,但是多边形容易陷入混乱,变得不存在,阻塞通常应该可以遍历的方式甚至变得无效并导致Farseer崩溃.

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

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

编辑:这是一个关于身体现在如何看起来的一个小例子:(每个数字都是一个身体)

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

Answer 1

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

你的问题始于一个矩形贪婪，其中正方形是free和non-free。从一开始，自由方块就是我们要用来建造墙壁的方块，非自由方块是空心空间。

1. 对于每个自由正方形，围绕该正方形进行扩展，看看该正方形可以属于的最大区域是多少。我所说的扩展是指从该正方形向各个方向移动，同时可以用自由正方形构建一个区域。将这个最大的区域与给定的自由正方形相关联。
2. 选择具有最大关联面积的正方形，并通过围绕该正方形扩展来构建合并墙。属于此合并的方块被标记为non-free。如果没有更多的空闲方块，则完成，否则转到步骤 1。

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

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

该算法对于矩形矩阵的复杂度n*m直观地约为O(n*n*m*m)。实际上，我认为您的数据处理起来会很快。请注意，该算法并不提供最少数量的对象，而是最大化所有区域的总和（根据您的问题）。我认为，就复杂性而言，最小化尸体总数的问题要困难得多。