引言
《王国保卫战》（Kingdom Rush）是经典塔防游戏的代表作，玩家需要在敌人进攻的路径上建造防御塔，合理分配有限的金币资源来抵御一波又一波的敌军。核心算法挑战在于：给定敌人波次信息和可用防御塔类型，如何在每个决策点贪婪地分配资源以最大化整体防御效果？ 本文用Java实现波次调度模拟器，结合贪心算法进行防御塔的最优布局与动态预算调整。
核心机制建模
防御塔系统
import java.util.*;
/**
* 防御塔基类：每种塔有不同的攻击方式、射程、攻速和造价
*/
abstract class Tower {
public final String name;
public final int baseCost; // 基础建造费用
public final int upgradeCost; // 升级费用
public final double range; // 攻击范围（像素/格数）
public final double attackSpeed; // 攻击间隔（秒/次）
public int level = 1; // 当前等级（1-4）
public final int maxLevel = 4;
// 塔的位置
public double x, y;
public Tower(String name, int baseCost, int upgradeCost,
double range, double attackSpeed) {
this.name = name;
this.baseCost = baseCost;
this.upgradeCost = upgradeCost;
this.range = range;
this.attackSpeed = attackSpeed;
}
/**
* 计算对特定敌人的伤害
*/
public abstract double calculateDamage(Enemy enemy);
/**
* 获取当前等级的总造价
*/
public int getTotalInvestment() {
return baseCost + (level - 1) * upgradeCost;
}
/**
* 升级塔
*/
public boolean upgrade() {
if (level >= maxLevel) return false;
level++;
return true;
}
@Override
public String toString() {
return String.format("%s Lv%d (造价:%d 射程:%.0f)",
name, level, getTotalInvestment(), range);
}
}
/**
* 箭塔：攻速快、费用低、物理伤害
*/
class ArcherTower extends Tower {
public final double baseDamage;
public ArcherTower() {
super("箭塔", 70, 110, 150, 0.5);
this.baseDamage = 8;
}
@Override
public double calculateDamage(Enemy enemy) {
// 箭塔对轻甲敌人有加成，对重甲有减益
double multiplier = enemy.armorType == ArmorType.LIGHT ? 1.3 :
enemy.armorType == ArmorType.HEAVY ? 0.6 : 1.0;
return baseDamage * level * multiplier;
}
}
/**
* 兵营：召唤士兵阻挡敌人
*/
class Barracks extends Tower {
public final int unitCount; // 士兵数量
public final double unitHealth; // 士兵生命值
public final double unitDamage; // 士兵伤害
public Barracks() {
super("兵营", 70, 110, 100, 1.0);
this.unitCount = 3;
this.unitHealth = 50 * level;
this.unitDamage = 3 * level;
}
@Override
public double calculateDamage(Enemy enemy) {
// 兵营的伤害取决于士兵阻挡的敌人数量和时长
// 简化模型：每秒造成 unitCount * unitDamage 的伤害
return unitCount * unitDamage;
}
/**
* 计算阻挡能力：能同时阻挡多少敌人
*/
public double getBlockCapability() {
return unitCount * unitHealth * level;
}
}
/**
* 法师塔：高伤害、忽视部分护甲
*/
class MageTower extends Tower {
public final double baseDamage;
public final double armorPenetration; // 护甲穿透比例
public MageTower() {
super("法师塔", 100, 160, 180, 1.5);
this.baseDamage = 25;
this.armorPenetration = 0.3 * level;
}
@Override
public double calculateDamage(Enemy enemy) {
double effectiveArmor = enemy.armor * (1 - armorPenetration);
double reduction = effectiveArmor / (effectiveArmor + 100);
return baseDamage * level * (1 - reduction);
}
}
/**
* 炮塔：范围伤害（AOE）
*/
class ArtilleryTower extends Tower {
public final double baseDamage;
public final double splashRadius; // 溅射范围
public ArtilleryTower() {
super("炮塔", 125, 200, 200, 2.5);
this.baseDamage = 15;
this.splashRadius = 60 * level;
}
@Override
public double calculateDamage(Enemy enemy) {
// 炮塔对重甲敌人有加成
double multiplier = enemy.armorType == ArmorType.HEAVY ? 1.5 :
enemy.armorType == ArmorType.LIGHT ? 0.7 : 1.0;
return baseDamage * level * multiplier;
}
/**
* AOE伤害：估算能同时命中多少敌人
*/
public double estimateAoeHitCount(List<Enemy> enemiesInRange) {
if (enemiesInRange.size() <= 1) return 1;
// 简化：假设敌人密度下平均命中数
return Math.min(enemiesInRange.size(), 1 + splashRadius / 30.0);
}
}
enum ArmorType { LIGHT, MEDIUM, HEAVY, MAGIC }
敌人系统
/**
* 敌人：具有生命值、护甲、速度、赏金等属性
*/
class Enemy {
public final String name;
public double health;
public final double maxHealth;
public final double armor;
public final ArmorType armorType;
public final double speed; // 移动速度
public final int bounty; // 击杀奖励金币
public final int dangerLevel; // 威胁等级（1-10）
// 动态状态
public double x, y; // 当前位置
public double distanceTraveled = 0; // 已行进距离
public boolean isBlocked = false; // 是否被兵营阻挡
public Enemy(String name, double health, double armor,
ArmorType type, double speed, int bounty, int danger) {
this.name = name;
this.maxHealth = health;
this.health = health;
this.armor = armor;
this.armorType = type;
this.speed = speed;
this.bounty = bounty;
this.dangerLevel = danger;
}
/**
* 计算生存时间预估：在当前火力下能存活多久
*/
public double estimateSurvivalTime(double dps) {
if (dps <= 0) return Double.POSITIVE_INFINITY;
return health / dps;
}
@Override
public String toString() {
return String.format("%s(血量:%.0f 护甲:%.0f 赏金:%d)",
name, health, armor, bounty);
}
}
/**
* 波次：包含一组同类型或混合类型的敌人
*/
class Wave {
public final int waveNumber;
public final List<Enemy> enemies;
public final double spawnInterval; // 敌人生成间隔
public final double totalBounty; // 总赏金
public final double totalHealth; // 总生命值
public final double totalDanger; // 总威胁值
public Wave(int number, List<Enemy> enemies, double spawnInterval) {
this.waveNumber = number;
this.enemies = new ArrayList<>(enemies);
this.spawnInterval = spawnInterval;
this.totalBounty = enemies.stream().mapToInt(e -> e.bounty).sum();
this.totalHealth = enemies.stream().mapToDouble(e -> e.maxHealth).sum();
this.totalDanger = enemies.stream().mapToInt(e -> e.dangerLevel).sum();
}
@Override
public String toString() {
return String.format("第%d波: %d个敌人 | 总血量:%.0f | 总赏金:%.0f | 威胁:%.0f",
waveNumber, enemies.size(), totalHealth, totalBounty, totalDanger);
}
}
贪心资源分配策略
贪心策略的核心思想是：在每个决策点，选择”单位金币投入能带来最大防御收益”的选项。
/**
* 防御策略引擎：使用贪心算法分配金币建造和升级防御塔
*/
public class DefenseStrategyEngine {
private int gold; // 当前金币
private final List<Tower> towers; // 已建造的塔
private final List<Wave> waves; // 即将到来的波次
private final List<double[]> path; // 敌人行进路径（坐标点序列）
private final Set<int[]> buildSlots; // 可建造位置
public DefenseStrategyEngine(int initialGold, List<Wave> waves,
List<double[]> path, Set<int[]> buildSlots) {
this.gold = initialGold;
this.towers = new ArrayList<>();
this.waves = waves;
this.path = path;
this.buildSlots = buildSlots;
}
/**
* 贪心决策：在当前金币和即将到来的波次下，做出最优建造/升级决策
*/
public List<Decision> makeDecisions(Wave upcomingWave) {
List<Decision> decisions = new ArrayList<>();
while (gold >= 70) { // 最便宜的塔需要70金币
Decision bestDecision = findBestDecision(upcomingWave);
if (bestDecision == null) break;
executeDecision(bestDecision);
decisions.add(bestDecision);
}
return decisions;
}
/**
* 评估所有可能的决策，返回收益/成本比最高的
*/
private Decision findBestDecision(Wave wave) {
Decision best = null;
double bestEfficiency = 0;
// 选项1：建造新塔
for (int[] slot : buildSlots) {
// 箭塔
if (gold >= 70) {
double eff = evaluateNewTower(new ArcherTower(), slot[0], slot[1], wave);
if (eff > bestEfficiency) {
bestEfficiency = eff;
best = new Decision(DecisionType.BUILD, new ArcherTower(), slot[0], slot[1], 70);
}
}
// 兵营
if (gold >= 70) {
double eff = evaluateNewTower(new Barracks(), slot[0], slot[1], wave);
if (eff > bestEfficiency) {
bestEfficiency = eff;
best = new Decision(DecisionType.BUILD, new Barracks(), slot[0], slot[1], 70);
}
}
// 法师塔
if (gold >= 100) {
double eff = evaluateNewTower(new MageTower(), slot[0], slot[1], wave);
if (eff > bestEfficiency) {
bestEfficiency = eff;
best = new Decision(DecisionType.BUILD, new MageTower(), slot[0], slot[1], 100);
}
}
// 炮塔
if (gold >= 125) {
double eff = evaluateNewTower(new ArtilleryTower(), slot[0], slot[1], wave);
if (eff > bestEfficiency) {
bestEfficiency = eff;
best = new Decision(DecisionType.BUILD, new ArtilleryTower(), slot[0], slot[1], 125);
}
}
}
// 选项2：升级现有塔
for (Tower tower : towers) {
if (tower.level >= tower.maxLevel) continue;
int upgradeCost = tower.upgradeCost;
if (gold < upgradeCost) continue;
double eff = evaluateUpgrade(tower, wave);
if (eff > bestEfficiency) {
bestEfficiency = eff;
best = new Decision(DecisionType.UPGRADE, tower, 0, 0, upgradeCost);
}
}
return best;
}
/**
* 评估在指定位置建造新塔的收益效率
* 效率 = 预期伤害输出 / 建造费用
*/
private double evaluateNewTower(Tower tower, int slotX, int slotY, Wave wave) {
tower.x = slotX;
tower.y = slotY;
// 计算该塔能覆盖路径的多少长度
double coveredPathLength = calculateCoveredPathLength(tower);
if (coveredPathLength <= 0) return 0;
// 估算对该波敌人的总伤害
double totalDamage = 0;
for (Enemy enemy : wave.enemies) {
// 判断敌人是否经过塔的射程范围
if (isPathWithinRange(enemy, tower)) {
double dmg = tower.calculateDamage(enemy);
double timeInRange = coveredPathLength / enemy.speed;
double attacks = timeInRange / tower.attackSpeed;
totalDamage += dmg * attacks;
}
}
// 考虑塔的特殊效果
double specialBonus = 0;
if (tower instanceof Barracks) {
// 兵营的价值在于阻挡，使其他塔有更多输出时间
specialBonus = ((Barracks) tower).getBlockCapability() * 0.5;
} else if (tower instanceof ArtilleryTower) {
// AOE额外价值
long enemiesInRange = wave.enemies.stream()
.filter(e -> isPathWithinRange(e, tower)).count();
specialBonus = totalDamage * (((ArtilleryTower) tower).estimateAoeHitCount(
wave.enemies.stream().filter(e -> isPathWithinRange(e, tower)).toList()) - 1);
}
double cost = tower.baseCost;
return (totalDamage + specialBonus) / cost;
}
/**
* 评估升级现有塔的收益效率
*/
private double evaluateUpgrade(Tower tower, Wave wave) {
double currentDps = 0;
double upgradedDps = 0;
for (Enemy enemy : wave.enemies) {
if (isPathWithinRange(enemy, tower)) {
double currentDmg = tower.calculateDamage(enemy) / tower.attackSpeed;
// 模拟升级后的伤害（创建临时升级副本）
int originalLevel = tower.level;
tower.level++;
double upgradedDmg = tower.calculateDamage(enemy) / tower.attackSpeed;
tower.level = originalLevel;
currentDps += currentDmg;
upgradedDps += upgradedDmg;
}
}
double damageIncrease = upgradedDps - currentDps;
return damageIncrease / tower.upgradeCost;
}
/**
* 判断敌人路径是否经过塔的射程范围
*/
private boolean isPathWithinRange(Enemy enemy, Tower tower) {
// 简化：检查路径上是否有任何点在塔射程内
for (double[] point : path) {
double dist = Math.sqrt(Math.pow(point[0] - tower.x, 2) +
Math.pow(point[1] - tower.y, 2));
if (dist <= tower.range) return true;
}
return false;
}
/**
* 计算塔覆盖的路径长度
*/
private double calculateCoveredPathLength(Tower tower) {
double coveredLength = 0;
for (int i = 0; i < path.size() - 1; i++) {
double[] p1 = path.get(i);
double[] p2 = path.get(i + 1);
// 检查线段是否与塔射程相交
if (isSegmentInRange(p1, p2, tower)) {
coveredLength += Math.sqrt(Math.pow(p2[0]-p1[0], 2) + Math.pow(p2[1]-p1[1], 2));
}
}
return coveredLength;
}
private boolean isSegmentInRange(double[] p1, double[] p2, Tower tower) {
// 点到线段距离公式
double dx = p2[0] - p1[0];
double dy = p2[1] - p1[1];
double len2 = dx*dx + dy*dy;
if (len2 == 0) {
return Math.sqrt(Math.pow(p1[0]-tower.x, 2) + Math.pow(p1[1]-tower.y, 2)) <= tower.range;
}
double t = Math.max(0, Math.min(1, ((tower.x - p1[0])*dx + (tower.y - p1[1])*dy) / len2));
double projX = p1[0] + t * dx;
double projY = p1[1] + t * dy;
return Math.sqrt(Math.pow(projX - tower.x, 2) + Math.pow(projY - tower.y, 2)) <= tower.range;
}
private void executeDecision(Decision decision) {
gold -= decision.cost;
if (decision.type == DecisionType.BUILD) {
decision.tower.x = decision.x;
decision.tower.y = decision.y;
towers.add(decision.tower);
buildSlots.remove(new int[]{(int)decision.x, (int)decision.y});
} else if (decision.type == DecisionType.UPGRADE) {
decision.tower.upgrade();
}
}
enum DecisionType { BUILD, UPGRADE }
static class Decision {
public final DecisionType type;
public final Tower tower;
public final int x, y;
public final int cost;
public Decision(DecisionType type, Tower tower, int x, int y, int cost) {
this.type = type;
this.tower = tower;
this.x = x;
this.y = y;
this.cost = cost;
}
@Override
public String toString() {
if (type == DecisionType.BUILD) {
return String.format("建造 %s 在 (%d,%d) 花费 %d金币", tower.name, x, y, cost);
} else {
return String.format("升级 %s 到 Lv%d 花费 %d金币", tower.name, tower.level + 1, cost);
}
}
}
}
波次难度评估与动态预算
/**
* 波次分析器：评估波次威胁并建议预算分配
*/
public class WaveAnalyzer {
/**
* 综合评估波次威胁等级
*/
public static WaveThreat assessThreat(Wave wave) {
double avgHealth = wave.totalHealth / wave.enemies.size();
double avgSpeed = wave.enemies.stream().mapToDouble(e -> e.speed).average().orElse(1);
double avgArmor = wave.enemies.stream().mapToDouble(e -> e.armor).average().orElse(0);
// 威胁分 = 总血量 × 平均速度 × (1 + 平均护甲/100) / 生成间隔
double threatScore = wave.totalHealth * avgSpeed * (1 + avgArmor / 100)
/ Math.max(0.5, wave.spawnInterval);
// 根据威胁分定级
ThreatLevel level;
if (threatScore < 500) level = ThreatLevel.LOW;
else if (threatScore < 1500) level = ThreatLevel.MEDIUM;
else if (threatScore < 3000) level = ThreatLevel.HIGH;
else level = ThreatLevel.EXTREME;
// 推荐预算：根据威胁等级和总赏金动态调整
int recommendedBudget = (int)(wave.totalBounty * (0.5 + level.ordinal() * 0.2));
// 推荐塔类型
List<String> recommendedTowers = new ArrayList<>();
long heavyCount = wave.enemies.stream().filter(e -> e.armorType == ArmorType.HEAVY).count();
long lightCount = wave.enemies.stream().filter(e -> e.armorType == ArmorType.LIGHT).count();
long magicCount = wave.enemies.stream().filter(e -> e.armorType == ArmorType.MAGIC).count();
if (heavyCount > wave.enemies.size() * 0.3) recommendedTowers.add("法师塔(破甲)");
if (lightCount > wave.enemies.size() * 0.3) recommendedTowers.add("箭塔(速射)");
if (wave.enemies.size() > 10) recommendedTowers.add("炮塔(AOE)");
if (wave.totalDanger > 30) recommendedTowers.add("兵营(阻挡)");
return new WaveThreat(level, threatScore, recommendedBudget, recommendedTowers);
}
public enum ThreatLevel { LOW, MEDIUM, HIGH, EXTREME }
public static class WaveThreat {
public final ThreatLevel level;
public final double score;
public final int recommendedBudget;
public final List<String> recommendedTowers;
public WaveThreat(ThreatLevel level, double score, int budget, List<String> towers) {
this.level = level;
this.score = score;
this.recommendedBudget = budget;
this.recommendedTowers = towers;
}
}
}
完整运行示例
public class KingdomRushSimulation {
public static void main(String[] args) {
// 定义路径（简化：从起点到终点的折线）
List<double[]> path = new ArrayList<>();
for (int i = 0; i <= 20; i++) {
path.add(new double[]{i * 20, 100 + Math.sin(i * 0.3) * 30});
}
// 可建造位置（路径两侧）
Set<int[]> buildSlots = new HashSet<>();
for (int i = 2; i < 18; i++) {
buildSlots.add(new int[]{i * 20, 60});
buildSlots.add(new int[]{i * 20, 140});
}
// 定义波次
List<Wave> waves = new ArrayList<>();
// 第1-3波：轻甲小怪
for (int i = 1; i <= 3; i++) {
List<Enemy> enemies = new ArrayList<>();
for (int j = 0; j < 5 + i * 2; j++) {
enemies.add(new Enemy("地精", 30 + i * 10, 0, ArmorType.LIGHT, 20, 5, 1));
}
waves.add(new Wave(i, enemies, 1.5));
}
// 第4-5波：重甲敌人
for (int i = 4; i <= 5; i++) {
List<Enemy> enemies = new ArrayList<>();
for (int j = 0; j < 4; j++) {
enemies.add(new Enemy("兽人", 120, 30, ArmorType.HEAVY, 12, 12, 3));
}
waves.add(new Wave(i, enemies, 2.0));
}
// 第6波：混合波（大量轻甲 + 少量重甲）
List<Enemy> mixed = new ArrayList<>();
for (int j = 0; j < 15; j++) mixed.add(new Enemy("地精", 50, 0, ArmorType.LIGHT, 20, 5, 1));
for (int j = 0; j < 3; j++) mixed.add(new Enemy("兽人", 150, 40, ArmorType.HEAVY, 10, 15, 4));
waves.add(new Wave(6, mixed, 1.0));
System.out.println("=== 王国保卫战波次分析与防御策略 ===\n");
// 分析每波威胁
System.out.println("--- 波次威胁评估 ---");
for (Wave wave : waves) {
WaveAnalyzer.WaveThreat threat = WaveAnalyzer.assessThreat(wave);
System.out.printf("%s | 威胁等级:%s | 推荐预算:%d金币 | 推荐塔:%s%n",
wave, threat.level, threat.recommendedBudget, threat.recommendedTowers);
}
// 逐波决策模拟
System.out.println("\n--- 逐波贪心决策模拟 ---");
int initialGold = 200;
DefenseStrategyEngine engine = new DefenseStrategyEngine(initialGold, waves, path, buildSlots);
int totalGold = initialGold;
for (Wave wave : waves) {
System.out.println("\n>> " + wave);
totalGold += (int)wave.totalBounty; // 获得上一波的赏金
List<DefenseStrategyEngine.Decision> decisions = engine.makeDecisions(wave);
System.out.println("决策结果（剩余金币:" + totalGold + "）:");
for (DefenseStrategyEngine.Decision d : decisions) {
System.out.println(" " + d);
totalGold -= d.cost;
}
if (decisions.isEmpty()) {
System.out.println(" （金币不足，暂不建造）");
}
}
System.out.println("\n=== 策略总结 ===");
System.out.println("总波次数: " + waves.size());
System.out.println("初始金币: " + initialGold);
System.out.println("总赏金收入: " + waves.stream().mapToDouble(w -> w.totalBounty).sum());
}
}
算法复杂度分析
| 模块 | 时间复杂度 | 说明 |
|---|---|---|
| 路径覆盖计算 | O(P) | P=路径点数 |
| 单塔收益评估 | O(E × P) | E=敌人数量 |
| 贪心决策 | O(S × T × E × P) | S=建造位, T=塔类型数 |
| 波次威胁评估 | O(E) | 线性遍历 |
对于典型关卡（20个建造位、4种塔类型、30个敌人、50个路径点），单次贪心决策在毫秒级完成，完全可以做到实时辅助决策。
扩展方向
-
多路径与飞行敌人：当地图有多条路径或出现飞行敌人（不受兵营阻挡）时，需要扩展路径覆盖计算和塔优先级评估。
-
英雄技能与援军：王国保卫战中的英雄和援军技能有冷却时间，可建模为带有冷却约束的资源分配问题。
-
动态难度调整：根据玩家已建造的塔类型，自适应调整后续波次的敌人构成（反制玩家的策略）。
-
协同防御网络：考虑塔与塔之间的协同效果（如箭塔+兵营的经典组合），在贪心评估中加入协同加成项。
总结
本文用Java实现了王国保卫战的核心防御决策系统，将塔防游戏的策略问题建模为资源分配优化问题，并通过贪心算法高效求解。贪心策略的核心思想——”每一块钱都花在边际收益最高的地方”——不仅适用于塔防游戏，也是现实世界中预算分配、投资组合等问题的经典解法。读者可以在此基础上加入更复杂的机制（多路径、英雄、天气效果），打造更完善的塔防策略分析工具。
