空间切割问题

前言

在游戏开发中，偶然遇到了一个这样的问题，感觉还比较有趣，特此记录一下。

以下是这个问题抽离出来的一小部分

---

问题

思路

思路一

1. 横向遍历一次找到所有连续空间
2. 竖向遍历一次找到所有连续空间
3. 最后对比一下连续空间的数量，然后返回

Lua代码

---@class GridInfo
---@field containerIndex number
---@field posX number
---@field posY number

---@class Rect
---@field posX number
---@field posY number
---@field SizeX number
---@field SizeY number

---@param needMarkGrid GridInfo[][]
---@return res table<number, Rect[]> 
function Test:ReArrangePart(needMarkGrid)
    --先收集每个index的零碎格子
    ---@type table<number, GridInfo>
    local index2Grids = {}
    for i=1,#needMarkGrid do
        for j=1,#needMarkGrid[i] do
            ---@type GridInfo
            local gridInfo = needMarkGrid[i][j]
            if not index2Grids[gridInfo.containerIndex] then
                index2Grids[gridInfo.containerIndex] = {}
            end
            table.insert(index2Grids[gridInfo.containerIndex], gridInfo)
        end
    end

    local res = {}
    --遍历收集的格子中的所有组合
    for containerIndex,gridSet in pairs(index2Grids) do
        if not res[containerIndex] then
            res[containerIndex] = {}
        end
        local colMax = 1
        local rowMax = 1
        local colMin = 10
        local rowMin = 10
        local map = {}
        for _, gridInfo in pairs(gridSet) do
            if gridInfo.posX > colMax then
                colMax = gridInfo.posX
            end
            if gridInfo.posY > rowMax then
                rowMax = gridInfo.posY
            end
            if gridInfo.posX <= colMin then
                colMin = gridInfo.posX
            end
            if gridInfo.posY <= rowMin then
                rowMin = gridInfo.posY
            end
            --map标志 以10为偏移
            map[gridInfo.posX + gridInfo.posY * 10] = 0
        end


        for i=colMin, colMax do
            for j=rowMin, rowMax do
                --横向
                if map[i + j*10] == 0 then
                    local colLen = 1
                    for m = i + 1, colMax do
                        if map[m + j*10] == 0 then
                            colLen = colLen + 1
                        else
                            break
                        end
                    end
                    local rowLen = 1
                    for m = j + 1, rowMax do
                        local isFull = true
                        for n = i, i + colLen-1 do
                            if map[n + m*10] == 0 then
                            else
                                isFull = false
                                break
                            end
                        end
                        if isFull == false then
                            break
                        end
                        rowLen = rowLen + 1
                    end
                    --将所有的标记一下
                    for m = i, i + colLen-1 do
                        for n = j, j + rowLen-1 do
                            map[m + n*10] = 1
                        end
                    end
                    table.insert(res[containerIndex], {posX = i, posY =j, sizeX = colLen, sizeY = rowLen})
                end
            end
        end
    end
    return res
end