游戏背景与问题建模
泡泡龙（Puzzle Bobble/Bust-a-Move）是一款经典消除游戏：屏幕顶部排列着彩色泡泡，玩家从底部发射泡泡，三个或以上同色相连即可消除。泡泡碰到墙壁会反弹，物理轨迹受发射角度影响。
本文用Java实现泡泡龙的核心算法系统，包括：发射路径计算、碰撞检测、连通分量检测（BFS）、以及最优发射角度搜索。
核心算法设计
1. 六边形网格表示
泡泡排列采用六边形密铺（Hexagonal Grid），每个泡泡有最多6个邻居：
– 奇偶行偏移：奇数行向右偏移半个泡泡直径
– 邻居方向向量：(±1,0), (0,±1), 以及对角线方向（取决于行奇偶性）
2. 发射轨迹与碰撞检测
泡泡沿直线飞行，碰到左右墙壁时水平速度反向（反射）。轨迹计算需检测：
– 墙壁碰撞：x坐标超出边界
– 泡泡碰撞：与已有泡泡距离小于直径
– 顶部边界：到达最高行
3. 连通消除（BFS）
发射泡泡落定后，从该位置进行BFS，找到所有同色连通泡泡。若连通数 $\ge 3$，全部消除。
4. 悬挂检测（Flood Fill）
消除后，从顶部边界进行Flood Fill标记所有与顶部相连的泡泡。未标记的泡泡因失去支撑而掉落。
5. 最优发射角度搜索
AI需要选择最佳发射角度，评估函数考虑：
– 直接消除数量
– 引发连锁反应（悬挂掉落）的潜力
– 避免造成死局（无法消除的颜色堆积）
Java实现
package puzzlebobble;
import java.util.*;
/**
* 泡泡龙核心算法系统
* 核心算法：六边形网格 + BFS连通消除 + 角度反射路径规划
*/
public class PuzzleBobbleSolver {
// 游戏常量
private static final int GRID_COLS = 8; // 每行泡泡数
private static final int GRID_ROWS = 12; // 总行数
private static final int COLORS = 5; // 颜色种类数
private static final double BUBBLE_RADIUS = 1.0;
private static final double WALL_LEFT = -0.5;
private static final double WALL_RIGHT = GRID_COLS - 0.5;
// 六边形邻居方向（偶数行和奇数行不同）
private static final int[][][] DIRECTIONS = {
// 偶数行: 左上, 右上, 左, 右, 左下, 右下
{{-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, -1}, {1, 0}},
// 奇数行
{{-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, 0}, {1, 1}}
};
private int[][] grid; // 0=空, 1..COLORS=泡泡颜色
public PuzzleBobbleSolver() {
this.grid = new int[GRID_ROWS][GRID_COLS];
}
/**
* 将泡泡放置到网格（发射后的落定）
* 使用最近邻算法找到最接近的合法空位
*/
public int[] snapToGrid(double x, double y) {
int row = (int) Math.round(y / (BUBBLE_RADIUS * Math.sqrt(3)));
int col;
if (row % 2 == 0) {
col = (int) Math.round(x);
} else {
col = (int) Math.round(x - 0.5);
}
row = Math.max(0, Math.min(row, GRID_ROWS - 1));
col = Math.max(0, Math.min(col, GRID_COLS - 1));
return new int[]{row, col};
}
/**
* 计算发射轨迹（考虑墙壁反射）
* @param startX 发射起点X
* @param startY 发射起点Y
* @param angle 发射角度（弧度，0=水平向右，π/2=垂直向上）
* @param color 发射泡泡颜色
* @return 落点坐标 [row, col]，若无法落定返回null
*/
public int[] calculateTrajectory(double startX, double startY, double angle, int color) {
double dx = Math.cos(angle);
double dy = -Math.sin(angle); // Y轴向下为正，所以向上为负
double speed = 0.1; // 每步移动距离
double x = startX, y = startY;
while (y >= 0) {
x += dx * speed;
y += dy * speed;
// 墙壁反射
if (x < WALL_LEFT) {
x = WALL_LEFT + (WALL_LEFT - x);
dx = -dx;
} else if (x > WALL_RIGHT) {
x = WALL_RIGHT - (x - WALL_RIGHT);
dx = -dx;
}
// 检测与顶部碰撞
if (y <= 0) {
int[] pos = snapToGrid(x, 0);
if (grid[pos[0]][pos[1]] == 0) return pos;
return null;
}
// 检测与已有泡泡碰撞
int[] nearest = findNearestBubble(x, y);
if (nearest != null) {
double br = BUBBLE_RADIUS;
double dist = getBubbleDistance(x, y, nearest[0], nearest[1]);
if (dist < 2 * br) {
// 找到碰撞点附近的空位
return findEmptyNeighbor(nearest[0], nearest[1]);
}
}
}
return null;
}
/**
* 计算两个泡泡中心之间的距离
*/
private double getBubbleDistance(double x1, double y1, int row2, int col2) {
double x2 = col2 + (row2 % 2 == 0 ? 0 : 0.5);
double y2 = row2 * BUBBLE_RADIUS * Math.sqrt(3);
return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
/**
* 找到离给定坐标最近的已有泡泡
*/
private int[] findNearestBubble(double x, double y) {
int[] best = null;
double bestDist = Double.MAX_VALUE;
for (int r = 0; r < GRID_ROWS; r++) {
for (int c = 0; c < GRID_COLS; c++) {
if (grid[r][c] == 0) continue;
double dist = getBubbleDistance(x, y, r, c);
if (dist < bestDist) {
bestDist = dist;
best = new int[]{r, c};
}
}
}
return best;
}
/**
* 找到指定泡泡周围的空位（用于落定新泡泡）
*/
private int[] findEmptyNeighbor(int row, int col) {
int dirIdx = row % 2;
for (int[] d : DIRECTIONS[dirIdx]) {
int nr = row + d[0], nc = col + d[1];
if (inBounds(nr, nc) && grid[nr][nc] == 0) {
return new int[]{nr, nc};
}
}
return null;
}
/**
* BFS查找同色连通分量
* @param startRow 起始行
* @param startCol 起始列
* @return 连通的所有位置列表
*/
public List<int[]> findConnectedComponent(int startRow, int startCol) {
int color = grid[startRow][startCol];
if (color == 0) return new ArrayList<>();
List<int[]> component = new ArrayList<>();
boolean[][] visited = new boolean[GRID_ROWS][GRID_COLS];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startRow, startCol});
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
component.add(cur);
int dirIdx = cur[0] % 2;
for (int[] d : DIRECTIONS[dirIdx]) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (inBounds(nr, nc) && !visited[nr][nc] && grid[nr][nc] == color) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
return component;
}
/**
* 消除连通分量（若大小>=3）并处理悬挂掉落
* @return 消除的泡泡总数（含连锁掉落）
*/
public int eliminate(int row, int col) {
List<int[]> component = findConnectedComponent(row, col);
if (component.size() < 3) return 0;
// 标记消除
for (int[] pos : component) {
grid[pos[0]][pos[1]] = 0;
}
int eliminated = component.size();
// 悬挂检测：从顶部进行Flood Fill
boolean[][] connected = new boolean[GRID_ROWS][GRID_COLS];
Queue<int[]> queue = new LinkedList<>();
// 初始化：顶部所有有泡泡的位置
for (int c = 0; c < GRID_COLS; c++) {
if (grid[0][c] != 0) {
connected[0][c] = true;
queue.offer(new int[]{0, c});
}
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int dirIdx = cur[0] % 2;
for (int[] d : DIRECTIONS[dirIdx]) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (inBounds(nr, nc) && !connected[nr][nc] && grid[nr][nc] != 0) {
connected[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
// 消除所有未与顶部连接的泡泡
for (int r = 0; r < GRID_ROWS; r++) {
for (int c = 0; c < GRID_COLS; c++) {
if (grid[r][c] != 0 && !connected[r][c]) {
grid[r][c] = 0;
eliminated++;
}
}
}
return eliminated;
}
/**
* AI评估函数：评估在某个角度发射的得分
* @param color 发射泡泡颜色
* @param angle 发射角度
* @return 评估得分（消除数量 + 连锁奖励 - 死局惩罚）
*/
public double evaluateShot(int color, double angle) {
// 模拟发射
int[] landing = calculateTrajectory(GRID_COLS / 2.0, GRID_ROWS * 2, angle, color);
if (landing == null) return -1000; // 无效发射
// 临时放置
int oldValue = grid[landing[0]][landing[1]];
grid[landing[0]][landing[1]] = color;
// 计算消除
int eliminated = eliminate(landing[0], landing[1]);
// 恢复网格（用于评估多个角度）
restoreGrid();
// 评分
double score = eliminated * 10;
// 如果消除了很多，额外奖励
if (eliminated >= 6) score += 50;
if (eliminated >= 10) score += 100;
return score;
}
private int[][] gridBackup;
private void backupGrid() {
gridBackup = new int[GRID_ROWS][GRID_COLS];
for (int r = 0; r < GRID_ROWS; r++) {
System.arraycopy(grid[r], 0, gridBackup[r], 0, GRID_COLS);
}
}
private void restoreGrid() {
if (gridBackup != null) {
for (int r = 0; r < GRID_ROWS; r++) {
System.arraycopy(gridBackup[r], 0, grid[r], 0, GRID_COLS);
}
}
}
/**
* AI搜索最佳发射角度
* @param color 发射泡泡颜色
* @return 最佳角度（弧度）
*/
public double findBestAngle(int color) {
backupGrid();
double bestAngle = Math.PI / 2; // 默认垂直向上
double bestScore = -Double.MAX_VALUE;
// 在有效范围内搜索角度（约20度到160度）
for (double angle = 0.35; angle < 2.79; angle += 0.017) { // 步进约1度
double score = evaluateShot(color, angle);
if (score > bestScore) {
bestScore = score;
bestAngle = angle;
}
}
restoreGrid();
return bestAngle;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < GRID_ROWS && c >= 0 && c < GRID_COLS;
}
/**
* 随机初始化网格
*/
public void randomInit(Random rand, int fillRows) {
for (int r = 0; r < fillRows; r++) {
for (int c = 0; c < GRID_COLS; c++) {
grid[r][c] = rand.nextInt(COLORS) + 1;
}
}
}
/**
* 打印网格状态
*/
public void printGrid() {
for (int r = 0; r < GRID_ROWS; r++) {
if (r % 2 == 1) System.out.print(" ");
for (int c = 0; c < GRID_COLS; c++) {
System.out.print(grid[r][c] == 0 ? ". " : grid[r][c] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
PuzzleBobbleSolver game = new PuzzleBobbleSolver();
Random rand = new Random(42);
// 初始化随机网格（前5行）
game.randomInit(rand, 5);
System.out.println("初始网格:");
game.printGrid();
// AI搜索最佳发射角度
int shootColor = rand.nextInt(COLORS) + 1;
System.out.println("\n发射泡泡颜色: " + shootColor);
double bestAngle = game.findBestAngle(shootColor);
System.out.printf("最佳发射角度: %.2f 度%n", Math.toDegrees(bestAngle));
// 执行发射
int[] landing = game.calculateTrajectory(GRID_COLS / 2.0, GRID_ROWS * 2, bestAngle, shootColor);
if (landing != null) {
System.out.println("落点位置: [" + landing[0] + ", " + landing[1] + "]");
game.grid[landing[0]][landing[1]] = shootColor;
int eliminated = game.eliminate(landing[0], landing[1]);
System.out.println("消除泡泡数量: " + eliminated);
System.out.println("\n发射后网格:");
game.printGrid();
}
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 轨迹计算 | $O(L)$，$L$ 为路径长度 | $O(1)$ |
| BFS连通分量 | $O(R \cdot C)$ | $O(R \cdot C)$ |
| 悬挂检测（Flood Fill） | $O(R \cdot C)$ | $O(R \cdot C)$ |
| 最佳角度搜索 | $O(A \cdot (L + R \cdot C))$，$A$ 为角度采样数 | $O(R \cdot C)$ |
扩展思考
- 预测对手/下轮颜色：结合颜色频率统计，优先消除高频颜色。
- 多步规划：使用Beam Search预测未来几步的最佳策略组合。
- 物理增强：引入真实碰撞物理（弹性碰撞、旋转等）。
总结
本文将泡泡龙游戏抽象为六边形网格上的连通图问题，使用Java实现了轨迹计算、BFS连通消除、悬挂检测和贪心角度搜索。核心算法展示了图论在游戏AI中的典型应用，是路径规划与连通性分析的综合案例。
