我正在为《矮人要塞》游戏使用名为Quickfort的工具。Quickfort将csv
/
xls格式的电子表格转换为矮人要塞要执行的一系列命令，以便在游戏中绘制“蓝图”。

我目前正在尝试以最佳方式解决此工具2.0版的区域绘图问题。

考虑下面的“蓝图”，它定义了二维网格的绘图命令。网格中的每个像元都应被挖出（“ d”），引导（“
c”）或不作图（“。”）。实际使用中可能存在许多不同的绘图命令。

. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c

为了最大程度地减少需要发送给Dwarf
Fortress的指令，我想找到一组最大的连续矩形，这些矩形可以形成为完全覆盖或“绘制”所有可绘制单元格。为了有效，所有给定矩形的像元必须包含相同的命令。

这是比Quickfort 1.0更快的方法：将每个像元分别绘制为1x1矩形。该视频显示了两个版本之间的性能差异。

对于上述蓝图，解决方案如下所示：

. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2

上方的每个相同编号的矩形表示一个连续的矩形。最大的矩形优先于也可以在其区域中形成的较小的矩形。编号/矩形的顺序并不重要。

我当前的方法是迭代的。在每次迭代中，我都通过在网格的所有四个方向上进行扩展来构建可以由每个网格的可绘制单元格形成的最大矩形的列表。首先对列表进行最大排序后，我从找到的最大矩形开始，将其基础单元格标记为“绘制”，然后将该矩形记录在列表中。在绘制每个矩形之前，请检查其基础单元以确保尚未绘制（与先前的图形重叠）。然后，我们再次开始，找到可以形成的剩余最大矩形，并对其进行绘制，直到将所有单元格绘制为某个矩形的一部分为止。

我认为这种方法比愚蠢的蛮力搜索略有优化，但是我浪费了很多周期（重新）计算单元格的最大矩形并检查基础单元格的状态。

当前，此矩形发现例程占据了工具总运行时间的大部分，特别是对于大型蓝图。为了提高速度，我只考虑了似乎形成矩形角的单元格中的矩形而牺牲了一些精度（使用某些并非总是正确的相邻单元格启发法来确定矩形）。作为这种“优化”的结果，我当前的代码实际上没有正确生成上述解决方案，但是已经足够接近了。

更广泛地讲，我认为最大矩形优先的目标是此应用程序的“足够好”的方法。但是我观察到，如果目标是找到 最小 的矩形 集 （ 最小
数量）以完全覆盖多个区域，则解决方案将如下所示：

. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8

第二个目标实际上代表了对该问题的最佳解决方案，因为更少的矩形通常意味着更少的发送给Dwarf
Fortress的命令。但是，基于我有限的数学知识，这种方法使我更接近NP-Hard。

如果您想更好地了解整体策略，我没有讨论Quickfort过程的其他方面，例如找到绘制所有矩形的最短光标路径。可能有一个针对此问题的解决方案，将这些多种策略紧密结合在一起。

任何形式的帮助将不胜感激。