图例1. 一个雪地单位以及其对应的作用区域（黄色部分）我们想要实现什么：拿到一个单元格列表，在最短的时间内，将相邻的单元格列表拼接，得到一个矩形数目最少（最优解）的矩形列表。给地形建立网格后，可以对单元格进行编号，并得到单元格有多少行多少列，根据单位32像素，很容易通过编号计算出它的位置。所以ipO是单元格列表{id, id, id, id, ...}->算法->矩形列表{ {x, y, wdith, height}, {x, y, wdith, height}, {x, y, wdith, height}, ...,}
图例2. 根据图例1绘制的测试数据，每个单元格上对应的数据是它的编号和（行，列）
图例3. 算法执行后得到的最优解的图形显示如果我们把每个矩形当成一个Block，每个Block的表示方法为（左下角单元格行列）-（右上角单元格行列），那么输出结果如下[LUA-PRint] ===Block:(12,8)-(12,19)[LUA-print] ===Block:(13,17)-(13,17)[LUA-print] ===Block:(13,12)-(13,15)[LUA-print] ===Block:(8,12)-(8,20)[LUA-print] ===Block:(9,9)-(11,19)[LUA-print] ===Block:(7,13)-(7,19)[LUA-print] ===Block:(10,20)-(10,20)[LUA-print] ===Block:(6,8)-(7,9)[LUA-print] ===Block:(10,7)-(10,7)[LUA-print] ====Calculator:recordResult 9[LUA-print] 72 0.025000000000034逻辑是lua实现的，其中单元格数量75，耗时25毫秒，最优结果为9个矩形。临时的解决方案：笔者比较才疏学浅，到现在也不太清楚这种算法的专业说法应该叫什么，只能根据字面意思称为是“矩形合并算法 ”。也可能是这个关键词不太专业，所以网上一番搜索并没有什么有用的信息。无可奈何之下，笔者根据所学知识，自己研究了一套计算思路（算是一种暴力搜索吧）。因为逻辑是在地形编辑器保存时进行计算，所以对算法的时间复杂度没有过多的优化。在此抛砖引玉一下，若有算法大神走过路过，希望能指点迷津。求一个解的情况大致如下：a. 首先我们拿到一个矩形，要看看它能不能变成一个更大的矩形，也就是说要从上下左右四个方向上去判断是否存在单元格能去扩大它。b. 如果这个矩形越扩越大，余下的单元格就越少，得到的解越接近最优解。c. 如果这个矩形四个方向上都不能扩大了，那就把这个矩形放入矩形列表，从余下的单元格随便抽出一个单元格来，将这个单元格当成矩形，进行步骤a的操作d. 如果没有单元格剩余了，那么我们就得到了一个解（不一定是最有解），而且得到了这个解的矩形数目。初看，这个算法肯定是逃不过一种树形结构的遍历的。上下左右加上不合并，一共五种情况的子节点遍历方向。为什么会有不合并这种情况？假设我们选中的当前需扩大的单元格是图例中377号单元格，你就懂了。
图例4. 遍历树形图所以，我们得到这个树形图的节点结构如下：矩形数目count_of_rectangle矩形列表（坐标、尺寸的列表，注意这里的矩形是单元格合并之后的） rectangle_list = { {x, y, wdith, height}, {x, y, wdith, height}, {x, y, wdith, height}, ...,}矩形列表包含的（已使用）单元格列表used_grids = {id, id, id, id, ...}当前待扩展矩形rectangle = {x, y, width, height}关于遍历与剪枝：上面我们知道了需要遍历，那是深度优先遍历，还是广度优先遍历呢？因为分支有5个之多，答案无意是前者。因为分支这么多，我们需要设计一些剪枝策略，来避免不必要的遍历。首先，想到的就是尽快求得一个解，以这个解的矩形数目为限制进行剪枝。在算法运行过程中，得到一个解时，记录下来，minResult_当求得其他的解result_，一直没有触发这个剪枝，则更新记录下的解，这样遍历停止时，我们就能得到最优解minResult_。广度优先遍历，一方面要维护一个子节点队列，随着遍历的（树）层级原来越深，子节点队列中的元素会越来越多，拿到第一个解的速度绝对是比深度优先遍历要慢的。其次，避免当前带扩展矩形的重复计算。我们每个节点是对应一个当前带扩展矩形的（如果没有，则这个节点表示是一个解），向下遍历即是对该矩形四个方向的扩展或者不合并。这5个情况已经包含了对该矩形处理的所有情况了，如果再次遍历得到这个矩形，则不需要往下遍历了。所以我们在算法进行的过程中就要记录下来已经计算过哪些矩形了，矩形Block的数据为{x, y, width, height}，为了方便记录，我们同时需要记录下来对应的（左下角单元格id，右上角单元格id）假设head = 左下角单元格idtail = 右上角单元格idlua中可以通过这种格式进行记录和判断marked_ = { [head][tail] = true, [head][tail] = true, [head][tail] = true, [head][tail] = true, ...,}其他问题：减少数据的拷贝（如何回溯和数据结构设计）有深度优先遍历、有剪枝，就会想我们如何去存数据。特别是节点信息中的那个“矩形列表包含的（已使用）单元格列表 ”，笔者不希望，每往下一层遍历，就要拷贝一次父节点的已使用单元格，然后再往里面塞我们扩展矩形后新增的已使用的单元格。同理，还有矩形列表的拷贝。拷贝，无疑会拖慢算法的速度。对于一个解result_的核心数据，笔者是用Block栈来表示的，栈的top表示这个解的矩形数目，栈里的Block对象表示矩形列表（具体数据），栈顶的Block即当前带扩展矩形因为算法已经设计成一种递归形式了，所以通过压栈、出栈，很方便的实现向下遍历和回溯。 self.result_:push(block) self:perm(depth, grids, nil) self.result_:pop()然后是矩形列表包含的（已使用）单元格列表，我们反过来用剩余单元格来表示。感谢排列组合算法的启发，我设计了一个数据结构ArrayX（有序数组 ）用来表示单元格列表grids。ArrayX本身会维护成员变量length_来表示它的元素个数，特殊在它的remove/removeAt函数、recover函数。remove/removeAt ：将指定元素与数组末尾的元素交换，并且length_自减1。（实际上数据还是在的）recover：将数组恢复成指定长度。（这样数据又回来了）最后对ArrayX遍历和取数据的时候，判断索引不要超过length_即可 local length = grids:length() ... if iter and not self:isMarked(head, tail) then -- 剪枝，矩形是否被遍历过 canMerge = true for i, id in iter do if grids:exist(id) then grids:remove(id) -- 剩余单元格列表中中移除对应方向扩展使用掉的单元格 else canMerge = false break end end end if canMerge then self:mark(head, tail) local newBlock = Block:create(head, tail) self:perm(depth, grids, newBlock) end grids:recover(length)5个扩展情况的优先级，不合并时如何选取下一个单元格？首先我们当然是希望能扩展的，如果不合并放在最前面，得到的第一个解就是单元格的数量，用这个解来剪枝并没有什么意义。因为cocos是笛卡尔坐标系（x向右，y向上），而且我们单元格编号和行、列号也遵循这个规则，所以我们的遍历的方向是 右 、上、 左、下。SEARCH_DIRECT = { { "lineRight", true, }, { "lineUp", true, }, { "lineLeft", false, }, { "lineDown", false, },}... for _, node in ipairs(SEARCH_DIRECT) do注意这里其实有顺序的然后关于这个顺序，其实可以引入一种贪心算法的思想，先计算四个方向上扩展需要消耗的单元格数量（也就是矩形的长、宽），进行排序，然后选择数量多的那个方向扩展。即，每次扩展消耗的单元格越多，剩余的单元格就越少，越快得到一个解。然后不合并时如何选取下一个单元格，笔者这里其实是偷懒的做法，直接取剩余单元格列表的第一个 local id = grids:item(1)自己的疑问：直到截稿之日，笔者对“矩形合并算法”这种说法还是心存疑惑。这方面的算法应该早就出现，不至于Google上一无所获。如果有人知道这个问题更专业的叫法，还望醍醐灌顶。这里只是提供一种暴力遍历来解决问题（其实是很挫的），或许有一种更好的算法等待着笔者去挖掘。因为想这个问题越想越觉得其实它有最优子结构N个单元格 的解 = （N-M）个单元格的解 + M个单元格的解（0<M<N）特别是在处理不合并的情况的时候，那我继续向下遍历，不就是将剩余单元格列表放入算法迭代，然后与当前遍历得到的Block列表合并么？奈何笔者思考了很久，还不太清楚怎么把动态规划应用到这个问题上来。也许哪天想通了，再写一份分享给大家吧。源码参考：https://github.com/Ron2014/lua_rect_union本例是在cocos2d-x-3.13.1的kill pests的示例代码的框架上修改的。具体逻辑参考以下文件：算法rect_union/models/Block.luarect_union/models/Calculator.lua界面rect_union/views/GridSprite.luarect_union/views/GridView.luarect_union/views/MainScene.lua数据结构util/type/array_x.luautil/type/stack.lua然后引擎中自己加了执行gm指令和reload脚本的小trick。因为和本文探讨的问题没有太大关联，就不在这里赘述了。新闻热点
疑难解答
