1. 項目概述從“三消”到“巧判”的核心躍遷做游戲開發(fā)的朋友尤其是接觸過休閑益智品類的對“消消樂”這類三消游戲肯定不陌生。表面上看它規(guī)則簡單玩家交換相鄰的兩個元素如果交換后能在橫豎方向湊齊三個或更多相同的就觸發(fā)消除。但當你真正動手去實現時第一個攔路虎往往不是華麗的特效或流暢的動畫而是那個最基礎、最核心的“消除條件判別算法”。為什么說它是個“坑”因為它的實現直接決定了游戲的“手感”和“智商”。一個低效的算法在玩家快速操作時可能導致卡頓一個邏輯有瑕疵的算法則會出現該消的不消、不該消的亂消讓玩家覺得游戲有BUG體驗極差。網上能找到的很多入門教程給出的往往是“暴力掃描全盤”的樸素實現這在棋盤較小比如8x8時勉強能用一旦棋盤變大或者需要支持“L型”、“T型”等復雜消除形狀時性能瓶頸和邏輯復雜性就會指數級上升。今天要分享的正是我在多個項目迭代后沉淀下來的一套“巧妙的消除條件判別算法”。它不依賴于每步操作后的全盤掃描而是以“變化點”為核心進行最小范圍的、增量式的條件檢測。這套算法的價值在于它將判別的時間復雜度從 O(n2)n為棋盤邊長降到了接近 O(1) 的常數級別并且邏輯清晰極易擴展支持“十字消”、“五連消”等特殊規(guī)則。無論你是用 Cocos Creator、Unity 還是其他引擎這套核心邏輯都是通用的。接下來我們就拋開引擎外殼直擊算法內核看看如何優(yōu)雅地解決這個經典問題。2. 算法核心思想從“全盤掃描”到“增量檢測”的范式轉變在深入代碼之前我們必須先統一思想。傳統的“消除條件判別”通常發(fā)生在玩家操作交換兩個格子之后流程是這樣的交換兩個格子的數據。遍歷整個棋盤的所有行和所有列檢查是否存在連續(xù)三個或以上相同的元素。如果找到記錄這些格子的位置準備消除。如果沒有找到則執(zhí)行“回退”操作將兩個格子交換回來。這個方法的問題顯而易見效率低下。無論玩家交換的是左上角還是右下角的格子算法都要檢查棋盤上每一個位置。在一個10x10的棋盤上就是100個格子的檢查而且每次操作后都要進行。當游戲需要每幀處理多個邏輯判斷時這會成為性能熱點。更關鍵的是邏輯容易遺漏?？紤]一個“十字形”消除一個棋子同時參與橫向和縱向的消除簡單的行列遍歷可能會在記錄消除列表時去重不當導致后續(xù)計算獎勵分數或觸發(fā)連鎖消除時出錯。我們提出的“增量檢測”算法其核心思想是一次有效的操作其影響范圍是有限的。玩家交換了兩個棋子A和B那么可能產生新消除的只可能是與A、B棋子相關的行和列。具體來說是棋子A所在的行和列以及棋子B所在的行和列。絕大多數的消除情況都發(fā)生在這四條線上。因此算法的第一步從“掃描全世界”縮小為“偵查四條線”。但這還不夠我們還需要在這四條線上以交換點為中心向兩端進行“擴散檢查”以找出所有可能的連續(xù)組合。這就是算法的骨架定位變化點 - 鎖定檢測線 - 雙向擴散尋找連續(xù)區(qū)間。3. 數據結構與準備工作為高效判別打下基礎在實現算法前我們需要設計好棋盤的數據結構。這里不依賴任何特定引擎的組件用一個二維數組來代表棋盤邏輯狀態(tài)是最清晰的。// 假設我們的棋盤是 8x8用數字代表不同的寶石類型0代表空位 const BOARD_SIZE 8; let gameBoard Array.from({ length: BOARD_SIZE }, () new Array(BOARD_SIZE).fill(0)); // 初始化棋盤隨機生成寶石例如1-6種類型 function initBoard() { for (let r 0; r BOARD_SIZE; r) { for (let c 0; c BOARD_SIZE; c) { // 避免初始狀態(tài)就出現可消除的情況需要一個簡單的校驗 gameBoard[r][c] getRandomTypeWithoutMatch(r, c); } } }這里有一個新手容易忽略的關鍵點棋盤的初始化。你不能簡單地用完全隨機數填充棋盤否則極大概率一開局就存在大量可消除項這不符合游戲設計。因此getRandomTypeWithoutMatch需要實現一個“無匹配生成”邏輯。通常的做法是在為當前位置(r, c)隨機選擇一個類型時檢查其左側兩個格子(r, c-1), (r, c-2)和上方兩個格子(r-1, c), (r-2, c)的類型。如果即將生成的類型與它們連續(xù)相同則重新隨機直到找到一個不會造成初始匹配的類型。這是一個細節(jié)但決定了游戲的基礎體驗。接下來我們需要定義“交換操作”。交換不僅僅是交換數組中的數據在判別之前我們還需要記錄這次交換的“元信息”即兩個棋子的坐標這是我們進行增量檢測的輸入。/** * 嘗試交換兩個格子 * param {number} r1 格子1的行 * param {number} c1 格子1的列 * param {number} r2 格子2的行 * param {number} c2 格子2的列 * returns {Array} 返回一個數組第一個元素是布爾值是否成功消除第二個元素是消除的格子坐標列表 */ function trySwap(r1, c1, r2, c2) { // 1. 校驗是否相鄰上下或左右 if (!((Math.abs(r1 - r2) 1 c1 c2) || (Math.abs(c1 - c2) 1 r1 r2))) { return [false, []]; } // 2. 執(zhí)行邏輯上的交換 [gameBoard[r1][c1], gameBoard[r2][c2]] [gameBoard[r2][c2], gameBoard[r1][c1]]; // 3. 核心增量檢測消除條件 let matchCells checkForMatchesAfterSwap(r1, c1, r2, c2); // 4. 如果沒有消除交換回來 if (matchCells.length 0) { [gameBoard[r1][c1], gameBoard[r2][c2]] [gameBoard[r2][c2], gameBoard[r1][c1]]; return [false, []]; } // 5. 返回成功及消除列表 return [true, matchCells]; }4. 核心判別算法實現四線掃描與雙向擴散現在來到最核心的部分checkForMatchesAfterSwap函數。它的任務是根據兩個交換棋子的新位置檢查四條線A的行、A的列、B的行、B的列上是否形成了新的連續(xù)匹配。注意這里有一個極其重要的思維轉換。檢查的不是“棋盤上所有匹配”而是“因這次交換而新產生的匹配”。因此我們的檢查必須圍繞交換后的新棋子進行。function checkForMatchesAfterSwap(r1, c1, r2, c2) { // 使用Set來存儲消除格子的坐標避免重復比如一個棋子同時參與橫豎消除 let matchSet new Set(); // 檢查第一個棋子新位置所在的行和列 findMatchesInLine(r1, c1, true, matchSet); // 檢查行 findMatchesInLine(r1, c1, false, matchSet); // 檢查列 // 檢查第二個棋子新位置所在的行和列 findMatchesInLine(r2, c2, true, matchSet); findMatchesInLine(r2, c2, false, matchSet); // 將Set轉換為數組返回 return Array.from(matchSet); }關鍵的findMatchesInLine函數實現了“雙向擴散”查找。它的思路是給定一個中心點(centerR, centerC)和一個方向isRow為 true 表示檢查行從中心點分別向左/右或上/下延伸找到所有與中心點類型相同的連續(xù)格子從而確定一個連續(xù)的“區(qū)間”。/** * 在一條線上查找包含中心點的所有匹配 * param {number} centerR 中心點行坐標 * param {number} centerC 中心點列坐標 * param {boolean} isRow true表示檢查行false表示檢查列 * param {Set} matchSet 用于存儲結果的集合 */ function findMatchesInLine(centerR, centerC, isRow, matchSet) { const targetType gameBoard[centerR][centerC]; if (targetType 0) return; // 空位不參與匹配 let startIndex, endIndex; if (isRow) { // 檢查行固定行號centerR變化列號 // 向左找起點 startIndex centerC; while (startIndex - 1 0 gameBoard[centerR][startIndex - 1] targetType) { startIndex--; } // 向右找終點 endIndex centerC; while (endIndex 1 BOARD_SIZE gameBoard[centerR][endIndex 1] targetType) { endIndex; } // 判斷連續(xù)長度是否3 if (endIndex - startIndex 1 3) { for (let c startIndex; c endIndex; c) { matchSet.add(${centerR},${c}); } } } else { // 檢查列固定列號centerC變化行號 // 向上找起點 startIndex centerR; while (startIndex - 1 0 gameBoard[startIndex - 1][centerC] targetType) { startIndex--; } // 向下找終點 endIndex centerR; while (endIndex 1 BOARD_SIZE gameBoard[endIndex 1][centerC] targetType) { endIndex; } // 判斷連續(xù)長度是否3 if (endIndex - startIndex 1 3) { for (let r startIndex; r endIndex; r) { matchSet.add(${r},${centerC}); } } } }這個算法的精妙之處在于高效它只檢查了最多4條線每條線的檢查通過雙指針startIndex和endIndex一次遍歷完成復雜度是O(n)n是棋盤邊長。相比全盤掃描的O(n2)在棋盤稍大時優(yōu)勢巨大。準確雙向擴散的方式確保了只要中心點位于一個連續(xù)序列中無論它在序列的哪個位置開頭、中間、結尾都能被完整地找出來。無重復使用Set存儲坐標字符串如“3,5”自動處理了一個棋子同時存在于橫向和縱向消除組的情況避免了后續(xù)邏輯的復雜性。5. 算法擴展支持特殊消除形狀與連鎖反應基礎的三消邏輯實現了但現代消消樂游戲還有更多花樣比如“L型”、“T型”消除通常有額外獎勵以及消除后空位掉落新棋子引發(fā)的“連鎖反應”。我們的算法框架可以很好地支持這些擴展。5.1 支持“L型”和“T型”消除所謂“L/T型”消除本質上是一個棋子同時參與了一個橫向消除組長度3和一個縱向消除組長度3。在我們的算法中這個棋子會被matchSet記錄兩次來自行檢查和列檢查但由于Set的去重特性它只出現一次。我們需要在判斷“特殊消除”時識別出這類棋子?？梢栽赾heckForMatchesAfterSwap函數返回后增加一個后處理步驟function getSpecialMatches(matchCellsArray) { let specialMatches []; let cellCountMap new Map(); // 記錄每個坐標被匹配到的方向數 // 重新檢查四條線這次記錄每個格子被匹配到的“方向” let tempSet new Set(matchCellsArray); // ... 這里需要重構 findMatchesInLine使其不僅能加入Set還能記錄某個格子是因行匹配還是列匹配被加入的。 // 簡化邏輯如果一個格子的坐標在 matchCellsArray 中 // 并且我們通過查找發(fā)現它同時存在于一個橫向匹配組長度3和一個縱向匹配組長度3中 // 那么它就是特殊消除棋子。 // 這需要更精細的數據結構來記錄匹配組信息而非單個格子。 }更實用的方法是修改findMatchesInLine讓它除了向matchSet添加單元格外還向一個matchGroups數組添加信息記錄每一個匹配組的起始、結束坐標和方向。然后遍歷所有匹配組尋找那些在橫、縱方向上有交集且交集點相同的組該交點即為特殊消除棋子。5.2 連鎖反應檢測連鎖反應是消除游戲的樂趣來源。實現它的關鍵在于當本輪消除的格子被清空設為0后上方的格子會“掉落”填補空位然后需要檢查這些“新掉落”的棋子是否形成了新的可消除組合。這個過程是一個循環(huán)消除并掉落將matchCells中的格子清空然后模擬物理掉落讓上方非空的格子逐行下落。生成新棋子在棋盤頂部空缺的位置生成新的隨機棋子。再次檢測注意這里不能再用增量檢測了。因為掉落和生成影響了整個棋盤的多列影響范圍很大。此時一個可靠且簡單的方法是進行一次全盤掃描。由于連鎖反應通常不會無限進行一般2-3輪且發(fā)生在消除動畫之后玩家感知不強一次全盤掃描的性能開銷是可以接受的。循環(huán)如果全盤掃描又發(fā)現了新的可消除組合則重復步驟1-3直到棋盤穩(wěn)定無新匹配。function cascadeCheck() { let hasNewMatch true; let allMatches []; while (hasNewMatch) { hasNewMatch false; // 進行一次全盤掃描查找所有匹配 let newMatches findAllMatchesOnBoard(); if (newMatches.length 0) { allMatches allMatches.concat(newMatches); // 消除這些格子 removeCells(newMatches); // 執(zhí)行掉落和新棋子生成 applyGravityAndFill(); hasNewMatch true; } } return allMatches; // 返回連鎖消除的所有格子 } // 全盤掃描函數僅在連鎖檢測時使用 function findAllMatchesOnBoard() { let matchSet new Set(); // 檢查所有行 for (let r 0; r BOARD_SIZE; r) { // 使用類似 findMatchesInLine 的邏輯但以每個格子為起點進行檢查優(yōu)化 // 更高效的方式是遍歷每行/每列使用“滑動窗口”一次找出所有連續(xù)段 let count 1; for (let c 1; c BOARD_SIZE; c) { if (c BOARD_SIZE gameBoard[r][c] gameBoard[r][c-1] gameBoard[r][c] ! 0) { count; } else { if (count 3) { for (let k c - count; k c; k) { matchSet.add(${r},${k}); } } count 1; } } } // 檢查所有列邏輯類似 // ... return Array.from(matchSet); }實操心得在連鎖檢測中使用全盤掃描是業(yè)界常見做法它邏輯簡單可靠避免了增量檢測在復雜掉落局面下可能出現的邊界情況遺漏。將“玩家操作后的即時判別”和“連鎖反應檢測”采用不同策略增量 vs 全盤是性能與魯棒性之間的一個很好平衡。6. 性能優(yōu)化與邊界情況處理即使算法核心很高效在實際項目中仍需注意一些優(yōu)化點和坑。6.1 預計算與緩存對于需要頻繁判斷的操作比如“提示系統”尋找當前棋盤所有可交換的對如果每次都模擬交換并調用判別算法開銷很大?？梢砸胍粋€“潛在匹配”的緩存機制。例如遍歷棋盤只檢查每個棋子與其右方、下方棋子交換后是否可能產生消除。將結果緩存起來當玩家一段時間無操作時直接從這個緩存里取一個結果作為提示。棋盤變化后消除、掉落再更新緩存。6.2 邊界情況空位與不可交換棋子我們的算法假設棋盤是充滿的。但在消除后會有空位值為0。findMatchesInLine函數開頭已經判斷了targetType 0則直接返回這是正確的因為空位不應該參與匹配。同時有些游戲有“障礙物”或“冰塊”等不可交換的棋子類型在交換校驗 (trySwap) 和匹配判斷時都需要將它們排除在外。6.3 交換回退的細節(jié)在trySwap中如果檢測沒有產生消除我們需要交換回來。這里要確保用于檢測的gameBoard狀態(tài)是交換后的而回退操作必須精確地還原。在復雜的項目里棋盤數據可能關聯著視圖組件需要同時更新數據層和視圖層確保狀態(tài)同步。6.4 關于“同時消除”的判斷我們的算法使用Set存儲坐標自動處理了一個格子同時處于橫豎兩個消除組的情況。但在計算得分、播放特效時你可能需要知道這是一個“十字消”還是普通的兩個消除。這就需要如前所述記錄更詳細的匹配組信息而不僅僅是單個格子集合。7. 在Cocos Creator中的集成要點雖然算法是引擎無關的但在 Cocos Creator 中集成時有一些實踐細節(jié)數據與視圖分離gameBoard二維數組是你的數據模型。每個棋盤格子對應一個cc.Node例如一個Sprite組件顯示寶石圖片這是視圖。所有邏輯判斷基于數據模型。操作成功后再同步更新視圖節(jié)點的位置、精靈幀和播放動畫。操作響應在trySwap函數中不要直接執(zhí)行視圖交換。應該先進行邏輯判斷。如果返回[true, matches]再執(zhí)行播放兩個棋子交換的動畫。播放matches中所有棋子的消除動畫如縮放、淡出。在消除動畫結束后觸發(fā)掉落邏輯更新數據模型并播放棋子掉落的動畫。掉落完成后調用cascadeCheck進行連鎖檢測。使用定時器管理流程消除、掉落、連鎖是一個序列化的動畫過程。使用setTimeout或schedule來管理這些步驟的時序讓玩家能清晰地看到每一步反饋而不是所有變化瞬間完成。資源管理預加載消除、掉落等音效和粒子特效資源在適當時機播放能極大提升游戲體驗。這套“增量檢測判別算法”是我從早期全盤掃描的卡頓到后來各種邊界BUG的修復中逐步提煉出來的。它的優(yōu)勢不在于用了多高深的數據結構而在于它精準地抓住了問題域的特點——局部性并以此設計了高效的解決方案。希望這次深入的拆解能幫你下次實現自己的三消游戲時直接繞開那些深坑寫出既高效又健壯的代碼。記住好的游戲手感往往就藏在這些基礎算法的細節(jié)里。