在具有最少数量矩形的正方形网格上填充任意 marked/selected 个图块的算法？
Algorithm to fill arbitrary marked/selected tiles on a square grid with the smallest number of rectangles?
我这里问的是一道算法题。我不是在询问如何使用我正在使用的编程语言或我当前正在使用的框架和库来实现它的具体细节。我想知道原则上如何做到这一点。
作为一种爱好，我正在研究 1992 年第一人称射击游戏 Wolfenstein 3D 的开源虚拟现实翻拍。我的程序将支持以 90 年代原始格式制作的 WOLF3D 经典模组和地图包。这意味着我的程序不会提前知道地图是什么。它们在运行时从用户提供的文件中加载。
Wolfenstein 3D 地图是通常为 64x64 方块的 2D 正方形网格。假设我有一个 2D 布尔数组，return 如果玩家可以遍历特定的图块则为真，如果无论游戏中发生什么都无法遍历该图块则为假。
我想为现代游戏引擎生成矩形碰撞对象，以防止碰撞地图上不可穿越的图块。现在，我在每个墙砖的每个表面上都有一个小碰撞对象，旁边有一个可穿越的瓷砖，这是非常低效的，因为它产生了比必要更多的碰撞对象。相反，我应该拥有的是较少数量的大矩形，它们填充网格上的所有正方形，其中我提到的二维数组具有错误值以指示不可遍历。
当我搜索任何可能针对类似问题进行的算法或研究时，我发现了很多关于矩形打包的信息，目的是为游戏制作纹理图集，将矩形打包成正方形，但是我还没有发现任何试图将最小数量的矩形打包成任意一组选定/标记的方形图块的方法。
我想到的天真的方法是首先制作代表 64 行的 64 个矩形，然后切掉任何可遍历的正方形。但我怀疑必须有一种算法可以做得更好，这意味着它可以用较少数量的矩形填充相同的空间。也许从我天真的方法开始，然后检查每个矩形是否有可以合并的相邻矩形？但我不确定这种方法能走多远，或者它是否会真正减少矩形的数量。
结果不一定是完美的。我只是在这里钓鱼，看看有没有人有什么魔术可以让我超越天真的方法。
以前有人做过吗？这叫什么？只要知道我什至需要谈论这个的一些词汇会有所帮助。谢谢！
（稍后编辑）
Here is some sample input as comma-separated values。 1代表必须用矩形填充的区域，0代表不应该用矩形填充的区域。
我希望结果是一组 4 个整数的列表，其中每个整数代表一个矩形，如下所示：
- 第一个整数是矩形 left/western 边的 x 坐标。
- 第二个整数是矩形 top/northern 边的 y 坐标。
- 第三个整数是矩形的宽度。
- 第四个整数是矩形的深度。
我的程序是用 C# 编写的，但我确信我可以用普通的主流通用编程语言或伪代码翻译任何内容。
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
无论它看起来多么简单，它可能会生成最少数量的矩形 - 仅仅是因为我们需要每对顶角至少有一个矩形。
为了更快地向下扩展，预先计算 table 保持所有元素顶部和左侧的总和是有意义的（又名 integral image）。
对于非重叠矩形，n x n“图像”的最坏情况复杂度不应超过 O(n^3)。如果矩形可以重叠（会导致它们的数量减少），则积分图像优化不适用，最坏的情况将是 O(n^4).
我这里问的是一道算法题。我不是在询问如何使用我正在使用的编程语言或我当前正在使用的框架和库来实现它的具体细节。我想知道原则上如何做到这一点。
作为一种爱好，我正在研究 1992 年第一人称射击游戏 Wolfenstein 3D 的开源虚拟现实翻拍。我的程序将支持以 90 年代原始格式制作的 WOLF3D 经典模组和地图包。这意味着我的程序不会提前知道地图是什么。它们在运行时从用户提供的文件中加载。
Wolfenstein 3D 地图是通常为 64x64 方块的 2D 正方形网格。假设我有一个 2D 布尔数组，return 如果玩家可以遍历特定的图块则为真，如果无论游戏中发生什么都无法遍历该图块则为假。
我想为现代游戏引擎生成矩形碰撞对象，以防止碰撞地图上不可穿越的图块。现在，我在每个墙砖的每个表面上都有一个小碰撞对象，旁边有一个可穿越的瓷砖，这是非常低效的，因为它产生了比必要更多的碰撞对象。相反，我应该拥有的是较少数量的大矩形，它们填充网格上的所有正方形，其中我提到的二维数组具有错误值以指示不可遍历。
当我搜索任何可能针对类似问题进行的算法或研究时，我发现了很多关于矩形打包的信息，目的是为游戏制作纹理图集，将矩形打包成正方形，但是我还没有发现任何试图将最小数量的矩形打包成任意一组选定/标记的方形图块的方法。
我想到的天真的方法是首先制作代表 64 行的 64 个矩形，然后切掉任何可遍历的正方形。但我怀疑必须有一种算法可以做得更好，这意味着它可以用较少数量的矩形填充相同的空间。也许从我天真的方法开始，然后检查每个矩形是否有可以合并的相邻矩形？但我不确定这种方法能走多远，或者它是否会真正减少矩形的数量。
结果不一定是完美的。我只是在这里钓鱼，看看有没有人有什么魔术可以让我超越天真的方法。
以前有人做过吗？这叫什么？只要知道我什至需要谈论这个的一些词汇会有所帮助。谢谢！
（稍后编辑）
Here is some sample input as comma-separated values。 1代表必须用矩形填充的区域，0代表不应该用矩形填充的区域。
我希望结果是一组 4 个整数的列表，其中每个整数代表一个矩形，如下所示：
- 第一个整数是矩形 left/western 边的 x 坐标。
- 第二个整数是矩形 top/northern 边的 y 坐标。
- 第三个整数是矩形的宽度。
- 第四个整数是矩形的深度。
我的程序是用 C# 编写的，但我确信我可以用普通的主流通用编程语言或伪代码翻译任何内容。
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
无论它看起来多么简单，它可能会生成最少数量的矩形 - 仅仅是因为我们需要每对顶角至少有一个矩形。
为了更快地向下扩展，预先计算 table 保持所有元素顶部和左侧的总和是有意义的（又名 integral image）。
对于非重叠矩形，n x n“图像”的最坏情况复杂度不应超过 O(n^3)。如果矩形可以重叠（会导致它们的数量减少），则积分图像优化不适用，最坏的情况将是 O(n^4).