一、背景介绍
宝石方块（Columns）是一款经典的三消类益智游戏，1990年由世嘉发行。玩家通过控制下落的宝石组合，使三个或以上同色宝石横、竖或斜线连成一线即可消除，得分并触发上方宝石下落填补空位，可能引发连锁消除反应。
本游戏的核心算法包括：
- 下落控制：根据用户输入旋转或加速宝石组合的下落。
- 贪心匹配检测：每次宝石稳定后扫描全盘寻找三连以上同色宝石。
- 级联消除：消除后上方宝石在重力作用下下落，可能形成新的匹配，需要反复迭代。
- 连锁加分：连续触发的级联消除会获得递增的额外奖励。
二、整体设计
游戏采用 MVC 模式，将界面、逻辑和数据分离。核心数据结构是一个二维字符数组，0 表示空位，1-7 表示不同颜色的宝石。
Cell：表示宝石的单元格。GameBoard：封装了棋盘状态、下落、匹配检测与消除等核心逻辑。GameEngine：游戏引擎，负责游戏循环与状态推进。GameMain：带main函数的入口，演示整局游戏。
三、完整代码实现
3.1 宝石单元格 Cell.java
/**
* 宝石单元格
* 颜色为 0 表示空位，1-7 表示 7 种宝石
*/
public class Cell {
public int color; // 颜色
public Cell(int color) { this.color = color; }
public boolean isEmpty() { return color == 0; }
}
3.2 游戏棋盘 GameBoard.java
import java.util.*;
/**
* 宝石方块游戏棋盘
* 提供下落、匹配检测、消除与重力下落等核心算法
*/
public class GameBoard {
public static final int ROWS = 12; // 行数
public static final int COLS = 6; // 列数
public static final int COLOR_COUNT = 7; // 宝石颜色数
private final int[][] grid = new int[ROWS][COLS];
/** 清空棋盘 */
public void clear() {
for (int[] row : grid) Arrays.fill(row, 0);
}
/**
* 检查位置是否合法
*/
private boolean inBounds(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}
/**
* 贪心检测所有可消除的宝石
* 返回需要消除的坐标集合
* 核心思路：
* 1) 水平方向：对每一行，从左到右扫描连续同色段，长度 >=3 标记
* 2) 垂直方向：对每一列，从下到上扫描连续同色段，长度 >=3 标记
* 3) 斜线方向（对角线）：从左上到右下、从右上到左下两个方向扫描
* 时间复杂度 O(R*C)
*/
public Set<String> findMatches() {
Set<String> matched = new HashSet<>();
// 水平扫描
for (int r = 0; r < ROWS; r++) {
int c = 0;
while (c < COLS) {
if (grid[r][c] == 0) { c++; continue; }
int start = c;
while (c < COLS && grid[r][c] == grid[r][start]) c++;
if (c - start >= 3) {
for (int k = start; k < c; k++) matched.add(r + "," + k);
}
}
}
// 垂直扫描
for (int c = 0; c < COLS; c++) {
int r = 0;
while (r < ROWS) {
if (grid[r][c] == 0) { r++; continue; }
int start = r;
while (r < ROWS && grid[r][c] == grid[start][c]) r++;
if (r - start >= 3) {
for (int k = start; k < r; k++) matched.add(k + "," + c);
}
}
}
// 对角线扫描（左上到右下）
for (int sr = 0; sr < ROWS; sr++) {
for (int sc = 0; sc < COLS; sc++) {
if (grid[sr][sc] == 0) continue;
int r = sr, c = sc;
while (inBounds(r + 1, c + 1) && grid[r + 1][c + 1] == grid[sr][sc]) {
r++; c++;
}
if (r - sr >= 2 && c - sc >= 2) {
for (int dr = sr; dr <= r; dr++)
for (int dc = sc; dc <= c; dc++)
matched.add(dr + "," + dc);
}
}
}
// 对角线扫描（右上到左下）
for (int sr = 0; sr < ROWS; sr++) {
for (int sc = 0; sc < COLS; sc++) {
if (grid[sr][sc] == 0) continue;
int r = sr, c = sc;
while (inBounds(r + 1, c - 1) && grid[r + 1][c - 1] == grid[sr][sc]) {
r++; c--;
}
if (r - sr >= 2 && sc - c >= 2) {
for (int dr = sr; dr <= r; dr++)
for (int dc = sc; dc >= c; dc--)
matched.add(dr + "," + dc);
}
}
}
return matched;
}
/**
* 消除指定坐标的宝石
*/
public int eliminate(Set<String> cells) {
for (String s : cells) {
String[] parts = s.split(",");
grid[Integer.parseInt(parts[0])][Integer.parseInt(parts[1])] = 0;
}
return cells.size();
}
/**
* 模拟重力，让宝石自然下落填补空位
* 对每一列从下往上扫描，遇到空格就把上方非空元素下移
* 时间复杂度 O(R*C)
*/
public void applyGravity() {
for (int c = 0; c < COLS; c++) {
int writeRow = ROWS - 1;
for (int r = ROWS - 1; r >= 0; r--) {
if (grid[r][c] != 0) {
grid[writeRow--][c] = grid[r][c];
}
}
// 顶部剩余位置清零
for (int r = writeRow; r >= 0; r--) grid[r][c] = 0;
}
}
/**
* 级联消除算法
* 反复执行：检测匹配 -> 消除 -> 重力 -> 再次检测
* 直到没有新的匹配出现
* 返回每级消除的宝石数（用于计算连锁奖励）
*/
public List<Integer> cascade() {
List<Integer> chain = new ArrayList<>();
while (true) {
Set<String> matched = findMatches();
if (matched.isEmpty()) break;
int count = eliminate(matched);
chain.add(count);
applyGravity();
}
return chain;
}
/**
* 在指定位置放置一列宝石（自顶向下）
* 模拟玩家释放组合后的稳定
*/
public boolean placeFallingPiece(int col, int[] colors) {
if (col < 0 || col >= COLS) return false;
// 找到最低可放置位置
int writeRow = ROWS - 1;
for (int i = colors.length - 1; i >= 0; i--) {
if (writeRow < 0) return false;
grid[writeRow--][col] = colors[i];
}
return true;
}
/** 打印棋盘（调试用） */
public void printBoard() {
for (int[] row : grid) {
StringBuilder sb = new StringBuilder();
for (int v : row) sb.append(v == 0 ? " . " : " " + v + " ");
System.out.println(sb);
}
}
public int[][] snapshot() {
int[][] copy = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) copy[i] = grid[i].clone();
return copy;
}
}
3.3 游戏引擎 GameEngine.java
import java.util.*;
/**
* 游戏引擎
* 负责：随机生成下落组合、模拟玩家操作、计分与连锁奖励
*/
public class GameEngine {
private final GameBoard board = new GameBoard();
private final Random rand = new Random();
private int score = 0;
private int chainLevel = 0;
public GameBoard getBoard() { return board; }
public int getScore() { return score; }
/** 随机生成一个三格宝石组合 */
public int[] generateFallingColors() {
int[] colors = new int[3];
for (int i = 0; i < 3; i++)
colors[i] = rand.nextInt(GameBoard.COLOR_COUNT) + 1;
return colors;
}
/**
* 模拟玩家释放宝石组合
* 触发级联消除与连锁奖励
* 连锁奖励：第 N 级消除获得 基础分 * 2^(N-1)
*/
public int dropPiece(int col) {
int[] colors = generateFallingColors();
if (!board.placeFallingPiece(col, colors)) return -1;
int gained = 0;
chainLevel = 0;
for (int count : board.cascade()) {
chainLevel++;
gained += (int) (count * 10 * Math.pow(2, chainLevel - 1));
}
score += gained;
return gained;
}
}
3.4 入口 GameMain.java
import java.util.*;
/**
* 宝石方块主程序
* 模拟 20 步随机操作，输出棋盘演化与最终得分
*/
public class GameMain {
public static void main(String[] args) {
GameEngine engine = new GameEngine();
Random rand = new Random();
System.out.println("=== 宝石方块游戏开始 ===");
for (int step = 1; step <= 20; step++) {
int col = rand.nextInt(GameBoard.COLS);
int gained = engine.dropPiece(col);
System.out.printf("Step %2d: drop at col %d, gained %d, total %d%n",
step, col, gained, engine.getScore());
engine.getBoard().printBoard();
System.out.println();
}
System.out.println("=== 最终得分: " + engine.getScore() + " ===");
}
}
四、算法分析
4.1 时间复杂度
- 匹配检测
findMatches：扫描整盘四次（水平、垂直、两条对角线），每次扫描 O(RC)。因此单次匹配检测时间复杂度为 O(R·C)*。 - 级联消除
cascade：每次级联至少消除 3 个宝石，最多消除 R·C 个，因此最坏情况下需要执行 O(R·C) 次级联。每次级联包括匹配 + 消除 + 重力各 O(R·C)，总时间复杂度为 O((R·C)²)。 - 重力应用
applyGravity：单列扫描 O(R)，共 C 列，总时间复杂度 O(R·C)。
4.2 空间复杂度
- 棋盘存储使用二维数组，空间复杂度 O(R·C)。
- 匹配集合使用 HashSet 存储最坏 O(R·C) 个坐标。
五、可扩展方向
- AI 玩家：基于棋盘评估函数（高度差、匹配机会数、未来消除潜力）使用 Minimax 或蒙特卡洛搜索。
- 特殊宝石：炸弹宝石（消除同色所有）、彩虹宝石（万能色）。
- 连击特效：动画呈现连锁消除，增强视觉体验。
- 联机对战：双玩家同时操作同一棋盘，奖励与惩罚相互影响。
六、运行说明
将 Cell.java、GameBoard.java、GameEngine.java、GameMain.java 放入同一目录，使用 javac *.java && java GameMain 即可运行。每一步会打印棋盘状态与得分变化。
