圖例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。因為和本文探討的問題沒有太大關聯，就不在這里贅述了。新聞熱點
疑難解答
