【网络通信】服务器寻路：A* 的格子实现与裁剪

---A* 寻路：曼哈顿启发式
function Path.find(mapId, sx, sy, tx, ty)
    local open = { { x = sx, y = sy, g = 0,
        f = math.abs(tx - sx) + math.abs(ty - sy) } }
    local came, gScore = {}, {}
    gScore[sx .. "," .. sy] = 0
    local steps = 0

    while #open > 0 do
        -- 取 f 最小的节点
        table.sort(open, function(a, b) return a.f < b.f end)
        local cur = table.remove(open, 1)
        steps = steps + 1
        if steps > 500 then return nil end     -- 规模裁剪
        if cur.x == tx and cur.y == ty then
            return Path.rebuild(came, cur)
        end
        for _, d in ipairs(Path.dirs) do
            local nx, ny = cur.x + d[1], cur.y + d[2]
            if gridattr(mapId, nx, ny, 1) then
                local ng = cur.g + 1
                local key = nx .. "," .. ny
                if not gScore[key] or ng < gScore[key] then
                    gScore[key] = ng
                    came[key] = cur.x .. "," .. cur.y
                    open[#open + 1] = { x = nx, y = ny,
                        g = ng,
                        f = ng + math.abs(tx - nx) + math.abs(ty - ny) }
                end
            end
        end
    end
    return nil
end

---路径的平滑：合并同方向的格子串
function Path.rebuild(came, goal)
    local path = {}
    local cur = goal.x .. "," .. goal.y
    while cur do
        local x, y = cur:match("(%d+),(%d+)")
        path[#path + 1] = { x = tonumber(x), y = tonumber(y) }
        cur = came[cur]
    end
    -- 反向得到起点到终点
    local out = {}
    for i = #path, 1, -1 do out[#out + 1] = path[i] end
    return Path.simplify(out)
end

---同向合并：十格直线变一个节点
function Path.simplify(path)
    local out = {}
    for i = 1, #path do
        local a, b = out[#out], path[i]
        if not a then
            out[1] = b
        else
            local dx1, dy1 = b.x - a.x, b.y - a.y
            local p = path[i - 1]
            local dx2, dy2 = a.x - p.x, a.y - p.y
            if dx1 * (dx2 == 0 and 0 or 1) ~= dx2 * (dx1 == 0 and 0 or 1)
                or dy1 ~= dy2 then
                out[#out + 1] = b
            end
        end
    end
    return out
end