G

function pathfind(map, x2, y2, x1, y1)

    map_width = #map[1]
    map_height = #map

    local function in_bounds(x, y) --check location is in bounds of map
        return x > 0 and
        y > 0 and
        x <= map_width and
        y <= map_height
    end

    local translations = { --valid move directions, note we do not have diagonal translations
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
    }

    path_map = {} --generate a new map of 0s that has the same dimensions
    for y, row in ipairs (map) do
        local new_row = {}
        for x, val in ipairs(row) do
            table.insert(new_row, 0)
        end
        table.insert(path_map, new_row)
    end

    local fill_positions = {{x1,y1,9}} -- startx, starty, currentvalue .. this is a list of positions to check next

    local sucess = false

    while #fill_positions > 0 do

        local current_pos = table.remove(fill_positions,1) --lua "pop" the first element in a table

        local xPos = current_pos[1]
        local yPos = current_pos[2]
        local count = current_pos[3]

        if in_bounds(xPos, yPos) then
            if map[yPos][xPos] == 0 and path_map[yPos][xPos] == 0 then --both squares on maps are free
                path_map [yPos][xPos] = count + 1 --mark with count + 1


                if xPos == x2 and yPos == y2 then
                    sucess = true
                    break --if we reach destination we can cancel flood fill
                end

                for _,translation in ipairs(translations) do --add all the surrounding squares to a check list
                    -- print(inspect(translation))
                    local new_fill_pos = {xPos + translation[1], yPos + translation[2], count +1}
                    table.insert(fill_positions, new_fill_pos)
                end
            end
        end
    end

    local results = {}

    if sucess then

        local current_pos = {x2,y2}

        table.insert (results, current_pos)

        while true do
            local current_number = path_map[current_pos[2]][current_pos[1]]
            if current_number == 10 then --we must have reached the destination (value 10)
                break --so break loop
            end

            for _, translation in ipairs(translations) do --look for first tile surrounding with a number one lower
                local check_pos = {current_pos[1]+translation[1], current_pos[2] + translation[2]}
                if in_bounds(check_pos[1], check_pos[2]) then
                    if path_map[check_pos[2]][check_pos[1]] == current_number - 1 then

                        table.insert(results, check_pos) --save the result
                        current_number = current_number - 1 --lower the current number
                        current_pos = check_pos
                        break --don't check any more translations as this one was okay (loop will continue)
                    end
                end
            end
        end
        return results
    end
end


local test_map = {
        {0, 0, 1, 0},
        {0, 0, 0, 0},
        {0, 1, 1, 0},
        {0, 0, 1, 0},
    }

print('PATHFIND TESTS')
print('pathfind result:',inspect(pathfind(test_map, 1,1, 4,4)))
print('pathfind result:',inspect(pathfind(test_map, 1,1, 3,4))) --blocked example