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