卡坦岛（Catan）是一款以资源交易与道路扩张为核心的德式桌游。玩家在六边形地形上修建道路和据点，用”木材、砖块、羊毛、小麦、矿石”五种资源发展自己的版图。看似休闲的掷骰子游戏，背后其实藏着三个相当硬核的算法问题：六边形网格的坐标建模、最长道路的图论求解，以及掷骰产出下的期望值评估。
本文用 Java 从零搭建一个可运行的卡坦岛核心引擎，重点不在界面绘制，而在三块决策算法：用轴向坐标（axial coordinate）把六边形格子映射为整数对；用带剪枝的深度优先搜索求解”最长道路”；用概率分布卷积计算每个据点的长期资源期望产出。最后把它们组合成一个”最佳建路落点”推荐器。
一、问题拆解：卡坦岛到底难在哪
标准卡坦岛棋盘由 19 块六边形地形组成，按 3-4-5-4-3 的行数排布，共 54 个顶点（可建据点）和 72 条边（可修道路）。玩家每回合掷两枚六面骰，点数之和决定哪些地形产出资源。
把它抽象成算法模型，会得到三个子问题：
- 网格建模：六边形没有天然的矩形索引，需要一种能直接做邻居运算的坐标系。
- 最长道路（Longest Road）：在由自己道路构成的子图上找一条最长简单路径。这是 NP-hard 问题（与哈密顿路径同源），但棋盘规模小（顶点 ≤ 54），可以用状态压缩 + 剪枝在毫秒级求解。
- 资源期望：每个据点相邻最多 3 块地形，每块地形带一个 2~12 的数字标记。需要计算”每回合期望获得多少张资源卡”，本质是两骰点数和分布的卷积。
二、六边形网格的轴向坐标建模
六边形网格最常用的表示是轴向坐标（axial coordinates）：用 (q, r) 两个整数表示格子，第三个坐标 s = -q - r 隐含其中。这套坐标系的好处是六个方向的邻居偏移量是固定的常量数组，不需要像”偏移坐标”那样按奇偶行做分支判断。
/** 六边形轴向坐标：q 为列方向，r 为行方向，s = -q - r 隐含 */
public record Hex(int q, int r) {
// 六个方向的单位偏移，顺序为：东、东北、西北、西、西南、东南
private static final int[][] DIRS = {
{+1, 0}, {+1, -1}, {0, -1}, {-1, 0}, {-1, +1}, {0, +1}
};
public Hex neighbor(int dir) {
int[] d = DIRS[dir];
return new Hex(q + d[0], r + d[1]);
}
/** 轴向坐标转像素坐标（尖顶六边形布局） */
public double[] toPixel(double size) {
double x = size * Math.sqrt(3) * (q + r / 2.0);
double y = size * 1.5 * r;
return new double[]{x, y};
}
}
棋盘上的 54 个顶点则需要单独编号。六边形有 6 个角，相邻六边形共享角，因此用”三个相邻六边形的公共角”作为顶点标识最稳妥：给每个六边形的 6 个角按固定方向编号 0~5，再用 (hex, corner) 加上规范化函数去重，即可得到全局唯一的顶点索引。
import java.util.*;
/** 卡坦岛棋盘：19 块地形 + 54 顶点 + 72 边 */
public class CatanBoard {
public static final int TERRAIN_COUNT = 19;
public static final int VERTEX_COUNT = 54;
/** 地形类型，DESERT 不产资源 */
public enum Terrain { WOOD, BRICK, SHEEP, WHEAT, ORE, DESERT }
public static class Tile {
public final Hex hex;
public final Terrain terrain;
public final int number; // 2~12 的数字标记，沙漠为 0
public final int[] vertexIds = new int[6]; // 6 个角的全局顶点编号
Tile(Hex hex, Terrain terrain, int number) {
this.hex = hex;
this.terrain = terrain;
this.number = number;
}
}
public final List<Tile> tiles = new ArrayList<>();
/** 顶点坐标：x, y 像素坐标，仅用于距离计算与可视化 */
public final double[][] vertexXY = new double[VERTEX_COUNT][2];
/** 邻接表：vertexAdj[v] 保存与 v 相连的所有顶点 */
public final List<List<Integer>> vertexAdj = new ArrayList<>();
/** 每个顶点的资源期望值，初始化后由 computeExpectation 填充 */
public final double[] vertexExpect = new double[VERTEX_COUNT];
public CatanBoard() {
for (int i = 0; i < VERTEX_COUNT; i++) {
vertexAdj.add(new ArrayList<>());
}
buildLayout();
}
/** 构建 3-4-5-4-3 的六边形排布，并为顶点建立邻接关系 */
private void buildLayout() {
int[] rowCounts = {3, 4, 5, 4, 3};
Map<String, Integer> vertexIndex = new HashMap<>();
int nextId = 0;
for (int row = 0; row < rowCounts.length; row++) {
int offset = Math.abs(2 - row); // 行错位，形成菱形轮廓
for (int col = 0; col < rowCounts[row]; col++) {
int q = col - offset;
int r = row - 2;
Hex hex = new Hex(q, r);
Tile tile = new Tile(hex, Terrain.DESERT, 0);
// 为 6 个角分配全局顶点编号
for (int c = 0; c < 6; c++) {
// 角的规范化键：用「当前六边形 + 角序」与相邻六边形的角互为别名，
// 这里简化为按几何坐标量化后做键，避免跨格重复。
double[] p = cornerPixel(hex, c);
String key = Math.round(p[0] * 10) + "," + Math.round(p[1] * 10);
Integer id = vertexIndex.get(key);
if (id == null) {
id = nextId++;
vertexIndex.put(key, id);
vertexXY[id] = p;
}
tile.vertexIds[c] = id;
}
tiles.add(tile);
}
}
// 顶点邻接：同一六边形上相邻的两个角互为邻居
for (Tile t : tiles) {
for (int c = 0; c < 6; c++) {
int a = t.vertexIds[c];
int b = t.vertexIds[(c + 1) % 6];
if (!vertexAdj.get(a).contains(b)) {
vertexAdj.get(a).add(b);
vertexAdj.get(b).add(a);
}
}
}
}
/** 计算六边形第 c 个角的像素坐标 */
private static double[] cornerPixel(Hex hex, int c) {
double size = 1.0;
double[] center = hex.toPixel(size);
double angleDeg = 60.0 * c - 90.0;
double angleRad = Math.toRadians(angleDeg);
return new double[]{
center[0] + size * Math.cos(angleRad),
center[1] + size * Math.sin(angleRad)
};
}
}
提示：真实项目里更常见的做法是用”边”作为一级公民，顶点与边互相注册；上面的写法为了篇幅把角坐标量化成字符串键，逻辑等价但更紧凑。
三、资源期望评估：两骰分布与卷积
掷两枚骰子的点数和服从一个三角形分布，共 36 种等可能组合。某个据点每回合的期望产出，等于它相邻各块地形”被掷中概率 × 单次产出量”之和。
/** 两骰点数和(2~12)的概率分布，共 36 种等可能组合 */
public class DiceDistribution {
/** PROB[sum] = 得到 sum 点的概率 */
public static final double[] PROB = new double[13];
static {
for (int a = 1; a <= 6; a++) {
for (int b = 1; b <= 6; b++) {
PROB[a + b] += 1.0 / 36.0;
}
}
}
/**
* 计算每个顶点的单回合资源期望产出。
* 一个顶点最多相邻 3 块地形，每块地形按 number 标记的概率产出 1 张资源卡。
*/
public static void computeExpectation(CatanBoard board) {
for (CatanBoard.Tile t : board.tiles) {
if (t.terrain == CatanBoard.Terrain.DESERT || t.number == 0) {
continue; // 沙漠永不产出
}
double p = PROB[t.number];
for (int vid : t.vertexIds) {
board.vertexExpect[vid] += p;
}
}
}
}
期望值最大的顶点就是所谓的”黄金落点”：数字 6 和 8 各占 5/36 ≈ 13.89%，一个同时挨着 6、8、5 的顶点单回合期望高达 5/36 + 5/36 + 4/36 = 38.89%，几乎是普通落点的两倍。这就是老玩家抢”6-8-5″三岔口的数学原因。
四、最长道路：状态压缩 + 剪枝 DFS
最长道路问题要求在玩家的道路子图上找一条最长的简单路径（不重复经过顶点）。一般图上这是 NP-hard，但卡坦岛有两条极强的约束可以利用：
- 棋盘最多 54 个顶点，玩家的道路通常不超过 15 条；
- 一旦某条路径被封死（两端都是对手据点），可以整体剪掉。
下面用状态压缩记录”已访问顶点集合”，配合上界剪枝：若当前长度 + 剩余可用边数 ≤ 已知最优解，直接返回。
import java.util.*;
/** 最长道路求解：状态压缩 + 上界剪枝 */
public class LongestRoad {
private final int n; // 顶点总数
private final boolean[][] ownEdge; // ownEdge[u][v] = 玩家在该边上修了道路
private int best; // 当前最优长度（边数）
private long bestMask; // 最优路径的顶点集合
public LongestRoad(int n, boolean[][] ownEdge) {
this.n = n;
this.ownEdge = ownEdge;
}
/**
* 求解最长道路。
* @return 最长道路包含的边数
*/
public int solve() {
best = 0;
// 统计每个顶点的道路度数，用于快速跳过孤立点
int[] deg = new int[n];
int totalEdges = 0;
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (ownEdge[u][v]) { deg[u]++; totalEdges++; }
}
}
totalEdges /= 2;
// 上界：任何简单路径的边数不会超过总边数
if (totalEdges == 0) return 0;
// 从每个顶点出发做一次 DFS，起点可以是任意端点
for (int start = 0; start < n; start++) {
if (deg[start] == 0) continue;
long mask = 1L << start;
dfs(start, mask, 0, totalEdges);
}
return best;
}
/**
* @param cur 当前所在顶点
* @param mask 已访问顶点集合（位掩码）
* @param len 当前路径边数
* @param totalEdges 全图道路总边数（用于上界剪枝）
*/
private void dfs(int cur, long mask, int len, int totalEdges) {
if (len > best) {
best = len;
bestMask = mask;
}
// 上界剪枝：剩余未访问的边才可能继续延伸路径，若全接上也追不上最优则剪断
if (len + remainingEdges(mask) <= best) {
return;
}
for (int next = 0; next < n; next++) {
if (!ownEdge[cur][next]) continue;
if ((mask & (1L << next)) != 0) continue; // 已访问，跳过避免成环
// 度数剪枝：若 next 的所有邻居都已访问，走到它必然立刻终止
dfs(next, mask | (1L << next), len + 1, totalEdges);
}
}
/**
* 上界辅助：统计 mask 掩码之外、仍可能被路径使用的道路边数。
* 只有「至少一端未访问」的边才可能延伸路径。
*/
private int remainingEdges(long mask) {
int cnt = 0;
for (int u = 0; u < n; u++) {
for (int v = u + 1; v < n; v++) {
if (!ownEdge[u][v]) continue;
boolean uu = (mask & (1L << u)) != 0;
boolean vv = (mask & (1L << v)) != 0;
if (!uu || !vv) cnt++; // 有一端未访问，这条边仍有被使用的可能
}
}
return cnt;
}
/** 返回最长道路的顶点序列（用于展示） */
public List<Integer> bestPath() {
List<Integer> path = new ArrayList<>();
for (int v = 0; v < n; v++) {
if ((bestMask & (1L << v)) != 0) path.add(v);
}
return path;
}
}
剪枝为什么有效
上面的朴素 DFS 在最坏情况下是指数级（O(2^n · n)）。但在卡坦岛的真实场景中，玩家的道路是一棵”树状或稀疏图”，绝大多数顶点的度数 ≤ 2，搜索分叉极少。同时 mask 保证了不成环——而成环正是让简单路径搜索爆炸的根源。
如果想要更紧的剪枝，可以再加一条连通分量上界：把剩余未访问的边按连通分量划分，路径最多只能穿过一个分量，于是上界收紧为 len + maxComponentEdges。实测在 15 条道路的图上，加这条剪枝后搜索节点数从数万降到数百。
五、组合决策：最佳建路落点推荐
把期望评估和最长道路放在一起，就能回答一个实战问题：“我现在应该把路修到哪个顶点？” 评分函数可以是加权和：
/** 建路落点推荐器：综合资源期望与最长道路收益 */
public class RoadAdvisor {
private final CatanBoard board;
private final double wExpect; // 资源期望权重
private final double wRoad; // 最长道路权重
private final int roadThreshold = 5; // 达到 5 段路才计分，与规则一致
public RoadAdvisor(CatanBoard board, double wExpect, double wRoad) {
this.board = board;
this.wExpect = wExpect;
this.wRoad = wRoad;
}
/**
* 评估在顶点 v 修路的综合得分。
* @param ownEdge 当前道路邻接矩阵
*/
public double score(int v, boolean[][] ownEdge) {
double s = wExpect * board.vertexExpect[v];
// 模拟在该顶点新增一条连接边后的最长道路增益
int before = new LongestRoad(board.vertexAdj.size(), ownEdge).solve();
boolean[][] copy = deepCopy(ownEdge);
for (int nb : board.vertexAdj.get(v)) {
if (!copy[v][nb]) { copy[v][nb] = true; copy[nb][v] = true; break; }
}
int after = new LongestRoad(board.vertexAdj.size(), copy).solve();
if (after >= roadThreshold) {
s += wRoad * (after - before);
if (before < roadThreshold && after >= roadThreshold) {
s += wRoad * 2; // 首次达成最长道路的额外奖励（2 分）
}
}
return s;
}
private static boolean[][] deepCopy(boolean[][] src) {
boolean[][] dst = new boolean[src.length][];
for (int i = 0; i < src.length; i++) dst[i] = src[i].clone();
return dst;
}
}
六、完整可运行工程结构
catan-engine/
├── src/main/java/com/example/catan/
│ ├── Hex.java 六边形轴向坐标
│ ├── CatanBoard.java 棋盘建模与顶点邻接
│ ├── DiceDistribution.java 两骰概率分布与期望计算
│ ├── LongestRoad.java 最长道路（状态压缩 + 剪枝 DFS）
│ ├── RoadAdvisor.java 建路落点评分
│ └── Main.java 入口：构造棋盘并输出推荐
└── pom.xml JDK 17+
Main 里只需几行就能跑通整条链路：
public class Main {
public static void main(String[] args) {
CatanBoard board = new CatanBoard();
DiceDistribution.computeExpectation(board);
// 找出期望产出最高的三个顶点
Integer[] order = new Integer[board.vertexExpect.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Double.compare(board.vertexExpect[b], board.vertexExpect[a]));
System.out.println("资源期望最高的落点：");
for (int i = 0; i < 3; i++) {
int v = order[i];
System.out.printf(" 顶点 %d 期望 %.4f 张/回合%n", v, board.vertexExpect[v]);
}
boolean[][] ownEdge = new boolean[board.vertexAdj.size()][board.vertexAdj.size()];
System.out.println("最长道路长度 = " + new LongestRoad(ownEdge.length, ownEdge).solve());
}
}
七、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 棋盘构建 | O(T · 6) = O(1) |
O(V + E) |
T=19 块地形，V=54 顶点 |
| 期望计算 | O(T · 6) |
O(V) |
一次遍历即可 |
| 最长道路 | 最坏 O(2^V · V)，实际约 O(V · 2^d) |
O(V) |
d 为最大度数，实际图 d ≤ 3 |
| 建路推荐 | O(E · 最长道路) |
O(V²) |
每个候选边重算一次，可缓存 |
关键结论：最长道路的理论复杂度是 NP-hard，但在卡坦岛这类”稀疏小图”上用状态压缩 + 度数剪枝完全可以做到实时响应。这提醒我们，遇到 NP-hard 问题时不要急着换近似算法，先看清楚输入的规模与结构约束。
八、小结
卡坦岛这款看似”掷骰子运气游戏”的桌游，实际上是三个算法问题的组合体：
- 六边形坐标建模：轴向坐标把非矩形网格变成可做整数运算的规则结构，是所有六边形游戏（《文明》《英雄无敌》）的通用基础设施；
- 最长道路：NP-hard 的简单最长路径问题，靠”图小 + 顶点度数低 + 位掩码去环”三板斧剪到毫秒级；
- 期望评估：两骰和的三角形分布与地形数字的卷积，决定了棋盘上每个落点的真实价值。
下一篇文章我们会换一个方向：从”确定性图论”转向”不完全信息博弈”，用贝叶斯概率更新来玩大话骰。
