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