部落冲突（Clash of Clans）是 Supercell 开发的经典策略手游，玩家需要建设自己的村庄基地，布置防御建筑抵御其他玩家的进攻。基地布局的优劣直接决定了防守成功率，而布局设计本质上是一个多目标优化问题：需要在有限的空间内平衡防御覆盖、资源保护、陷阱触发路径以及建筑之间的协同效应。本文将用 Java 实现部落冲突基地布局的核心评估算法，重点讲解防御覆盖范围计算、攻击路径模拟以及基于贪心策略的最优建筑放置。
一、基地模型与数据表示
1.1 棋盘与建筑类型
部落冲突的基地可抽象为一个 40×40 的离散网格（实际游戏更大，但核心算法相同）。建筑分为以下几类：
– 防御建筑：加农炮、箭塔、法师塔、防空火箭等，具有攻击范围和伤害输出
– 资源建筑：金矿、圣水收集器、储金罐等，需要被保护
– 城墙：阻挡地面部队移动，可被攻破
– 陷阱：隐形弹簧、炸弹、搜空地雷等，一次性触发
– 其他：大本营、兵营、法术工厂等
1.2 建筑属性
每种防御建筑有：
– range：攻击半径（格数）
– damage：每秒伤害（DPS）
– targetType：目标类型（地面/空中/全部）
– attackSpeed：攻击间隔
1.3 攻击者模型
进攻部队简化为点单位，具有：
– speed：移动速度（格/秒）
– hp：生命值
– damage：对建筑伤害
– targetPreference：优先攻击目标（防御/资源/最近）
– movementType：移动类型（地面/空中）
二、核心算法
2.1 防御覆盖计算
使用网格化方法计算每个格子被哪些防御建筑覆盖，以及综合 DPS：
1. 对每个防御建筑，以自身为中心、range 为半径画圆
2. 圆内所有可攻击的格子增加该防御的 DPS
3. 最终得到全图的”防御热力图”
2.2 攻击路径模拟（A* 寻路）
进攻部队从基地边缘出发，按以下规则移动：
1. 优先攻击优先目标（如防御建筑）
2. 若优先目标在射程外，使用 A* 算法寻找最短路径
3. 城墙会显著增加通过成本（需多次攻击才能破坏）
4. 路径选择考虑各格子的防御 DPS（高 DPS 区域增加路径成本，体现”绕路”行为）
2.3 基地布局评估函数
综合评估指标：
– 防御覆盖率：资源建筑被防御覆盖的比例
– DPS 均衡度：各区域的防御火力不应有显著短板
– 路径长度：攻击者到达核心建筑需要走的路径越长越好
– 城墙效率：城墙的拦截效率（成功迫使攻击者绕路的次数）
– 陷阱触发率：攻击者触发陷阱的概率
2.4 贪心优化策略
通过贪心算法迭代优化基地布局：
1. 随机生成初始布局
2. 对每座建筑，尝试与空位或其他建筑交换位置
3. 若交换后评估分数提升，则保留新布局
4. 迭代若干轮后输出最优布局
三、Java 实现
import java.util.*;
/**
* 部落冲突基地布局评估与优化
* 核心算法：防御覆盖计算、A*路径模拟、贪心布局优化
*/
public class ClashOfClansBase {
private static final int GRID_SIZE = 40;
private static final int EMPTY = 0;
// 建筑类型定义
private static final int CANNON = 1; // 加农炮
private static final int ARCHER_TOWER = 2; // 箭塔
private static final int WIZARD_TOWER = 3; // 法师塔
private static final int WALL = 4; // 城墙
private static final int GOLD_STORAGE = 5; // 储金罐
private static final int TOWN_HALL = 6; // 大本营
private static final int TRAP = 7; // 陷阱
// 建筑属性：{类型, 射程, DPS, 目标类型(0=地面,1=空中,2=全部)}
private static final int[][] BUILDING_STATS = {
{}, // 0: empty
{CANNON, 7, 60, 0}, // 加农炮
{ARCHER_TOWER, 10, 50, 2}, // 箭塔
{WIZARD_TOWER, 7, 40, 2}, // 法师塔
{WALL, 0, 0, 0}, // 城墙
{GOLD_STORAGE, 0, 0, 0}, // 储金罐
{TOWN_HALL, 0, 0, 0}, // 大本营
{TRAP, 2, 200, 2} // 陷阱（触发范围2，伤害200）
};
private int[][] grid; // 基地网格
private double[][] dpsMap; // 防御热力图（对地DPS）
private List<Building> buildings;
public ClashOfClansBase() {
this.grid = new int[GRID_SIZE][GRID_SIZE];
this.dpsMap = new double[GRID_SIZE][GRID_SIZE];
this.buildings = new ArrayList<>();
}
/**
* 建筑类
*/
static class Building {
int type, x, y, range, dps, targetType;
Building(int type, int x, int y) {
this.type = type;
this.x = x;
this.y = y;
this.range = BUILDING_STATS[type][1];
this.dps = BUILDING_STATS[type][2];
this.targetType = BUILDING_STATS[type][3];
}
}
/**
* 在基地中添加建筑
*/
public void addBuilding(int type, int x, int y) {
if (x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE) return;
if (grid[x][y] != EMPTY) return;
grid[x][y] = type;
buildings.add(new Building(type, x, y));
}
/**
* 计算防御热力图：每个格子受到的对地DPS总和
*/
public void computeDpsMap() {
// 清空
for (int i = 0; i < GRID_SIZE; i++) {
Arrays.fill(dpsMap[i], 0);
}
for (Building b : buildings) {
if (b.dps <= 0) continue; // 非防御建筑跳过
if (b.targetType == 1) continue; // 仅对空，暂不计算
// 在射程范围内增加DPS
int rangeSq = b.range * b.range;
for (int dx = -b.range; dx <= b.range; dx++) {
for (int dy = -b.range; dy <= b.range; dy++) {
int nx = b.x + dx;
int ny = b.y + dy;
if (nx >= 0 && nx < GRID_SIZE && ny >= 0 && ny < GRID_SIZE) {
if (dx * dx + dy * dy <= rangeSq) {
dpsMap[nx][ny] += b.dps;
}
}
}
}
}
}
/**
* 计算两点之间的欧几里得距离
*/
private double distance(int x1, int y1, int x2, int y2) {
return Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
/**
* A* 寻路算法：计算攻击者从入口到目标的最短路径
* @param startX, startY 起始位置（基地边缘）
* @param targetX, targetY 目标位置
* @param isGround 是否为地面部队
* @return 路径上的格子列表，null表示无法到达
*/
public List<int[]> findPath(int startX, int startY, int targetX, int targetY, boolean isGround) {
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));
boolean[][] closed = new boolean[GRID_SIZE][GRID_SIZE];
Node[][] nodeMap = new Node[GRID_SIZE][GRID_SIZE];
Node start = new Node(startX, startY, null, 0,
distance(startX, startY, targetX, targetY));
open.add(start);
nodeMap[startX][startY] = start;
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};
while (!open.isEmpty()) {
Node current = open.poll();
if (current.x == targetX && current.y == targetY) {
return reconstructPath(current);
}
closed[current.x][current.y] = true;
for (int[] d : dirs) {
int nx = current.x + d[0];
int ny = current.y + d[1];
if (nx < 0 || nx >= GRID_SIZE || ny < 0 || ny >= GRID_SIZE) continue;
if (closed[nx][ny]) continue;
// 计算移动成本
double moveCost = getMoveCost(nx, ny, isGround);
if (moveCost == Double.MAX_VALUE) continue; // 不可通过
double g = current.g + moveCost;
double h = distance(nx, ny, targetX, targetY);
if (nodeMap[nx][ny] == null || g < nodeMap[nx][ny].g) {
Node neighbor = new Node(nx, ny, current, g, h);
nodeMap[nx][ny] = neighbor;
open.add(neighbor);
}
}
}
return null; // 无法到达
}
/**
* 获取某格子的移动成本
*/
private double getMoveCost(int x, int y, boolean isGround) {
int cell = grid[x][y];
// 空地：基础成本 + DPS惩罚（部队不愿意穿过高火力区）
if (cell == EMPTY) {
return 1.0 + dpsMap[x][y] / 100.0;
}
// 城墙：地面部队需要破坏，成本极高
if (cell == WALL && isGround) {
return 50.0;
}
// 其他建筑：可以攻击破坏后通过
if (cell != WALL) {
return 5.0 + dpsMap[x][y] / 50.0;
}
return Double.MAX_VALUE; // 不可通过
}
/**
* 重构路径
*/
private List<int[]> reconstructPath(Node end) {
List<int[]> path = new ArrayList<>();
Node current = end;
while (current != null) {
path.add(0, new int[]{current.x, current.y});
current = current.parent;
}
return path;
}
/**
* A* 节点类
*/
static class Node {
int x, y;
Node parent;
double g, h, f;
Node(int x, int y, Node parent, double g, double h) {
this.x = x; this.y = y;
this.parent = parent;
this.g = g; this.h = h;
this.f = g + h;
}
}
/**
* 基地布局综合评估
*/
public double evaluateBase() {
computeDpsMap();
double score = 0;
// 1. 资源建筑防御覆盖率
List<Building> resources = new ArrayList<>();
List<Building> defenses = new ArrayList<>();
Building townHall = null;
for (Building b : buildings) {
if (b.type == GOLD_STORAGE) resources.add(b);
else if (b.type == TOWN_HALL) townHall = b;
else if (b.dps > 0) defenses.add(b);
}
// 资源覆盖评分
for (Building res : resources) {
score += dpsMap[res.x][res.y] * 2;
}
// 大本营覆盖评分（权重最高）
if (townHall != null) {
score += dpsMap[townHall.x][townHall.y] * 5;
}
// 2. DPS 均衡度（标准差越小越好）
double avgDps = 0;
int count = 0;
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
if (grid[i][j] == EMPTY) {
avgDps += dpsMap[i][j];
count++;
}
}
}
avgDps /= Math.max(count, 1);
double variance = 0;
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
if (grid[i][j] == EMPTY) {
variance += (dpsMap[i][j] - avgDps) * (dpsMap[i][j] - avgDps);
}
}
}
score -= Math.sqrt(variance / Math.max(count, 1)) * 0.5;
// 3. 从边缘到核心建筑的路径长度（越长越好）
if (townHall != null) {
int edgeX = 0, edgeY = GRID_SIZE / 2;
List<int[]> path = findPath(edgeX, edgeY, townHall.x, townHall.y, true);
if (path != null) {
score += path.size() * 10;
}
}
// 4. 防御建筑之间的协同（距离过近浪费，过远脱节）
for (int i = 0; i < defenses.size(); i++) {
for (int j = i + 1; j < defenses.size(); j++) {
Building d1 = defenses.get(i);
Building d2 = defenses.get(j);
double dist = distance(d1.x, d1.y, d2.x, d2.y);
if (dist < 3) score -= 20; // 太近，浪费
else if (dist > 15) score -= 5; // 太远，协同差
else score += 10; // 适中，有协同
}
}
return score;
}
/**
* 贪心优化：随机交换建筑位置，保留更优布局
*/
public void optimizeLayout(int iterations) {
double bestScore = evaluateBase();
Random rand = new Random();
for (int iter = 0; iter < iterations; iter++) {
// 随机选择两个位置交换
int x1 = rand.nextInt(GRID_SIZE);
int y1 = rand.nextInt(GRID_SIZE);
int x2 = rand.nextInt(GRID_SIZE);
int y2 = rand.nextInt(GRID_SIZE);
if (grid[x1][y1] == grid[x2][y2]) continue;
// 交换
int temp = grid[x1][y1];
grid[x1][y1] = grid[x2][y2];
grid[x2][y2] = temp;
// 更新建筑位置
for (Building b : buildings) {
if (b.x == x1 && b.y == y1) { b.x = x2; b.y = y2; }
else if (b.x == x2 && b.y == y2) { b.x = x1; b.y = y1; }
}
double newScore = evaluateBase();
if (newScore > bestScore) {
bestScore = newScore;
} else {
// 恢复
temp = grid[x1][y1];
grid[x1][y1] = grid[x2][y2];
grid[x2][y2] = temp;
for (Building b : buildings) {
if (b.x == x1 && b.y == y1) { b.x = x2; b.y = y2; }
else if (b.x == x2 && b.y == y2) { b.x = x1; b.y = y1; }
}
}
}
}
/**
* 打印基地热力图
*/
public void printHeatMap() {
computeDpsMap();
System.out.println("Defense Heat Map (DPS):");
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
if (grid[i][j] != EMPTY) {
String[] symbols = {".", "C", "A", "W", "#", "G", "T", "X"};
System.out.print(symbols[grid[i][j]] + " ");
} else {
int intensity = (int)(dpsMap[i][j] / 20);
System.out.print(intensity + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
ClashOfClansBase base = new ClashOfClansBase();
// 构建一个初始基地
// 大本营放中心
base.addBuilding(TOWN_HALL, 20, 20);
// 资源建筑围绕大本营
base.addBuilding(GOLD_STORAGE, 18, 18);
base.addBuilding(GOLD_STORAGE, 22, 18);
base.addBuilding(GOLD_STORAGE, 18, 22);
base.addBuilding(GOLD_STORAGE, 22, 22);
// 防御建筑
base.addBuilding(CANNON, 15, 20);
base.addBuilding(CANNON, 25, 20);
base.addBuilding(ARCHER_TOWER, 20, 15);
base.addBuilding(ARCHER_TOWER, 20, 25);
base.addBuilding(WIZARD_TOWER, 16, 16);
base.addBuilding(WIZARD_TOWER, 24, 24);
// 城墙
for (int i = 14; i <= 26; i++) {
base.addBuilding(WALL, i, 14);
base.addBuilding(WALL, i, 26);
base.addBuilding(WALL, 14, i);
base.addBuilding(WALL, 26, i);
}
System.out.println("Initial score: " + base.evaluateBase());
// 优化布局
base.optimizeLayout(1000);
System.out.println("Optimized score: " + base.evaluateBase());
base.printHeatMap();
// 模拟攻击路径
List<int[]> path = base.findPath(0, 20, 20, 20, true);
if (path != null) {
System.out.println("Path to Town Hall length: " + path.size());
}
}
}
四、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 防御热力图 | O(N × R²) | O(G²) | N 为防御建筑数，R 为平均射程 |
| A* 寻路 | O(G² log G) | O(G²) | G 为网格边长（40） |
| 布局评估 | O(G² + N²) | O(G²) | 含 DPS 均衡度和协同计算 |
| 贪心优化 | O(I × (G² + N²)) | O(G²) | I 为迭代次数 |
在 40×40 的网格上，单次评估可在毫秒级完成，1000 轮贪心优化约需 1-3 秒。
五、总结
部落冲突的基地布局问题是一个典型的多目标空间优化问题。本文通过防御热力图量化火力覆盖，借助 A* 算法模拟攻击者的最优进攻路径，并设计了涵盖覆盖度、均衡性、路径长度和协同效应的综合评估函数。贪心优化策略虽然无法保证全局最优，但能在合理时间内显著改进布局质量。读者可以在此基础上引入遗传算法或模拟退火来探索更广阔的设计空间，或者针对特定进攻流派（如 Hog Rider、Dragon 等）进行专项防御优化。
