如何在物理引擎中有效地模拟静态矩形网格？
我正在制作一个发生在一个大地牢中的太空射击游戏，它由大矩形组成来定义墙壁。游戏中的一切都是使用 Farseer 物理进行物理模拟的。但有一个问题：我希望地下城看起来足够大，但这要求我的网格中至少有 80x80 的矩形，这意味着在最坏的情况下，我有 6400 个物理模拟身体，这并不完全是正如您可以猜到的那样，性能友好。
我的临时解决方案是将网格划分为垂直切片，以便对于每一列，使用布尔添加操作添加所有矩形，然后使用生成的凹多边形创建一个实体。它稍微提高了性能，但多边形往往会变得混乱、变得不存在、阻塞通常应该可穿越的道路，甚至变得无效并导致 Farseer 崩溃。
我一直在考虑制作某种算法，以某种方式找到墙壁的最大区域并将它们合并成一个大矩形，并继续对较小的矩形执行此操作，直到所有孔都被填满，但我不知道如何实现这一点。这似乎是完美的解决方案，因为它可以解决性能问题以及我现在遇到的凹多边形混乱。有谁知道如何实施这样的事情吗？
完全停止使用物理引擎并不是一个解决方案，因为我的游戏中的很多东西都依赖于它。
编辑：这是身体现在的样子的一个小例子：（每个数字都是一个身体） 
这就是我希望它们成为的样子：
I'm making a space shooter which takes place in a big dungeon, which consists of large rectangles to define walls. Everything in the game is physically simulated using Farseer Physics. There's one problem though: I want the dungeon to look sufficiently large, but that requires me to have at least 80x80 rectangles in my grid, which means that I have, in the worst case scenario, 6400 physically simulated bodies, which isn't exactly performance friendly, as you can guess.
My temporary solution was to divide the grid in vertical slices, so that, for every column, all rectangles are added using a boolean add operation, and then a body is created, using the resulting concave polygon. It increases performance a bit, but the polygons have a tendency to mess up, become non-existent, block ways that should normally be traversable or even become invalid and cause Farseer to crash.
I've been thinking about making some kind of algorithm that somehow finds the biggest areas of walls and merges them together into one big rectangle, and keeps doing this for smaller rectangles until all holes are filled, but I have no idea how to implement this. It seems like the perfect solution because it'd solve the performance problems and also the concave polygon mess I have right now. Does anyone have a clue on how to implement something like this?
It is not a solution to stop using a physics engine altogether, because a lot of things in my game rely on it.
EDIT: Here's a little example of how the bodies look like right now: (every number is a body)
And this is how I want them to be:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我可能没有正确理解这个问题，但让我提出一个我认为有点暗示解决你的问题的算法。
您的问题始于一个矩形贪婪，其中正方形是自由和非自由。从一开始，自由方块就是我们用来建造墙壁的方块，非自由方块是空心空间。
完成后，您应该将尽可能大的墙块组合在一起。
为了澄清，围绕一个自由正方形的扩展是指取假设的最大矩形，该矩形可以从给定的正方形开始在所有可用方向上构建。
对于矩形
n*m矩阵，该算法的复杂度直观地约为O(n*n*m*m)。实际上，我认为您的数据处理起来会很快。请注意，该算法并不提供最少数量的对象，而是最大化所有区域的总和（根据您的问题）。我认为，就复杂性而言，最小化尸体总数的问题要困难得多。I might not understand the question correctly, but let me propose an algorithm that I think kinda hints at solving your problem.
Your problem starts with a rectangular greed where squares are free and non-free. From start the free squares are the ones we are going to build walls with, and the non-free squares are the hollow spaces.
After you are done, you should have the largest possible blocks of wall grouped together.
To clarify, by expansion around a free square I mean taking the hypothetical largest rectangle that can be built starting from the given square in all available directions.
The complexity of this algorithm for a rectangle
n*mmatrix is intuitively aroundO(n*n*m*m). In practice i think it'll be quite quick with your data. Note that this algorithm doesn't provide the fewest number of objects, but rather maximizes the sum of all areas (as per your question). I intune that the problem of minimizing the total number of bodies is much more difficult in terms of complexity.这是我在我的一款游戏中使用的内容（也不是在 C# 中）：
首先创建一个带有实心墙的数组，创建一个类似
Wall的结构，其中包含整数x、y、width和height，创建很多它们，每个块一个。然后循环遍历它们并合并具有相同
y和height且相邻的那些 (x₁ + width₁ = x2)。然后再次循环，这次使用
x而不是y（反之亦然），并使用width而不是height>（反之亦然）。这尚未优化，但您可以修改它以使其更快。这是我在游戏中使用的实现，它对你来说可能太慢了。
运行此命令会生成 38 个主体（与您发布的示例中的主体数量相同）：
颠倒最后两步的顺序会生成 36 个实体：
Here's what I used in one of my games (not in C#, also):
First create an array with the solid walls, create a structure like
Wall, with the intergersx,y,widthandheight, create lots of them, one for each block.Then loop through them and merge the ones which have the same
yandheight, and are neighbors (x₁ + width₁ = x₂).Then loop again, this time using
xinstead ofy(and vice versa), and usingwidthinstead ofheight(and vice versa).This is not optimized, but you can modify it to make it faster. This was the implementation that I used in my game, it may be too slow for you.
Running this generates 38 bodies (that's the same number of bodies as in the example your posted):
Reversing the order in the last two steps generates 36 bodies:
使用 Farseer 时，应该使用EDGES，而不是用如此多的实体构建地图/世界/关卡，这可能会导致性能问题。
如果您能找到一种方法将地图转换为顺序顶点坐标列表，也许是一种追踪墙壁并生成列表的算法，那么您可以这样做...
创建 1 个主体并添加第一个边：
然后循环遍历所有按顺序添加其他顶点坐标，然后将每个新边附加到前一个边结束坐标。 （按顺序将边链接在一起直到完成）
这会产生 1 个实体，而不是 35 个以上。
Using Farseer one should use EDGES instead of constructing your map/world/level with so many bodies, which could result in performance issues.
If you can find a way to convert your map into a list of sequential vertex coords, maybe an algorithm that traces the walls and generates the list, you could then do this...
Create 1 body and add FIRST edge:
Then loop through all other vertex coords in sequence and then attach each new edge to the previous edge end coordinate. (chaining edges together in sequence until done)
This results in 1 body instead of having 35+.