找到覆盖多个区域的最大连续矩形集
我正在为游戏 Quickfort 开发一个名为 Quickfort 的工具 矮人要塞。 Quickfort 将 csv/xls 格式的电子表格转换为一系列命令，供 Dwarf Fortress 执行，以便在游戏中绘制“蓝图”。
我目前正在尝试以最佳方式解决该工具 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
为了最大限度地减少需要发送到矮人堡垒的指令数量，我想找到一组最大的连续矩形，可以形成完全覆盖或“绘制”所有可绘制单元格。为了有效，给定矩形的所有单元格必须包含相同的命令。
这是比 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
上面每个相同编号的矩形表示一个连续的矩形。最大的矩形优先于也可以在其区域中形成的较小的矩形。编号/矩形的顺序并不重要。
我的当前方法是迭代的。在每次迭代中，我都会构建一个最大矩形列表，这些矩形可以通过从单元格的所有 4 个方向延伸来由每个网格的可绘制单元格形成。首先对列表进行最大排序后，我从找到的最大矩形开始，将其底层单元格标记为“已绘制”，并将该矩形记录在列表中。在绘制每个矩形之前，会检查其底层单元格以确保它们尚未绘制（与先前的绘图重叠）。然后我们再次开始，找到可以形成的最大的剩余矩形并绘制它们，直到所有单元格都被绘制为某个矩形的一部分。
我认为这种方法比愚蠢的暴力搜索稍微优化一些，但我浪费了大量的周期（重新）计算单元格的最大矩形并检查底层单元格的状态。
目前，此矩形发现例程占用了该工具总运行时间的大部分，特别是对于大型蓝图。为了速度，我牺牲了一些准确性，只考虑看起来形成矩形角的单元格中的矩形（使用一些并不总是正确的相邻单元格启发法确定）。由于这种“优化”，我当前的代码实际上并未正确生成上述解决方案，但它已经足够接近了。
更广泛地说，我认为最大矩形优先的目标是该应用程序的“足够好”方法。然而，我观察到，如果目标是找到完全覆盖多个区域的最小矩形集（最少数量），则解决方案将如下所示：
. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8
第二个目标实际上代表了更优化的解决方案解决这个问题，因为更少的矩形通常意味着发送到矮人要塞的命令更少。然而，基于我有限的数学知识，这种方法让我觉得更接近 NP-Hard。
如果您想更好地了解整体策略，请观看视频；我没有讨论 Quickfort 过程的其他方面，例如找到绘制所有矩形的最短光标路径。也许有一个解决这个问题的方法，可以将这些多种策略连贯地结合起来。
任何形式的帮助将不胜感激。
I'm working on a tool called Quickfort for the game Dwarf Fortress. Quickfort turns spreadsheets in csv/xls format into a series of commands for Dwarf Fortress to carry out in order to plot a "blueprint" within the game.
I am currently trying to optimally solve an area-plotting problem for the 2.0 release of this tool.
Consider the following "blueprint" which defines plotting commands for a 2-dimensional grid. Each cell in the grid should either be dug out ("d"), channeled ("c"), or left unplotted ("."). Any number of distinct plotting commands might be present in actual usage.
. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c
To minimize the number of instructions that need to be sent to Dwarf Fortress, I would like to find the set of largest contiguous rectangles that can be formed to completely cover, or "plot", all of the plottable cells. To be valid, all of a given rectangle's cells must contain the same command.
This is a faster approach than Quickfort 1.0 took: plotting every cell individually as a 1x1 rectangle. This video shows the performance difference between the two versions.
For the above blueprint, the solution looks like this:
. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2
Each same-numbered rectangle above denotes a contiguous rectangle. The largest rectangles take precedence over smaller rectangles that could also be formed in their areas. The order of the numbering/rectangles is unimportant.
My current approach is iterative. In each iteration, I build a list of the largest rectangles that could be formed from each of the grid's plottable cells by extending in all 4 directions from the cell. After sorting the list largest first, I begin with the largest rectangle found, mark its underlying cells as "plotted", and record the rectangle in a list. Before plotting each rectangle, its underlying cells are checked to ensure they are not yet plotted (overlapping a previous plot). We then start again, finding the largest remaining rectangles that can be formed and plotting them until all cells have been plotted as part of some rectangle.
I consider this approach slightly more optimized than a dumb brute-force search, but I am wasting a lot of cycles (re)calculating cells' largest rectangles and checking underlying cells' states.
Currently, this rectangle-discovery routine takes the lion's share of the total runtime of the tool, especially for large blueprints. I have sacrificed some accuracy for the sake of speed by only considering rectangles from cells which appear to form a rectangle's corner (determined using some neighboring-cell heuristics which aren't always correct). As a result of this 'optimization', my current code doesn't actually generate the above solution correctly, but it's close enough.
More broadly, I consider the goal of largest-rectangles-first to be a "good enough" approach for this application. However I observe that if the goal is instead to find the minimum set (fewest number) of rectangles to completely cover multiple areas, the solution would look like this instead:
. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8
This second goal actually represents a more optimal solution to the problem, as fewer rectangles usually means fewer commands sent to Dwarf Fortress. However, this approach strikes me as closer to NP-Hard, based on my limited math knowledge.
Watch the video if you'd like to better understand the overall strategy; I have not addressed other aspects of Quickfort's process, such as finding the shortest cursor-path that plots all rectangles. Possibly there is a solution to this problem that coherently combines these multiple strategies.
Help of any form would be appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我找到了 San- 的论文 Fast Algorithms To Partition Simple Rectilinear Polygons Yuan Wu 和 Sartaj Sahni，您可能会感兴趣。在您的示例中，带有字符“d”的区域形成一个直线多边形，带有“c”和“.”的区域也是如此。本文包含无孔简单直线多边形的算法。
如果多边形包含孔，则有一些算法需要 O(n^3/2 log n) 时间运行，如论文中的 JM Keil 多边形分解（第 11 页）指出。
如果另一个优化标准是最小化分割过程中引入的线段的总长度，则如果多边形包含孔，则问题将变为 NP 完全问题（第 12 页）。对于这些问题存在近似算法（本文引用了具有此类算法的论文）。如果多边形不包含孔，则存在 O(n^4) 时间算法。
I found the paper Fast Algorithms To Partition Simple Rectilinear Polygons from San-Yuan Wu and Sartaj Sahni, which could be of interest to you. In your example the region with character 'd' forms a rectilinear polygon, also the regions with 'c' and '.'. This paper includes algorithms for hole-free simple rectilinear polygons.
If a polygon includes holes, there are algorithms running with O(n^3/2 log n) time, as JM Keil in the paper Polygon Decomposition on page 11 states.
If minimizing the total length of the line segments introduced in the partitioning process is the other optimization criterion, the problem becomes NP-complete if the polygon contains holes (page 12). For these problems approximation algorithms exist (the paper refers to papers with such algorithms). If the polygon doesn't contain holes there is an O(n^4) time algorithm.
这并不是真正的答案，但使用天真的搜索你可以得到
基本上你从左上角开始并将其用作下一个矩形的左上角，然后检查你可以将其向右和向下延伸多远，然后找到剩余位的最上面和最左边的单元，依此类推。
在某些情况下，这可能非常无效，但速度很快，因为您不必重新计算任何内容。
This is not really an answer but using a naive search you can get
Basically you start from the top left corner and use it as the top left corner of your next rectangle, then you check how far you can extend it to the right and down, then find the topmost and leftmost cell of the remaining bits and so on.
This is probably very ineffective in some cases but it's quick as you don't have to recalculate anything..
在我看来，所有找到一组覆盖原始区域的矩形的解决方案都是正确的。找到一组较小的矩形会更好，因为它压缩/性能更好。
所以我不建议尝试寻找最佳解决方案。 （我猜这也是 NP 难的）。
为了获得更快的运行解决方案，您可以最初将矩阵平铺为 4 个单元格的组，如果它们相同，则尝试合并它们。之后，如果 4 组相同，则可以将它们合并。如果完成，则递归地执行此操作。
这不会找到最佳解决方案，但会非常快。如果你的矩阵很大，有很大的连续区域，那么与最优矩阵的差异不会那么大。
In my view, all solutions that find a set of rectangles that cover the original area is a correct one. Finding a smaller set of rectangles is better because it compresses/performs better.
So I would not advise trying to find the optimal solution. (I would guess it is NP-hard as well).
For a faster running solution, you could tile the matrix into groups of 4 cells initially, and try to merge them if they are the same. After that, you can merge groups of 4 groups, if they are the same. And do so recursively if you are done.
This won't find the optimal solution but will be very fast. If your matrixes are large, with large contiguous areas, the difference with the optimal won't be that great.