tile mergin algorithm: takes sparse matrix of which tiles are solid and returns merged rectangles, drastically reducing the number of shapes

merging.lua

local tile_width, tile_height = -- tile size, for example 32x32
local is_solid_matrix = -- sparse matrix for whom get(x, y) returns true if a tile at position x, y (1-indexed) is solid, false otherwise
local min_x, min_y, max_x, max_y = -- index range of is_solid_matrix, for example -32, -15, 125, 268, depending on map chunking

local visited = {} -- dense 2d matrix, keeps track of which tiles are already merged
local function is_visited(x, y)
    return visited[y] and visited[y][x]
end

local function find_rectangle(x, y)
    -- initialize rectangle dimensions: start with 1x1 tile
    local width, height = 0, 1

    -- Phase 1: expand horizontally (right) as much as possible
    -- keep expanding width while tiles to the right are solid
    while is_solid_matrix:get(x + width, y) do
        width = width + 1
    end

    -- Phase 2: choose expansion strategy based on initial horizontal expansion
    if width == 1 then
        -- horizontal expansion failed (only 1 tile wide)
        -- try vertical expansion first, then horizontal

        -- expand vertically (down) as much as possible for single column
        while is_solid_matrix:get(x, y + height) do
            height = height + 1
        end

        -- now try to expand horizontally while maintaining the vertical height
        while true do
            -- check if we can add another column to the right
            -- verify all tiles in the new column (from y to y + height) are solid
            for col_offset = 0, height do
                local current_x, current_y = x + width, y + col_offset
                if is_solid_matrix:get(current_x, current_y) ~= true then
                    goto done
                end
            end
            -- all tiles in the new column are solid, expand width
            width = width + 1
        end
        ::done::
    else
        -- strategy B: horizontal expansion succeeded (width > 1)
        -- try to expand vertically while maintaining the horizontal width

        while true do
            -- check if we can add another row below
            -- verify all tiles in the new row (from x to x + width) are solid
            for row_offset = 0, width do
                local current_x, current_y = x + row_offset, y + height
                if is_solid_matrix:get(current_x, current_y) ~= true then
                    goto done
                end
            end
            -- all tiles in the new row are solid, expand height
            height = height + 1
        end
        ::done::
    end

    -- phase 3: mark all tiles in the found rectangle as visited
    -- this prevents them from being processed again in future iterations
    for i = 0, height - 1 do
        for j = 0, width - 1 do
            -- ensure the row exists in the visited table
            if not visited[y + i] then
                visited[y + i] = {}
            end
            -- eark this specific tile as visited
            visited[y + i][x + j] = true
        end
    end

    -- return the rectangle bounds: top-left corner (x,y) and dimensions (width,height)
    return x, y, width, height
end

-- iterate all tiles, then merge hitboxes
for y = min_y, max_y do
    for x = min_x, max_x do
        if is_solid_matrix:get(x, y) and not is_visited(x, y) then
            local x, y, w, h = find_rectangle(x, y)
            x = (x - 1) * tile_width
            y = (y - 1) * tile_height
            w = w * tile_width
            h = h * tile_height

            -- use hitbox, which is aabb x, y, w, h
        end
    end
end