每日算法 — 使用java实现植物大战僵尸：波次生成与贪心资源调度策略

可莉爸爸 AI算法

引言

《植物大战僵尸》是一款风靡全球的塔防策略游戏，玩家通过种植不同功能的植物来抵御一波波进攻的僵尸。从算法视角看，这款游戏的核心魅力在于波次生成系统与实时资源调度的精妙设计。本文将用Java实现其中的关键算法：基于泊松分布的僵尸波次生成引擎，以及面向多路防御的贪心植物种植策略，帮助读者在经典游戏场景中掌握概率建模与贪心算法的实战应用。

一、核心算法架构

游戏的算法系统可分为三个核心模块：

  1. 波次生成器（Wave Generator）：基于泊松过程建模僵尸的生成时机与类型分布，让每波进攻既不可预测又符合节奏感。
  2. 路径威胁评估器（Threat Evaluator）：对5条草坪路径分别计算僵尸密度、推进速度和突破风险，量化每一路的紧急程度。
  3. 贪心种植调度器（Greedy Scheduler）：在阳光预算约束下，按威胁优先级贪心选择种植位置与植物类型，实现实时防御决策。

三个模块通过”生成—评估—决策”的闭环协同运作，形成完整的塔防AI逻辑。

二、泊松分布与僵尸波次生成

2.1 算法原理

在真实游戏中，僵尸的出场时机并非均匀分布，而是呈现出”扎堆出现”的聚类特征。泊松分布（Poisson Distribution）恰好适合描述单位时间内随机事件发生次数的概率分布。其概率质量函数为：

$$P(X=k) = \frac{\lambda^k e^{-\lambda}}{k!}$$

其中 λ 为单位时间内的平均事件发生次数。对于游戏波次设计，我们将整个关卡划分为多个时间窗口，在每个窗口内根据当前难度动态调整 λ，控制僵尸的生成密度。

2.2 Java实现

import java.util.*;

/**
 * 僵尸波次生成器：基于泊松分布与加权随机选择生成僵尸进攻波次
 */
public class ZombieWaveGenerator {
    private final Random random = new Random();
    // 僵尸类型及其基础权重
    private final Map<ZombieType, Double> zombieWeights = new LinkedHashMap<>();
    // 当前游戏难度系数（随波次递增）
    private double difficultyFactor = 1.0;

    public enum ZombieType {
        NORMAL,       // 普通僵尸
        CONE,         // 路障僵尸
        BUCKET,       // 铁桶僵尸
        POLE_VAULTING,// 撑杆僵尸
        NEWSPAPER,    // 报纸僵尸
        FOOTBALL      // 橄榄球僵尸
    }

    public ZombieWaveGenerator() {
        // 初始化基础权重：越强的僵尸权重越低
        zombieWeights.put(ZombieType.NORMAL, 40.0);
        zombieWeights.put(ZombieType.CONE, 25.0);
        zombieWeights.put(ZombieType.BUCKET, 15.0);
        zombieWeights.put(ZombieType.POLE_VAULTING, 10.0);
        zombieWeights.put(ZombieType.NEWSPAPER, 7.0);
        zombieWeights.put(ZombieType.FOOTBALL, 3.0);
    }

    /**
     * 泊松分布：计算单位时间窗口内生成的僵尸数量
     * @param lambda 该窗口的平均僵尸数
     * @return 实际生成的僵尸数量
     */
    public int poissonRandom(double lambda) {
        // Knuth算法：利用指数分布与泊松分布的关系
        double L = Math.exp(-lambda);
        double p = 1.0;
        int k = 0;
        do {
            k++;
            p *= random.nextDouble();
        } while (p > L);
        return k - 1;
    }

    /**
     * 根据当前难度动态调整各类僵尸的权重
     * 难度越高，强力僵尸的相对权重越高
     */
    private Map<ZombieType, Double> getDynamicWeights() {
        Map<ZombieType, Double> dynamic = new LinkedHashMap<>();
        for (Map.Entry<ZombieType, Double> entry : zombieWeights.entrySet()) {
            double weight = entry.getValue();
            ZombieType type = entry.getKey();
            // 强力僵尸随难度提升获得指数级权重加成
            switch (type) {
                case BUCKET -> weight *= Math.pow(difficultyFactor, 1.5);
                case FOOTBALL -> weight *= Math.pow(difficultyFactor, 2.0);
                case POLE_VAULTING -> weight *= Math.pow(difficultyFactor, 1.2);
                default -> weight *= Math.pow(difficultyFactor, 0.5);
            }
            dynamic.put(type, weight);
        }
        return dynamic;
    }

    /**
     * 加权随机选择：根据动态权重选择一只僵尸类型
     */
    public ZombieType weightedRandomZombie() {
        Map<ZombieType, Double> weights = getDynamicWeights();
        double total = weights.values().stream().mapToDouble(Double::doubleValue).sum();
        double threshold = random.nextDouble() * total;
        double cumulative = 0.0;
        for (Map.Entry<ZombieType, Double> entry : weights.entrySet()) {
            cumulative += entry.getValue();
            if (cumulative >= threshold) {
                return entry.getKey();
            }
        }
        return ZombieType.NORMAL; // fallback
    }

    /**
     * 生成一波僵尸
     * @param waveNumber 波次数（从1开始）
     * @param lanes 草坪路径总数（通常为5）
     * @return 该波次所有僵尸的生成计划
     */
    public List<ZombieSpawnPlan> generateWave(int waveNumber, int lanes) {
        // 难度随波次增长：lambda = 2 + waveNumber * 0.8
        difficultyFactor = 1.0 + waveNumber * 0.15;
        double lambda = 2.0 + waveNumber * 0.8;
        int count = poissonRandom(lambda);

        List<ZombieSpawnPlan> wave = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            ZombieType type = weightedRandomZombie();
            int lane = random.nextInt(lanes); // 均匀随机分配到某一路
            // 同波次内的僵尸在0~10秒内随机延迟出现，形成"集群冲锋"感
            double delaySeconds = random.nextDouble() * 10.0;
            wave.add(new ZombieSpawnPlan(type, lane, delaySeconds));
        }
        // 按延迟时间排序，模拟先后出场的节奏
        wave.sort(Comparator.comparingDouble(ZombieSpawnPlan::getDelay));
        return wave;
    }

    // 僵尸生成计划数据类
    public static class ZombieSpawnPlan {
        private final ZombieType type;
        private final int lane;
        private final double delaySeconds;

        public ZombieSpawnPlan(ZombieType type, int lane, double delaySeconds) {
            this.type = type;
            this.lane = lane;
            this.delaySeconds = delaySeconds;
        }

        public ZombieType getType() { return type; }
        public int getLane() { return lane; }
        public double getDelay() { return delaySeconds; }

        @Override
        public String toString() {
            return String.format("[%s] 第%d路 延迟%.1fs", type, lane + 1, delaySeconds);
        }
    }

    public static void main(String[] args) {
        ZombieWaveGenerator generator = new ZombieWaveGenerator();
        System.out.println("=== 植物大战僵尸 波次生成模拟 ===\n");
        for (int wave = 1; wave <= 5; wave++) {
            List<ZombieSpawnPlan> plans = generator.generateWave(wave, 5);
            System.out.printf("第 %d 波 (难度=%.2f): 生成 %d 只僵尸\n",
                wave, generator.difficultyFactor, plans.size());
            for (ZombieSpawnPlan plan : plans) {
                System.out.println("  " + plan);
            }
            System.out.println();
        }
    }
}

2.3 运行效果分析

上述代码中，poissonRandom 使用 Knuth 算法高效模拟泊松分布，确保波次内的僵尸数量围绕 λ 值波动，既不会过于稀疏也不会密集到无法防守。weightedRandomZombie 则实现了基于难度的加权随机：前期以普通僵尸为主，后期铁桶、橄榄球等高血量僵尸的比例显著提升，形成自然递增的难度曲线。

三、多路威胁评估与贪心种植策略

3.1 威胁评估模型

5条草坪路径各自独立，玩家的核心决策是”把有限的阳光花在哪条路的哪个格子”。为此，我们需要对每条路计算一个威胁分数：

$$Threat_{lane} = \sum_{z \in zombies_{lane}} \frac{HP_z \times Speed_z}{Distance_z + 1}$$

  • HP：僵尸生命值（不同类型权重不同）
  • Speed：移动速度（越快越紧急）
  • Distance：僵尸距离左侧底线的剩余格数（越近越紧急）

3.2 贪心种植调度器

当阳光积累到一定阈值时，调度器按以下贪心策略执行：

  1. 选择目标路：优先在威胁分数最高的路径种植。
  2. 选择种植列：在目标路上选择最右侧的空格（让植物尽早开始攻击）。
  3. 选择植物类型：根据当前阳光余额和威胁类型贪心选择性价比最高的植物。

植物的”性价比”定义为：

$$Value_{plant} = \frac{Damage \times Range}{Cost}$$

3.3 Java实现

import java.util.*;

/**
 * 贪心植物种植调度器：基于威胁评估实时决策最优种植方案
 */
public class GreedyPlantScheduler {
    // 5行9列的草坪网格
    public static final int LANES = 5;
    public static final int COLUMNS = 9;
    private final Plant[][] grid = new Plant[LANES][COLUMNS];
    private int sunlight = 50; // 初始阳光

    public enum PlantType {
        SUNFLOWER(50, 0, 0, "向日葵"),     // 产阳光，无攻击
        PEA_SHOOTER(100, 20, 8, "豌豆射手"), // 单列直线攻击
        SNOW_PEA(175, 20, 8, "寒冰射手"),    // 减速攻击
        WALL_NUT(50, 0, 0, "坚果墙"),        // 高血量阻挡
        REPEATER(200, 40, 8, "双发豌豆"),    // 双倍伤害
        CHERRY_BOMB(150, 500, 1, "樱桃炸弹"); // 范围爆炸

        final int cost;      // 阳光消耗
        final int damage;    // 伤害（或爆炸伤害）
        final int range;     // 攻击射程（格）
        final String name;

        PlantType(int cost, int damage, int range, String name) {
            this.cost = cost;
            this.damage = damage;
            this.range = range;
            this.name = name;
        }

        // 计算植物性价比（防御单位优先用伤害/成本，生产单位用特殊逻辑）
        public double getValue() {
            if (this == SUNFLOWER) return 2.0; // 产阳光，优先级中等
            if (this == WALL_NUT) return 3.0;  // 阻挡价值高
            if (this == CHERRY_BOMB) return 5.0; // 紧急情况优先
            return (double) damage * range / cost;
        }
    }

    public static class Plant {
        PlantType type;
        int hp;
        int lane;
        int column;

        public Plant(PlantType type, int lane, int column) {
            this.type = type;
            this.lane = lane;
            this.column = column;
            this.hp = (type == PlantType.WALL_NUT) ? 4000 : 300;
        }
    }

    public static class Zombie {
        String name;
        int hp;
        int speed;        // 每 tick 前进的像素/格数
        int maxHp;
        double position;  // 当前列位置（浮点数，9.0为最右侧，0.0为底线）

        public Zombie(String name, int hp, int speed) {
            this.name = name;
            this.maxHp = hp;
            this.hp = hp;
            this.speed = speed;
            this.position = 9.0; // 从右侧入场
        }

        public double getThreatScore() {
            // 威胁分 = (剩余生命比例 * 速度) / (距离底线 + 1)
            double lifeRatio = (double) hp / maxHp;
            double distance = Math.max(position, 0.01);
            return (lifeRatio * speed) / (distance + 0.5);
        }
    }

    /**
     * 计算每条路径的总威胁分数
     */
    public double[] evaluateLaneThreats(List<List<Zombie>> laneZombies) {
        double[] threats = new double[LANES];
        for (int i = 0; i < LANES; i++) {
            double sum = 0.0;
            for (Zombie z : laneZombies.get(i)) {
                sum += z.getThreatScore();
            }
            threats[i] = sum;
        }
        return threats;
    }

    /**
     * 贪心决策：在阳光预算内选择最优种植方案
     * @param laneZombies 当前各路的僵尸列表
     * @return 本次决策的种植动作，若无则返回null
     */
    public PlantDecision makeGreedyDecision(List<List<Zombie>> laneZombies) {
        double[] threats = evaluateLaneThreats(laneZombies);

        // 按威胁分数降序排列路径索引
        Integer[] laneIndices = new Integer[LANES];
        for (int i = 0; i < LANES; i++) laneIndices[i] = i;
        Arrays.sort(laneIndices, (a, b) -> Double.compare(threats[b], threats[a]));

        // 优先处理威胁最高的路
        for (int lane : laneIndices) {
            if (threats[lane] < 0.1) continue; // 威胁极低，不处理

            // 在该路寻找最右侧的空格种植
            for (int col = COLUMNS - 1; col >= 0; col--) {
                if (grid[lane][col] != null) continue;

                // 根据威胁等级和阳光余额选择植物
                PlantType chosen = selectBestPlant(laneZombies.get(lane), col);
                if (chosen != null && sunlight >= chosen.cost) {
                    return new PlantDecision(chosen, lane, col);
                }
            }
        }
        return null;
    }

    /**
     * 根据僵尸特征和位置选择最优植物类型
     */
    private PlantType selectBestPlant(List<Zombie> zombies, int plantCol) {
        boolean hasCloseThreat = false;
        boolean hasFastThreat = false;
        for (Zombie z : zombies) {
            if (z.position < 3.0) hasCloseThreat = true;
            if (z.speed >= 2) hasFastThreat = true;
        }

        // 紧急情况：僵尸已接近底线，优先使用樱桃炸弹
        if (hasCloseThreat && sunlight >= PlantType.CHERRY_BOMB.cost) {
            return PlantType.CHERRY_BOMB;
        }

        // 快速僵尸需要减速
        if (hasFastThreat && sunlight >= PlantType.SNOW_PEA.cost) {
            return PlantType.SNOW_PEA;
        }

        // 该行已有攻击植物，补充坚果墙阻挡
        boolean hasAttacker = false;
        for (int c = 0; c < COLUMNS; c++) {
            if (grid[0][c] != null && grid[0][c].type.damage > 0) {
                hasAttacker = true;
                break;
            }
        }
        if (!hasAttacker && sunlight >= PlantType.WALL_NUT.cost) {
            return PlantType.WALL_NUT;
        }

        // 阳光充足时选择高伤害植物
        if (sunlight >= PlantType.REPEATER.cost) {
            return PlantType.REPEATER;
        }
        if (sunlight >= PlantType.PEA_SHOOTER.cost) {
            return PlantType.PEA_SHOOTER;
        }
        if (sunlight >= PlantType.SUNFLOWER.cost) {
            return PlantType.SUNFLOWER;
        }
        return null;
    }

    /**
     * 执行种植操作
     */
    public void plant(PlantDecision decision) {
        if (decision == null) return;
        PlantType type = decision.type;
        int lane = decision.lane;
        int col = decision.column;
        if (sunlight >= type.cost && grid[lane][col] == null) {
            grid[lane][col] = new Plant(type, lane, col);
            sunlight -= type.cost;
            System.out.printf("☀ 消耗%d阳光 → 在[%d路,%d列]种植【%s】，剩余阳光：%d\n",
                type.cost, lane + 1, col + 1, type.name, sunlight);
        }
    }

    /**
     * 模拟阳光自然增长（向日葵额外产阳光）
     */
    public void produceSunlight() {
        int base = 25; // 基础自然增长
        for (int i = 0; i < LANES; i++) {
            for (int j = 0; j < COLUMNS; j++) {
                if (grid[i][j] != null && grid[i][j].type == PlantType.SUNFLOWER) {
                    base += 25;
                }
            }
        }
        sunlight += base;
        System.out.println("☀ 阳光增长 +" + base + "，当前阳光：" + sunlight);
    }

    // 决策数据类
    public static class PlantDecision {
        final PlantType type;
        final int lane;
        final int column;

        public PlantDecision(PlantType type, int lane, int column) {
            this.type = type;
            this.lane = lane;
            this.column = column;
        }
    }

    public static void main(String[] args) {
        GreedyPlantScheduler scheduler = new GreedyPlantScheduler();
        Random rand = new Random();

        // 模拟当前各路的僵尸分布
        List<List<Zombie>> laneZombies = new ArrayList<>();
        for (int i = 0; i < LANES; i++) {
            List<Zombie> list = new ArrayList<>();
            int count = rand.nextInt(3); // 每路0~2只僵尸
            for (int j = 0; j < count; j++) {
                Zombie z = new Zombie("普通僵尸", 200, 1);
                z.position = 5.0 + rand.nextDouble() * 4.0; // 位置在5~9格之间
                list.add(z);
            }
            laneZombies.add(list);
        }

        // 模拟5轮决策
        System.out.println("=== 贪心植物种植调度模拟 ===\n");
        for (int round = 1; round <= 5; round++) {
            System.out.println("--- 第 " + round + " 轮 ---");
            scheduler.produceSunlight();
            PlantDecision decision = scheduler.makeGreedyDecision(laneZombies);
            if (decision != null) {
                scheduler.plant(decision);
            } else {
                System.out.println("（阳光不足或威胁过低，本轮不种植）");
            }
            // 僵尸推进
            for (List<Zombie> list : laneZombies) {
                for (Zombie z : list) {
                    z.position -= z.speed * 0.5;
                }
            }
            System.out.println();
        }
    }
}

3.4 策略解析

上述实现展现了贪心算法的核心思想：每一步都在当前信息下做出局部最优选择。evaluateLaneThreats 将多维战场信息压缩为一维威胁分数，selectBestPlant 则根据局部态势（僵尸距离、速度、阳光余额）快速匹配植物类型。虽然贪心策略不一定保证全局最优，但在实时塔防场景中，其 O(n) 的时间复杂度远优于动态规划或搜索算法，能够在毫秒级完成决策，保证游戏流畅性。

四、完整项目结构与扩展方向

plant-vs-zombie-algorithm/
├── ZombieWaveGenerator.java    // 波次生成引擎
├── GreedyPlantScheduler.java   // 种植调度器
├── GameSimulator.java          // 主循环：整合生成—评估—决策
└── model/
    ├── Zombie.java
    ├── Plant.java
    └── LaneState.java

读者可以在此基础上进一步探索以下方向：

  • 动态规划优化：将阳光预算与多路防守建模为多维背包问题，用DP求解全局最优种植序列。
  • 遗传算法进化：将植物布局编码为染色体，通过多代进化搜索最强防守阵型。
  • 蒙特卡洛模拟：在波次生成前模拟数千种可能的僵尸进攻路线，提前预留关键防守位。

五、复杂度分析

模块 时间复杂度 空间复杂度 说明
泊松波次生成 O(k) O(k) k为当前波次僵尸数量，Knuth算法期望迭代 λ+1 次
威胁评估 O(m×n) O(m) m为路数(固定5)，n为该路僵尸数
贪心种植决策 O(m×c) O(m) c为列数(固定9)，排序路数开销可忽略

所有模块均为线性或近线性复杂度，完全满足实时游戏的性能要求。

结语

本文从《植物大战僵尸》这一经典游戏出发，实现了泊松波次生成与贪心资源调度两大核心算法。泊松分布让僵尸进攻既充满随机性又保持节奏感，而贪心策略则在瞬息万变的战场上做出了高效、可解释的实时决策。掌握这两个算法，不仅能够帮助读者理解塔防游戏的设计精髓，更能将概率建模与贪心思想迁移到调度系统、流量控制和资源分配等广泛的工程场景中。

Tagged with: