引言
《三国战纪》是街机厅中经久不衰的动作闯关游戏，玩家操控蜀汉名将过关斩将、攻城略地。若将游戏中的各个城池抽象为节点、关卡路径抽象为边，则整个游戏地图便构成一张带权有向图。如何在兵力有限的情况下规划最优攻城路线，以最小的代价统一版图？本文用Java实现一个三国战纪战略AI，通过图论建模势力分布，运用Dijkstra算法计算最短补给线，并结合贪心策略制定最优攻城顺序。
核心算法思路
势力图建模
将游戏世界建模为带权有向图 $G=(V, E)$：
– 节点 $V$：代表城池，每个节点具有守军数量、城防等级、资源产出等属性。
– 边 $E$：代表可通行的道路，边权表示行军距离或消耗粮草数。
– 势力归属：每个节点属于魏、蜀、吴或中立势力，相邻同势力节点之间可互相增援。
最短补给线（Dijkstra算法）
攻城需要持续的粮草补给，补给线长度直接影响作战持续性。使用Dijkstra算法从己方主城出发，计算到达每一座目标城池的最短路径（最小粮草消耗），作为攻城优先级的重要参考。
贪心最优攻城策略
定义每座城池的”攻城价值指数”：
$$
\text{Value} = \frac{\text{资源产出}}{\text{守军数量} \times \text{城防等级} \times \text{补给距离}}
$$
贪心策略每次选择Value最高的城池进行攻击，攻下后更新势力版图并重新计算。若相邻城池属于同一敌方势力，优先攻击连接该势力的”关键节点”（割点），切断其增援路线。
完整Java实现
import java.util.*;
/**
* 三国战纪战略AI —— 图论势力建模与贪心最优攻城路径
*/
public class ThreeKingdomsAI {
// 势力枚举
public enum Force { SHU, WEI, WU, NEUTRAL }
// 城池节点
public static class City {
int id;
String name;
Force force;
int defenders; // 守军数量
int defenseLevel; // 城防等级（1-10）
int resources; // 资源产出/回合
int x, y; // 坐标（用于距离计算）
public City(int id, String name, Force force, int defenders,
int defenseLevel, int resources, int x, int y) {
this.id = id;
this.name = name;
this.force = force;
this.defenders = defenders;
this.defenseLevel = defenseLevel;
this.resources = resources;
this.x = x;
this.y = y;
}
/** 计算攻城代价估算值 */
public int siegeCost() {
return defenders * defenseLevel;
}
}
// 道路边
public static class Road {
int from, to;
int distance; // 行军距离
public Road(int from, int to, int distance) {
this.from = from;
this.to = to;
this.distance = distance;
}
}
private final List<City> cities;
private final List<Road> roads;
private final int n;
private final int[][] adj; // 邻接矩阵
public ThreeKingdomsAI(List<City> cities, List<Road> roads) {
this.cities = cities;
this.roads = roads;
this.n = cities.size();
this.adj = new int[n][n];
for (int[] row : adj) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (Road r : roads) {
adj[r.from][r.to] = r.distance;
adj[r.to][r.from] = r.distance; // 无向图
}
for (int i = 0; i < n; i++) adj[i][i] = 0;
}
/**
* Dijkstra算法：计算从起点到所有城池的最短距离
*/
public int[] dijkstra(int start) {
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0];
if (visited[u]) continue;
visited[u] = true;
for (int v = 0; v < n; v++) {
if (adj[u][v] < Integer.MAX_VALUE / 2 && !visited[v]) {
int newDist = dist[u] + adj[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(new int[]{v, dist[v]});
}
}
}
}
return dist;
}
/**
* 计算每座敌方城池的攻城价值指数
*/
public double[] calculateValueIndex(int[] supplyDist) {
double[] value = new double[n];
for (City c : cities) {
if (c.force == Force.SHU) {
value[c.id] = -1; // 己方城池不攻击
continue;
}
int cost = c.siegeCost();
int dist = supplyDist[c.id];
if (dist >= Integer.MAX_VALUE / 2 || cost == 0) {
value[c.id] = 0;
} else {
value[c.id] = (double) c.resources / (cost * Math.max(dist, 1));
}
}
return value;
}
/**
* 贪心策略：制定最优攻城顺序
*/
public List<City> planConquest(int capitalId) {
List<City> order = new ArrayList<>();
Set<Integer> conquered = new HashSet<>();
conquered.add(capitalId);
while (conquered.size() < n) {
int[] supplyDist = dijkstra(capitalId);
double[] value = calculateValueIndex(supplyDist);
// 只考虑与已征服区域相邻的敌方城池
int bestId = -1;
double bestValue = -1;
for (City c : cities) {
if (conquered.contains(c.id) || c.force == Force.SHU) continue;
// 检查是否与已征服区域相邻
boolean adjacent = false;
for (Road r : roads) {
if ((r.from == c.id && conquered.contains(r.to)) ||
(r.to == c.id && conquered.contains(r.from))) {
adjacent = true;
break;
}
}
if (!adjacent) continue;
if (value[c.id] > bestValue) {
bestValue = value[c.id];
bestId = c.id;
}
}
if (bestId == -1) break; // 无可达目标
City target = cities.get(bestId);
order.add(target);
conquered.add(bestId);
cities.get(bestId).force = Force.SHU; // 攻下后归属我方
}
return order;
}
/**
* 查找敌方势力的关键节点（割点）—— 使用Tarjan算法简化版
*/
public List<City> findKeyNodes(Force enemyForce) {
List<City> keyNodes = new ArrayList<>();
Set<Integer> enemyCities = new HashSet<>();
for (City c : cities) {
if (c.force == enemyForce) enemyCities.add(c.id);
}
// 对每个敌方节点，检查移除后是否导致其他敌方节点不再连通
for (int candidate : enemyCities) {
boolean isCut = false;
Set<Integer> reachable = bfsReachable(enemyCities, candidate);
if (reachable.size() < enemyCities.size() - 1) {
isCut = true;
}
if (isCut) {
keyNodes.add(cities.get(candidate));
}
}
return keyNodes;
}
private Set<Integer> bfsReachable(Set<Integer> nodes, int exclude) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
for (int start : nodes) {
if (start != exclude) {
q.offer(start);
visited.add(start);
break;
}
}
while (!q.isEmpty()) {
int u = q.poll();
for (Road r : roads) {
int v = -1;
if (r.from == u) v = r.to;
else if (r.to == u) v = r.from;
if (v != -1 && nodes.contains(v) && v != exclude && !visited.contains(v)) {
visited.add(v);
q.offer(v);
}
}
}
return visited;
}
public static void main(String[] args) {
// 构造示例地图：10座城池
List<City> cities = Arrays.asList(
new City(0, "成都", Force.SHU, 100, 8, 50, 0, 0),
new City(1, "汉中", Force.WEI, 60, 5, 30, 3, 4),
new City(2, "荆州", Force.WU, 70, 6, 40, 8, 2),
new City(3, "襄阳", Force.WEI, 55, 5, 25, 6, 5),
new City(4, "江陵", Force.WU, 50, 4, 20, 9, 3),
new City(5, "长安", Force.WEI, 90, 9, 45, 2, 8),
new City(6, "洛阳", Force.WEI, 80, 8, 40, 5, 9),
new City(7, "建业", Force.WU, 75, 7, 35, 12, 1),
new City(8, "合肥", Force.WEI, 45, 4, 20, 10, 6),
new City(9, "南郡", Force.NEUTRAL, 30, 3, 15, 7, 4)
);
List<Road> roads = Arrays.asList(
new Road(0, 1, 5), new Road(0, 9, 7),
new Road(1, 3, 4), new Road(1, 5, 6),
new Road(2, 4, 3), new Road(2, 9, 2),
new Road(3, 5, 4), new Road(3, 6, 5),
new Road(4, 7, 6), new Road(4, 9, 3),
new Road(5, 6, 3), new Road(6, 8, 5),
new Road(7, 8, 4), new Road(8, 9, 6)
);
ThreeKingdomsAI ai = new ThreeKingdomsAI(cities, roads);
System.out.println("=== Dijkstra最短补给线（从成都出发）===");
int[] dist = ai.dijkstra(0);
for (City c : cities) {
System.out.printf("到 %s: 距离=%d%n", c.name,
dist[c.id] >= Integer.MAX_VALUE / 2 ? -1 : dist[c.id]);
}
System.out.println("\n=== 贪心最优攻城顺序 ===");
List<City> order = ai.planConquest(0);
for (int i = 0; i < order.size(); i++) {
City c = order.get(i);
System.out.printf("第%d步: 攻占 %s (守军%d, 城防%d, 资源%d)%n",
i + 1, c.name, c.defenders, c.defenseLevel, c.resources);
}
System.out.println("\n=== 魏国关键节点（割点）===");
List<City> weiKeys = ai.findKeyNodes(Force.WEI);
for (City c : weiKeys) {
System.out.println("关键节点: " + c.name);
}
}
}
复杂度分析
- Dijkstra时间复杂度：$O(V^2 \log V)$ 或 $O(E \log V)$（使用优先队列优化），$V$ 为城池数，$E$ 为道路数。
- 贪心攻城策略时间复杂度：$O(V^2 \cdot (E \log V))$，每轮攻下一城后重新计算Dijkstra。
- 割点检测时间复杂度：$O(V \cdot (V + E))$，对每个节点执行一次BFS连通性检测。
- 空间复杂度：$O(V^2)$，邻接矩阵存储图结构。
扩展方向
- 最小生成树优化补给网：使用Kruskal或Prim算法构建连接所有已征服城池的最小生成树，最小化整体补给线建设成本。
- 博弈论多方对抗：引入魏、吴AI对手，使用 minimax 或蒙特卡洛树搜索进行多方博弈决策。
- 动态事件响应：模拟随机事件（如敌方援军、粮草短缺），使用A*搜索实时调整攻城计划。
总结
本文以《三国战纪》为背景，将古典战略问题抽象为图论模型，通过Dijkstra最短路径与贪心策略的结合，构建了一套完整的攻城略地决策系统。核心思想在于：最优战略不是盲目进攻最强或最弱的城池，而是综合评估资源收益、军事代价与后勤距离三者的平衡。这一框架可自然迁移到物流网络优化、设施选址、网络安全渗透路径规划等现实问题中。
