十滴水（又称 Flood It 或水滴扩散）是一款极简却极具策略深度的益智小游戏。玩家点击一个格子，该格子的水滴会向上下左右四个方向扩散，若相邻格子水滴数达到上限则连锁爆裂。本文将用 Java 实现完整的十滴水游戏 AI，核心讲解泛洪填充算法计算水滴扩散范围、贪心策略决策最优点击位置，以及连通块染色优化技巧。
一、游戏规则与状态建模
十滴水的核心规则可抽象如下：
- 棋盘为 $N \times N$ 的方格，每个格子有 0-4 滴水
- 点击某格子时，该格子水滴数 +1
- 若某格子水滴数超过 4，则向四邻域各扩散 1 滴，自身归零，形成连锁反应
- 目标通常是让棋盘全部归零，或使某个目标区域最大化清零
/**
* 十滴水游戏状态
*/
public class FloodGame {
public static final int SIZE = 6; // 棋盘大小
public static final int MAX_DROP = 4; // 爆裂上限（四邻域格子）
private int[][] board;
private int steps; // 已用步数
public FloodGame() {
board = new int[SIZE][SIZE];
steps = 0;
}
/** 深拷贝构造函数，用于搜索 */
public FloodGame(FloodGame other) {
this.board = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++)
System.arraycopy(other.board[i], 0, this.board[i], 0, SIZE);
this.steps = other.steps;
}
/** 随机初始化棋盘，每个格子 0-3 滴水 */
public void randomInit() {
java.util.Random rand = new java.util.Random();
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
board[i][j] = rand.nextInt(MAX_DROP);
}
/** 获取格子水滴数 */
public int get(int r, int c) {
return board[r][c];
}
/** 设置格子水滴数 */
public void set(int r, int c, int v) {
board[r][c] = v;
}
public int getSteps() { return steps; }
}
二、泛洪填充：连锁反应模拟
点击一个格子后，连锁反应的模拟本质上是一个BFS 泛洪填充过程。我们使用队列处理所有待爆裂的格子，直到系统达到稳态。
/**
* 四方向偏移量：上、下、左、右
*/
public class Directions {
public static final int[][] DIR = {{-1,0},{1,0},{0,-1},{0,1}};
}
public class FloodSimulator {
/**
* 在指定位置点击，模拟连锁反应，返回最终状态
* @param game 当前游戏状态
* @param r 点击行
* @param c 点击列
* @return 新的游戏状态（深拷贝修改）
*/
public static FloodGame click(FloodGame game, int r, int c) {
FloodGame next = new FloodGame(game);
next.set(r, c, next.get(r, c) + 1);
// BFS 队列存储待爆裂的格子
java.util.ArrayDeque<int[]> queue = new java.util.ArrayDeque<>();
boolean[][] inQueue = new boolean[FloodGame.SIZE][FloodGame.SIZE];
// 初始检查点击位置是否爆裂
if (next.get(r, c) > FloodGame.MAX_DROP) {
queue.add(new int[]{r, c});
inQueue[r][c] = true;
}
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int cr = cell[0], cc = cell[1];
int drops = next.get(cr, cc);
if (drops <= FloodGame.MAX_DROP) continue; // 已被其他连锁降低
int overflow = drops; // 实际爆裂时全部释放
next.set(cr, cc, 0); // 自身归零
// 向四邻域扩散
for (int[] d : Directions.DIR) {
int nr = cr + d[0], nc = cc + d[1];
if (nr < 0 || nr >= FloodGame.SIZE || nc < 0 || nc >= FloodGame.SIZE)
continue;
next.set(nr, nc, next.get(nr, nc) + 1);
// 若邻域达到爆裂条件且未入队，加入队列
if (next.get(nr, nc) > FloodGame.MAX_DROP && !inQueue[nr][nc]) {
queue.add(new int[]{nr, nc});
inQueue[nr][nc] = true;
}
}
}
return next;
}
}
三、贪心策略：单步最优决策
对于大型棋盘，完整的状态空间搜索（BFS/DFS）会遭遇组合爆炸。我们采用贪心策略：在当前状态下，评估每个可点击位置的”收益”，选择收益最大的动作。
收益函数设计需综合考虑以下因素：
- 清零格数：连锁反应后棋盘上有多少格子归零
- 中心化程度：爆裂是否发生在棋盘中心（中心爆裂波及范围更大）
- 后续潜力：是否存在即将爆裂的”临界”格子（值为 4）
public class GreedyStrategy {
/**
* 评估点击 (r,c) 的收益得分
* @param before 点击前的状态
* @param after 点击后的状态
* @param r 点击行
* @param c 点击列
* @return 收益得分（越高越好）
*/
public static double evaluate(FloodGame before, FloodGame after, int r, int c) {
double score = 0;
int size = FloodGame.SIZE;
// 1. 清零格子奖励
int cleared = 0;
int beforeSum = 0, afterSum = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (before.get(i,j) > 0 && after.get(i,j) == 0) cleared++;
beforeSum += before.get(i,j);
afterSum += after.get(i,j);
}
}
score += cleared * 10.0;
// 2. 总水滴数减少奖励
score += (beforeSum - afterSum) * 2.0;
// 3. 中心化奖励：中心区域连锁收益更高
double centerDist = Math.abs(r - size/2.0) + Math.abs(c - size/2.0);
score += Math.max(0, (size - centerDist)) * 1.5;
// 4. 制造临界格子（值为4）的惩罚——避免给对手创造机会
int criticalAfter = 0;
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
if (after.get(i,j) == FloodGame.MAX_DROP) criticalAfter++;
score -= criticalAfter * 3.0;
// 5. 边缘点击惩罚（边缘格子扩散范围受限）
boolean isEdge = (r == 0 || r == size-1 || c == 0 || c == size-1);
if (isEdge) score -= 2.0;
return score;
}
/**
* 贪心选择最优点击位置
* @param game 当前状态
* @return [row, col] 最优位置，若全部归零则返回 null
*/
public static int[] chooseBestMove(FloodGame game) {
int size = FloodGame.SIZE;
double bestScore = Double.NEGATIVE_INFINITY;
int[] bestMove = null;
for (int r = 0; r < size; r++) {
for (int c = 0; c < size; c++) {
// 跳过已清零的格子（通常不可点击，或点击无意义）
if (game.get(r, c) == 0) continue;
FloodGame after = FloodSimulator.click(game, r, c);
double score = evaluate(game, after, r, c);
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{r, c};
}
}
}
return bestMove;
}
}
四、连通块染色优化
高级策略需要识别棋盘上的连通块——由相同水滴数或相邻关系构成的区域。通过连通块分析，可以预判一次点击能波及的最大范围。
/**
* 连通块分析工具
*/
public class ConnectedComponents {
/**
* 标记所有连通块，返回每个格子所属连通块编号
* 这里以"格子是否非零"作为连通条件（四连通）
*/
public static int[][] labelComponents(FloodGame game) {
int size = FloodGame.SIZE;
int[][] labels = new int[size][size];
for (int i = 0; i < size; i++)
java.util.Arrays.fill(labels[i], -1);
int label = 0;
for (int r = 0; r < size; r++) {
for (int c = 0; c < size; c++) {
if (game.get(r, c) > 0 && labels[r][c] == -1) {
// BFS 标记整个连通块
java.util.ArrayDeque<int[]> q = new java.util.ArrayDeque<>();
q.add(new int[]{r, c});
labels[r][c] = label;
int count = 0;
while (!q.isEmpty()) {
int[] cell = q.poll();
count++;
int cr = cell[0], cc = cell[1];
for (int[] d : Directions.DIR) {
int nr = cr + d[0], nc = cc + d[1];
if (nr >= 0 && nr < size && nc >= 0 && nc < size
&& game.get(nr, nc) > 0 && labels[nr][nc] == -1) {
labels[nr][nc] = label;
q.add(new int[]{nr, nc});
}
}
}
label++;
}
}
}
return labels;
}
/**
* 计算连通块大小分布
*/
public static java.util.Map<Integer, Integer> componentSizes(int[][] labels) {
java.util.Map<Integer, Integer> sizes = new java.util.HashMap<>();
for (int[] row : labels) {
for (int l : row) {
if (l >= 0) sizes.merge(l, 1, Integer::sum);
}
}
return sizes;
}
}
五、完整游戏引擎与自动求解
public class FloodGameEngine {
private FloodGame game;
public FloodGameEngine() {
game = new FloodGame();
game.randomInit();
}
public void printBoard() {
System.out.println(" 0 1 2 3 4 5");
for (int r = 0; r < FloodGame.SIZE; r++) {
System.out.print(r + " ");
for (int c = 0; c < FloodGame.SIZE; c++) {
System.out.print(game.get(r, c) + " ");
}
System.out.println();
}
System.out.println();
}
/** 检查是否全部清零 */
public boolean isCleared() {
for (int r = 0; r < FloodGame.SIZE; r++)
for (int c = 0; c < FloodGame.SIZE; c++)
if (game.get(r, c) > 0) return false;
return true;
}
/** 执行一步贪心点击 */
public boolean step() {
if (isCleared()) return false;
int[] move = GreedyStrategy.chooseBestMove(game);
if (move == null) return false;
System.out.printf("Step: click (%d, %d)%n", move[0], move[1]);
game = FloodSimulator.click(game, move[0], move[1]);
printBoard();
return true;
}
/** 自动求解直到清零或无法继续 */
public void autoSolve() {
System.out.println("Initial board:");
printBoard();
int maxSteps = 50;
for (int i = 0; i < maxSteps && step(); i++) {
if (isCleared()) {
System.out.println("Cleared in " + (i+1) + " steps!");
return;
}
}
System.out.println("Could not clear completely.");
}
public static void main(String[] args) {
FloodGameEngine engine = new FloodGameEngine();
engine.autoSolve();
}
}
六、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 单次点击模拟 | O(N²) | O(N²) | BFS 最坏遍历全棋盘 |
| 贪心单步决策 | O(N⁴) | O(N²) | 需评估 N² 个位置，每个模拟 O(N²) |
| 连通块标记 | O(N²) | O(N²) | 一次 BFS/DFS 遍历 |
| 完整贪心求解 | O(K·N⁴) | O(N²) | K 为实际步数 |
对于 $6 \times 6$ 的棋盘，贪心策略的每步决策约需 $6^4 = 1296$ 次基本操作，在毫秒级完成。若棋盘扩大到 $10 \times 10$，则每步约 $10^4 = 10000$ 次操作，仍可接受。
七、策略升级方向
- 蒙特卡洛树搜索（MCTS）：每步模拟数千次随机 rollout，用 UCB 公式平衡探索与利用，显著提升胜率。
- 值函数近似：用神经网络评估盘面状态，替代手工设计的收益函数。
- 最小步数求解：将问题建模为最短路径问题，用 A* 搜索配合启发式函数（如剩余水滴总数）寻找最优解。
十滴水的魅力在于极简规则下蕴含的复杂动态。泛洪填充模拟连锁反应、贪心策略快速决策、连通块分析预判局势——这套算法组合拳不仅适用于水滴游戏，也是处理级联故障、病毒传播模拟等现实问题的经典范式。
