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).

@RealShadowCaster ooh i like that, ill give that a try as that should cut the time down by at least half, the first fill will be the outside section and any subsequent fills will be the inside sections

@bbread, there should be only one fill : once the outside fill marked every tile connected to the border as "border", you don't need another fill :
every false remaining is inside a shape and has just to turn to true. You can go over every cell without needing to check cell neighborhood.

@RealShadowCaster I just implemented that and the one catch for that as you pointed out is you cant let the user draw on the border as if they enclose the section the enclosed detection function starts in then the rest of the screen will be considered as an enclosed shape.

its improved the efficiency a bit but I'm still trying to make it better

im gonna try to mess around with storing the drawing board as an array of binary values instead of Booleans so i can check multiple cells at the same time



[Please log in to post a comment]