我在这里问的是一个算法问题。我不是在询问如何用我正在使用的编程语言或我目前正在使用的框架和库来做这件事的细节。我想知道原则上如何做到这一点。

作为爱好，我正在开发 1992 年第一人称射击游戏 Wolfenstein 3D 的开源虚拟现实重制版。我的程序将支持以 90 年代原始格式制作的 WOLF3D 的经典模块和地图包。这意味着我的程序不会提前知道地图将是什么。它们在运行时从用户提供的档案中加载。

Wolfenstein 3D 地图是通常为 64x64 瓦片的 2D 方形网格。假设我有一个 2D 布尔阵列，如果玩家可以遍历特定的图块，则回传 true；如果无论游戏中发生什么，该图块将永远不可遍历，则回传 false。

我想为现代游戏引擎生成矩形碰撞物件，以防止碰撞到地图上的不可穿越的瓷砖。现在，我在每个墻砖的每个表面上都有一个小的碰撞物件，旁边有一个可移动的砖，这是非常低效的，因为它产生的碰撞物件比需要的要多。相反，我应该拥有较少数量的大矩形，它们填充网格上的所有正方形，其中我提到的 2D 阵列具有错误值以指示不可遍历。

当我搜索任何可能针对类似问题进行的算法或研究时，我发现了很多关于矩形打包的信息，用于制作游戏的纹理图集，将矩形打包成正方形，但我还没有找到任何试图将最少数量的矩形打包到任意一组选定/标记的方形瓷砖中的东西。

我想到的幼稚方法是首先制作代表 64 行的 64 个矩形，然后切掉任何可遍历的正方形。但我怀疑一定有一种算法可以做得更好，这意味着它可以用较少数量的矩形填充相同的空间。也许从我的幼稚方法开始，然后检查每个矩形是否有可以合并的相邻矩形？但我不确定采用这种方法能走多远，或者它是否会真正减少矩形的数量。

结果不一定是完美的。我只是在这里钓鱼，看看是否有人有任何魔术可以让我超越天真的方法。

有没有人这样做过？这叫什么？只要知道我什至需要谈论的一些词汇是有帮助的。谢谢！

（稍后编辑）

这是一些以逗号分隔的值的示例输入。1 表示必须用矩形填充的区域，而 0 表示不应用矩形填充的区域。

我希望结果将是一个包含 4 个整数的集合串列，其中每个集合代表一个矩形，如下所示：

1. 第一个整数是矩形左/西边缘的 x 坐标。
2. 第二个整数将是矩形顶部/北部边缘的 y 坐标。
3. 第三个整数是矩形的宽度。
4. 第四个整数是矩形的深度。

我的程序是用 C# 撰写的，但我确信我可以用普通的主流通用编程语言或伪代码翻译任何东西。

uj5u.com热心网友回复：

Mark all tiles as not visited
For each tile:
    skip if the tile is not a top-left corner or was visited before
    # now, the tile is a top-left corner
    expand right until top-right corner is found
    expand down
    save the rectangle
    mark all tiles in the rectangle as visited

不管它看起来多么简单，它可能会生成最少数量的矩形——这仅仅是因为我们每对顶角至少需要一个矩形。

为了更快地向下扩展，预先计算一个表格，该表格包含所有元素顶部和左侧的总和（也称为积分影像）。

对于不重叠的矩形，n x n“影像”的最坏情况复杂度不应超过O(n^3). 如果矩形可以重叠（会导致它们的数量减少），则不适用积分影像优化，最坏的情况是O(n^4).