每日算法 — 使用java实现红色警戒：拓扑排序建造依赖与资源采集贪心调度

引言

《红色警戒》作为经典的即时战略游戏，其核心策略在于如何高效地管理基地建设与资源采集。建造高级单位往往需要前置建筑，形成复杂的依赖链；而采矿车如何在多个矿区间选择最优路线，直接决定了经济优势。本文用Java实现拓扑排序解析建造依赖树与贪心策略调度资源采集，构建一个高效的基地运营决策引擎。

核心算法设计

1. 建造依赖的拓扑排序

游戏中的建筑之间存在严格的依赖关系：建造兵营需要先建发电厂，建造战车工厂需要先建兵营。这构成了一张有向无环图（DAG）。使用Kahn算法进行拓扑排序，可在O(V+E)时间内计算出合法的建造顺序，并检测循环依赖错误。

2. 资源采集贪心调度

采矿车面对多个矿区时，需要综合考虑：矿区剩余资源量、距离远近、当前排队车辆数。贪心策略每次选择”单位时间内期望收益最高”的矿区，实现资源采集效率最大化。

完整Java实现

import java.util.*;

/**
 * 红色警戒风格基地运营算法
 * 包含拓扑排序建造依赖解析与资源采集贪心调度
 */
public class RedAlertBase {

    // 建筑定义
    static class Building {
        String name;
        int cost;           // 造价
        int buildTime;      // 建造时间（秒）
        int power;          // 耗电量（负值表示发电）
        List<String> dependencies; // 前置建筑名称列表

        Building(String name, int cost, int time, int power, List<String> deps) {
            this.name = name;
            this.cost = cost;
            this.buildTime = time;
            this.power = power;
            this.dependencies = deps != null ? deps : new ArrayList<>();
        }
    }

    // 矿区定义
    static class OreField {
        String name;
        Vec2 pos;           // 位置
        int totalOre;       // 总储量
        int remainingOre;   // 剩余储量
        double miningRate;  // 每秒开采速度
        List<MiningTruck> queue; // 当前排队车辆

        OreField(String name, Vec2 pos, int ore, double rate) {
            this.name = name;
            this.pos = pos;
            this.totalOre = ore;
            this.remainingOre = ore;
            this.miningRate = rate;
            this.queue = new ArrayList<>();
        }

        // 计算当前排队等待时间
        double queueWaitTime() {
            return queue.size() * 5.0; // 假设每车装载5秒
        }

        // 预计单位时间收益 = 矿区价值 / (往返时间 + 排队时间)
        double expectedYield(Vec2 basePos, double truckSpeed) {
            double distance = pos.dist(basePos);
            double travelTime = distance / truckSpeed * 2; // 往返
            double waitTime = queueWaitTime();
            double effectiveRate = Math.min(miningRate, remainingOre / 100.0);
            return effectiveRate / (travelTime + waitTime + 1.0);
        }
    }

    static class Vec2 {
        double x, y;
        Vec2(double x, double y) { this.x = x; this.y = y; }
        double dist(Vec2 v) {
            return Math.sqrt((x-v.x)*(x-v.x) + (y-v.y)*(y-v.y));
        }
    }

    static class MiningTruck {
        String id;
        Vec2 pos;
        int capacity;      // 运载容量
        int load;          // 当前装载量
        OreField target;   // 目标矿区

        MiningTruck(String id, Vec2 pos, int cap) {
            this.id = id;
            this.pos = pos;
            this.capacity = cap;
            this.load = 0;
        }
    }

    private Map<String, Building> buildingDB;

    public RedAlertBase() {
        buildingDB = new HashMap<>();
        initBuildings();
    }

    private void initBuildings() {
        // 发电厂不依赖任何建筑
        buildingDB.put("发电厂", new Building("发电厂", 800, 10, 200, null));
        // 兵营需要发电厂
        buildingDB.put("兵营", new Building("兵营", 500, 15, -50, 
            Arrays.asList("发电厂")));
        // 矿石精炼厂需要发电厂
        buildingDB.put("矿石精炼厂", new Building("矿石精炼厂", 2000, 20, -75,
            Arrays.asList("发电厂")));
        // 战车工厂需要兵营和矿石精炼厂
        buildingDB.put("战车工厂", new Building("战车工厂", 2000, 25, -100,
            Arrays.asList("兵营", "矿石精炼厂")));
        // 雷达站需要矿石精炼厂
        buildingDB.put("雷达站", new Building("雷达站", 1000, 20, -150,
            Arrays.asList("矿石精炼厂")));
        // 作战实验室需要雷达站和战车工厂
        buildingDB.put("作战实验室", new Building("作战实验室", 2000, 30, -200,
            Arrays.asList("雷达站", "战车工厂")));
        // 空指部需要作战实验室
        buildingDB.put("空指部", new Building("空指部", 1500, 25, -100,
            Arrays.asList("作战实验室")));
        // 核弹发射井需要作战实验室
        buildingDB.put("核弹发射井", new Building("核弹发射井", 5000, 60, -300,
            Arrays.asList("作战实验室")));
    }

    /**
     * Kahn算法拓扑排序：计算建造目标建筑所需的完整建造顺序
     * 返回从基础到目标的合法建造序列
     */
    public List<String> buildOrder(String target) {
        if (!buildingDB.containsKey(target)) {
            throw new IllegalArgumentException("未知建筑: " + target);
        }

        // 收集所有相关建筑（目标及其所有依赖）
        Set<String> relevant = new HashSet<>();
        collectDependencies(target, relevant);

        // 构建子图的入度表
        Map<String, Integer> inDegree = new HashMap<>();
        Map<String, List<String>> adj = new HashMap<>();
        for (String b : relevant) {
            inDegree.put(b, 0);
            adj.put(b, new ArrayList<>());
        }

        for (String b : relevant) {
            Building building = buildingDB.get(b);
            for (String dep : building.dependencies) {
                if (relevant.contains(dep)) {
                    adj.get(dep).add(b); // dep -> b
                    inDegree.put(b, inDegree.get(b) + 1);
                }
            }
        }

        // Kahn算法
        Queue<String> queue = new LinkedList<>();
        for (String b : relevant) {
            if (inDegree.get(b) == 0) queue.offer(b);
        }

        List<String> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            order.add(cur);
            for (String next : adj.get(cur)) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) queue.offer(next);
            }
        }

        if (order.size() != relevant.size()) {
            throw new RuntimeException("存在循环依赖，无法建造");
        }
        return order;
    }

    private void collectDependencies(String building, Set<String> collected) {
        if (collected.contains(building)) return;
        collected.add(building);
        Building b = buildingDB.get(building);
        if (b != null) {
            for (String dep : b.dependencies) {
                collectDependencies(dep, collected);
            }
        }
    }

    /**
     * 计算建造总成本与总时间
     */
    public BuildPlan analyzeBuildPlan(String target) {
        List<String> order = buildOrder(target);
        int totalCost = 0;
        int totalTime = 0;
        int powerBalance = 0;

        for (String name : order) {
            Building b = buildingDB.get(name);
            totalCost += b.cost;
            totalTime += b.buildTime;
            powerBalance += b.power;
        }

        return new BuildPlan(order, totalCost, totalTime, powerBalance);
    }

    static class BuildPlan {
        List<String> order;
        int totalCost, totalTime, powerBalance;
        BuildPlan(List<String> o, int c, int t, int p) {
            this.order = o; this.totalCost = c; this.totalTime = t; this.powerBalance = p;
        }
    }

    /**
     * 贪心调度：为每辆采矿车分配最优矿区
     * 每次选择使全局收益增量最大的分配方案
     */
    public void greedyAssignTrucks(List<MiningTruck> trucks, List<OreField> fields, 
                                    Vec2 basePos, double truckSpeed) {
        // 清空旧队列
        for (OreField f : fields) f.queue.clear();

        for (MiningTruck truck : trucks) {
            OreField bestField = null;
            double bestYield = -1;

            for (OreField field : fields) {
                if (field.remainingOre <= 0) continue;

                // 临时加入队列，计算边际收益
                field.queue.add(truck);
                double yield = field.expectedYield(basePos, truckSpeed);
                field.queue.remove(truck);

                if (yield > bestYield) {
                    bestYield = yield;
                    bestField = field;
                }
            }

            if (bestField != null) {
                truck.target = bestField;
                bestField.queue.add(truck);
            }
        }
    }

    /**
     * 模拟一帧资源采集更新
     */
    public void simulateMining(List<MiningTruck> trucks, List<OreField> fields,
                                Vec2 basePos, double truckSpeed, double dt) {
        for (MiningTruck truck : trucks) {
            if (truck.target == null) continue;

            OreField target = truck.target;
            double distToField = truck.pos.dist(target.pos);
            double distToBase = truck.pos.dist(basePos);

            if (truck.load < truck.capacity && distToField > 1.0) {
                // 前往矿区
                Vec2 dir = new Vec2(
                    (target.pos.x - truck.pos.x) / distToField,
                    (target.pos.y - truck.pos.y) / distToField
                );
                truck.pos = new Vec2(
                    truck.pos.x + dir.x * truckSpeed * dt,
                    truck.pos.y + dir.y * truckSpeed * dt
                );
            } else if (truck.load < truck.capacity && distToField <= 1.0) {
                // 在矿区装载
                int mined = (int)(target.miningRate * dt);
                mined = Math.min(mined, target.remainingOre);
                mined = Math.min(mined, truck.capacity - truck.load);
                truck.load += mined;
                target.remainingOre -= mined;
            } else if (truck.load >= truck.capacity && distToBase > 1.0) {
                // 返回基地
                Vec2 dir = new Vec2(
                    (basePos.x - truck.pos.x) / distToBase,
                    (basePos.y - truck.pos.y) / distToBase
                );
                truck.pos = new Vec2(
                    truck.pos.x + dir.x * truckSpeed * dt,
                    truck.pos.y + dir.y * truckSpeed * dt
                );
            } else if (truck.load >= truck.capacity && distToBase <= 1.0) {
                // 卸货
                truck.load = 0;
            }
        }
    }

    // 演示主方法
    public static void main(String[] args) {
        RedAlertBase game = new RedAlertBase();

        // 测试拓扑排序
        System.out.println("=== 建造核弹发射井的依赖分析 ===");
        BuildPlan plan = game.analyzeBuildPlan("核弹发射井");
        System.out.println("建造顺序: " + String.join(" -> ", plan.order));
        System.out.printf("总造价: $%d, 总时间: %ds, 电力盈余: %d%n",
            plan.totalCost, plan.totalTime, plan.powerBalance);

        // 测试资源采集调度
        System.out.println("\n=== 矿区采集贪心调度 ===");
        Vec2 basePos = new Vec2(50, 50);
        List<OreField> fields = Arrays.asList(
            new OreField("富矿区A", new Vec2(20, 20), 5000, 10.0),
            new OreField("贫矿区B", new Vec2(80, 30), 2000, 5.0),
            new OreField("富矿区C", new Vec2(30, 80), 6000, 12.0)
        );

        List<MiningTruck> trucks = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            trucks.add(new MiningTruck("T" + i, new Vec2(50, 50), 100));
        }

        // 贪心分配
        game.greedyAssignTrucks(trucks, fields, basePos, 10.0);
        System.out.println("采矿车分配结果:");
        for (MiningTruck t : trucks) {
            System.out.printf("  %s -> %s%n", t.id, t.target != null ? t.target.name : "无");
        }

        // 模拟采集
        System.out.println("\n模拟采集过程:");
        for (int i = 0; i < 10; i++) {
            game.simulateMining(trucks, fields, basePos, 10.0, 1.0);
            if (i % 3 == 0) {
                System.out.printf("  第%ds: A=%d, B=%d, C=%d%n", i,
                    fields.get(0).remainingOre, fields.get(1).remainingOre, fields.get(2).remainingOre);
            }
        }
    }
}

算法复杂度分析

其中V为建筑种类数，E为依赖边数，T为矿车数量，F为矿区数量。

扩展思考

1. 关键路径优化：在拓扑排序基础上，结合建造时间和资源约束，使用关键路径法（CPM）压缩总建造时间。
2. 动态矿区重分配：当某个矿区枯竭或发现新矿区时，使用匈牙利算法进行全局最优重分配。
3. 多基地协同：多个基地共享资源时，引入网络流模型求解全局最优运输方案。