三消游戏核心算法：并查集实现高效消除判定与工程实践

1. 从“三消”到“巧判”：一个被低估的核心算法

做游戏开发的朋友，尤其是接触过休闲益智类项目的，对“消消乐”（三消）这个品类肯定不陌生。市面上从《Candy Crush Saga》到《开心消消乐》，无数成功产品验证了这个玩法的巨大市场。很多刚入行的开发者，甚至一些有经验的同行，可能会觉得三消游戏的核心算法“就那么回事”——无非是遍历棋盘，找三个或以上连在一起的相同元素，然后消除，再补充新元素。

但如果你真的动手实现过一个手感流畅、判定精准、毫无BUG的三消游戏，尤其是用Cocos Creator、Unity这类引擎时，你就会发现，那个看似简单的“消除条件判别”环节，恰恰是决定游戏体验上限还是下限的关键。它远不止一个if语句判断相邻格子颜色是否相等那么简单。一个“巧妙”的判别算法，需要高效地处理任意形状的匹配（横、竖、L型、T型、十字型等），需要在玩家操作后瞬间完成全盘扫描，需要优雅地处理连锁消除和多次匹配，更需要为后续的动画、计分、特效触发提供清晰、无歧义的数据结构。

今天，我想结合自己做过和看过的一些项目，深入聊聊这个“消除条件判别算法”。我们不止要实现它，更要实现得高效、健壮、易于扩展。我会从最基础的暴力遍历开始，逐步优化到一种结合了“并查集”思想与“预计算标记”的混合策略，这种策略在中等规模棋盘（如8x8, 10x10）上表现非常出色，逻辑清晰且不易出错。

2. 问题本质与算法设计目标拆解

在动手写代码之前，我们必须把问题定义清楚。消除判别算法的输入是什么？输出又是什么？它需要在什么约束下工作？

2.1 核心输入与输出

输入：一个M x N的二维数组board，代表游戏棋盘。每个格子board[i][j]存储一个代表“元素类型”的值（比如整数1代表红色糖果，2代表黄色糖果等）。此外，通常还会有一个emptyValue（比如-1或0）代表空格子。在一次玩家交换操作后，棋盘状态是确定的。

输出：一个包含了所有可消除“单元”的集合。这里的“单元”是关键。它不应该只是简单地返回一个坐标列表[(x1,y1), (x2,y2)...]，因为一次消除可能包含多个互不相连的匹配组（例如，玩家一次交换同时触发了上下各一个三连消）。更理想的输出是一个列表，列表中的每一项代表一个独立的“匹配组”，每个组本身是一个坐标列表。例如：

输出: [ [ (1,2), (1,3), (1,4), (1,5) ], // 一个横向的四连消 [ (3,5), (4,5), (5,5) ] // 一个纵向的三连消 ]

这样的数据结构对于后续流程极其友好：你可以轻松地为每个独立的匹配组播放不同的消除动画，计算连击分，触发不同的特效（四连、五连、L型消除对应不同特效）。

约束条件：

1. 高效性：判别必须在一次Update循环内完成，不能造成卡顿。对于10x10的棋盘，O(M*N)的复杂度是基础，但要避免O((M*N)^2)的嵌套暴力搜索。
2. 正确性：必须识别出所有符合规则的匹配，不能有遗漏。规则通常是：在水平或垂直方向上，连续三个或以上相同类型的元素构成一个可消除组。一个元素可以同时属于水平和垂直的匹配（即L型、T型等）。
3. 完整性：对于组合消除（如十字形），算法需要能将其正确识别为一个完整的匹配组，还是拆分为横竖两个？这取决于游戏规则。通常，为了特效和得分，会将其合并为一个大的匹配组。
4. 可扩展性：算法应该能方便地支持不同的匹配规则（比如需要四个才能消除，或者支持特殊障碍物）。

2.2 基础方案：行列扫描法及其缺陷

最直观的方法是进行两次独立的扫描：一次按行扫描，一次按列扫描。

// 伪代码示例：基础行列扫描 function findMatchesBasic(board) { let matches = []; const rows = board.length; const cols = board[0].length; // 横向扫描 for (let i = 0; i < rows; i++) { let start = 0; while (start < cols) { let end = start; while (end + 1 < cols && board[i][end] === board[i][end + 1] && board[i][end] !== EMPTY) { end++; } if (end - start + 1 >= 3) { let match = []; for (let k = start; k <= end; k++) match.push([i, k]); matches.push(match); } start = end + 1; } } // 纵向扫描 for (let j = 0; j < cols; j++) { let start = 0; while (start < rows) { let end = start; while (end + 1 < rows && board[end][j] === board[end + 1][j] && board[end][j] !== EMPTY) { end++; } if (end - start + 1 >= 3) { let match = []; for (let k = start; k <= end; k++) match.push([k, j]); matches.push(match); } start = end + 1; } } return matches; }

这个方案简单直接，但它有致命缺陷：

1. 重复元素问题：如果一个格子同时处于一个横向匹配和一个纵向匹配中（即L/T/十字形的交点），它会被分别加入到两个不同的match数组中。这会导致后续消除时，这个格子被错误地处理了两次（比如扣两次分，播放两次消失动画）。
2. 匹配组割裂问题：一个十字形消除会被割裂成一个横条和一个竖条两个匹配组，无法作为一个整体来处理，从而可能无法触发“十字消除”的特殊效果或更高分数。
3. 效率并非最优：虽然复杂度是O(M*N)，但进行了两次全盘扫描，且合并匹配组需要额外的处理。

那么，如何解决“一个元素属于多个匹配”这个核心矛盾？这就是引入“并查集”或“连通分量”思想的动机。

3. 核心优化：基于并查集的连通分量分析

我们的目标是将所有相连的、可消除的格子，合并到同一个集合中。这里的“相连”指的是在棋盘上相邻（上下左右），且元素类型相同。这本质上是一个在二维网格上寻找“连通分量”的经典问题，并查集是解决此类问题的利器。

3.1 并查集快速回顾

并查集（Union-Find）是一种数据结构，主要用于处理一些不相交集合的合并及查询问题。它支持两种操作：

• Find(x): 确定元素x属于哪一个子集。
• Union(x, y): 将包含x和y的两个子集合并。

在消除判别中，每个棋盘格子可以看作一个元素。初始时，每个格子自成一个集合。我们遍历棋盘，对于每个格子，检查其右方和下方的邻居（避免重复检查）。如果邻居与当前格子类型相同且非空，就执行Union操作，将它们合并到同一个集合中。

遍历结束后，所有直接或间接相连的相同类型格子，都属于同一个并查集集合。

3.2 算法步骤详解

让我们结合代码，一步步实现这个“巧妙的判别算法”。

第一步：初始化与辅助函数我们首先定义一个并查集类，或者直接用二维数组表示父节点。为了清晰，这里用类来表示。

class UnionFind { constructor(size) { this.parent = new Array(size); for (let i = 0; i < size; i++) { this.parent[i] = i; // 初始时，每个节点的父节点是自己 } } find(x) { // 路径压缩优化 if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { let rootX = this.find(x); let rootY = this.find(y); if (rootX !== rootY) { this.parent[rootY] = rootX; // 将rootY的父节点设为rootX } } } // 工具函数：将二维坐标映射到一维索引 function index(row, col, cols) { return row * cols + col; }

第二步：第一次遍历，构建连通关系这是算法的核心。我们只遍历每个格子，检查其右侧和下方的邻居。这是标准的“四连通”检测，且避免重复。

function findMatchesWithUF(board) { const rows = board.length; const cols = board[0].length; const totalCells = rows * cols; const uf = new UnionFind(totalCells); const EMPTY = -1; // 假设-1代表空格 // 第一次遍历：合并相邻的相同类型格子 for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { const currentVal = board[i][j]; if (currentVal === EMPTY) continue; const currentIdx = index(i, j, cols); // 检查右侧邻居 if (j + 1 < cols && board[i][j + 1] === currentVal) { uf.union(currentIdx, index(i, j + 1, cols)); } // 检查下方邻居 if (i + 1 < rows && board[i + 1][j] === currentVal) { uf.union(currentIdx, index(i + 1, j, cols)); } } }

第三步：收集并筛选有效的匹配组遍历结束后，我们得到了一个并查集，它把棋盘上所有连通区域都划分好了。但并不是所有连通区域都是可消除的——可能有两个相同格子相邻，但不够三个。所以我们需要筛选。

// 第二步：收集每个连通分量（集合）的所有成员 const groups = new Map(); // key: 根节点索引, value: 该集合所有坐标的数组 for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (board[i][j] === EMPTY) continue; const idx = index(i, j, cols); const root = uf.find(idx); if (!groups.has(root)) { groups.set(root, []); } groups.get(root).push([i, j]); } } // 第三步：筛选出大小 >= 3 的连通分量，即为可消除组 const matches = []; for (let [root, cells] of groups) { if (cells.length >= 3) { matches.push(cells); } } return matches; }

至此，我们得到了一个matches数组，其中每个元素就是一个独立的、大小至少为3的匹配组。十字形、L形等复杂形状都会被正确识别为一个组。

注意：这里有一个非常重要的细节。并查集合并的是所有相邻的相同格子。这意味着，如果棋盘上有两个分离的、但类型相同的三连消，它们会被识别为两个不同的连通分量（因为不相邻），这正是我们想要的。而一个十字形，由于其所有格子都相邻（通过中心点连接），所以会被合并成一个包含5个格子的连通分量。

3.3 方案优势与潜在问题

优势：

1. 完美解决重复与割裂问题：每个格子只属于一个集合，每个匹配组都是完整的连通区域。
2. 逻辑清晰，易于理解：算法步骤明确，先找连通关系，再按大小筛选。
3. 为特效提供完美数据：你可以轻松判断一个匹配组的形状（通过其坐标集合），从而触发不同的消除特效（直线、爆炸、全屏等）。

潜在问题与优化：

1. 性能：对于N*N的棋盘，并查集操作的平均时间复杂度接近O(α(N))（阿克曼函数的反函数，极小），整体算法是近似O(M*N)的，完全满足需求。但在JavaScript等语言中，递归实现的find可能在大棋盘上存在栈溢出风险，可以用循环改写。
2. “最小匹配单元”的争议：有些游戏规则中，一个超过3个的匹配（比如4个一横排），可能同时产生一个“四连消”特效和两个基础的三连消。我们的算法目前只将其作为一个组。如果需要拆解，可以在得到大组后，根据规则进行二次划分，但这通常不是判别算法的职责。
3. 空格子处理：我们的算法跳过了EMPTY格子，这很重要。否则空格子可能会把不该连接的区域连起来。

4. 工程实践：在Cocos Creator中的集成与优化

理论很美好，但放到实际的游戏引擎里，我们还得考虑更多工程细节。以Cocos Creator为例，我们的棋盘数据可能不是简单的二维数组，而是一个cc.Node的二维数组，每个节点上挂载着脚本组件，存储着类型、坐标、是否正在消除等状态。

4.1 数据结构与算法适配

首先，我们需要将视觉上的节点网格，映射到算法需要的逻辑数据。

// GameManager.ts 或类似的管理脚本中 import { _decorator, Component, Node } from 'cc'; @ccclass('GameManager') export class GameManager extends Component { private _board: number[][] = []; // 逻辑棋盘 private _tileNodes: Node[][] = []; // 节点棋盘，与逻辑棋盘一一对应 private readonly EMPTY = 0; // 初始化棋盘，例如从关卡数据加载 initBoard(levelData) { const { rows, cols, layout } = levelData; this._board = new Array(rows); this._tileNodes = new Array(rows); for (let i = 0; i < rows; i++) { this._board[i] = new Array(cols); this._tileNodes[i] = new Array(cols); for (let j = 0; j < cols; j++) { this._board[i][j] = layout[i][j]; // 填充逻辑类型 // 实例化对应的Tile节点，并设置位置 const tileNode = instantiate(this.tilePrefab); this._tileNodes[i][j] = tileNode; // ... 设置父节点、位置、初始化Tile脚本等 } } } // 核心的消除判别函数 private checkForMatches(): Array<Array<[number, number]>> { const rows = this._board.length; const cols = this._board[0].length; const uf = new UnionFind(rows * cols); // 1. 构建连通关系 for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { const val = this._board[r][c]; if (val === this.EMPTY) continue; const idx = r * cols + c; // 右邻居 if (c + 1 < cols && this._board[r][c + 1] === val) { uf.union(idx, r * cols + (c + 1)); } // 下邻居 if (r + 1 < rows && this._board[r + 1][c] === val) { uf.union(idx, (r + 1) * cols + c); } } } // 2. 收集分组 const groupsMap = new Map<number, [number, number][]>(); for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (this._board[r][c] === this.EMPTY) continue; const idx = r * cols + c; const root = uf.find(idx); if (!groupsMap.has(root)) { groupsMap.set(root, []); } groupsMap.get(root)!.push([r, c]); } } // 3. 筛选并返回有效匹配 const matches: Array<Array<[number, number]>> = []; for (const [, cells] of groupsMap) { if (cells.length >= 3) { matches.push(cells); } } return matches; } }

4.2 判别时机与流程整合

消除判别不是孤立运行的，它嵌入在游戏主循环中。一个典型的流程是：

1. 玩家操作：交换两个相邻棋子的位置（或直接点击某个棋子）。
2. 操作验证：交换后，立即调用checkForMatches()。如果返回的matches数组为空，说明此次交换无效，需要将两个棋子动画回退到原位置。这是三消游戏的基础反馈。
3. 消除执行：如果matches不为空，则进入消除流程： a.标记消除：遍历matches中的每个组，将对应逻辑棋盘位置设为EMPTY，并触发Tile节点上的“消除动画”（如缩放、变淡、播放粒子特效）。 b.结算与得分：根据每个匹配组的大小和形状计算得分。 c.掉落填充：模拟重力，让上方的棋子依次下落，填补空位，并在顶部生成新棋子。 d.连锁检测：填充完成后，必须再次调用checkForMatches()。因为掉落可能形成新的可消除组合。如果仍有匹配，则重复步骤3，实现连锁消除。这是一个循环过程，直到某次检测后matches为空为止。

// 在GameManager中处理一次玩家交换 async onTileSwap(posA: [number, number], posB: [number, number]) { // 1. 交换逻辑棋盘数据 this.swapBoardData(posA, posB); // 2. 播放交换动画（可选） // 3. 检查匹配 let matches = this.checkForMatches(); if (matches.length === 0) { // 无效交换，回退 this.swapBoardData(posA, posB); // 换回来 await this.playSwapBackAnimation(posA, posB); // 播放回流动画 return; } // 4. 有效交换，进入消除循环 while (matches.length > 0) { // a. 处理本轮所有消除（得分、动画） await this.processMatches(matches); // b. 掉落与填充 await this.applyGravityAndFill(); // c. 再次检查是否引发新的消除 matches = this.checkForMatches(); } // 5. 消除循环结束，检查游戏目标（如收集特定物品）是否达成 this.checkLevelGoals(); }

4.3 性能优化与边界情况处理

在实际项目中，我们还需要考虑以下问题：

1. 避免频繁的GC（垃圾回收）上面的checkForMatches函数每次都会创建新的UnionFind实例、Map和数组。在连锁消除多次调用的高频场景下，可能引发GC压力。一个优化点是复用数据结构。

private _uf: UnionFind | null = null; private _reusableGroupsMap: Map<number, [number, number][]> = new Map(); private checkForMatchesOptimized(): Array<Array<[number, number]>> { const rows = this._board.length; const cols = this._board[0].length; const total = rows * cols; // 复用或创建UnionFind if (!this._uf || this._uf.parent.length !== total) { this._uf = new UnionFind(total); } else { // 重置UnionFind (需要实现reset方法) this._uf.reset(); } // 清空复用Map this._reusableGroupsMap.clear(); // ... 后续合并、收集逻辑与之前相同，但使用 this._uf 和 this._reusableGroupsMap ... // 将结果提取到新数组返回，但复用内部容器 const matches: Array<Array<[number, number]>> = []; for (const [, cells] of this._reusableGroupsMap) { if (cells.length >= 3) { // 注意：这里需要浅拷贝cells，因为_reusableGroupsMap下次会被清空 matches.push([...cells]); } } return matches; }

2. 处理特殊元素与障碍物真实的消消乐游戏有冰块、铁链、彩虹糖等特殊元素。我们的算法基础框架可以很好地扩展。

• 不可消除的障碍物：在遍历合并时，直接跳过这些格子（if (val === OBSTACLE) continue），它们不会参与连通分量计算。
• 彩虹糖（全消型）：可以将其视为一个特殊的“通配符”类型。在合并逻辑上需要特殊处理：它可以与任何相邻的普通糖果合并，但两个彩虹糖相邻呢？这取决于具体规则。一种常见设计是，彩虹糖自身不参与普通匹配，只在被消除时触发全屏或特定行/列消除。
• 特效组合：比如直线特效和爆炸特效组合。这通常在匹配组被识别后，根据组的大小和形状，生成对应的“特效棋子”对象，并挂载到逻辑棋盘上。下一轮判别时，这些特效棋子有自己独特的消除逻辑。

3. 匹配组的“形状”识别为了触发不同的特效，我们需要判断一个匹配组是横向、纵向还是L/T/十字形。

private getMatchShape(cells: [number, number][]): string { if (cells.length < 3) return 'none'; // 检查是否在同一行 const firstRow = cells[0][0]; const allSameRow = cells.every(cell => cell[0] === firstRow); if (allSameRow) return 'horizontal'; // 检查是否在同一列 const firstCol = cells[0][1]; const allSameCol = cells.every(cell => cell[1] === firstCol); if (allSameCol) return 'vertical'; // 检查是否构成紧凑的2x2, L型等，这里可以计算包围盒 const rows = cells.map(c => c[0]); const cols = cells.map(c => c[1]); const minRow = Math.min(...rows); const maxRow = Math.max(...rows); const minCol = Math.min(...cols); const maxCol = Math.max(...cols); const width = maxCol - minCol + 1; const height = maxRow - minRow + 1; const area = width * height; // 如果格子数等于包围盒面积，且大于3，可能是方形或T型等 if (cells.length === area && cells.length > 3) { if (width === height) return 'square'; // 如2x2的4连 // 更复杂的形状判断可以继续细化 } // 默认返回一个通用类型，如'special' return 'special'; }

5. 踩坑实录：从理论到稳定可用的距离

纸上得来终觉浅，绝知此事要躬行。在实际项目中实现这个算法，我踩过几个印象深刻的坑，这里分享出来，希望大家能绕过去。

坑一：并查集Find函数的栈溢出在JavaScript/TypeScript中，如果棋盘很大（比如15x15），并且存在一个非常大的连通区域（比如开局全是一种颜色），递归实现的find函数可能会导致调用栈溢出。务必使用循环版本。

find(x: number): number { while (this.parent[x] !== x) { // 路径压缩：将x的父节点指向祖父节点 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }

坑二：消除与填充的时序问题这是新手最容易出错的地方。判别出匹配组后，你不能立即从逻辑棋盘上删除它们并开始掉落，因为消除动画还在播放。如果立即更新棋盘，下一帧的判别可能会基于一个“半空”的棋盘，导致逻辑错误。正确的顺序是：

1. 标记哪些格子要消除（设置一个isRemoving状态）。
2. 开始播放这些格子的消除动画。
3. 等待所有消除动画播放完毕（可以用Promise.all或回调）。
4. 将逻辑棋盘上这些格子的值设为EMPTY。
5. 执行掉落计算，更新逻辑棋盘。
6. 播放掉落动画。
7. 掉落动画结束后，在顶部生成新元素，并更新逻辑棋盘。
8. 再次调用判别函数，检查连锁。

坑三：无限连锁与死循环如果你的掉落填充算法是随机的，理论上有可能在极端情况下，新生成的棋子恰好又构成可消除组合，导致消除-掉落-消除的无限循环。虽然概率极低，但为了程序健壮性，必须设置一个安全计数器。

let chainCount = 0; const MAX_CHAIN = 50; // 设置一个足够大的安全上限 while (matches.length > 0 && chainCount < MAX_CHAIN) { await this.processMatches(matches); await this.applyGravityAndFill(); matches = this.checkForMatches(); chainCount++; } if (chainCount >= MAX_CHAIN) { console.error('Possible infinite loop detected in match chain!'); // 采取恢复措施，比如强制刷新棋盘 }

坑四：特效元素的判别逻辑冲突当棋盘上存在“直线消除”特效棋子时，它的消除规则是整行或整列。如果你简单地将它当作一个普通类型加入并查集，它的连通性会出问题。我的做法是，在主判别流程之前，先单独处理特效棋子。例如，遍历棋盘，如果发现一个“横向火箭”特效被匹配（或即将被引爆），则直接将整行的坐标生成一个匹配组，并将这些位置标记为“已处理”。在后续的并查集主流程中，跳过这些已处理的位置。这样可以避免规则冲突。

6. 算法变体与扩展思考

基础的并查集连通算法已经能解决90%的问题。但针对特定需求，还有一些变体和优化思路。

变体一：基于BFS/DFS的搜索法如果不喜欢并查集，也可以用广度优先搜索（BFS）或深度优先搜索（DFS）来寻找连通分量。逻辑同样清晰：从一个未访问的非空格子出发，搜索其上下左右相同类型的邻居，标记为已访问并加入当前组，直到找不到新成员。然后继续寻找下一个未访问的起点。这种方法在代码上可能更直观，但需要维护一个额外的visited访问标记数组。性能上与优化后的并查集相差无几，可根据个人喜好选择。

变体二：预计算“匹配潜力”在一些需要提示（Hint）功能的游戏中，我们需要快速判断当前棋盘是否存在任何可能的移动。暴力方法是模拟交换所有相邻格子，然后调用判别函数，复杂度是O(M*N * (判别成本))。可以基于当前判别结果进行优化。例如，如果一个格子属于一个大小>=2的连通分量，那么移动它附近的格子就很有可能形成匹配。我们可以优先检查这些“潜在匹配点”的周围，减少计算量。

扩展：六边形网格消除如果游戏是六边形网格（如《Hexic》），相邻关系从4方向变成了6方向。我们的算法只需要修改合并邻居的判断条件即可。在遍历时，对于六边形网格，一个格子的邻居坐标计算规则会发生变化（奇数行和偶数行的邻居列偏移不同），但并查集或BFS的核心思想完全适用。

从一行行、一列列笨拙地扫描，到利用并查集将问题抽象为“寻找连通分量”，这个思维转变让消除判别算法从一堆if-else的泥潭中解脱出来，变得清晰、健壮且强大。它不仅仅是一个算法实现，更是一种对游戏状态进行建模的思路。当你掌握了这种方法，再回头看那些纷繁复杂的消除类游戏，你会发现它们的核心逻辑竟是如此相似和优雅。实现过程中对动画时序、状态管理、边界情况的处理，才是真正磨练一个游戏开发者功力的地方。希望这篇长文能帮你少走些弯路，更顺畅地打造出体验出色的消除游戏。