每日算法 — 使用java实现植物大战僵尸：波次调度与贪心防御布局策略

引言

《植物大战僵尸》是一款经典的塔防游戏，玩家需要在花园中种植各种植物来抵御不断进攻的僵尸。从算法视角来看，这款游戏的核心挑战在于波次调度（何时、以何种组合生成僵尸）与防御布局优化（如何选择和放置植物以最小化资源消耗并最大化防御效率）。本文将用Java实现一个简化版的植物大战僵尸核心算法框架，重点讲解波次生成算法和贪心防御布局策略。

核心算法一：波次调度生成算法

僵尸的波次生成遵循一定的节奏和难度曲线。我们使用加权随机抽样结合难度递增函数来生成每一波的僵尸组合。

算法思路

1. 定义僵尸类型及其基础权重（普通、路障、铁桶、旗帜等）
2. 随着波次增加，高级僵尸的权重线性上升
3. 使用别名方法（Alias Method）或累积概率进行O(1)或O(log n)的加权随机选择
4. 大波次（Flag Wave）固定出现大量僵尸

import java.util.*;

/**
 * 僵尸类型枚举，包含基础属性和权重
 */
enum ZombieType {
    NORMAL(50, 1.0, 1.0),      // 普通僵尸：血量50，速度1.0，基础权重1.0
    CONE(100, 1.0, 0.6),       // 路障僵尸
    BUCKET(200, 0.8, 0.3),     // 铁桶僵尸
    FLAG(50, 1.2, 0.1),        // 旗帜僵尸，带领一波进攻
    NEWSPAPER(100, 1.5, 0.2);  // 报纸僵尸，受伤后加速

    final int hp;
    final double speed;
    final double baseWeight;

    ZombieType(int hp, double speed, double baseWeight) {
        this.hp = hp;
        this.speed = speed;
        this.baseWeight = baseWeight;
    }
}

/**
 * 波次调度器：负责生成每一波的僵尸组合
 */
public class WaveScheduler {
    private static final Random rand = new Random();
    private final int totalLanes;      // 总车道数（通常为5或6）
    private final int totalWaves;      // 总波次数
    private final double difficultyCurve; // 难度曲线系数

    public WaveScheduler(int totalLanes, int totalWaves, double difficultyCurve) {
        this.totalLanes = totalLanes;
        this.totalWaves = totalWaves;
        this.difficultyCurve = difficultyCurve;
    }

    /**
     * 计算第wave波中某僵尸类型的动态权重
     * 权重随波次递增，实现难度曲线
     */
    private double computeDynamicWeight(ZombieType type, int wave) {
        double progress = (double) wave / totalWaves;
        // 高级僵尸在后期波次权重显著提升
        double difficultyMultiplier = 1.0 + difficultyCurve * progress * type.hp / 50.0;
        return type.baseWeight * difficultyMultiplier;
    }

    /**
     * 使用累积概率进行加权随机选择（可优化为Alias Method达到O(1)）
     * @return 选中的僵尸类型
     */
    private ZombieType weightedRandomSelect(ZombieType[] types, double[] weights) {
        double total = 0;
        for (double w : weights) total += w;
        double threshold = rand.nextDouble() * total;
        double cumulative = 0;
        for (int i = 0; i < types.length; i++) {
            cumulative += weights[i];
            if (cumulative >= threshold) {
                return types[i];
            }
        }
        return types[types.length - 1];
    }

    /**
     * 生成第wave波的僵尸部署计划
     * @param wave 当前波次（从1开始）
     * @return 每个车道上的僵尸列表
     */
    public List<ZombieType>[] generateWave(int wave) {
        @SuppressWarnings("unchecked")
        List<ZombieType>[] lanes = new ArrayList[totalLanes];
        for (int i = 0; i < totalLanes; i++) {
            lanes[i] = new ArrayList<>();
        }

        // 计算本波僵尸总数：随波次递增，大波次额外增加
        boolean isBigWave = (wave % 10 == 0) || (wave == totalWaves);
        int baseCount = 2 + wave / 3;
        int zombieCount = isBigWave ? baseCount * 3 : baseCount;

        ZombieType[] allTypes = ZombieType.values();
        double[] weights = new double[allTypes.length];

        for (int i = 0; i < allTypes.length; i++) {
            weights[i] = computeDynamicWeight(allTypes[i], wave);
        }

        // 为每个僵尸随机分配车道
        for (int i = 0; i < zombieCount; i++) {
            int lane = rand.nextInt(totalLanes);
            ZombieType type = weightedRandomSelect(allTypes, weights);
            lanes[lane].add(type);
        }

        return lanes;
    }

    public static void main(String[] args) {
        WaveScheduler scheduler = new WaveScheduler(5, 50, 2.0);
        // 模拟生成前5波
        for (int w = 1; w <= 5; w++) {
            List<ZombieType>[] wave = scheduler.generateWave(w);
            int total = Arrays.stream(wave).mapToInt(List::size).sum();
            System.out.println("第" + w + "波，共" + total + "只僵尸");
            for (int lane = 0; lane < wave.length; lane++) {
                System.out.println("  车道" + lane + ": " + wave[lane]);
            }
        }
    }
}

核心算法二：贪心防御布局策略

面对不断生成的僵尸波次，玩家（或AI）需要决定在每个车道种植什么植物。我们采用贪心策略结合威胁评估来进行自动化布局决策。

算法思路

1. 威胁评估：根据每个车道即将到达的僵尸数量和类型，计算车道威胁值
2. 植物选择：根据威胁类型选择最优植物（豌豆射手对付普通僵尸，坚果墙拖延时间，樱桃炸弹应对集群）
3. 资源约束：阳光值有限，需要在各车道间进行资源分配
4. 贪心决策：每次选择”单位阳光收益最高”的种植方案

import java.util.*;

/**
 * 植物类型及其属性
 */
enum PlantType {
    PEASHOOTER(100, 25, 1, 20),   // 阳光成本，冷却时间，攻击范围，伤害
    SUNFLOWER(50, 5, 0, 0),       // 产生阳光，无攻击
    WALLNUT(50, 15, 0, 0),        // 高血量防御墙
    CHERRY_BOMB(150, 30, 3, 500), // 范围爆炸伤害，范围3格
    REPEATER(200, 25, 1, 40);     // 双发射手，伤害翻倍

    final int sunCost;
    final int cooldown;   // 冷却回合数
    final int range;      // 攻击范围（0表示无攻击，3表示3x3范围）
    final int damage;

    PlantType(int sunCost, int cooldown, int range, int damage) {
        this.sunCost = sunCost;
        this.cooldown = cooldown;
        this.range = range;
        this.damage = damage;
    }
}

/**
 * 表示一个车道的威胁状态
 */
class LaneThreat {
    int laneId;
    double threatScore;       // 综合威胁值
    List<ZombieInfo> incoming; // 即将到来的僵尸

    LaneThreat(int laneId) {
        this.laneId = laneId;
        this.threatScore = 0;
        this.incoming = new ArrayList<>();
    }
}

class ZombieInfo {
    ZombieType type;
    double distance;  // 距离家园的距离（格子数）
    double arriveTurn; // 预计到达回合

    ZombieInfo(ZombieType type, double distance, double speed) {
        this.type = type;
        this.distance = distance;
        this.arriveTurn = distance / speed;
    }
}

/**
 * 贪心防御布局决策器
 */
public class DefensePlanner {
    private final int totalLanes;
    private final int mapLength; // 地图长度（格子数）
    private int availableSun;     // 可用阳光

    public DefensePlanner(int totalLanes, int mapLength, int initialSun) {
        this.totalLanes = totalLanes;
        this.mapLength = mapLength;
        this.availableSun = initialSun;
    }

    /**
     * 计算每个车道的威胁值
     * 威胁值 = Σ(僵尸血量 / 预计到达回合^2)
     * 越近且越强的僵尸威胁越大
     */
    public LaneThreat[] evaluateThreats(List<ZombieType>[] incomingZombies) {
        LaneThreat[] threats = new LaneThreat[totalLanes];
        for (int i = 0; i < totalLanes; i++) {
            threats[i] = new LaneThreat(i);
            if (incomingZombies[i] == null) continue;

            for (ZombieType z : incomingZombies[i]) {
                // 假设僵尸从地图最右侧进入，速度决定到达时间
                double arriveTurn = mapLength / z.speed;
                double urgency = 1.0 / (arriveTurn * arriveTurn);
                threats[i].threatScore += z.hp * urgency;
                threats[i].incoming.add(new ZombieInfo(z, mapLength, z.speed));
            }
        }
        return threats;
    }

    /**
     * 贪心选择最优种植方案
     * @return 建议的种植操作列表 [车道, 植物类型]
     */
    public List<int[]> planDefense(LaneThreat[] threats) {
        List<int[]> plans = new ArrayList<>();

        // 按威胁值降序排序车道
        Integer[] laneOrder = new Integer[totalLanes];
        for (int i = 0; i < totalLanes; i++) laneOrder[i] = i;
        Arrays.sort(laneOrder, (a, b) -> Double.compare(threats[b].threatScore, threats[a].threatScore));

        for (int laneIdx : laneOrder) {
            LaneThreat threat = threats[laneIdx];
            if (threat.threatScore < 10) continue; // 威胁过低，暂不处理

            PlantType chosen = selectBestPlant(threat);
            if (chosen != null && availableSun >= chosen.sunCost) {
                plans.add(new int[]{laneIdx, chosen.ordinal()});
                availableSun -= chosen.sunCost;
            }
        }
        return plans;
    }

    /**
     * 根据威胁特征选择最优植物
     */
    private PlantType selectBestPlant(LaneThreat threat) {
        boolean hasCluster = threat.incoming.size() >= 3;
        boolean hasTank = threat.incoming.stream().anyMatch(z -> z.type.hp >= 200);
        boolean urgent = threat.incoming.stream().anyMatch(z -> z.arriveTurn < 5);

        // 集群威胁 → 樱桃炸弹
        if (hasCluster && availableSun >= PlantType.CHERRY_BOMB.sunCost) {
            return PlantType.CHERRY_BOMB;
        }
        // 紧急且高血量 → 坚果墙拖延
        if (urgent && hasTank && availableSun >= PlantType.WALLNUT.sunCost) {
            return PlantType.WALLNUT;
        }
        // 高血量但距离较远 → 双发射手
        if (hasTank && availableSun >= PlantType.REPEATER.sunCost) {
            return PlantType.REPEATER;
        }
        // 默认选择豌豆射手
        if (availableSun >= PlantType.PEASHOOTER.sunCost) {
            return PlantType.PEASHOOTER;
        }
        return null;
    }

    public static void main(String[] args) {
        DefensePlanner planner = new DefensePlanner(5, 10, 500);
        // 模拟5个车道的 incoming 僵尸
        @SuppressWarnings("unchecked")
        List<ZombieType>[] zombies = new ArrayList[5];
        for (int i = 0; i < 5; i++) zombies[i] = new ArrayList<>();
        zombies[0].add(ZombieType.NORMAL); zombies[0].add(ZombieType.NORMAL);
        zombies[1].add(ZombieType.BUCKET);
        zombies[2].add(ZombieType.NORMAL); zombies[2].add(ZombieType.CONE); zombies[2].add(ZombieType.NORMAL);
        zombies[3].add(ZombieType.FLAG); zombies[3].add(ZombieType.NORMAL); zombies[3].add(ZombieType.CONE);

        LaneThreat[] threats = planner.evaluateThreats(zombies);
        List<int[]> plans = planner.planDefense(threats);
        System.out.println("防御部署计划：");
        for (int[] plan : plans) {
            System.out.println("  车道" + plan[0] + " 种植 " + PlantType.values()[plan[1]]);
        }
    }
}

核心算法三：战斗模拟与伤害结算

将波次生成与防御布局结合，进行回合制战斗模拟。每个回合僵尸前进、植物攻击、判断胜负。

import java.util.*;

/**
 * 简化版战斗模拟引擎
 */
public class BattleSimulator {
    static class Plant {
        PlantType type;
        int hp = 100; // 植物基础血量
        int cooldownRemaining = 0;

        Plant(PlantType type) {
            this.type = type;
            if (type == PlantType.WALLNUT) this.hp = 400;
        }
    }

    static class Zombie {
        ZombieType type;
        int hp;
        double position; // 距离家园的格子数
        double speed;

        Zombie(ZombieType type, double startPosition) {
            this.type = type;
            this.hp = type.hp;
            this.speed = type.speed;
            this.position = startPosition;
        }
    }

    private final int mapLength;
    private final List<Plant>[] lanePlants; // 每个车道的植物队列
    private final List<Zombie>[] laneZombies;

    public BattleSimulator(int lanes, int mapLength) {
        this.mapLength = mapLength;
        lanePlants = new ArrayList[lanes];
        laneZombies = new ArrayList[lanes];
        for (int i = 0; i < lanes; i++) {
            lanePlants[i] = new ArrayList<>();
            laneZombies[i] = new ArrayList<>();
        }
    }

    public void addPlant(int lane, PlantType type) {
        lanePlants[lane].add(new Plant(type));
    }

    public void addZombie(int lane, ZombieType type) {
        laneZombies[lane].add(new Zombie(type, mapLength));
    }

    /**
     * 模拟一回合战斗
     * @return true 表示家园安全，false 表示有僵尸突破
     */
    public boolean simulateTurn() {
        for (int lane = 0; lane < lanePlants.length; lane++) {
            List<Plant> plants = lanePlants[lane];
            List<Zombie> zombies = laneZombies[lane];

            // 1. 植物攻击阶段
            for (Plant p : plants) {
                if (p.hp <= 0) continue;
                if (p.type == PlantType.SUNFLOWER) continue; // 向日葵不攻击
                if (p.cooldownRemaining > 0) {
                    p.cooldownRemaining--;
                    continue;
                }

                if (p.type == PlantType.CHERRY_BOMB) {
                    // 樱桃炸弹：消灭范围内所有僵尸，然后自毁
                    zombies.removeIf(z -> z.position <= 3);
                    p.hp = 0;
                    continue;
                }

                // 单体攻击：攻击最前方的僵尸
                if (!zombies.isEmpty()) {
                    Zombie target = zombies.get(0);
                    target.hp -= p.type.damage;
                }
                p.cooldownRemaining = p.type.cooldown;
            }

            // 2. 移除死亡僵尸
            zombies.removeIf(z -> z.hp <= 0);

            // 3. 僵尸前进与啃食
            Iterator<Zombie> it = zombies.iterator();
            while (it.hasNext()) {
                Zombie z = it.next();
                // 检查前方是否有植物
                boolean blocked = false;
                for (Plant p : plants) {
                    if (p.hp > 0 && Math.abs(z.position - mapLength / 2) < 1.0) {
                        // 简化：僵尸啃食植物
                        p.hp -= 10;
                        blocked = true;
                        break;
                    }
                }
                if (!blocked) {
                    z.position -= z.speed;
                }
                if (z.position <= 0) {
                    return false; // 僵尸突破防线
                }
            }

            // 4. 清理死亡植物
            plants.removeIf(p -> p.hp <= 0);
        }
        return true;
    }

    public static void main(String[] args) {
        BattleSimulator sim = new BattleSimulator(1, 10);
        sim.addPlant(0, PlantType.PEASHOOTER);
        sim.addPlant(0, PlantType.PEASHOOTER);
        sim.addZombie(0, ZombieType.NORMAL);
        sim.addZombie(0, ZombieType.CONE);

        for (int turn = 1; turn <= 20; turn++) {
            boolean safe = sim.simulateTurn();
            System.out.println("回合" + turn + ": " + (safe ? "防守成功" : "僵尸突破！"));
            if (!safe) break;
        }
    }
}

复杂度分析

总结

本文通过Java实现了一个简化版植物大战僵尸的核心算法框架，涵盖：
– 波次调度：加权随机抽样实现动态难度曲线
– 贪心防御：基于威胁评估的自动化植物布局
– 战斗模拟：回合制伤害结算与胜负判定

读者可以在此基础上扩展更多植物类型、僵尸AI行为以及更复杂的策略网络，进一步探索塔防游戏中的算法之美。