每日算法 — 使用java实现塔防：Dinic最小割塔位封锁与距离场覆盖评估

塔防的本质是”割”

塔防（Tower Defense）的核心博弈常常被误解成”哪块地放塔伤害最高”。真正决定胜负的是另一件事：能不能把敌人的行进路线掐断或者拉长。

把所有可通行格子建成一张图，出生点是源 S、基地是汇 T。一个塔位如果能把 S 到 T 的所有路径都切断，这批敌人就永远到不了基地——这就是图论里的割（cut）。而”造价最低的封路方案”就是最小割，由最大流最小割定理，它等价于 S→T 的最大流。

不过塔防还有一条硬规则：必须至少留一条路，否则敌人无处可走，游戏会判定地图非法（或者敌人直接改走另一条动态路径）。所以我们要解的是”带单路径保留约束的最小割“，这个精确版本是 NP-hard 的，但网格地图上可以用一个非常实用的迭代松弛法把它做出来。

建模：节点分裂消点权

塔的造价是格子成本（点权），而最大流处理的是边权。标准做法是节点分裂（node splitting）：把每个格子 v 拆成 v_in → v_out，中间连一条容量等于造价的边。所有原本连接 u→v 的边改成 u_out → v_in，容量 INF。

这样最小割切到的必然是若干条 v_in→v_out 边，每条对应一个格子，割的容量和就是总造价。

public final class GridFlow {
    private static final int INF = 1 << 28;
    private final int h, w;
    private final int n;          // 2 * h * w 个节点
    private Dinic dinic;
    private final int[][] cost;   // 每格塔造价，-1 表示不可建

    public GridFlow(int[][] cost) {
        this.cost = cost;
        this.h = cost.length;
        this.w = cost[0].length;
        this.n = h * w * 2;
        this.dinic = new Dinic(n);
        build();
    }

    private int in(int y, int x)  { return (y * w + x) * 2; }
    private int out(int y, int x) { return (y * w + x) * 2 + 1; }

    private void build() {
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                int cap = (cost[y][x] < 0) ? INF : Math.max(1, cost[y][x]);
                dinic.addEdge(in(y, x), out(y, x), cap);       // 点权 → 边权
                for (int k = 0; k < 4; k++) {
                    int ny = y + DY[k], nx = x + DX[k];
                    if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
                    dinic.addEdge(out(y, x), in(ny, nx), INF);  // 移动边不设限
                }
            }
        }
    }
}

Dinic 实现

Dinic 在单位容量网格图上表现极好（O(E√V) 级别），比 Edmonds-Karp 快一到两个数量级。核心是 BFS 分层 + DFS 多路增广 + 当前弧优化。

final class Dinic {
    static final class Edge {
        int to, rev, cap;
        Edge(int to, int rev, int cap) { this.to = to; this.rev = rev; this.cap = cap; }
    }
    private final List<Edge>[] g;
    private final int[] level, iter;

    @SuppressWarnings("unchecked")
    Dinic(int n) {
        g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        level = new int[n];
        iter = new int[n];
    }

    void addEdge(int u, int v, int cap) {
        g[u].add(new Edge(v, g[v].size(), cap));
        g[v].add(new Edge(u, g[u].size() - 1, 0));   // 反向边容量 0
    }

    private boolean bfs(int s, int t) {
        Arrays.fill(level, -1);
        Deque<Integer> q = new ArrayDeque<>();
        level[s] = 0; q.add(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (Edge e : g[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.add(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    private int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (; iter[u] < g[u].size(); iter[u]++) {       // 当前弧优化
            Edge e = g[u].get(iter[u]);
            if (e.cap <= 0 || level[e.to] != level[u] + 1) continue;
            int d = dfs(e.to, t, Math.min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                g[e.to].get(e.rev).cap += d;
                return d;
            }
        }
        return 0;
    }

    long maxflow(int s, int t) {
        long flow = 0;
        while (bfs(s, t)) {
            Arrays.fill(iter, 0);
            int f;
            while ((f = dfs(s, t, Integer.MAX_VALUE)) > 0) flow += f;
        }
        return flow;
    }
}

从最大流回溯出最小割（塔位集合）

最大流跑完后，在残量网络上从 S 做一次可达性 BFS，得到集合 R。所有 u ∈ R 且 v ∉ R 的原始正向边就是割边。对应到节点分裂图，割边 v_in → v_out 就是”需要在 v 放塔”的格子。

public List<int[]> minCutCells() {
    long flow = dinic.maxflow(in(sy, sx), out(ty, tx));
    // 残量网络可达集
    boolean[] reach = dinic.residualReachable(in(sy, sx));
    List<int[]> cells = new ArrayList<>();
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            if (cost[y][x] < 0) continue;
            if (reach[in(y, x)] && !reach[out(y, x)]) {   // 割到的点权边
                cells.add(new int[]{y, x});
            }
        }
    }
    return cells;   // 造价总和 == flow，且封路后 S 与 T 不可达
}

这一步给出的就是”最便宜的全封方案“，总造价恰好等于最大流值。但它把路完全掐断了，不符合”必须留路”的规则。下面的迭代松弛就是为解决这一点。

迭代松弛：保留一条主干路径

思路很直接：最小割一定会切到”最便宜的那条路径”。那我们就把这条路径保护起来（相关格子的容量改成 INF），再算一次最小割——新割必然会绕开它，从而保留这条路。

public List<int[]> minCutKeepOnePath() {
    List<int[]> cut = minCutCells();
    for (int round = 0; round < 3; round++) {
        // 1) 找出被割格子中"最便宜路径"经过的那一个，解除封锁
        List<int[]> path = shortestPathWithCost();     // Dijkstra，跳过已割格子以外
        if (path.isEmpty()) break;
        for (int[] c : path) {
            if (contains(cut, c)) cost[c[0]][c[1]] = -1;  // 视为不可建，保住这条通道
        }
        // 2) 重建图并重新求割
        rebuild();
        List<int[]> next = minCutCells();
        if (next.size() <= cut.size()) { cut = next; } else break;
    }
    return cut;
}

每轮”封一条最便宜路径、保留它”，最多迭代 3~5 轮就能得到一个既省钱又留路的方案。这是把 NP-hard 的约束版割问题，用”割 → 解封最便宜路径 → 重割”的局部修正近似掉了。

塔位覆盖评估：Dijkstra 距离场

割解决了”路怎么走”，但真正造成伤害的是敌人在这条路上被塔覆盖了多久。用 Dijkstra 距离场（从基地反向跑一次最短路）可以给每个格子标注”到基地的距离”，进而算出：

• 塔位 p 的覆盖圈内，敌人经过的总步数 = 覆盖格子的 dist 分布跨度；
• 覆盖价值可以用加权和：value(p) = Σ_{q ∈ range(p)} w(dist(q))，其中 w 是”早击杀价值更高”的衰减函数，例如 w(d) = exp(-d / τ)。

public final class CoverageField {
    private final int[] dist;          // 到基地的最短步数
    private final int h, w;

    /** 反向 Dijkstra：从基地出发，得到全图距离场 */
    public CoverageField(boolean[][] walkable, int ty, int tx) {
        h = walkable.length; w = walkable[0].length;
        dist = new int[h * w];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        dist[ty * w + tx] = 0;
        pq.add(new int[]{0, ty, tx});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[0] != dist[cur[1] * w + cur[2]]) continue;
            for (int k = 0; k < 4; k++) {
                int ny = cur[1] + DY[k], nx = cur[2] + DX[k];
                if (ny < 0 || nx < 0 || ny >= h || nx >= w || !walkable[ny][nx]) continue;
                if (dist[ny * w + nx] > cur[0] + 1) {
                    dist[ny * w + nx] = cur[0] + 1;
                    pq.add(new int[]{cur[0] + 1, ny, nx});
                }
            }
        }
    }

    /** 单塔价值：覆盖圈内按距离衰减加权 */
    public double towerValue(int y, int x, int range, double tau) {
        double v = 0;
        for (int dy = -range; dy <= range; dy++) {
            for (int dx = -range; dx <= range; dx++) {
                if (dy * dy + dx * dx > range * range) continue;
                int ny = y + dy, nx = x + dx;
                if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
                int d = dist[ny * w + nx];
                if (d == Integer.MAX_VALUE) continue;
                v += Math.exp(-d / tau);
            }
        }
        return v;
    }
}

把”最小割给出的必需封锁格”和”覆盖价值最高的格子”合并：先按割集建塔保底，再用剩余预算按 value/cost 降序贪心补塔，直到预算耗尽。

完整项目结构

tower-defense-cut/
├── pom.xml
└── src/main/java/com/daily/algorithm/td/
    ├── GridFlow.java          // 节点分裂图构建 + 重建
    ├── Dinic.java             // 最大流 / 最小割
    ├── CutExtractor.java      // 残量网络回溯割边
    ├── CoverageField.java     // Dijkstra 距离场与覆盖价值
    ├── TowerPlanner.java      // 割集保底 + 性价比贪心补塔
    └── Main.java              // 示例地图与输出

复杂度分析

设格子数 V = h·w，节点数 2V，边数约 6V（每格 1 条点权边 + 4 条移动边）。

• 单次最大流：Dinic 在网格图上 O(E√V) = O(V^1.5)；100×100 地图约 200 万次边松弛，单次 50ms 内可出结果；
• 迭代松弛：最多 k 轮，总代价 O(k·V^1.5)；
• 距离场：一次 Dijkstra O(V log V)；
• 覆盖评估：O(V·π·range²)，range=3 时约 28 倍常数。

对比”随机撒塔 + 怪物模拟”的暴力评估（每方案都要跑一遍完整模拟），这套流程把方案筛选从”万次模拟”压缩到”几十次割求解”，是塔防 AI 的实用骨架。

小结

塔防看起来是”摆塔补伤害”，本质却是图论上的割问题。最大流最小割定理给出了”最低造价的封锁方案”；节点分裂把点权（塔造价）转成边权；残量网络回溯把抽象的流值变成具体的格子坐标。再加上”封路必须留一条”的规则，用迭代松弛近似求解；最后用 Dijkstra 距离场把”封路”翻译成”敌人暴露时长”，让塔位选择真正对齐到伤害收益。这三步组合，就是一套可解释、可复现的塔防布局 AI。