【javascript】泡泡龍游戲中反彈和查找匹配算法

引言

泡泡龍游戲的核心玩法依賴于物理碰撞與顏色匹配的算法實現。反彈效果需要模擬泡泡與邊界或障礙物的彈性碰撞，確保軌跡符合物理規律；匹配算法則需快速檢測相鄰同色泡泡，觸發消除邏輯。高效的處理方式直接影響游戲流暢度和玩家體驗。

以下主要介紹反彈與匹配算法的多種實現思路和代碼示例。

一、反彈物理計算

幾何變換法 Canvas/CSS 對稱反射,無需手動計算角度，適用于垂直邊界的反彈，屬于鏡像反射的簡化實現

（1）入射角度
計算鼠標相對與射擊器中心的角度

//得到一個從射擊器中心指向鼠標位置的角度值（單位：角度）
let iAngle = Math.abs((Math.atan2(ey - oy, ex - ox) * 180) / PI);
iAngle = Math.min(170, Math.max(10, iAngle)); //限制射擊角度在 10° ~ 170° 范圍內
iAngle = -angleToRadian(iAngle); //將角度轉換回弧度，并反向處理

//補充工具函數
const normalizeAngle = (angle: number) => {// 角度可能超出 [0°, 360°)，先歸一化：return ((angle % 360) + 360) % 360;
}const radianTOAngle = (radian: number) => {return radian * 180 / Math.PI;
}const angleToRadian = (angle: number) => {return angle * Math.PI / 180;
}

（2）反射角度

左右反彈通過x軸方向，左邊界反彈法線是x軸正方向，反射角度=-π -入射角度
右邊界法線是x軸負方向，反射角度= π -入射角度

前端角度轉換成數學角度，前端（CSS/Canvas）的旋轉角度和數學計算角度差異（如下圖），前端需要順時針轉90，方向從順時轉成逆時針取反，就得到90-前端角度=數學角度

圖1-前端角度數學角度對比圖

網上還有另外一種思路，垂直反射改變水平移動速度
shooterBubble.dx表示泡泡水平移動速度 shooterBubble.dx = -shooterBubble.dx; 實現水平方向反彈, 鏡像反射的簡化方式，適用于垂直邊界, 若原方向為 30°，碰到右邊界后變為 150°（即對稱角度）,實際上沒有計算角度，只是改變 x 軸方向。

向量計算法通用 2D/3D 反射精確，適用于任意方向

（1）概念

利用向量的點積（dot product）和叉積（cross product）計算角度，適用于任意方向的入射角計算。
點積（內積）返回一個標量（數值），用于計算夾角、投影、相似度（光照、碰撞檢測）。
叉積（外積）返回一個向量（在 3D 中），用于計算垂直方向、旋轉方向、面積（法線、扭矩、幾何判斷）。

點積定義為 a?b=∣a∣?∣b∣?cosθ, ∣a∣ 和 ∣b∣ 是向量的模, θ 是兩向量之間的夾角

在 2D 和 3D 中，點積的計算公式為：
(2D)a?b=ax bx +ay by (2D)
(3D)a?b=ax bx +ay by +az bz (3D)

function dotProduct(a, b) {return a.x * b.x + a.y * b.y; // 2D
}const a = { x: 1, y: 0 }; // 向右
const b = { x: 0, y: 1 }; // 向上const dot = dotProduct(a, b); // 0（垂直）
const angle = Math.acos(dot / (Math.hypot(a.x, a.y) * Math.hypot(b.x, b.y))); // 90°

（2）計算入射向量和法線向量：

入射向量 v1 = (x1, y1)
表面法線向量 n = (nx, ny)（垂直于反射面）

（3）計算反射向量（根據反射定律）：反射向量=v1?2×(v1?n)×n（其中 · 是點積）

（4）計算角度：

用 Math.atan2 計算反射向量與水平軸的夾角：Math.atan2(reflectedY, reflectedX)(這里需要注意在數學計算中使用的是弧度值)

function calculateReflectionAngle(incidentVec, normalVec) {const dot = incidentVec.x * normalVec.x + incidentVec.y * normalVec.y;const reflectedX = incidentVec.x - 2 * dot * normalVec.x;const reflectedY = incidentVec.y - 2 * dot * normalVec.y;return Math.atan2(reflectedY, reflectedX); // 返回弧度
}

復習三角函數
a 表示 “arc”（弧），即通過比值反推角度

函數	含義	范圍	場景
Math.sin(x)	正弦 (對邊/斜邊)	[-1, 1]	周期性運動、旋轉計算、波形生成
Math.cos(x)	余弦 (鄰邊/斜邊)	[-1, 1]	周期性運動、旋轉計算、波形生成
Math.tan(x)	正切 (對邊/鄰邊)	(-∞, ∞)	斜率計算、視角映射、透視校正
Math.asin(x)	反正弦	[-π/2, π/2]	角度反推、碰撞檢測
Math.acos(x)	反余弦	[0, π]	角度反推、碰撞檢測
Math.atan(x)	反正切	[-π/2, π/2]	簡單斜率計算
Math.atan2(x)	帶象限的反正切	[-π, π]	精準角度計算（自動處理象限）

二、迭代BFS算法

概念

BFS（Breadth-First Search 廣度優先搜索）是一種圖遍歷算法，它從根節點開始，先訪問所有相鄰節點，然后再依次訪問這些相鄰節點的相鄰節點，以此類推，逐層擴展。

核心思路
隊列數據結構：使用隊列來存儲待訪問的節點（下面代碼中queue）
層級遍歷：按照距離起始節點的層級順序訪問
避免重復訪問：使用標記數組或哈希表記錄已訪問節點（下面代碼中visited）

獲取六邊形相鄰布局節點

從左上開始按順時針方向進行遍歷，不要忘記進行邊界檢查

  getNeighborsTiles(newPao: Tile): Tile[] {// 定義6個相鄰方向（六邊形網格）// 順序：左上、右上、右、右下、左下、左const isEvenRow = (newPao.x % 2 === 0);const directions = [{ dx: -1, dy: isEvenRow ? -1 : 0, info: '左上' },{ dx: -1, dy: isEvenRow ? 0 : 1, info: '右上' },{ dx: 0, dy: 1, info: '右' },{ dx: 1, dy: isEvenRow ? 0 : 1, info: '右下' },{ dx: 1, dy: isEvenRow ? -1 : 0, info: '左下' },{ dx: 0, dy: -1, info: '左' }];const neighbors = [];// 按順時針方向遞歸檢查相鄰泡泡for (const dir of directions) {const nx = newPao.x + dir.dx;const ny = newPao.y + dir.dy;// 邊界檢查if (nx < 0 || nx >= this.maxRow ||ny < 0 || ny >= (nx % 2 === 0 ? this.maxCol : this.maxCol - 1)) {continue;}const pao = this.grid.cells?.[nx]?.[ny];// console.log(`${nx}-${ny}-${dir.info}`, pao);if (pao) neighbors.push(pao)}return neighbors}

查找所有相鄰的同色泡泡,返回需要消除的泡泡

查找過程:以當前停靠的泡泡為起點，查看周圍所有與它相鄰的泡泡，如果發現周圍有相同顏色（數字相同）的泡泡，那么就以這個泡泡為起點，繼續查看其周圍相鄰的泡泡…一直重復這個過程，直到周圍不再有相鄰的泡泡為止。時間和空間復雜度O(N)。

  searchRemovePaos(newPao: Tile): Tile[] {// 記錄所有相鄰的泡泡,六邊形布局以左上角泡泡為開始,順時針進行查找相鄰的泡泡const visited: Set<string> = new Set();//已訪問集合,避免重復查找；const queue: Tile[] = [newPao]; //BFS 隊列用于廣度優先查找；const removePaos: Tile[] = [];// 存放最終要消除的泡泡；// 起始泡泡先加入visited.add(`${newPao.x},${newPao.y}`);removePaos.push(newPao);while (queue.length > 0) {const current = queue.pop();console.log('查找current', current);if (!current) continue;const neighbors = this.getNeighborsTiles(current);for (const neighbor of neighbors) {const key = `${neighbor.x},${neighbor.y}`;if (visited.has(key)) continue; // 已經查過，跳過visited.add(key); // 標記為已訪問if (neighbor.color === current.color) {removePaos.push(neighbor); // 同色泡泡加入消除列表queue.push(neighbor);      // 并繼續擴散查找}}}return removePaos.length >= 3 ? removePaos : [];}

懸浮泡泡消除

使用BFS 遍歷查找所有與頂部相連的泡泡，再次遍歷整個網格，找出所有未與頂部相連的泡泡（懸空泡泡），并返回它們，時間和空間復雜度O(M × N)

  searchDropPaos() {const visited: Set<string> = new Set();//用于記錄已經訪問過的泡泡const connectedToTop: Set<string> = new Set();// 存儲和頂部相連的泡泡const queue: Tile[] = [];// BFS 隊列// 初始化隊列，將頂部的泡泡加入for (let y = 0; y < (0 % 2 === 0 ? this.maxCol : this.maxCol - 1); y++) {const topPao = this.grid.cells[0][y];if (topPao) {const key = `${0},${y}`;queue.push(topPao);visited.add(key);connectedToTop.add(key);}}// BFS 遍歷查找所有與頂部相連的泡泡：while (queue.length > 0) {const current = queue.shift();if (!current) continue;const neighbors = this.getNeighborsTiles(current);for (const neighbor of neighbors) {const key = `${neighbor.x},${neighbor.y}`;if (visited.has(key)) continue;visited.add(key);connectedToTop.add(key);queue.push(neighbor);}}// 只能從頂部出發，找到所有直接或間接與頂部相連的泡泡。但無法直接標記出 未與頂部相連 的泡泡// 需再次遍歷整個網格，找出所有未和頂部相連的泡泡const dropPaos: Tile[] = [];for (let x = 0; x < this.boxRow; x++) {const maxColInRow = x % 2 === 0 ? this.maxCol : this.maxCol - 1;for (let y = 0; y < maxColInRow; y++) {const pao = this.grid.cells?.[x]?.[y];if (pao) {const key = `${x},${y}`;if (!connectedToTop.has(key)) {dropPaos.push(pao);}}}}return dropPaos;}

擴展

另一種圖遍歷算法 DFS（Depth-First Search 深度優先搜索），它沿著一條路徑盡可能深入地搜索，直到無法繼續前進，然后回溯并嘗試其他路徑。

核心思路
棧數據結構：使用棧（遞歸調用棧或顯式棧）來存儲待訪問節點
深度優先：盡可能深地探索一條路徑
回溯機制：當無法繼續前進時返回上一個分叉點

遞歸DFS（隱式棧）

優點：①數據規模小（如二叉樹深度<1000）②代碼簡潔性優先
缺陷：①棧溢出風險：深度過大時（如1萬+層）會觸發Maximum call stack size exceeded ②函數調用比循環消耗更多資源

// 遞歸DFS（鄰接鏈表表示）
function dfsRecursive(graph, node, visited = new Set()) {console.log(node);       // 訪問節點visited.add(node);for (const neighbor of graph[node]) {if (!visited.has(neighbor)) {dfsRecursive(graph, neighbor, visited); // 遞歸調用, 這行是隱式使用調用棧（Call Stack）保存狀態 visited}}
}// 使用示例
const graph2 = {'A': ['B', 'C'],'B': ['D'],'C': ['E'],'D': [],'E': []
};
dfsRecursive(graph2, 'A'); // 輸出: A → B → D → C → E

迭代DFS（顯式棧）

優點：①避免棧溢出：棧大小由堆內存控制，可處理超深結構 ②性能更好：減少函數調用開銷 ③靈活控制：可隨時暫停/恢復遍歷
缺點：代碼可讀性低需手動管理狀態（循環推薦手動管理stack和visited ）

// 迭代DFS（顯式棧）顯式使用棧結構（數組）代替調用棧
function dfsIterative(graph, start) {const stack = [start];         // 顯式棧,模擬調用棧無深度限制（受限于堆內存而非調用棧）,通過push/pop操作實現棧操作const visited = new Set();// 減少函數調用開銷,可隨時暫停/恢復遍歷,更靈活while (stack.length > 0) {const node = stack.pop();    // 取棧頂if (visited.has(node)) continue;console.log(node);           // 訪問節點visited.add(node); // 通過循環推進// 逆序壓棧保證遍歷順序（與遞歸一致）for (let i = graph[node].length - 1; i >= 0; i--) {stack.push(graph[node][i]);}}
}// 使用相同的graph
dfsIterative(graph2, 'A'); // 輸出: A → C → E → B → D

特性	BFS	DFS
數據結構	隊列	棧（遞歸或顯式）
空間復雜度	O(V)（最寬層級）	O(V)（最長路徑）
最短路徑	可以找到（無權圖）	不一定能找到
實現方式	通常迭代實現	遞歸或迭代實現
適用場景	最短路徑、層級關系	拓撲排序、連通性檢測

總結

泡泡反彈使用Math.atan2(mouseY - SHOOTER_Y, mouseX - SHOOTER_X)計算鼠標相對于炮臺的發射角度，簡單的垂直方向反射可以直接用 PI 去計算，其他方向反射用向量計算法更準確。泡泡消除查詢匹配使用BFS，BFS 適合從頂部逐層向下擴展，天然符合“與頂部連接”的邏輯。更容易控制邊界條件：BFS 按層處理，適合六邊形網格這種結構較復雜的布局。DFS 不利于全局連通性判斷：DFS 更適合路徑探索或圖的連通性判定，但在這種網格結構中，BFS 更直觀、更高效。