【高级技巧】BFS广度优先：最短路径的队列搜索封装

local function bfsPath(grid, start, finish)
    local queue = { start }
    local visited = { [start.x .. "," .. start.y] = true }
    local prev = {}
    while #queue > 0 do
        local cur = table.remove(queue, 1)
        if cur.x == finish.x and cur.y == finish.y then
            local path = {}
            local key = cur.x .. "," .. cur.y
            while key do
                table.insert(path, 1, key)
                key = prev[key]
            end
            return path
        end
        for _, d in ipairs({ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }) do
            local nx, ny = cur.x + d[1], cur.y + d[2]
            local key = nx .. "," .. ny
            if grid[ny] and grid[ny][nx] == 1 and not visited[key] then
                visited[key] = true
                prev[key] = cur.x .. "," .. cur.y
                queue[#queue + 1] = { x = nx, y = ny }
            end
        end
    end
    return nil
end

local path = bfsPath(walkGrid, { x = 1, y = 1 }, { x = 8, y = 8 })
if path then
    print("最短路径 " .. #path .. " 步")
end