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