植物大战僵尸是经典的塔防策略游戏，玩家通过种植不同功能的植物来抵御僵尸入侵。本文用Java实现简化版植物大战僵尸的核心算法，重点讲解资源分配策略中的贪心最优决策，以及僵尸路径搜索与攻击优先级判定。
游戏机制与问题建模
简化版植物大战僵尸的核心规则：
- 游戏区域为
ROWS × COLS的网格，僵尸从右侧出现并向左侧移动 - 玩家拥有阳光资源，用于种植不同成本的植物
- 植物类型：向日葵（产阳光）、豌豆射手（远程攻击）、坚果墙（防御）
- 僵尸有生命值和移动速度，到达最左侧则游戏结束
核心算法挑战：
1. 最优种植决策：给定当前阳光和僵尸分布，选择种什么、种哪里
2. 攻击优先级：植物优先攻击哪一行/哪一个僵尸
3. 资源平衡：如何在产阳光和防御之间分配资源
贪心防御布局算法
贪心策略的核心是：每一步都选择”当前性价比最高”的种植方案。我们为每个空格子计算一个防御价值分数，选择分数最高的位置种植最合适的植物。
import java.util.*;
/**
* 植物大战僵尸 - 贪心防御布局决策器
* 根据当前局势计算最优种植策略
*/
public class DefensePlanner {
private static final int ROWS = 5;
private static final int COLS = 9;
// 植物类型定义
enum PlantType {
SUNFLOWER(50, 0, 0, "向日葵"), // 产阳光
PEASHOOTER(100, 20, 5, "豌豆射手"), // 远程攻击
WALLNUT(50, 0, 0, "坚果墙"), // 高血量防御
REPEATER(200, 40, 5, "双发射手"), // 高伤害
SNOWPEA(175, 20, 5, "寒冰射手"); // 减速攻击
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;
}
}
static class Zombie {
int row; // 所在行
double col; // 所在列(小数表示中间位置)
int hp; // 生命值
double speed; // 移动速度
boolean slowed; // 是否被减速
Zombie(int row, double col, int hp, double speed) {
this.row = row; this.col = col;
this.hp = hp; this.speed = speed;
}
}
/**
* 贪心策略：为每个格子计算防御价值
* 价值 = 威胁等级 × 植物效用 / 成本
*/
public PlantDecision decideNextPlant(
int sun,
int[][] board, // 0=空, 1=向日葵, 2=豌豆, ...
List<Zombie> zombies) {
// 统计每行的僵尸威胁值
double[] rowThreat = new double[ROWS];
for (Zombie z : zombies) {
// 威胁值 = 生命值 / (距离 × 速度)，越近越快越肉威胁越大
double distance = Math.max(1, z.col);
double threat = z.hp / (distance * 0.5 + 1) * z.speed;
rowThreat[z.row] += threat;
}
PlantDecision best = null;
double bestValue = -1;
// 遍历所有空格
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != 0) continue;
// 根据威胁等级选择植物类型
PlantType type = choosePlantType(sun, rowThreat[r], c);
if (type == null) continue;
if (type.cost > sun) continue;
// 计算该位置的防御价值
double value = evaluatePosition(r, c, type, rowThreat, board, zombies);
if (value > bestValue) {
bestValue = value;
best = new PlantDecision(r, c, type, value);
}
}
}
return best;
}
/**
* 根据局势贪心选择植物类型
*/
private PlantType choosePlantType(int sun, double threat, int col) {
// 早期优先种向日葵积累资源
if (sun < 150 && col < 3) {
return (sun >= PlantType.SUNFLOWER.cost) ? PlantType.SUNFLOWER : null;
}
// 高威胁行优先种攻击植物
if (threat > 30) {
if (sun >= PlantType.REPEATER.cost) return PlantType.REPEATER;
if (sun >= PlantType.PEASHOOTER.cost) return PlantType.PEASHOOTER;
}
// 中等威胁
if (threat > 10) {
if (sun >= PlantType.SNOWPEA.cost) return PlantType.SNOWPEA;
if (sun >= PlantType.PEASHOOTER.cost) return PlantType.PEASHOOTER;
}
// 低威胁行种向日葵补充经济
if (sun >= PlantType.SUNFLOWER.cost) return PlantType.SUNFLOWER;
return null;
}
/**
* 评估种植位置的价值
*/
private double evaluatePosition(int row, int col, PlantType type,
double[] rowThreat, int[][] board, List<Zombie> zombies) {
double value = 0;
// 基础价值：该行威胁越高，价值越大
value += rowThreat[row] * 2;
// 位置加成：越靠右越早发挥作用，但太靠前容易被吃掉
if (col >= 2 && col <= 6) value += 10;
else if (col > 6) value += 5;
// 列协同：同列已有攻击植物，种向日葵提供经济支持
boolean hasAttackerInCol = false;
for (int r = 0; r < ROWS; r++) {
if (board[r][col] == 2 || board[r][col] == 4) hasAttackerInCol = true;
}
if (hasAttackerInCol && type == PlantType.SUNFLOWER) value += 8;
// 行协同：该行已有坚果，种射手在其后输出
boolean hasWallnut = false;
for (int c = 0; c < COLS; c++) {
if (board[row][c] == 3) hasWallnut = true;
}
if (hasWallnut && type.damage > 0) value += 15;
// 成本效益
value = value * 100 / type.cost;
return value;
}
static class PlantDecision {
int row, col;
PlantType type;
double value;
PlantDecision(int row, int col, PlantType type, double value) {
this.row = row; this.col = col; this.type = type; this.value = value;
}
}
}
僵尸AI与攻击判定
僵尸使用简单的贪心策略选择路径（直走），植物使用贪心策略选择攻击目标（优先攻击最近的僵尸）。
/**
* 植物大战僵尸 - 战斗模拟引擎
* 处理僵尸移动、植物攻击、碰撞检测
*/
public class BattleEngine {
private static final int ROWS = 5;
private static final int COLS = 9;
private static final double CELL_WIDTH = 80;
static class Plant {
int row, col;
int type;
int hp;
int damage;
int range;
double attackCooldown;
double currentCooldown;
boolean producesSun;
double sunCooldown;
double currentSunCooldown;
Plant(int row, int col, int type, int hp, int damage, int range,
boolean producesSun, double attackCd, double sunCd) {
this.row = row; this.col = col; this.type = type; this.hp = hp;
this.damage = damage; this.range = range; this.producesSun = producesSun;
this.attackCooldown = attackCd; this.sunCooldown = sunCd;
this.currentCooldown = 0; this.currentSunCooldown = sunCd;
}
}
static class Zombie {
int row;
double x; // 像素坐标
int hp;
double speed;
int damage;
double attackCooldown;
double currentAttackCd;
boolean slowed;
double slowTimer;
Zombie(int row, double x, int hp, double speed, int damage) {
this.row = row; this.x = x; this.hp = hp;
this.speed = speed; this.damage = damage;
this.attackCooldown = 1.0;
this.currentAttackCd = 0;
this.slowed = false; this.slowTimer = 0;
}
}
private List<Plant> plants = new ArrayList<>();
private List<Zombie> zombies = new ArrayList<>();
/**
* 更新所有植物攻击
* 每株植物使用贪心策略选择最近的目标
*/
public void updatePlants(double dt) {
for (Plant plant : plants) {
if (plant.hp <= 0) continue;
// 产阳光
if (plant.producesSun) {
plant.currentSunCooldown -= dt;
if (plant.currentSunCooldown <= 0) {
plant.currentSunCooldown = plant.sunCooldown;
// 产生阳光...（在Game类中处理）
}
}
if (plant.damage <= 0) continue; // 非攻击植物
// 冷却更新
plant.currentCooldown -= dt;
if (plant.currentCooldown > 0) continue;
// 贪心选择攻击目标：同列/同行最近的僵尸
Zombie target = findNearestZombie(plant);
if (target != null) {
target.hp -= plant.damage;
plant.currentCooldown = plant.attackCooldown;
// 减速效果
if (plant.type == 5) { // 寒冰射手
target.slowed = true;
target.slowTimer = 3.0;
}
}
}
}
/**
* 贪心策略：找到植物攻击范围内的最近僵尸
*/
private Zombie findNearestZombie(Plant plant) {
Zombie nearest = null;
double minDist = Double.MAX_VALUE;
double plantX = plant.col * CELL_WIDTH + CELL_WIDTH / 2;
for (Zombie z : zombies) {
if (z.row != plant.row || z.hp <= 0) continue;
// 只攻击右侧的僵尸（僵尸从右向左走）
if (z.x < plantX) continue;
double dist = z.x - plantX;
double maxRange = plant.range * CELL_WIDTH;
if (dist > maxRange) continue;
// 贪心选择最近的
if (dist < minDist) {
minDist = dist;
nearest = z;
}
}
return nearest;
}
/**
* 更新所有僵尸
*/
public void updateZombies(double dt) {
Iterator<Zombie> it = zombies.iterator();
while (it.hasNext()) {
Zombie z = it.next();
if (z.hp <= 0) {
it.remove();
continue;
}
// 处理减速
double actualSpeed = z.speed;
if (z.slowed) {
actualSpeed *= 0.5;
z.slowTimer -= dt;
if (z.slowTimer <= 0) z.slowed = false;
}
// 检查前方是否有植物
Plant blocker = findBlocker(z);
if (blocker != null) {
// 攻击植物
z.currentAttackCd -= dt;
if (z.currentAttackCd <= 0) {
blocker.hp -= z.damage;
z.currentAttackCd = z.attackCooldown;
}
} else {
// 移动
z.x -= actualSpeed * dt;
}
// 到达左侧边界
if (z.x < 0) {
// 游戏结束信号
}
}
}
/**
* 找到僵尸正前方的植物（阻挡者）
*/
private Plant findBlocker(Zombie z) {
double zombieCol = z.x / CELL_WIDTH;
Plant blocker = null;
double minDist = Double.MAX_VALUE;
for (Plant p : plants) {
if (p.row != z.row || p.hp <= 0) continue;
double pCol = p.col;
// 植物在僵尸左侧且最近
if (pCol < zombieCol) {
double dist = zombieCol - pCol;
if (dist < minDist) {
minDist = dist;
blocker = p;
}
}
}
// 只有当僵尸与植物距离足够近才算碰撞
if (blocker != null && minDist > 0.8) return null;
return blocker;
}
}
完整可运行项目
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.List;
/**
* 植物大战僵尸简化版完整实现
*/
public class PlantsVsZombiesGame extends JPanel implements ActionListener, MouseListener {
private static final int ROWS = 5;
private static final int COLS = 9;
private static final int CELL_SIZE = 80;
private static final int WIDTH = COLS * CELL_SIZE + 200;
private static final int HEIGHT = ROWS * CELL_SIZE + 100;
private Timer timer;
private Random rand = new Random();
private int sun = 150; // 阳光
private int selectedPlant = -1; // 当前选择的植物类型
private int score = 0;
private int wave = 1;
private double spawnTimer = 0;
private boolean gameOver = false;
private int[][] board = new int[ROWS][COLS]; // 0=空
private List<Plant> plants = new ArrayList<>();
private List<Zombie> zombies = new ArrayList<>();
private List<SunDrop> sunDrops = new ArrayList<>();
// 植物配置
private String[] plantNames = {"向日葵", "豌豆射手", "坚果墙", "双发射手", "寒冰射手"};
private int[] plantCosts = {50, 100, 50, 200, 175};
private Color[] plantColors = {Color.YELLOW, Color.GREEN, Color.ORANGE, Color.GREEN.darker(), Color.CYAN};
class Plant {
int row, col, type, hp;
double attackCd, sunCd;
double atkTimer, sunTimer;
Plant(int r, int c, int t) {
row = r; col = c; type = t;
switch(t) {
case 0 -> { hp = 50; sunCd = 5; } // 向日葵
case 1 -> { hp = 50; attackCd = 1.5; } // 豌豆
case 2 -> { hp = 300; } // 坚果
case 3 -> { hp = 50; attackCd = 1.5; } // 双发
case 4 -> { hp = 50; attackCd = 1.5; } // 寒冰
}
atkTimer = attackCd; sunTimer = sunCd;
}
}
class Zombie {
int row, hp, damage = 10;
double x, speed = 20;
boolean slowed;
double slowTimer;
double attackCd = 1, atkTimer;
Zombie(int row, int hp) {
this.row = row; this.hp = hp;
this.x = COLS * CELL_SIZE;
this.atkTimer = attackCd;
}
}
class SunDrop {
double x, y;
int value;
SunDrop(double x, double y, int v) { this.x = x; this.y = y; this.value = v; }
}
public PlantsVsZombiesGame() {
setPreferredSize(new Dimension(WIDTH, HEIGHT));
setBackground(new Color(100, 180, 100));
addMouseListener(this);
timer = new Timer(50, this);
}
@Override
public void actionPerformed(ActionEvent e) {
if (gameOver) return;
double dt = 0.05;
// 生成僵尸
spawnTimer -= dt;
if (spawnTimer <= 0) {
int count = 1 + wave / 3;
for (int i = 0; i < count; i++) {
int row = rand.nextInt(ROWS);
int hp = 50 + wave * 20;
zombies.add(new Zombie(row, hp));
}
spawnTimer = Math.max(3, 8 - wave * 0.3);
}
// 更新植物
for (Plant p : plants) {
if (p.hp <= 0) continue;
// 产阳光
if (p.type == 0) {
p.sunTimer -= dt;
if (p.sunTimer <= 0) {
p.sunTimer = p.sunCd;
sunDrops.add(new SunDrop(p.col * CELL_SIZE + 20, p.row * CELL_SIZE + 40, 25));
}
}
// 攻击
if (p.type == 1 || p.type == 3 || p.type == 4) {
p.atkTimer -= dt;
if (p.atkTimer <= 0) {
p.atkTimer = p.attackCd;
shoot(p);
}
}
}
// 更新僵尸
Iterator<Zombie> zit = zombies.iterator();
while (zit.hasNext()) {
Zombie z = zit.next();
if (z.hp <= 0) { zit.remove(); score += 10; continue; }
double speed = z.speed;
if (z.slowed) {
speed *= 0.5;
z.slowTimer -= dt;
if (z.slowTimer <= 0) z.slowed = false;
}
// 检查前方植物
Plant blocker = findBlocker(z);
if (blocker != null) {
z.atkTimer -= dt;
if (z.atkTimer <= 0) {
blocker.hp -= z.damage;
z.atkTimer = z.attackCd;
if (blocker.hp <= 0) board[blocker.row][blocker.col] = 0;
}
} else {
z.x -= speed * dt;
}
if (z.x < 0) gameOver = true;
}
// 更新阳光掉落
Iterator<SunDrop> sit = sunDrops.iterator();
while (sit.hasNext()) {
SunDrop s = sit.next();
s.y += 30 * dt;
if (s.y > HEIGHT - 50) sit.remove();
}
// 清理死亡植物
plants.removeIf(p -> p.hp <= 0);
repaint();
}
/**
* 贪心策略：植物射击最近的同排僵尸
*/
private void shoot(Plant p) {
Zombie target = null;
double minDist = Double.MAX_VALUE;
double px = p.col * CELL_SIZE + CELL_SIZE / 2;
for (Zombie z : zombies) {
if (z.row != p.row || z.hp <= 0 || z.x < px) continue;
double dist = z.x - px;
if (dist < minDist) {
minDist = dist;
target = z;
}
}
if (target != null) {
int dmg = (p.type == 3) ? 40 : 20; // 双发伤害更高
target.hp -= dmg;
if (p.type == 4) { // 寒冰减速
target.slowed = true;
target.slowTimer = 3;
}
}
}
private Plant findBlocker(Zombie z) {
double zc = z.x / CELL_SIZE;
for (Plant p : plants) {
if (p.row != z.row || p.hp <= 0) continue;
if (p.col < zc && zc - p.col < 0.8) return p;
}
return null;
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
// 绘制网格
g.setColor(new Color(80, 160, 80));
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
g.drawRect(c * CELL_SIZE, r * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// 绘制植物
for (Plant p : plants) {
if (p.hp <= 0) continue;
int x = p.col * CELL_SIZE + 10;
int y = p.row * CELL_SIZE + 10;
g.setColor(plantColors[p.type]);
g.fillOval(x, y, CELL_SIZE - 20, CELL_SIZE - 20);
g.setColor(Color.BLACK);
g.drawOval(x, y, CELL_SIZE - 20, CELL_SIZE - 20);
g.setFont(new Font("Arial", Font.BOLD, 10));
g.drawString(plantNames[p.type].substring(0, 2), x + 10, y + 25);
// 血条
g.setColor(Color.RED);
g.fillRect(x, y - 8, (CELL_SIZE - 20) * p.hp / getMaxHp(p.type), 5);
}
// 绘制僵尸
for (Zombie z : zombies) {
int x = (int) z.x;
int y = z.row * CELL_SIZE + 20;
g.setColor(z.slowed ? Color.BLUE : Color.DARK_GRAY);
g.fillRect(x, y, 40, 40);
g.setColor(Color.RED);
g.fillRect(x, y - 8, 40 * z.hp / (50 + wave * 20), 5);
}
// 绘制阳光
g.setColor(Color.YELLOW);
for (SunDrop s : sunDrops) {
g.fillOval((int)s.x, (int)s.y, 20, 20);
}
// 右侧植物选择栏
g.setColor(new Color(139, 90, 43));
g.fillRect(COLS * CELL_SIZE, 0, 200, HEIGHT);
g.setColor(Color.WHITE);
g.setFont(new Font("Microsoft YaHei", Font.BOLD, 16));
g.drawString("阳光: " + sun, COLS * CELL_SIZE + 20, 30);
g.drawString("波次: " + wave, COLS * CELL_SIZE + 20, 55);
g.drawString("分数: " + score, COLS * CELL_SIZE + 20, 80);
for (int i = 0; i < plantNames.length; i++) {
int y = 120 + i * 70;
g.setColor(plantColors[i]);
g.fillRect(COLS * CELL_SIZE + 20, y, 50, 50);
g.setColor(selectedPlant == i ? Color.RED : Color.WHITE);
g.drawRect(COLS * CELL_SIZE + 20, y, 50, 50);
g.drawString(plantNames[i] + " " + plantCosts[i], COLS * CELL_SIZE + 80, y + 30);
}
if (gameOver) {
g.setColor(new Color(0, 0, 0, 180));
g.fillRect(0, 0, WIDTH, HEIGHT);
g.setColor(Color.RED);
g.setFont(new Font("Microsoft YaHei", Font.BOLD, 48));
g.drawString("游戏结束", WIDTH/2 - 100, HEIGHT/2);
}
}
@Override
public void mousePressed(MouseEvent e) {
int mx = e.getX(), my = e.getY();
// 点击植物栏
if (mx > COLS * CELL_SIZE) {
for (int i = 0; i < plantNames.length; i++) {
int y = 120 + i * 70;
if (my >= y && my <= y + 50) {
selectedPlant = i;
repaint();
return;
}
}
}
// 点击收集阳光
Iterator<SunDrop> sit = sunDrops.iterator();
while (sit.hasNext()) {
SunDrop s = sit.next();
if (Math.abs(mx - s.x) < 20 && Math.abs(my - s.y) < 20) {
sun += s.value;
sit.remove();
repaint();
return;
}
}
// 种植
if (selectedPlant >= 0) {
int c = mx / CELL_SIZE;
int r = my / CELL_SIZE;
if (r < ROWS && c < COLS && board[r][c] == 0 && sun >= plantCosts[selectedPlant]) {
sun -= plantCosts[selectedPlant];
board[r][c] = selectedPlant + 1;
plants.add(new Plant(r, c, selectedPlant));
selectedPlant = -1;
repaint();
}
}
}
private int getMaxHp(int type) {
return switch(type) { case 2 -> 300; default -> 50; };
}
public void start() { timer.start(); }
@Override public void mouseClicked(MouseEvent e) {}
@Override public void mouseReleased(MouseEvent e) {}
@Override public void mouseEntered(MouseEvent e) {}
@Override public void mouseExited(MouseEvent e) {}
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
JFrame frame = new JFrame("植物大战僵尸 - 资源分配与贪心策略");
PlantsVsZombiesGame game = new PlantsVsZombiesGame();
frame.add(game);
frame.pack();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
game.start();
});
}
}
算法复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 防御布局决策 | O(ROWS × COLS × N) | O(ROWS) | N为僵尸数，枚举所有空格 |
| 最近僵尸查找 | O(N) | O(1) | 每株植物独立查找 |
| 阻挡植物查找 | O(P) | O(1) | P为场上植物数 |
| 僵尸移动更新 | O(Z × P) | O(1) | Z为僵尸数 |
| 级联攻击判定 | O(P × Z) | O(1) | 每帧所有植物攻击判定 |
贪心策略在塔防游戏中的优势在于响应速度快、易于理解，适合实时决策场景。对于离线最优布局，可以考虑用动态规划或遗传算法优化。
扩展方向
- 多行攻击植物：如西瓜投手可攻击多行，需要扩展目标搜索范围
- A*路径规划：僵尸遇到障碍可绕行，而非简单直线前进
- 协同防御网络：用图论建模植物间的覆盖范围，最大化防御效率
