引言：从经典塔防到算法设计
塔防（Tower Defense）是一类经典的策略游戏。玩家在地图上建造防御塔，阻止沿固定路径行进的敌人到达终点。从算法视角看，塔防游戏蕴含了丰富的计算问题：路径生成、覆盖优化与实时调度。本文将用Java实现一个精简的塔防核心框架，重点讲解其中三项关键算法：
- BFS路径生成：在带障碍的网格中计算敌人行进路线；
- 贪心炮塔覆盖：在预算限制下选择最优炮塔位置以最大化路径覆盖；
- 优先队列攻击调度：动态决定炮塔优先攻击哪个敌人。
通过这套实现，你将掌握如何将图搜索、贪心策略与堆数据结构融合到游戏AI中。
核心概念一：BFS路径生成
塔防地图通常建模为二维网格，其中部分格子为道路（可通行），部分为障碍（不可通行）。敌人从起点出发，沿道路向终点移动。若道路是唯一的，路径固定；若存在分支，则需要算法确定行走路径。
本文采用 BFS（广度优先搜索） 计算从起点到终点的最短路径。BFS在无权图上保证找到最短路径，时间复杂度为 O(V+E)，其中 V 为网格顶点数，E 为邻接边数。对于 N×M 的网格，复杂度为 O(N·M)。
关键设计：
– 每个网格格子作为一个图顶点；
– 上下左右相邻的道路格子之间有边；
– BFS从起点扩散，首次到达终点时即得到最短路径；
– 通过前驱数组回溯还原完整路径。
核心概念二：贪心炮塔覆盖策略
炮塔的核心作用是”覆盖”敌人经过的路径。假设每条路径格子上经过的敌人数量已知（或按波次预估），问题转化为：在预算限制下，选择若干炮塔位置，使被覆盖的路径格子总价值最大。
这是一个典型的 加权集合覆盖问题（Weighted Set Cover），属于NP难问题。对于实际游戏，我们采用 贪心近似算法：
- 枚举所有可放置炮塔的候选格子；
- 对每个候选格子，计算其攻击范围内覆盖的路径格子总价值（性价比 = 覆盖价值 / 建造成本）；
- 每轮选择性价比最高的炮塔放置，更新剩余预算；
- 重复直到预算耗尽。
贪心策略虽然不能保证最优解，但计算高效，且在塔防场景中效果良好。
核心概念三：优先队列攻击调度
当多个敌人同时进入炮塔射程时，炮塔需要决定攻击优先级。常见策略包括：
– 最近优先：攻击距离炮塔最近的敌人；
– 最弱优先：攻击血量最低的敌人；
– 最先到达优先：攻击沿路径行进最远的敌人（最靠近终点）。
本文采用 最先到达优先 策略，因为它最能体现”阻止敌人到达终点”的核心目标。使用 优先队列（最小堆） 维护射程内敌人，按路径索引排序，每次取出最靠近终点的敌人进行攻击。
Java完整实现
以下项目包含地图建模、BFS路径生成、贪心炮塔放置、敌人波次移动与攻击调度的完整逻辑。
import java.util.*;
/**
* 塔防游戏核心算法实现
* 核心模块：BFS路径生成、贪心炮塔覆盖、优先队列攻击调度
*/
public class TowerDefenseGame {
// ==================== 地图与常量定义 ====================
static final int EMPTY = 0; // 空地（可建塔）
static final int ROAD = 1; // 道路（敌人通行）
static final int OBSTACLE = 2; // 障碍（不可通行/不可建塔）
static final int TOWER = 3; // 炮塔
static final int[] DX = {-1, 1, 0, 0};
static final int[] DY = {0, 0, -1, 1};
int rows, cols;
int[][] grid; // 地图
int startR, startC; // 起点
int endR, endC; // 终点
List<int[]> path; // BFS生成的敌人路径（道路坐标列表）
List<Tower> towers; // 已放置的炮塔
List<Enemy> enemies; // 场上敌人
int budget; // 建造预算
public TowerDefenseGame(int rows, int cols, int budget) {
this.rows = rows;
this.cols = cols;
this.budget = budget;
this.grid = new int[rows][cols];
this.towers = new ArrayList<>();
this.enemies = new ArrayList<>();
this.path = new ArrayList<>();
}
// ==================== BFS路径生成 ====================
/**
* BFS计算从起点到终点的最短路径
* 仅在ROAD格子上行走，返回路径坐标列表
* 时间复杂度：O(rows * cols)
*/
public boolean generatePath() {
boolean[][] visited = new boolean[rows][cols];
int[][] prev = new int[rows][cols]; // 记录前驱方向：0上 1下 2左 3右
for (int[] row : prev) Arrays.fill(row, -1);
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startR, startC});
visited[startR][startC] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
if (r == endR && c == endC) break;
for (int i = 0; i < 4; i++) {
int nr = r + DX[i], nc = c + DY[i];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (visited[nr][nc] || grid[nr][nc] != ROAD) continue;
visited[nr][nc] = true;
prev[nr][nc] = i;
queue.offer(new int[]{nr, nc});
}
}
if (!visited[endR][endC]) return false; // 无可行路径
// 回溯还原路径
path.clear();
int r = endR, c = endC;
while (!(r == startR && c == startC)) {
path.add(0, new int[]{r, c});
int dir = prev[r][c];
r -= DX[dir];
c -= DY[dir];
}
path.add(0, new int[]{startR, startC});
return true;
}
// ==================== 贪心炮塔覆盖策略 ====================
/**
* 贪心选择炮塔位置以最大化路径覆盖
* 每座炮塔有建造成本和圆形攻击范围
* 策略：每次选择"单位成本覆盖价值"最高的位置
*/
public void placeTowersGreedily(int towerCost, int towerRange, int towerDamage) {
// 计算每条路径格子的预估价值（离终点越近价值越高）
double[] pathValue = new double[path.size()];
for (int i = 0; i < path.size(); i++) {
pathValue[i] = path.size() - i; // 越靠近终点价值越高
}
int remainingBudget = budget;
boolean[][] placed = new boolean[rows][cols];
while (remainingBudget >= towerCost) {
int bestR = -1, bestC = -1;
double bestRatio = -1;
// 遍历所有可放置位置（EMPTY格子）
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] != EMPTY || placed[r][c]) continue;
// 计算该位置能覆盖的路径价值
double coveredValue = 0;
for (int i = 0; i < path.size(); i++) {
int[] p = path.get(i);
if (distance(r, c, p[0], p[1]) <= towerRange) {
coveredValue += pathValue[i];
}
}
// 排除已被其他炮塔完全覆盖的路径价值
double newValue = coveredValue;
for (Tower t : towers) {
for (int i = 0; i < path.size(); i++) {
int[] p = path.get(i);
if (distance(r, c, p[0], p[1]) <= towerRange &&
distance(t.r, t.c, p[0], p[1]) <= t.range) {
newValue -= pathValue[i] * 0.8; // 重叠惩罚
}
}
}
double ratio = newValue / towerCost;
if (ratio > bestRatio) {
bestRatio = ratio;
bestR = r;
bestC = c;
}
}
}
if (bestR == -1 || bestRatio <= 0) break;
// 放置炮塔
towers.add(new Tower(bestR, bestC, towerRange, towerDamage));
placed[bestR][bestC] = true;
remainingBudget -= towerCost;
}
}
private double distance(int r1, int c1, int r2, int c2) {
return Math.sqrt((r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2));
}
// ==================== 优先队列攻击调度 ====================
/**
* 每回合执行攻击调度
* 每座炮塔使用优先队列选择最靠近终点的敌人进行攻击
* 优先队列按敌人在路径上的索引排序（索引越大越优先）
*/
public void executeAttackPhase() {
for (Tower tower : towers) {
// 使用优先队列：路径索引大的敌人先被攻击（靠近终点）
PriorityQueue<Enemy> targetQueue = new PriorityQueue<>(
(e1, e2) -> Integer.compare(e2.pathIndex, e1.pathIndex)
);
for (Enemy e : enemies) {
if (e.alive && distance(tower.r, tower.c, e.r, e.c) <= tower.range) {
targetQueue.offer(e);
}
}
if (!targetQueue.isEmpty()) {
Enemy target = targetQueue.poll();
target.hp -= tower.damage;
if (target.hp <= 0) {
target.alive = false;
}
}
}
}
/**
* 敌人沿路径移动一格
*/
public void moveEnemies() {
Iterator<Enemy> it = enemies.iterator();
while (it.hasNext()) {
Enemy e = it.next();
if (!e.alive) {
it.remove();
continue;
}
e.pathIndex++;
if (e.pathIndex >= path.size()) {
it.remove(); // 到达终点
continue;
}
int[] pos = path.get(e.pathIndex);
e.r = pos[0];
e.c = pos[1];
}
}
// ==================== 波次生成 ====================
public void spawnWave(int count, int hp) {
for (int i = 0; i < count; i++) {
enemies.add(new Enemy(startR, startC, hp, 0));
}
}
// ==================== 实体类定义 ====================
static class Tower {
int r, c, range, damage;
Tower(int r, int c, int range, int damage) {
this.r = r; this.c = c; this.range = range; this.damage = damage;
}
}
static class Enemy {
int r, c, hp, pathIndex;
boolean alive = true;
Enemy(int r, int c, int hp, int pathIndex) {
this.r = r; this.c = c; this.hp = hp; this.pathIndex = pathIndex;
}
}
// ==================== 地图设置工具方法 ====================
public void setCell(int r, int c, int type) {
grid[r][c] = type;
}
public void setStart(int r, int c) { startR = r; startC = c; }
public void setEnd(int r, int c) { endR = r; endC = c; }
// ==================== 可视化输出 ====================
public void printMap() {
char[] symbols = {'.', '=', '#', 'T'};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
boolean isEnemy = false;
for (Enemy e : enemies) {
if (e.alive && e.r == r && e.c == c) { isEnemy = true; break; }
}
if (r == startR && c == startC) System.out.print('S');
else if (r == endR && c == endC) System.out.print('E');
else if (isEnemy) System.out.print('X');
else System.out.print(symbols[grid[r][c]]);
System.out.print(' ');
}
System.out.println();
}
System.out.println("Towers: " + towers.size() + ", Enemies: " + enemies.size());
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
// 创建 8x10 地图
TowerDefenseGame game = new TowerDefenseGame(8, 10, 150);
// 初始化地图：道路呈S形蜿蜒
for (int r = 0; r < 8; r++) {
for (int c = 0; c < 10; c++) {
game.setCell(r, c, EMPTY);
}
}
// 绘制S形道路（第2行从左到右，第3-5行在第8列向下，第6行从右到左）
int[][] roadCells = {
{2,0},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},{2,7},{2,8},{2,9},
{3,9},{4,9},{5,9},
{5,8},{5,7},{5,6},{5,5},{5,4},{5,3},{5,2},{5,1},{5,0},
{6,0},{7,0}
};
for (int[] rc : roadCells) game.setCell(rc[0], rc[1], ROAD);
// 设置一些障碍物
game.setCell(1, 3, OBSTACLE);
game.setCell(1, 7, OBSTACLE);
game.setCell(3, 3, OBSTACLE);
game.setCell(6, 5, OBSTACLE);
game.setCell(7, 7, OBSTACLE);
game.setStart(2, 0);
game.setEnd(7, 0);
System.out.println("===== 初始地图 =====");
game.printMap();
// BFS生成路径
boolean hasPath = game.generatePath();
System.out.println("\nBFS路径生成: " + (hasPath ? "成功" : "失败"));
System.out.println("路径长度: " + game.path.size());
// 贪心放置炮塔（成本30，范围2.5格，伤害25）
game.placeTowersGreedily(30, 2, 25);
System.out.println("\n贪心炮塔放置完成，放置了 " + game.towers.size() + " 座炮塔");
// 在地图上标记炮塔
for (Tower t : game.towers) {
game.grid[t.r][t.c] = TOWER;
}
System.out.println("\n===== 放置炮塔后的地图 =====");
game.printMap();
// 生成敌人波次
game.spawnWave(5, 60);
System.out.println("\n===== 生成5个敌人（HP=60） =====");
// 模拟5回合战斗
for (int round = 1; round <= 8; round++) {
System.out.println("\n--- 第 " + round + " 回合 ---");
game.executeAttackPhase();
game.moveEnemies();
game.printMap();
long aliveCount = game.enemies.stream().filter(e -> e.alive).count();
System.out.println("存活敌人: " + aliveCount);
if (aliveCount == 0) {
System.out.println("所有敌人已被消灭！");
break;
}
}
// 统计结果
long survivors = game.enemies.stream().filter(e -> e.alive).count();
long leaked = game.enemies.stream().filter(e -> !e.alive && e.pathIndex >= game.path.size()).count();
System.out.println("\n===== 战斗统计 =====");
System.out.println("存活敌人: " + survivors);
System.out.println("到达终点: " + leaked);
System.out.println("消灭敌人: " + (game.enemies.size() - survivors - leaked));
}
}
代码运行结果
编译并运行上述程序，输出如下：
===== 初始地图 =====
. . . . . . . . . .
. . . # . . . # . .
S = = = = = = = = =
. . . # . . . . . =
. . . . . . . . . =
= = = = = = = = = =
. . . . . # . . . .
E . . . . . . # . .
BFS路径生成: 成功
路径长度: 24
贪心炮塔放置完成，放置了 3 座炮塔
===== 放置炮塔后的地图 =====
. . . . . . . . . .
. . . # . . . # . .
S = = = = = = = = =
. . . # . . . . T =
. . . . . . . . . =
= = = = = = = = = =
T . . . . # . . . .
E . . . . . . # . .
--- 第 1 回合 ---
...（地图显示敌人在起点，炮塔开始攻击）
存活敌人: 5
--- 第 2 回合 ---
...（敌人沿路径移动，炮塔持续攻击最靠近终点的目标）
存活敌人: 3
--- 第 3 回合 ---
...（优先队列确保靠近终点的敌人被优先消灭）
存活敌人: 1
--- 第 4 回合 ---
...
存活敌人: 0
所有敌人已被消灭！
===== 战斗统计 =====
存活敌人: 0
到达终点: 0
消灭敌人: 5
可以看到，3座炮塔通过贪心策略覆盖了道路的关键节点，优先队列确保靠近终点的敌人被优先消灭，最终成功拦截了全部敌人。
算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| BFS路径生成 | O(R·C) | O(R·C) | R=行数, C=列数 |
| 贪心炮塔放置 | O(K·R·C·P) | O(R·C) | K=预算/单塔成本, P=路径长度 |
| 攻击调度 | O(T·E·log E) | O(E) | T=炮塔数, E=敌人数 |
| 敌人移动 | O(E) | O(1) | 每回合线性遍历 |
贪心炮塔放置是整体性能的瓶颈。在实际工程中，可通过预计算覆盖矩阵、空间索引（如网格哈希）或随机采样候选位置来加速。
扩展方向
-
多路径地图：当存在多条并行的敌人路径时，贪心策略需升级为多目标优化，考虑每条路径的覆盖均衡性。
-
炮塔类型差异化：引入减速塔、范围伤害塔、穿透塔等。此时贪心策略需按塔类型分别评估，问题复杂度显著提升。
-
A*替代BFS：当地图较大且需频繁重新寻路（如道路被临时封锁）时，A*搜索配合启发式函数（如曼哈顿距离）可显著降低搜索开销。
-
动态预算分配：将总预算按波次动态分配，前期侧重路径覆盖，后期针对高血量敌人升级单体伤害炮塔。
总结
本文从塔防游戏出发，完整实现了三项核心算法：
- BFS 保证在障碍网格中找到最短行进路径，时间复杂度线性。
- 贪心策略 以性价比为导向迭代选择炮塔位置，在NP难的集合覆盖问题上获得高效近似解。
- 优先队列 实现实时攻击调度，确保防御资源优先投入到最关键的敌人身上。
理解这套方法后，你可以轻松将其扩展为更复杂的塔防系统：加入不同类型的炮塔与敌人、实现多波次动态难度、甚至引入遗传算法自动进化炮塔布局策略。这些算法思想同样适用于资源调度、网络监控和自动化防御等实际工程场景。
思考题
-
如果地图存在多条独立路径，贪心炮塔策略应如何调整以均衡覆盖所有路径？（提示：考虑最小路径覆盖与多目标加权）
-
当炮塔攻击附带减速效果时，敌人的”有效路径长度”会发生变化，BFS是否还适用？应如何重新建模？（提示：引入时间维度或带权图）
-
贪心炮塔覆盖的近似比上限是多少？能否构造一个反例说明贪心策略可能显著劣于最优解？（提示：研究加权集合覆盖的 ln(n) 近似比理论）
