泡泡射击（Bubble Shooter）是经典的消除类游戏，玩家从屏幕底部发射彩色泡泡，当三个或以上同色泡泡相连时即可消除。本文用Java实现完整的泡泡射击游戏，重点讲解发射角度与抛物线轨迹计算、六边形网格坐标映射以及BFS连通块检测与悬空掉落算法。
一、游戏机制与算法目标
泡泡射击的核心规则：
– 屏幕顶部排列着六边形密铺的彩色泡泡矩阵
– 玩家调整发射角度，泡泡沿直线轨迹飞行
– 泡泡碰撞到墙壁会反弹，碰撞到已有泡泡则粘附
– 当同色泡泡形成三个以上的连通块时，整组消除
– 消除后若某些泡泡与顶部失去连接，则全部掉落得分
需要解决的三个核心算法问题：
1. 如何将鼠标位置转换为发射角度，并计算泡泡的飞行轨迹
2. 如何在六边形密铺网格中快速定位泡泡的落点坐标
3. 如何用BFS检测同色连通块，并判断哪些泡泡因失去顶部连接而掉落
二、核心算法原理
2.1 六边形网格坐标系
泡泡采用奇偶行偏移的六边形密铺布局。设行号为 row，列号为 col：
– 偶数行：泡泡中心 x = col * DIAMETER + RADIUS
– 奇数行：泡泡中心 x = col * DIAMETER + RADIUS + OFFSET
– 所有行：泡泡中心 y = row * ROW_HEIGHT + RADIUS
其中 ROW_HEIGHT = RADIUS * sqrt(3)，确保六边形紧密排列。
2.2 发射轨迹与落点判定
发射角度 $\theta$ 决定速度向量：
$$
v_x = v \cdot \cos(\theta), \quad v_y = -v \cdot \sin(\theta)
$$
每帧更新位置，检测与边界或已有泡泡的碰撞。碰撞检测转化为：新泡泡中心与任一已有泡泡中心的距离是否小于直径。
2.3 BFS连通块检测
当泡泡粘附后，从该位置出发进行BFS：
1. 队列初始化为该泡泡的坐标
2. 每次出队，检查六邻域（上、下、左、右、左上、右下等）中同色且未访问的泡泡
3. 若连通块大小 $\geq 3$，标记为待消除
2.4 悬空掉落检测
消除连通块后，需要判断哪些泡泡与顶部失去连接：
1. 从第一行的每个泡泡出发进行BFS/DFS，标记所有可达泡泡
2. 未被标记的泡泡即为”悬空”泡泡，应掉落消除
3. 时间复杂度 $O(N)$，$N$ 为网格中泡泡总数
三、完整Java实现
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.List;
/**
* 泡泡射击游戏：实现角度轨迹计算、六边形网格与BFS连通消除
*/
public class BubbleShooter extends JPanel implements ActionListener, MouseMotionListener, MouseListener {
private static final int WIDTH = 600;
private static final int HEIGHT = 700;
private static final int RADIUS = 20;
private static final int DIAMETER = RADIUS * 2;
private static final double ROW_HEIGHT = RADIUS * Math.sqrt(3);
private static final int GRID_COLS = 15;
private static final int GRID_ROWS = 20;
private static final double BUBBLE_SPEED = 12.0;
// 颜色池
private static final Color[] COLORS = {
new Color(255, 80, 80), // 红
new Color(80, 200, 80), // 绿
new Color(80, 80, 255), // 蓝
new Color(255, 255, 80), // 黄
new Color(255, 80, 255), // 紫
};
// 六边形网格：-1表示空，0~4表示颜色索引
private int[][] grid = new int[GRID_ROWS][GRID_COLS];
// 发射中的泡泡
private double flyingX, flyingY;
private double flyingVx, flyingVy;
private int flyingColor = -1;
private boolean isFlying = false;
// 待发射的泡泡（显示在发射器位置）
private int nextColor;
// 鼠标位置（用于计算发射角度）
private int mouseX = WIDTH / 2;
private int mouseY = 0;
private int score = 0;
private int bubblesCleared = 0;
private boolean gameOver = false;
private Random random = new Random();
private Timer timer;
// 发射器位置
private static final int SHOOTER_X = WIDTH / 2;
private static final int SHOOTER_Y = HEIGHT - 50;
public BubbleShooter() {
setPreferredSize(new Dimension(WIDTH, HEIGHT));
setBackground(new Color(30, 30, 50));
addMouseMotionListener(this);
addMouseListener(this);
// 初始化顶部5行泡泡
initGrid();
nextColor = random.nextInt(COLORS.length);
timer = new Timer(16, this);
timer.start();
}
private void initGrid() {
for (int r = 0; r < 5; r++) {
int maxCol = (r % 2 == 0) ? GRID_COLS : GRID_COLS - 1;
for (int c = 0; c < maxCol; c++) {
grid[r][c] = random.nextInt(COLORS.length);
}
}
}
/**
* 将网格行列转换为屏幕像素坐标
*/
private double[] gridToPixel(int row, int col) {
double x = col * DIAMETER + RADIUS;
if (row % 2 == 1) {
x += RADIUS;
}
double y = row * ROW_HEIGHT + RADIUS;
return new double[]{x, y};
}
/**
* 将屏幕像素坐标转换为最近的网格行列
*/
private int[] pixelToGrid(double x, double y) {
int row = (int)Math.round((y - RADIUS) / ROW_HEIGHT);
row = Math.max(0, Math.min(GRID_ROWS - 1, row));
double offsetX = (row % 2 == 1) ? RADIUS : 0;
int col = (int)Math.round((x - RADIUS - offsetX) / DIAMETER);
col = Math.max(0, Math.min(GRID_COLS - 1, col));
return new int[]{row, col};
}
/**
* 获取指定网格位置的六邻域坐标
*/
private List<int[]> getNeighbors(int row, int col) {
List<int[]> neighbors = new ArrayList<>();
// 六边形网格的6个方向偏移，奇偶行不同
int[][] evenDirs = {{-1, 0}, {-1, -1}, {0, -1}, {0, 1}, {-1, 1}, {1, 0}};
int[][] oddDirs = {{-1, 0}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}};
int[][] dirs = (row % 2 == 0) ? evenDirs : oddDirs;
for (int[] d : dirs) {
int nr = row + d[0];
int nc = col + d[1];
if (nr >= 0 && nr < GRID_ROWS && nc >= 0 && nc < GRID_COLS) {
neighbors.add(new int[]{nr, nc});
}
}
return neighbors;
}
/**
* BFS查找同色连通块
*/
private List<int[]> findConnectedGroup(int startRow, int startCol) {
List<int[]> group = new ArrayList<>();
boolean[][] visited = new boolean[GRID_ROWS][GRID_COLS];
Queue<int[]> queue = new LinkedList<>();
int color = grid[startRow][startCol];
if (color < 0) return group;
queue.add(new int[]{startRow, startCol});
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
group.add(curr);
for (int[] nb : getNeighbors(curr[0], curr[1])) {
if (!visited[nb[0]][nb[1]] && grid[nb[0]][nb[1]] == color) {
visited[nb[0]][nb[1]] = true;
queue.add(nb);
}
}
}
return group;
}
/**
* 检测并移除悬空的泡泡（与顶部无连接）
*/
private List<int[]> findFloatingBubbles() {
boolean[][] connected = new boolean[GRID_ROWS][GRID_COLS];
Queue<int[]> queue = new LinkedList<>();
// 从第一行的所有泡泡开始BFS
for (int c = 0; c < GRID_COLS; c++) {
if (grid[0][c] >= 0) {
connected[0][c] = true;
queue.add(new int[]{0, c});
}
}
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] nb : getNeighbors(curr[0], curr[1])) {
if (!connected[nb[0]][nb[1]] && grid[nb[0]][nb[1]] >= 0) {
connected[nb[0]][nb[1]] = true;
queue.add(nb);
}
}
}
// 收集所有未被标记的泡泡（悬空）
List<int[]> floating = new ArrayList<>();
for (int r = 0; r < GRID_ROWS; r++) {
for (int c = 0; c < GRID_COLS; c++) {
if (grid[r][c] >= 0 && !connected[r][c]) {
floating.add(new int[]{r, c});
}
}
}
return floating;
}
/**
* 核心游戏循环：更新飞行泡泡并处理碰撞
*/
@Override
public void actionPerformed(ActionEvent e) {
if (gameOver || !isFlying) {
repaint();
return;
}
// 更新飞行位置
flyingX += flyingVx;
flyingY += flyingVy;
// 墙壁反弹
if (flyingX - RADIUS < 0) {
flyingX = RADIUS;
flyingVx = -flyingVx;
} else if (flyingX + RADIUS > WIDTH) {
flyingX = WIDTH - RADIUS;
flyingVx = -flyingVx;
}
// 顶部碰撞检测
if (flyingY - RADIUS < 0) {
attachBubble();
return;
}
// 与已有泡泡的碰撞检测
for (int r = 0; r < GRID_ROWS; r++) {
for (int c = 0; c < GRID_COLS; c++) {
if (grid[r][c] < 0) continue;
double[] pos = gridToPixel(r, c);
double dist = Math.hypot(flyingX - pos[0], flyingY - pos[1]);
if (dist < DIAMETER - 2) { // 允许2像素容差
attachBubble();
return;
}
}
}
repaint();
}
/**
* 将飞行泡泡附着到网格，并触发消除逻辑
*/
private void attachBubble() {
isFlying = false;
int[] gc = pixelToGrid(flyingX, flyingY);
// 找到最近的空位
int bestRow = gc[0], bestCol = gc[1];
double bestDist = Double.MAX_VALUE;
for (int r = Math.max(0, gc[0] - 1); r <= Math.min(GRID_ROWS - 1, gc[0] + 1); r++) {
int maxC = (r % 2 == 0) ? GRID_COLS - 1 : GRID_COLS - 2;
for (int c = Math.max(0, gc[1] - 1); c <= Math.min(maxC, gc[1] + 1); c++) {
if (grid[r][c] < 0) {
double[] pos = gridToPixel(r, c);
double d = Math.hypot(flyingX - pos[0], flyingY - pos[1]);
if (d < bestDist) {
bestDist = d;
bestRow = r;
bestCol = c;
}
}
}
}
// 若位置被占，强制放入计算位置
if (grid[bestRow][bestCol] >= 0) {
bestRow = gc[0];
bestCol = gc[1];
}
if (bestRow >= 0 && bestRow < GRID_ROWS && bestCol >= 0 && bestCol < GRID_COLS) {
grid[bestRow][bestCol] = flyingColor;
// 1. BFS检测同色连通消除
List<int[]> group = findConnectedGroup(bestRow, bestCol);
if (group.size() >= 3) {
for (int[] cell : group) {
grid[cell[0]][cell[1]] = -1;
}
score += group.size() * 10;
bubblesCleared += group.size();
// 2. 检测悬空泡泡并消除
List<int[]> floating = findFloatingBubbles();
for (int[] cell : floating) {
grid[cell[0]][cell[1]] = -1;
}
score += floating.size() * 20; // 悬空掉落奖励更高
bubblesCleared += floating.size();
}
}
// 检查是否触及底部
for (int c = 0; c < GRID_COLS; c++) {
if (grid[GRID_ROWS - 1][c] >= 0) {
gameOver = true;
}
}
// 准备下一发
flyingColor = nextColor;
nextColor = random.nextInt(COLORS.length);
}
/**
* 鼠标点击发射泡泡
*/
@Override
public void mousePressed(MouseEvent e) {
if (isFlying || gameOver) return;
double dx = e.getX() - SHOOTER_X;
double dy = e.getY() - SHOOTER_Y;
double angle = Math.atan2(dy, dx);
// 限制发射角度不能向下（必须向上发射）
if (angle > 0) {
angle = -Math.PI / 2; // 默认垂直向上
}
flyingX = SHOOTER_X;
flyingY = SHOOTER_Y;
flyingVx = BUBBLE_SPEED * Math.cos(angle);
flyingVy = BUBBLE_SPEED * Math.sin(angle);
flyingColor = nextColor;
nextColor = random.nextInt(COLORS.length);
isFlying = true;
}
@Override public void mouseMoved(MouseEvent e) { mouseX = e.getX(); mouseY = e.getY(); repaint(); }
@Override public void mouseDragged(MouseEvent e) { mouseX = e.getX(); mouseY = e.getY(); repaint(); }
@Override public void mouseClicked(MouseEvent e) {}
@Override public void mouseReleased(MouseEvent e) {}
@Override public void mouseEntered(MouseEvent e) {}
@Override public void mouseExited(MouseEvent e) {}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
// 绘制网格中的泡泡
for (int r = 0; r < GRID_ROWS; r++) {
for (int c = 0; c < GRID_COLS; c++) {
if (grid[r][c] < 0) continue;
double[] pos = gridToPixel(r, c);
drawBubble(g2d, pos[0], pos[1], COLORS[grid[r][c]]);
}
}
// 绘制发射引导线
if (!isFlying && !gameOver) {
double dx = mouseX - SHOOTER_X;
double dy = mouseY - SHOOTER_Y;
double angle = Math.atan2(dy, dx);
if (angle <= 0) {
g2d.setColor(new Color(255, 255, 255, 80));
g2d.setStroke(new BasicStroke(2, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND,
0, new float[]{8, 8}, 0));
double lineLen = 100;
g2d.drawLine(SHOOTER_X, SHOOTER_Y,
(int)(SHOOTER_X + lineLen * Math.cos(angle)),
(int)(SHOOTER_Y + lineLen * Math.sin(angle)));
g2d.setStroke(new BasicStroke(1));
}
}
// 绘制飞行中的泡泡
if (isFlying) {
drawBubble(g2d, flyingX, flyingY, COLORS[flyingColor]);
}
// 绘制发射器位置的待发射泡泡
if (!isFlying && !gameOver) {
drawBubble(g2d, SHOOTER_X, SHOOTER_Y, COLORS[nextColor]);
g2d.setColor(Color.WHITE);
g2d.setFont(new Font("Arial", Font.BOLD, 12));
g2d.drawString("NEXT", SHOOTER_X - 15, SHOOTER_Y + 35);
}
// 绘制UI
g2d.setColor(Color.WHITE);
g2d.setFont(new Font("Microsoft YaHei", Font.BOLD, 18));
g2d.drawString("Score: " + score, 20, 30);
g2d.drawString("Cleared: " + bubblesCleared, 180, 30);
if (gameOver) {
g2d.setColor(new Color(0, 0, 0, 180));
g2d.fillRect(0, 0, WIDTH, HEIGHT);
g2d.setColor(Color.WHITE);
g2d.setFont(new Font("Microsoft YaHei", Font.BOLD, 40));
g2d.drawString("GAME OVER", WIDTH / 2 - 110, HEIGHT / 2);
}
}
private void drawBubble(Graphics2D g2d, double x, double y, Color color) {
// 主体渐变
GradientPaint gp = new GradientPaint(
(int)(x - RADIUS), (int)(y - RADIUS), color.brighter(),
(int)(x + RADIUS), (int)(y + RADIUS), color.darker());
g2d.setPaint(gp);
g2d.fillOval((int)(x - RADIUS), (int)(y - RADIUS), DIAMETER, DIAMETER);
// 高光
g2d.setColor(new Color(255, 255, 255, 120));
g2d.fillOval((int)(x - RADIUS / 2), (int)(y - RADIUS / 2), RADIUS, RADIUS);
// 边框
g2d.setColor(color.darker());
g2d.drawOval((int)(x - RADIUS), (int)(y - RADIUS), DIAMETER, DIAMETER);
}
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
JFrame frame = new JFrame("泡泡射击 - BFS连通消除与六边形网格");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(new BubbleShooter());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
});
}
}
四、关键算法详解
4.1 六边形网格的邻域坐标
六边形密铺的邻居关系与正方形网格不同，存在6个方向而非4个。更特殊的是，奇数行和偶数行的水平偏移导致邻域坐标公式不一致：
偶数行(row%2==0): 左上=(r-1,c-1), 右上=(r-1,c)
奇数行(row%2==1): 左上=(r-1,c), 右上=(r-1,c+1)
代码中使用两组方向偏移数组 evenDirs 和 oddDirs 分别处理，这是六边形网格编程中最容易出错的地方。
4.2 悬空泡泡的顶部连通性检测
消除同色连通块后，某些泡泡可能不再通过任何路径连接到顶部第一行。检测方法本质上是一次多源BFS：
- 将所有第一行的泡泡作为BFS起点
- 遍历所有六邻域可达泡泡
- 未被访问到的泡泡即为悬空
这种”反向思考”（标记可达而非标记悬空）大幅简化了代码逻辑，时间复杂度严格为 $O(N)$。
4.3 发射角度限制与反弹
为防止玩家向下发射，代码限制角度：
if (angle > 0) angle = -Math.PI / 2;
墙壁反弹通过简单反转水平速度实现：
if (flyingX - RADIUS < 0) flyingVx = -flyingVx;
这假设墙壁为完全弹性碰撞，是经典街机游戏的常用简化。
五、复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 飞行碰撞检测 | $O(N)$ | $N$ 为网格中泡泡总数 |
| BFS连通块检测 | $O(K)$ | $K$ 为连通块大小 |
| 悬空泡泡检测 | $O(N)$ | 全图BFS |
| 附着位置查找 | $O(1)$ | 仅检查9个邻域格子 |
由于网格尺寸固定（约300个格子），所有操作在实际运行中均为常数时间。
六、扩展思路
- AI自动瞄准：对每个空位模拟发射，计算能消除的最大连通块，选择最优角度
- 墙壁多次反弹：精确计算射线与边界的交点，实现多段反弹轨迹
- 特殊泡泡：炸弹泡泡（消除周围一圈）、彩虹泡泡（匹配任意颜色）
- 网络对战：实时同步双方网格状态，比拼消除速度
泡泡射击将几何坐标变换、图论BFS搜索与物理碰撞检测完美融合，是理解六边形网格算法的最佳实践项目之一。
