每日算法 — 使用java实现植物大战僵尸：波次生成与行优先防御部署策略

游戏场景与算法概述

《植物大战僵尸》是一款经典的塔防游戏，玩家需要在五条水平路径上种植各种植物，抵御从右侧不断涌来的僵尸。本文将用Java实现该游戏的核心算法：基于难度曲线的波次生成算法、利用贪心策略的行优先防御部署，以及阳光资源的最优分配策略。

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

波次生成需要根据当前关卡进度动态调整僵尸的种类、数量和出现间隔。我们使用难度曲线函数来平滑控制游戏节奏：前期以普通僵尸为主，间隔较长；中期引入强化僵尸，间隔缩短；后期出现高威胁僵尸，间隔密集。

import java.util.*;

public class WaveGenerator {
    private int currentWave = 0;
    private Random random = new Random();

    public enum ZombieType {
        NORMAL(1, 1.0), CONEHEAD(2, 2.0), BUCKETHEAD(3, 3.5),
        DANCER(4, 5.0), GARGANTUAR(5, 8.0);
        final int tier;
        final double threat;
        ZombieType(int tier, double threat) { this.tier = tier; this.threat = threat; }
    }

    public static class ZombieSpawn {
        public int lane, delay;
        public ZombieType type;
        public ZombieSpawn(int lane, int delay, ZombieType type) {
            this.lane = lane; this.delay = delay; this.type = type;
        }
    }

    // 难度曲线：随着波次增加，僵尸强度和密度上升
    public List<ZombieSpawn> generateWave(int waveNumber) {
        List<ZombieSpawn> spawns = new ArrayList<>();
        currentWave = waveNumber;
        int baseCount = 3 + waveNumber / 2 + random.nextInt(3);
        double difficulty = Math.log1p(waveNumber) * 0.8 + 0.5;

        for (int i = 0; i < baseCount; i++) {
            int lane = random.nextInt(5);
            int delay = i * Math.max(60, 120 - waveNumber * 3);
            spawns.add(new ZombieSpawn(lane, delay, selectZombieType(difficulty)));
        }
        return spawns;
    }

    private ZombieType selectZombieType(double difficulty) {
        double roll = random.nextDouble() * difficulty;
        if (roll > 4.5) return ZombieType.GARGANTUAR;
        if (roll > 3.5) return ZombieType.DANCER;
        if (roll > 2.5) return ZombieType.BUCKETHEAD;
        if (roll > 1.5) return ZombieType.CONEHEAD;
        return ZombieType.NORMAL;
    }
}

核心算法二：行优先防御部署

当阳光资源有限时，采用贪心策略优先保护威胁最大的行：

1. 行威胁评估：计算每行当前僵尸的总威胁值（类型权重 × 数量 × 距离倒数）
2. 优先级排序：威胁值越高的行越需要优先部署防御
3. 植物选择：根据威胁类型选择最优植物

public class DefenseDeployer {
    private static final int LANES = 5;
    private static final int COLUMNS = 9;

    public enum PlantType {
        SUNFLOWER(50, 0), PEASHOOTER(100, 2.0),
        SNOW_PEA(150, 2.5), REPEATER(175, 4.0);
        final int cost; final double dps;
        PlantType(int cost, double dps) { this.cost = cost; this.dps = dps; }
    }

    public static class PlantAction {
        public int lane, col;
        public PlantType type;
        public PlantAction(int lane, int col, PlantType type) {
            this.lane = lane; this.col = col; this.type = type;
        }
    }

    // 贪心策略：优先在威胁最大的行部署防御
    public PlantAction decideNextPlant(List<Zombie> zombies, int sunPoints, PlantType[][] grid) {
        double[] laneThreat = new double[LANES];
        for (Zombie z : zombies) {
            double distanceFactor = 1.0 / (z.x + 1);
            laneThreat[z.lane] += z.threatLevel * distanceFactor;
        }

        Integer[] lanes = new Integer[LANES];
        for (int i = 0; i < LANES; i++) lanes[i] = i;
        Arrays.sort(lanes, (a, b) -> Double.compare(laneThreat[b], laneThreat[a]));

        for (int lane : lanes) {
            if (laneThreat[lane] < 0.5) continue;
            int bestCol = findBestColumn(lane, grid);
            PlantType bestPlant = selectOptimalPlant(laneThreat[lane], sunPoints);
            if (bestPlant != null && bestPlant.cost <= sunPoints) {
                return new PlantAction(lane, bestCol, bestPlant);
            }
        }
        return null;
    }

    private int findBestColumn(int lane, PlantType[][] grid) {
        for (int col = 1; col < COLUMNS; col++) {
            if (grid[lane][col] == null) return col;
        }
        return -1;
    }

    private PlantType selectOptimalPlant(double threat, int sunPoints) {
        if (sunPoints >= 175 && threat > 5.0) return PlantType.REPEATER;
        if (sunPoints >= 150 && threat > 3.0) return PlantType.SNOW_PEA;
        if (sunPoints >= 100) return PlantType.PEASHOOTER;
        if (sunPoints >= 50) return PlantType.SUNFLOWER;
        return null;
    }
}

核心算法三：阳光资源最优分配

采用动态优先级策略管理阳光使用：早期建立经济基础，中期平衡攻防，后期全力防御。

public class SunlightManager {
    private int totalSun = 50;

    public static class Allocation {
        public int economy, attack, reserve;
        public Allocation(int e, int a, int r) { economy = e; attack = a; reserve = r; }
    }

    public Allocation allocateSun(int waveNumber, double maxLaneThreat) {
        double economyRatio, attackRatio, reserveRatio;
        if (waveNumber <= 3) {
            economyRatio = 0.70; attackRatio = 0.20; reserveRatio = 0.10;
        } else if (waveNumber <= 8) {
            economyRatio = 0.30; attackRatio = 0.50; reserveRatio = 0.20;
        } else {
            economyRatio = 0.10; attackRatio = 0.60; reserveRatio = 0.30;
        }
        if (maxLaneThreat > 8.0) {
            reserveRatio = 0.0; attackRatio += 0.30;
        }
        return new Allocation(
            (int)(totalSun * economyRatio),
            (int)(totalSun * attackRatio),
            (int)(totalSun * reserveRatio)
        );
    }
}

复杂度分析

总结

本文通过波次生成算法实现动态难度平衡，利用行优先贪心策略高效部署防御，结合分阶段阳光分配完成资源优化。读者可在此基础上扩展更多植物与僵尸AI，深入理解贪心算法在塔防游戏中的应用。