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型消除对应不同特效。约束条件高效性判别必须在一次Update循环内完成不能造成卡顿。对于10x10的棋盘O(M*N)的复杂度是基础但要避免O((M*N)^2)的嵌套暴力搜索。正确性必须识别出所有符合规则的匹配不能有遗漏。规则通常是在水平或垂直方向上连续三个或以上相同类型的元素构成一个可消除组。一个元素可以同时属于水平和垂直的匹配即L型、T型等。完整性对于组合消除如十字形算法需要能将其正确识别为一个完整的匹配组还是拆分为横竖两个这取决于游戏规则。通常为了特效和得分会将其合并为一个大的匹配组。可扩展性算法应该能方便地支持不同的匹配规则比如需要四个才能消除或者支持特殊障碍物。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; }这个方案简单直接但它有致命缺陷重复元素问题如果一个格子同时处于一个横向匹配和一个纵向匹配中即L/T/十字形的交点它会被分别加入到两个不同的match数组中。这会导致后续消除时这个格子被错误地处理了两次比如扣两次分播放两次消失动画。匹配组割裂问题一个十字形消除会被割裂成一个横条和一个竖条两个匹配组无法作为一个整体来处理从而可能无法触发“十字消除”的特殊效果或更高分数。效率并非最优虽然复杂度是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 方案优势与潜在问题优势完美解决重复与割裂问题每个格子只属于一个集合每个匹配组都是完整的连通区域。逻辑清晰易于理解算法步骤明确先找连通关系再按大小筛选。为特效提供完美数据你可以轻松判断一个匹配组的形状通过其坐标集合从而触发不同的消除特效直线、爆炸、全屏等。潜在问题与优化性能对于N*N的棋盘并查集操作的平均时间复杂度接近O(α(N))阿克曼函数的反函数极小整体算法是近似O(M*N)的完全满足需求。但在JavaScript等语言中递归实现的find可能在大棋盘上存在栈溢出风险可以用循环改写。“最小匹配单元”的争议有些游戏规则中一个超过3个的匹配比如4个一横排可能同时产生一个“四连消”特效和两个基础的三连消。我们的算法目前只将其作为一个组。如果需要拆解可以在得到大组后根据规则进行二次划分但这通常不是判别算法的职责。空格子处理我们的算法跳过了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(): ArrayArray[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 Mapnumber, [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: ArrayArray[number, number] []; for (const [, cells] of groupsMap) { if (cells.length 3) { matches.push(cells); } } return matches; } }4.2 判别时机与流程整合消除判别不是孤立运行的它嵌入在游戏主循环中。一个典型的流程是玩家操作交换两个相邻棋子的位置或直接点击某个棋子。操作验证交换后立即调用checkForMatches()。如果返回的matches数组为空说明此次交换无效需要将两个棋子动画回退到原位置。这是三消游戏的基础反馈。消除执行如果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: Mapnumber, [number, number][] new Map(); private checkForMatchesOptimized(): ArrayArray[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: ArrayArray[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; }坑二消除与填充的时序问题这是新手最容易出错的地方。判别出匹配组后你不能立即从逻辑棋盘上删除它们并开始掉落因为消除动画还在播放。如果立即更新棋盘下一帧的判别可能会基于一个“半空”的棋盘导致逻辑错误。正确的顺序是标记哪些格子要消除设置一个isRemoving状态。开始播放这些格子的消除动画。等待所有消除动画播放完毕可以用Promise.all或回调。将逻辑棋盘上这些格子的值设为EMPTY。执行掉落计算更新逻辑棋盘。播放掉落动画。掉落动画结束后在顶部生成新元素并更新逻辑棋盘。再次调用判别函数检查连锁。坑三无限连锁与死循环如果你的掉落填充算法是随机的理论上有可能在极端情况下新生成的棋子恰好又构成可消除组合导致消除-掉落-消除的无限循环。虽然概率极低但为了程序健壮性必须设置一个安全计数器。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的泥潭中解脱出来变得清晰、健壮且强大。它不仅仅是一个算法实现更是一种对游戏状态进行建模的思路。当你掌握了这种方法再回头看那些纷繁复杂的消除类游戏你会发现它们的核心逻辑竟是如此相似和优雅。实现过程中对动画时序、状态管理、边界情况的处理才是真正磨练一个游戏开发者功力的地方。希望这篇长文能帮你少走些弯路更顺畅地打造出体验出色的消除游戏。
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型消除对应不同特效。约束条件高效性判别必须在一次Update循环内完成不能造成卡顿。对于10x10的棋盘O(M*N)的复杂度是基础但要避免O((M*N)^2)的嵌套暴力搜索。正确性必须识别出所有符合规则的匹配不能有遗漏。规则通常是在水平或垂直方向上连续三个或以上相同类型的元素构成一个可消除组。一个元素可以同时属于水平和垂直的匹配即L型、T型等。完整性对于组合消除如十字形算法需要能将其正确识别为一个完整的匹配组还是拆分为横竖两个这取决于游戏规则。通常为了特效和得分会将其合并为一个大的匹配组。可扩展性算法应该能方便地支持不同的匹配规则比如需要四个才能消除或者支持特殊障碍物。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; }这个方案简单直接但它有致命缺陷重复元素问题如果一个格子同时处于一个横向匹配和一个纵向匹配中即L/T/十字形的交点它会被分别加入到两个不同的match数组中。这会导致后续消除时这个格子被错误地处理了两次比如扣两次分播放两次消失动画。匹配组割裂问题一个十字形消除会被割裂成一个横条和一个竖条两个匹配组无法作为一个整体来处理从而可能无法触发“十字消除”的特殊效果或更高分数。效率并非最优虽然复杂度是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 方案优势与潜在问题优势完美解决重复与割裂问题每个格子只属于一个集合每个匹配组都是完整的连通区域。逻辑清晰易于理解算法步骤明确先找连通关系再按大小筛选。为特效提供完美数据你可以轻松判断一个匹配组的形状通过其坐标集合从而触发不同的消除特效直线、爆炸、全屏等。潜在问题与优化性能对于N*N的棋盘并查集操作的平均时间复杂度接近O(α(N))阿克曼函数的反函数极小整体算法是近似O(M*N)的完全满足需求。但在JavaScript等语言中递归实现的find可能在大棋盘上存在栈溢出风险可以用循环改写。“最小匹配单元”的争议有些游戏规则中一个超过3个的匹配比如4个一横排可能同时产生一个“四连消”特效和两个基础的三连消。我们的算法目前只将其作为一个组。如果需要拆解可以在得到大组后根据规则进行二次划分但这通常不是判别算法的职责。空格子处理我们的算法跳过了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(): ArrayArray[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 Mapnumber, [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: ArrayArray[number, number] []; for (const [, cells] of groupsMap) { if (cells.length 3) { matches.push(cells); } } return matches; } }4.2 判别时机与流程整合消除判别不是孤立运行的它嵌入在游戏主循环中。一个典型的流程是玩家操作交换两个相邻棋子的位置或直接点击某个棋子。操作验证交换后立即调用checkForMatches()。如果返回的matches数组为空说明此次交换无效需要将两个棋子动画回退到原位置。这是三消游戏的基础反馈。消除执行如果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: Mapnumber, [number, number][] new Map(); private checkForMatchesOptimized(): ArrayArray[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: ArrayArray[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; }坑二消除与填充的时序问题这是新手最容易出错的地方。判别出匹配组后你不能立即从逻辑棋盘上删除它们并开始掉落因为消除动画还在播放。如果立即更新棋盘下一帧的判别可能会基于一个“半空”的棋盘导致逻辑错误。正确的顺序是标记哪些格子要消除设置一个isRemoving状态。开始播放这些格子的消除动画。等待所有消除动画播放完毕可以用Promise.all或回调。将逻辑棋盘上这些格子的值设为EMPTY。执行掉落计算更新逻辑棋盘。播放掉落动画。掉落动画结束后在顶部生成新元素并更新逻辑棋盘。再次调用判别函数检查连锁。坑三无限连锁与死循环如果你的掉落填充算法是随机的理论上有可能在极端情况下新生成的棋子恰好又构成可消除组合导致消除-掉落-消除的无限循环。虽然概率极低但为了程序健壮性必须设置一个安全计数器。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的泥潭中解脱出来变得清晰、健壮且强大。它不仅仅是一个算法实现更是一种对游戏状态进行建模的思路。当你掌握了这种方法再回头看那些纷繁复杂的消除类游戏你会发现它们的核心逻辑竟是如此相似和优雅。实现过程中对动画时序、状态管理、边界情况的处理才是真正磨练一个游戏开发者功力的地方。希望这篇长文能帮你少走些弯路更顺畅地打造出体验出色的消除游戏。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
