【进阶实战】A 寻路的表驱动实现：开放列表与启发函数

local walkable = {}
for y = 1, 10 do
    walkable[y] = {}
    for x = 1, 10 do
        walkable[y][x] = 1
    end
end
walkable[5][3] = 0
walkable[5][4] = 0
walkable[5][5] = 0
local function heuristic(x1, y1, x2, y2)
    return math.abs(x1 - x2) + math.abs(y1 - y2)
end
local function findPath(sx, sy, ex, ey)
    local open = { { x = sx, y = sy, g = 0, f = heuristic(sx, sy, ex, ey) } }
    local closed = {}
    local came = {}
    local iter = 0
    while #open > 0 do
        iter = iter + 1
        if iter > 200 then
            return nil
        end
        local bi = 1
        for i = 2, #open do
            if open[i].f < open[bi].f then
                bi = i
            end
        end
        local cur = table.remove(open, bi)
        local ck = cur.x .. "," .. cur.y
        if closed[ck] then
            goto continue
        end
        closed[ck] = true
        if cur.x == ex and cur.y == ey then
            local path = {}
            local k = ck
            while k do
                table.insert(path, 1, k)
                k = came[k]
            end
            return path
        end
        local dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }
        for _, d in ipairs(dirs) do
            local nx, ny = cur.x + d[1], cur.y + d[2]
            if nx >= 1 and nx <= 10 and ny >= 1 and ny <= 10
                and walkable[ny][nx] == 1 then
                local g = cur.g + 1
                table.insert(open, { x = nx, y = ny, g = g,
                    f = g + heuristic(nx, ny, ex, ey) })
                came[nx .. "," .. ny] = ck
            end
        end
        ::continue::
    end
    return nil
end

local path = findPath(1, 1, 8, 8)
if path then
    sendmsg(nil, 1, "找到路径，途经 " .. #path .. " 格")
end