joe*_*lpt 19 algorithm geometry
我正在为矮人要塞游戏开发一个名为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
为了最大限度地减少需要发送到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
上面的每个相同编号的矩形表示连续的矩形.最大的矩形优先于可能在其区域中形成的较小矩形.编号/矩形的顺序并不重要.
我目前的方法是迭代的.在每次迭代中,我通过从单元格的所有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过程的其他方面,例如找到绘制所有矩形的最短光标路径.可能有一个解决这个问题的方法,它将这些多种策略连贯地结合在一起.
任何形式的帮助将不胜感激.
Chr*_*mer 10
我找到了来自San-Yuan Wu和Sartaj Sahni的快速算法分区简单直线多边形,这可能是你感兴趣的.在您的示例中,具有字符"d"的区域形成直线多边形,也形成具有"c"和"."的区域.本文包括无孔简单直线多边形的算法.
如果多边形包含孔,则算法运行时间为O(n ^ 3/2 log n),如第11页的纸质多边形分解中的JM Keil所述.
如果最小化分区过程中引入的线段的总长度是另一个优化标准,则如果多边形包含孔(第12页),问题将变为NP完全.对于这些问题,存在近似算法(该论文涉及具有这种算法的论文).如果多边形不包含孔,则存在O(n ^ 4)时间算法.