【Lua实战】A星寻路实战：竞技场护卫追击的网格路径计算

local open, closed = {}, {}
local function key(x, y) return x * 1000 + y end
table.insert(open, { x = sx, y = sy, g = 0, f = 0 })
local function popBest(list)
    local bi, b = 1, list[1]
    for i = 2, #list do
        if list[i].f < b.f then bi, b = i, list[i] end
    end
    table.remove(list, bi)
    return b
end

local dirs = { {1,0}, {-1,0}, {0,1}, {0,-1} }
for step = 1, 400 do
    if #open == 0 then return nil end
    local cur = popBest(open)
    if cur.x == tx and cur.y == ty then return buildPath(closed, cur) end
    closed[key(cur.x, cur.y)] = cur
    for _, d in ipairs(dirs) do
        local nx, ny = cur.x + d[1], cur.y + d[2]
        if passable(nx, ny) and not closed[key(nx, ny)] then
            local g = cur.g + 1
            local h = math.abs(nx - tx) + math.abs(ny - ty)
            table.insert(open, { x = nx, y = ny, g = g, f = g + h })
        end
    end
end