Log In  



Hello! I just recently started messing around with pico-8 and am currently trying to make a fill detection function for a drawing game im working on

this function will take a 96x80 table (drawing_board) of either true or false values and will locate all enclosed loops of true values and fill them in.

My code works albeit very inefficiently (takes about 3 seconds with a sparse canvas) so any tips/suggestions to improve my functions would be greatly appreciated

 
-- Fill functions
function fill_enclosed_areas(drawing_board)
    local enclosed_areas = check_enclosed_areas(drawing_board)

    for i = 1, #enclosed_areas do
        fill_area(drawing_board, enclosed_areas[i])
    end
    return drawing_board
end

function check_enclosed_areas(drawing_board)
    local visited = {}
    local enclosed_areas = {}
    local enclosed_areas_coords = {}

    -- need to copy the drawing board to visited
    for x = 1, 96 do
        visited[x] = {}
        for y = 1, 80 do
            visited[x][y] = drawing_board[x][y]
        end
    end
    for x = 1, 96 do
        for y = 1, 80 do
            if visited[x][y] == false then
                visited, enclosed_areas_coords = fill_area(visited, {x=x, y=y})
                if #enclosed_areas_coords > 0 then
                    add(enclosed_areas, enclosed_areas_coords[1])
                end
            end
        end
    end
    return enclosed_areas
end

function fill_area(drawing_board, coords)
    drawing_board[coords.x][coords.y] = true

    local stack = {}
    local enclosed = true
    local enclosed_areas = {}

    add(stack, {x=coords.x, y=coords.y})

    while #stack > 0 do
        local current = stack[#stack]

        -- check up
        if current.y > 1 then
            if drawing_board[current.x][current.y - 1] == false then
                add(stack, {x = current.x, y = current.y - 1})
                drawing_board[current.x][current.y - 1] = true
            end
        else
            enclosed = false
        end

        -- check down
        if current.y < 80 then
            if drawing_board[current.x][current.y + 1] == false then
                add(stack, {x = current.x, y = current.y + 1})
                drawing_board[current.x][current.y + 1] = true
            end
        else
            enclosed = false
        end

        -- check left
        if current.x > 1 then
            if drawing_board[current.x - 1][current.y] == false then
                add(stack, {x = current.x - 1, y = current.y})
                drawing_board[current.x - 1][current.y] = true
            end
        else
            enclosed = false
        end

        -- check right
        if current.x < 96 then
            if drawing_board[current.x + 1][current.y] == false then
                add(stack, { x = current.x + 1, y = current.y})
                drawing_board[current.x + 1][current.y] = true
            end
        else
            enclosed = false
        end

        del(stack, current)

    end

    if enclosed then
        add(enclosed_areas, {x = coords.x, y = coords.y})
    end
    return drawing_board, enclosed_areas
end
2

First, I recommend using pset() and pget() to make the purpose and result clear.
By doing this, you can omit the two-dimensional table drawing_board by using the screen buffer, which should make the code easier to read.
(The next steps will help you to make your code the shortest and fastest.)

https://www.lexaloffle.com/dl/docs/pico-8_manual.html#PSET
https://www.lexaloffle.com/dl/docs/pico-8_manual.html#PGET

You also need to run 'cls()' beforehand to clean the screen.

@bbread, do you need the list of enclosed areas or just the coloring ?
If it's just the coloring, you could add a 1 tile border to the array, do a flood fill from a corner, converting false to a third value "border", and after that , going over the array, turning "border" to false and the unattained false to true.

For the flood fill itself, since you seek performance rather than tokens, you should deal with horizontal segments (the board is wider than it's tall) rather than single cells. (span filling).



[Please log in to post a comment]