Lua A 寻路：启发函数引导的路径搜索

-- 错误：无差别扩散，大地图穷举到天荒地老
for _, step in ipairs(allDirections) do
    expand(step)
end

local function heuristic(x, y, tx, ty)
    return math.abs(x - tx) + math.abs(y - ty)
end
local function findPath(sx, sy, tx, ty)
    local open = {{x = sx, y = sy, g = 0,
        f = heuristic(sx, sy, tx, ty)}}
    local closed, from = {}, {}
    local keyOf = function(x, y) return x .. "_" .. y end
    while #open > 0 do
        local best = 1
        for i = 2, #open do
            if open[i].f < open[best].f then best = i end
        end
        local cur = table.remove(open, best)
        local ck = keyOf(cur.x, cur.y)
        if closed[ck] then
        else
            closed[ck] = true
            if cur.x == tx and cur.y == ty then
                local path = {}
                local k = ck
                while from[k] do
                    path[#path + 1] = k
                    k = from[k]
                end
                return path
            end
            for _, d in ipairs({{1,0},{-1,0},{0,1},{0,-1}}) do
                local nx, ny = cur.x + d[1], cur.y + d[2]
                local nk = keyOf(nx, ny)
                if not closed[nk] and passable(nx, ny) then
                    from[nk] = ck
                    local g = cur.g + 1
                    open[#open + 1] = {x = nx, y = ny,
                        g = g, f = g + heuristic(nx, ny, tx, ty)}
                end
            end
        end
    end
    return nil
end