box-server/nodes/battle/lib/utils_bt_grid.lua

--[[
    方形之路，格子相关算法处理
]]
local root = {}

local printf = print

-- 最短的龙大小
local MIN_LONG_SIZE = 3

function root:grids_to_color_map(grids)
    local ret = {}

    for _, v in ipairs(grids) do
        local x, y = v.x + 1, v.y + 1
        if not ret[y] then
            ret[y] = {}
        end
        if v:cantLink() then
            ret[y][x] = -1
        else
            ret[y][x] = v.color
        end
    end

    return ret
end

function root:grids_to_id_map(grids)
    local ret = {}

    for _, v in ipairs(grids) do
        local x, y = v.x + 1, v.y + 1
        if not ret[y] then
            ret[y] = {}
        end
        ret[y][x] = v.id
    end

    return ret
end

-- 随机一个地图。1~4是四种颜色，5是万能色块，0是不可以连线的
function root:random_map()
    local w, h = 5, 10

    local ret = {}
    for y = 1, h do
        local oneRow = {}
        for x = 1, w do
            local color = math.random(1, 4)
            table.insert(oneRow, color)
        end
        table.insert(ret, oneRow)
    end

    -- 随机3~4次万能色块。注意：可能4次都是同一个格子
    local allColorCount = math.random(3, 4)
    for i = 1, allColorCount do
        local y = math.random(h)
        local x = math.random(w)
        ret[y][x] = 5
    end

    -- local ret = {
    --     {3, 2, 3, 1, 2},
    --     {4, 3, 5, 2, 1},
    --     {3, 3, 3, 2, 3},
    --     {2, 4, 1, 2, 5},
    --     {1, 4, 4, 2, 1},
    --     {5, 1, 4, 2, 4},
    --     {2, 4, 1, 4, 1},
    --     {3, 4, 3, 4, 1},
    --     {3, 3, 4, 2, 4},
    --     {5, 3, 3, 2, 1}
    -- }

    return ret
end

-- 获取半场地图。seat=1下边，seat=2上边
function root:get_half_map(seat, map)
    local maxH = #map
    local minY, maxY
    if seat == 1 then
        minY, maxY = 1, maxH / 2
    else
        minY, maxY = maxH / 2 + 1, maxH
    end

    local ret = {}
    for y, v in ipairs(map) do
        ret[y] = {}
        for x, vv in ipairs(v) do
            if y >= minY and y <= maxY then
                ret[y][x] = vv
            else
                ret[y][x] = 0
            end
        end
    end
    return ret
end

-- 获取所有的龙
function root:get_all_long(halfMap)
    local h = #halfMap
    local w = #halfMap[1]

    -- 将地图分块
    local longList = self:split_map(halfMap)

    return longList
end

-- 将地图分块，同色连通的放在一块。万能色块可以重复使用
function root:split_map(map)
    local ret = {}

    local h = #map
    local w = #map[1]

    -- 同色地图字典
    local sameColorMapDict = {
        [1] = self:new_zero_map(w, h),
        [2] = self:new_zero_map(w, h),
        [3] = self:new_zero_map(w, h),
        [4] = self:new_zero_map(w, h)
    }
    for y, oneRow in ipairs(map) do
        for x, color in ipairs(oneRow) do
            if color >= 1 and color <= 4 then
                local sameColorMap = sameColorMapDict[color]
                sameColorMap[y][x] = color
            elseif color == 5 then
                for _, sameColorMap in ipairs(sameColorMapDict) do
                    sameColorMap[y][x] = color
                end
            end
        end
    end

    -- 每种颜色进行分割
    for _, sameColorMap in ipairs(sameColorMapDict) do
        local list = self:split_same_color_map(sameColorMap)
        self:array_merge(ret, list)
    end

    return ret
end

-- 对同色地图进行分割
function root:split_same_color_map(sameColorMap)
    local ret = {}

    for y, oneRow in ipairs(sameColorMap) do
        for x, color in ipairs(oneRow) do
            if color >= 1 and color <= 4 then
                sameColorMap[y][x] = 0

                local pos = {x = x, y = y, color = color}
                local oneLong = {pos}

                self:pickup_one_long(oneLong, sameColorMap, pos)
                if #oneLong >= MIN_LONG_SIZE then
                    table.insert(ret, oneLong)
                end
            end
        end
    end

    return ret
end

-- 拾取一条龙。与pos想连的色块加入到oneLong，并被设置为0
function root:pickup_one_long(oneLong, sameColorMap, pos)
    local x1 = pos.x
    local y1 = pos.y
    local nextPosList = {}
    -- 九宫格示例
    -- 1 2 3
    -- 4 x 6
    -- 7 8 9
    local deltaList = {
        {dx = -1, dy = 1},
        {dx = 0, dy = 1},
        {dx = 1, dy = 1},
        {dx = -1, dy = 0},
        {dx = 1, dy = 0},
        {dx = -1, dy = -1},
        {dx = 0, dy = -1},
        {dx = 1, dy = -1}
    }
    for _, v in ipairs(deltaList) do
        local x2 = x1 + v.dx
        local y2 = y1 + v.dy
        if sameColorMap[y2] and sameColorMap[y2][x2] and sameColorMap[y2][x2] > 0 then
            local newPos = {x = x2, y = y2, color = sameColorMap[y2][x2]}
            table.insert(nextPosList, newPos)
            table.insert(oneLong, newPos)
            sameColorMap[y2][x2] = 0
        end
    end

    for _, v in ipairs(nextPosList) do
        self:pickup_one_long(oneLong, sameColorMap, v)
    end
end

-- 获取地图的所有龙（连通色块）
function root:get_map_all_long(seat, map)
    local halfMap = self:get_half_map(seat, map)
    -- 要求是长度满足的龙
    local longList = self:get_all_long(halfMap)

    return longList
end

-- 获取地图的所有连线
function root:get_map_all_link(seat, map)
    local halfMap = self:get_half_map(seat, map)
    local h = #halfMap
    local w = #halfMap[1]
    local longList = self:get_all_long(halfMap)

    local ret = {}
    for _, v in ipairs(longList) do
        local linkList = self:get_long_all_link(v, w, h)
        self:array_merge(ret, linkList)
    end
    return ret
end

-- 从一片相连的色块中，获取所有的连线
-- 约束：连线间不存在包含关系
function root:get_long_all_link(long, w, h)
    local map = self:long_to_map(long, w, h)

    local ret = {}
    local maxLen = 0
    for y, oneRow in ipairs(map) do
        for x, color in ipairs(oneRow) do
            if color > 0 then
                local result = {}
                local links = {}
                local pos = {x = x, y = y, color = color}
                self:dfs(result, links, map, pos)

                if #result == maxLen then
                    if not self:is_same_link(result, ret) then
                        table.insert(ret, result)
                    end
                elseif #result > maxLen and #result >= MIN_LONG_SIZE then
                    ret = {result}
                    maxLen = #result
                end
            end
        end
    end

    return ret
end

-- 获取地图的最长连线
function root:get_map_max_link(seat, map)
    local halfMap = self:get_half_map(seat, map)
    local h = #halfMap
    local w = #halfMap[1]
    local longList = self:get_all_long(halfMap)

    table.sort(
        longList,
        function(a, b)
            return #a > #b
        end
    )

    local maxLink = {}
    for _, v in ipairs(longList) do
        if #maxLink >= #v then
            break
        end

        local link = self:get_long_max_link(v, w, h)
        if #link > #maxLink then
            maxLink = link
        end
    end
    return maxLink
end

-- 获取地图的最长连线列表（同一片色块只取一个）
function root:get_map_max_link_list(seat, map)
    local halfMap = self:get_half_map(seat, map)
    local h = #halfMap
    local w = #halfMap[1]
    local longList = self:get_all_long(halfMap)

    local maxLinkList = {}
    for _, v in ipairs(longList) do
        local link = self:get_long_max_link(v, w, h)
        table.insert(maxLinkList, link)
    end
    return maxLinkList
end

-- 从一片相连的色块中，获取最长的连线
function root:get_long_max_link(long, w, h)
    local map = self:long_to_map(long, w, h)

    local ret = {}
    local maxLen = 0
    for y, oneRow in ipairs(map) do
        for x, color in ipairs(oneRow) do
            if color > 0 then
                local result = {}
                local links = {}
                local pos = {x = x, y = y, color = color}
                self:dfs(result, links, map, pos)

                if #result > maxLen and #result >= MIN_LONG_SIZE then
                    ret = result
                    maxLen = #result

                    if #ret == #long then
                        return ret
                    end
                end
            end
        end
    end

    return ret
end

-- 拾取一条连线
function root:dfs(result, links, map, pos, nearCountMap)
    local x, y, tempColor = pos.x, pos.y, pos.color
    map[y][x] = 0
    table.insert(links, pos)

    local nearMap = {
        {x = -1, y = -1},
        {x = -1, y = 0},
        {x = -1, y = 1},
        {x = 0, y = -1},
        {x = 0, y = 1},
        {x = 1, y = -1},
        {x = 1, y = 0},
        {x = 1, y = 1}
    }
    for _, v in ipairs(nearMap) do
        local x1 = x + v.x
        local y1 = y + v.y
        if map[y1] and map[y1][x1] and map[y1][x1] > 0 then
            local color1 = map[y1][x1]
            local pos1 = {x = x1, y = y1, color = color1}
            self:dfs(result, links, map, pos1)
        end
    end

    if #links > #result then
        for ii, vv in ipairs(links) do
            result[ii] = vv
        end
    elseif nearCountMap and #links == #result then
        local pos1 = links[#links]
        local pos2 = result[#result]
        if nearCountMap[pos2.y][pos2.x] < nearCountMap[pos1.y][pos1.x] then
            for ii, vv in ipairs(links) do
                result[ii] = vv
            end
        end
    end

    table.remove(links)
    map[y][x] = tempColor
end

------------------------------ 工具方法 ------------------------------

-- 新建一个全0的地图
function root:new_zero_map(w, h)
    local ret = {}

    for y = 1, h do
        local oneRow = {}
        for x = 1, w do
            table.insert(oneRow, 0)
        end
        table.insert(ret, oneRow)
    end

    return ret
end

-- 合并数值
function root:array_merge(dest, src)
    for _, v in ipairs(src) do
        table.insert(dest, v)
    end
end

-- long 转 地图
function root:long_to_map(long, w, h)
    local map = self:new_zero_map(w, h)

    for _, v in ipairs(long) do
        map[v.y][v.x] = v.color
    end

    return map
end

-- 地图 转 long
function root:map_to_long(map)
    local long = {}

    for y, oneRow in ipairs(map) do
        for x, color in ipairs(oneRow) do
            if color > 0 then
                table.insert(long, {x = x, y = y, color = color})
            end
        end
    end

    return long
end

--[[ 判断是否同一条连线
条件1：数量一样
条件2：首尾一样或相反（落点一样）
条件3：都是一样的格子
]]
function root:is_same_link(link, list)
    local oneLink = list[1]
    if #link ~= #oneLink then
        -- 不是 数量一样
        return false
    end

    local linkX1, linkY1 = link[1].x, link[1].y
    local linkXN, linkYN = link[#link].x, link[#link].y
    local linkKey = self:get_link_key(link)
    for _, v in ipairs(list) do
        local x1, y1 = v[1].x, v[1].y
        local xN, yN = v[#v].x, v[#v].y
        if
            (linkX1 == x1 and linkY1 == y1 and linkXN == xN and linkYN == yN) or
                (linkX1 == xN and linkY1 == yN and linkXN == x1 and linkYN == y1)
         then
            -- 条件2：首尾一样或相反（落点一样）
            if linkKey == self:get_link_key(link) then
                -- 条件3：都是一样的格子
                return true
            end
        end
    end

    return false
end

-- 获取连线的key，格子相同字连线key一样
function root:get_link_key(link)
    local list = {}
    for _, v in ipairs(link) do
        local x, y = v.x, v.y
        local flag = y * 10 + x
        table.insert(list, flag)
    end
    table.sort(list)

    return table.concat(list, "")
end

-- 获取点周围的节点数
function root:get_near_pos_count(map, pos)
    local ret = 0

    local x, y = pos.x, pos.y
    local nearMap = {
        {x = -1, y = -1},
        {x = -1, y = 0},
        {x = -1, y = 1},
        {x = 0, y = -1},
        {x = 0, y = 1},
        {x = 1, y = -1},
        {x = 1, y = 0},
        {x = 1, y = 1}
    }
    for _, v in ipairs(nearMap) do
        local x1 = x + v.x
        local y1 = y + v.y
        if map[y1] and map[y1][x1] and map[y1][x1] > 0 then
            ret = ret + 1
        end
    end

    return ret
end

-- 打印一条龙
function root:print_long(formatStr, long, w, h)
    local map = self:long_to_map(long, w, h)
    self:print_map(formatStr, map)
end

-- 打印地图
function root:print_map(formatStr, map)
    local middleRow = #map / 2

    local rows = {}

    -- insert 在前面的原因：第一行输出在最后，即下面
    for y, oneRow in ipairs(map) do
        local str = string.format("| %s |", table.concat(oneRow, " "))
        table.insert(rows, 1, str)
        if y == middleRow then
            table.insert(rows, 1, "| - - - - - |")
        end
    end

    table.insert(rows, 1, "| - - - - - |")
    table.insert(rows, "| - - - - - |")

    local msg = table.concat(rows, "\n")
    printf(string.format(formatStr, msg))
end

-- 打印地图列表，水平排列
function root:print_map_list(formatStr, mapList)
    local height = #mapList[1]
    local middleRow = height / 2

    local rows = {}
    for i = 1, height + 3 do
        table.insert(rows, "")
    end

    local rowMap = {}
    -- y: 01 02 03 04 05 | 06 07 08 09 10
    -- r: 12 11 10 09 08 | 06 05 04 03 02
    for i = 1, height do
        if i <= middleRow then
            rowMap[i] = height - i + 3 -- 10 - 1 + 3
        else
            rowMap[i] = height - i + 2 -- 10 - 6 + 2
        end
    end

    for _, v in ipairs(mapList) do
        for y, oneRow in ipairs(v) do
            local row = rowMap[y]
            local str = string.format(" | %s |", table.concat(oneRow, " "))
            rows[row] = rows[row] .. str
        end

        rows[1] = rows[1] .. " | - - - - - |"
        rows[middleRow + 2] = rows[middleRow + 2] .. " | - - - - - |"
        rows[height + 3] = rows[height + 3] .. " | - - - - - |"
    end

    local msg = table.concat(rows, "\n")
    printf(string.format(formatStr, msg))
end

-- 单元测试
function root:test()
    math.randomseed(os.time())

    local map = self:random_map()
    -- local list = {{1, 1}, {1, 2}, {2, 2}, {3, 2}, {1, 3}, {1, 4}}
    -- for _, v in ipairs(list) do
    --     map[v[1]][v[2]] = 0
    -- end
    self:print_map("随机一个地图：\n%s", map)
    printf("")

    local map1 = self:get_half_map(1, map)
    self:print_map("获取下半部分地图：\n%s", map1)
    printf("")

    local map2 = self:get_half_map(2, map)
    self:print_map("获取上半部分地图：\n%s", map2)
    printf("")

    printf("获取上半部分地图的所有龙：")
    local map2 = self:get_half_map(2, map)
    local h = #map2
    local w = #map2[1]
    local longList = self:get_all_long(map2)
    for i, v in ipairs(longList) do
        local formatStr = "龙" .. i .. "：\n%s"
        self:print_long(formatStr, v, w, h)
    end
    printf("")

    printf("获取上半部分地图的所有最长连线：")
    local linkList = self:get_map_all_link(2, map)
    for i, v in ipairs(linkList) do
        local formatStr = "连线" .. i .. "：\n%s"
        self:print_long(formatStr, v, w, h)
    end
    printf("")

    printf("获取上半部分地图的最长连线：")
    local link = self:get_map_max_link(2, map)
    local formatStr = "最长连线：\n%s"
    self:print_long(formatStr, link, w, h)
    printf("")

    printf("获取上半部分地图的最长连线列表：")
    local linkList = self:get_map_max_link_list(2, map)
    for i, v in ipairs(linkList) do
        local formatStr = "最长连线" .. i .. "：\n%s"
        self:print_long(formatStr, v, w, h)
    end
    printf("")
end

function root:test_time(count)
    math.randomseed(os.time())

    local errorCount = 0
    for i = 1, count do
        local map = self:random_map()

        -- local map2 = self:get_half_map(2, map)
        -- self:get_all_long(map2)

        local linkList = self:get_map_all_link(2, map)
        -- local maxLink1 = {}
        -- for _, v in ipairs(linkList) do
        --     if #v > #maxLink1 then
        --         maxLink1 = v
        --     end
        -- end
    end

    printf("error count " .. errorCount)
end

-- root:test()
-- root:test_time(1000)

return root