引言
消灭星星（PopStar）是一款风靡全球的消除类益智游戏。玩家通过点击相邻的同色星星块来消除它们，消除的块越多得分越高，最终目标是清空棋盘获得最高分数。看似简单的规则背后，蕴含着丰富的算法设计空间：如何高效检测连通块？怎样选择最优消除顺序以最大化得分？本文将用Java完整实现消灭星星的核心算法，重点讲解BFS连通块检测与贪心消除策略。
游戏规则与算法建模
规则抽象
游戏棋盘通常是一个 10×10 的矩形网格，每个格子包含一种颜色（用整数1~5表示）。当玩家点击某个格子时，所有与其上下左右相邻且颜色相同的格子构成一个连通块。若连通块大小不少于2，则这些格子被消除，上方格子下落填补空缺，右侧整列向左移动压缩。
核心算法问题
- 连通块检测：给定点击位置，快速找出所有同色相邻格子
- 重力模拟：消除后让上方星星下落、右侧列左移
- 消除策略：在每一步选择最优的连通块进行消除，以最大化最终得分
BFS连通块检测算法
连通块检测本质上是图遍历问题。将棋盘每个格子视为图的节点，相邻同色格子之间存在边。从点击位置出发，使用BFS或DFS遍历即可找到整个连通块。BFS在此场景下更为直观，且天然适合寻找最短路径层数（虽然本题不需要）。
import java.util.*;
/**
* 消灭星星游戏核心算法实现
* 重点：BFS连通块检测 + 贪心消除策略
*/
public class PopStarSolver {
// 棋盘大小
private static final int ROWS = 10;
private static final int COLS = 10;
// 颜色种类数
private static final int COLORS = 5;
// 四个方向：上、下、左、右
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 棋盘状态，0表示空，1~5表示不同颜色
private int[][] board;
public PopStarSolver() {
this.board = new int[ROWS][COLS];
}
/**
* 使用BFS检测从(r,c)出发的连通块
* @param r 起始行
* @param c 起始列
* @return 连通块中所有格子的坐标列表
*/
public List<int[]> findConnectedComponent(int r, int c) {
List<int[]> component = new ArrayList<>();
// 边界检查与空格子检查
if (!isValid(r, c) || board[r][c] == 0) {
return component;
}
int color = board[r][c];
boolean[][] visited = new boolean[ROWS][COLS];
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{r, c});
visited[r][c] = true;
component.add(new int[]{r, c});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cr = cur[0], cc = cur[1];
// 遍历四个邻居
for (int[] dir : DIRS) {
int nr = cr + dir[0];
int nc = cc + dir[1];
// 检查边界、未访问、同色
if (isValid(nr, nc) && !visited[nr][nc] && board[nr][nc] == color) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
component.add(new int[]{nr, nc});
}
}
}
return component;
}
private boolean isValid(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}
/**
* 计算连通块的得分：消除n个块的得分公式通常为 n * n * 5
* 例如消除2块得20分，消除5块得125分，鼓励大规模消除
*/
public int calculateScore(int blockCount) {
if (blockCount < 2) return 0;
return blockCount * blockCount * 5;
}
重力模拟与棋盘压缩
消除连通块后，需要模拟两个物理效果：
1. 纵向重力：每列中被消除的格子上方星星下落
2. 横向压缩：若某列完全为空，右侧所有列向左移动
/**
* 消除指定连通块，并应用重力与压缩
* @param component 要消除的连通块坐标列表
* @return 本次消除获得的分数
*/
public int eliminate(List<int[]> component) {
if (component.size() < 2) return 0;
// 标记消除位置
for (int[] pos : component) {
board[pos[0]][pos[1]] = 0;
}
// 纵向重力：每列从下往上收集非零元素
for (int c = 0; c < COLS; c++) {
int writeRow = ROWS - 1; // 从底部开始写入
for (int r = ROWS - 1; r >= 0; r--) {
if (board[r][c] != 0) {
board[writeRow][c] = board[r][c];
if (writeRow != r) {
board[r][c] = 0;
}
writeRow--;
}
}
// 剩余位置已经是0（因为消除时标记了）
while (writeRow >= 0) {
board[writeRow--][c] = 0;
}
}
// 横向压缩：将非空列向左移动
int writeCol = 0;
for (int c = 0; c < COLS; c++) {
// 检查该列是否全空
boolean isEmpty = true;
for (int r = 0; r < ROWS; r++) {
if (board[r][c] != 0) {
isEmpty = false;
break;
}
}
if (!isEmpty) {
if (writeCol != c) {
for (int r = 0; r < ROWS; r++) {
board[r][writeCol] = board[r][c];
board[r][c] = 0;
}
}
writeCol++;
}
}
return calculateScore(component.size());
}
贪心消除策略
消灭星星是一个典型的NP-hard问题（可归约为分组问题），对于大规模棋盘难以求得全局最优解。实践中采用贪心策略：每一步选择当前能消除的最大连通块。这种策略虽然无法保证全局最优，但在多数情况下表现良好。
/**
* 贪心策略：找出当前棋盘中最大的连通块并消除
* @return 本次操作得分，若无可消除块返回-1表示游戏结束
*/
public int greedyEliminate() {
List<int[]> bestComponent = new ArrayList<>();
boolean[][] visited = new boolean[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != 0 && !visited[r][c]) {
// BFS找连通块，同时标记visited避免重复计算
List<int[]> comp = findConnectedComponentWithVisited(r, c, visited);
if (comp.size() > bestComponent.size()) {
bestComponent = comp;
}
}
}
}
if (bestComponent.size() < 2) {
return -1; // 游戏结束
}
return eliminate(bestComponent);
}
/**
* 带visited标记的BFS，用于批量查找所有连通块
*/
private List<int[]> findConnectedComponentWithVisited(int r, int c, boolean[][] visited) {
List<int[]> component = new ArrayList<>();
int color = board[r][c];
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{r, c});
visited[r][c] = true;
component.add(new int[]{r, c});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] dir : DIRS) {
int nr = cur[0] + dir[0];
int nc = cur[1] + dir[1];
if (isValid(nr, nc) && !visited[nr][nc] && board[nr][nc] == color) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
component.add(new int[]{nr, nc});
}
}
}
return component;
}
完整可运行程序
/**
* 初始化随机棋盘
*/
public void initRandomBoard() {
Random rand = new Random();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
board[r][c] = rand.nextInt(COLORS) + 1;
}
}
}
/**
* 打印当前棋盘状态
*/
public void printBoard() {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
System.out.print(board[r][c] == 0 ? ". " : board[r][c] + " ");
}
System.out.println();
}
System.out.println();
}
/**
* 运行完整游戏流程
*/
public int playGame() {
int totalScore = 0;
int step = 0;
System.out.println("=== 初始棋盘 ===");
printBoard();
while (true) {
int score = greedyEliminate();
if (score < 0) break;
totalScore += score;
step++;
System.out.println("第" + step + "步消除，得分: " + score);
printBoard();
}
// 清空奖励：若棋盘全空额外加1000分
boolean isEmpty = true;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != 0) {
isEmpty = false;
break;
}
}
}
if (isEmpty) {
totalScore += 1000;
System.out.println("棋盘清空！奖励1000分");
}
System.out.println("游戏结束！总步数: " + step + "，总得分: " + totalScore);
return totalScore;
}
public static void main(String[] args) {
PopStarSolver game = new PopStarSolver();
game.initRandomBoard();
game.playGame();
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| BFS连通块检测 | O(k) | O(k) | k为连通块大小 |
| 重力模拟 | O(ROWS×COLS) | O(1) | 原地操作 |
| 贪心全遍历 | O(ROWS×COLS) | O(ROWS×COLS) | visited数组 |
| 单步最优消除 | O((ROWS×COLS)²) | O(ROWS×COLS) | 最坏情况需遍历全图 |
对于 10×10 的棋盘，每一步贪心选择的计算量在可接受范围内。若需优化，可使用并查集（Union-Find）动态维护连通块，将单步复杂度降至近似O(1)。
进阶思考：DFS vs BFS的选择
虽然本文使用BFS实现连通块检测，但在消灭星星场景中DFS同样适用。两者的区别在于：
– BFS：按层扩展，适合寻找最短路径或需要按距离分层的场景
– DFS：递归深入，代码更简洁，但可能因连通块过大导致栈溢出
对于大棋盘（如 20×20），建议仍使用BFS配合显式队列，避免递归深度限制。
总结
消灭星星游戏的Java实现涵盖了BFS图遍历、二维数组操作、贪心策略等多个经典算法主题。通过本文的代码，读者不仅能理解消除类游戏的核心机制，还能掌握如何将算法思维应用于实际游戏开发。并查集优化、A*启发式搜索寻找更优消除序列等都是值得深入探索的扩展方向。
