find一组最大的连续矩形来覆盖多个区域

我正在为“ 矮人堡垒”(Dwarf Fortress)这款游戏开发一款名叫“ Quickfort ”的工具。 Quickfort将csv / xls格式的电子表格转换为一系列矮人要塞的命令,以便在游戏中绘制“蓝图”。

我目前正在尝试优化解决这个工具的2.0版本的面积绘图问题。

考虑下面的“蓝图”,它定义了二维网格的绘图命令。 网格中的每个单元格应该挖出(“d”),通道(“c”)或不保留(“。”)。 实际使用中可能会出现任意数量的不同绘图命令。

. d . dcc ddddcc . ddd . c dddddc . d . ddc 

为了尽量减less需要发送给矮人堡垒的指令数量,我想find一组最大的连续矩形,它们可以形成为完全覆盖或“绘制”所有绘图单元格。 为了有效,给定矩形的所有单元必须包含相同的命令。

这是比Quickfort 1.0更快的方法:将每个单元分别绘制为1×1的矩形。 这个video显示了两个版本之间的性能差异。

对于上面的蓝图,解决scheme如下所示:

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

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

我目前的做法是迭代的。 在每一次迭代中,我都会build立一个最大的矩形列表,这个矩形可以从每个网格的可绘制单元格中通过从单元格的所有4个方向延伸而形成。 在sorting最大的列表之后,我首先find最大的矩形,将其底层单元标记为“绘图”,并将该矩形logging在列表中。 绘制每个矩形之前,检查其底层单元以确保它们尚未绘制(与上一个绘图重叠)。 然后,我们再次开始,find剩余的最大矩形,然后绘制它们,直到所有的单元格都被绘制为某个矩形的一部分。

我认为这种方法稍微比一个愚蠢的蛮力search优化,但我浪费了很多周期(重新)计算单元格最大的矩形和检查底层细胞的状态。

目前,这个矩形发现例程占据了工具总运行时间的大部分,特别是对于大型蓝图。 为了速度,我牺牲了一些准确性,只考虑来自单元格的矩形,这些单元看起来形成了一个矩形的angular落(使用一些邻居单元启发式来确定,这并不总是正确的)。 作为这个“优化”的结果,我目前的代码实际上并没有正确地产生上面的解决scheme,但它足够接近。

更广泛地说,我认为最大的矩形的目标 – 首先是对这个应用程序“足够好”的方法。 但是我观察到,如果目标是find矩形的最小集合 (最less数量)来完全覆盖多个区域,那么解决scheme将如下所示:

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

这个第二个目标实际上代表了一个更优化的问题解决scheme,因为更less的矩形通常意味着更less的命令发送到矮人堡垒。 然而,根据我有限的math知识,这种方法让我更接近NP-Hard。

如果您想更好地理解整体战略,请观看video ; 我没有提到Quickfort过程的其他方面,例如find绘制所有矩形的最短光标path。 这个问题可能有一个解决scheme来连贯地结合这些多种策略。

任何forms的帮助将不胜感激。

我find了一些快速algorithm来分割来自三元吴和Sartaj Sahni的简单直线多边形 ,这可能是你感兴趣的。 在你的例子中,带有字符“d”的区域形成了一个直线多边形,也是带有“c”和“。”的区域。 本文包括无孔简单直线多边形的algorithm。

如果一个多边形包含有孔,那么运行O(n ^ 3/2 log n)时间的algorithm,正如第11页的纸张多边形分解中的JM Keil所述。

如果最小化在分区过程中引入的线段的总长度是另一个优化标准 ,则如果多边形包含孔(第12页),则问题变为NP完全。 对于这些问题,存在近似algorithm(本文是指具有这种algorithm的论文)。 如果多边形不包含孔,则有一个O(n ^ 4)时间algorithm。

这不是一个真正的答案,但使用一个天真的search,你可以得到

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

基本上,你从左上angular开始,用它作为下一个矩形的左上angular,然后检查你可以向右和向下扩展多less,然后find剩余位的最上面和最左边的单元格,等等。

这在某些情况下可能是非常无效的,但速度很快,因为您不必重新计算任何东西。

在我看来,所有find覆盖原始区域的矩形的解决scheme都是正确的。 find更小的一组矩形更好,因为它压缩/执行更好。

所以我不build议试图find最佳的解决scheme。 (我想这也是NP难)。

对于更快的运行解决scheme,您可以将matrix初始化为4个单元组,并尝试合并它们(如果它们相同)。 之后,如果它们相同,则可以合并4个组的组。 如果你完成了recursion的话。

这不会find最佳的解决scheme,但会非常快。 如果你的matrix很大,有很大的连续区域,那么与最优化的差别就不会那么大。