5

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

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

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

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

编辑：这里有一个小例子，说明身体现在的样子：（每个数字都是一个身体） http://i.imgur.com/6x06o.png

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

在此处输入图像描述

4

3 回答 3

1

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

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

  1. Foreach自由方格围绕该方格进行扩展，并查看该方格可以属于的最大区域是多少。通过扩展，我的意思是从那个广场向各个方向前进，同时可以用自由广场建立一个区域。将这个最大的区域与给定的自由方格相关联。
  2. 选择关联面积最大的正方形，并通过围绕该正方形展开来构建合并的墙。属于此合并的方块被标记为non-free。如果没有更多的空闲方块完成，则转到第 1 步。

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

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

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

于 2011-07-17T01:42:14.413 回答
1
于 2011-07-17T02:13:35.430 回答
0

使用 Farseer 时应该使用EDGES而不是用这么多物体构建地图/世界/关卡，这可能会导致性能问题。

如果您能找到将地图转换为顺序顶点坐标列表的方法，也许是一种跟踪墙壁并生成列表的算法，那么您可以这样做......

创建 1 个主体并添加第一条边：

Body dungeon = BodyFactory.CreateEdge(world, start, end);

然后依次循环遍历所有其他顶点坐标，然后将每个新边附加到前一个边的结束坐标。（按顺序将边缘链接在一起直到完成）

FixtureFactory.AttachEdge(start, end, dungeon);

这导致 1 个身体而不是 35+。

于 2013-02-10T05:17:11.827 回答