J2ME 遊戲碰撞偵測算法入門：矩形與圓形碰撞數學原理與整數運算優化

碰撞偵測在遊戲中的核心地位

從「子彈擊中敵機」到「角色撞牆阻擋」，碰撞偵測是遊戲邏輯的基石。J2ME 平台無浮點運算 (CLDC 1.0) 或浮點效能極差 (CLDC 1.1 早期裝置)，演算法必須以整數運算為主，並避免開方、三角函數等昂貴操作。

算法一：軸對齊矩形碰撞 (AABB)

幾何定義：矩形 1 左上角 (x1, y1)、寬 w1、高 h1；矩形 2 左上角 (x2, y2)、寬 w2、高 h2。

數學條件：兩矩形中心點在 X 軸距離 ≤ 寬度和一半，且 Y 軸距離 ≤ 高度和一半。

| (x1 + w1/2) - (x2 + w2/2) | ≤ (w1 + w2) / 2
| (y1 + h1/2) - (y2 + h2/2) | ≤ (h1 + h2) / 2

整數優化實作 (避免除法與絕對值)：

public boolean rectCollide(int x1, int y1, int w1, int h1,
                           int x2, int y2, int w2, int h2) {
    // 分離軸定理 (SAT) 形式：任一軸投影不重疊即無碰撞
    if (x1 + w1 < x2) return false; // rect1 在 rect2 左側
    if (x2 + w2 < x1) return false; // rect1 在 rect2 右側
    if (y1 + h1 < y2) return false; // rect1 在 rect2 上方
    if (y2 + h2 < y1) return false; // rect1 在 rect2 下方
    return true; // 所有軸投影重疊 → 碰撞
}

算法二：圓形碰撞

幾何定義：圓 1 中心 (x1, y1)、半徑 r1；圓 2 中心 (x2, y2)、半徑 r2。

數學條件：兩圓心距離 ≤ 半徑和。

√[(x1-x2)² + (y1-y2)²] ≤ r1 + r2

整數優化：雙方同乘平方，消除開方運算：

(x1-x2)² + (y1-y2)² ≤ (r1+r2)²

完整實作：

public boolean circleCollide(int x1, int y1, int r1,
                             int x2, int y2, int r2) {
    int dx = x1 - x2;
    int dy = y1 - y2;
    int rSum = r1 + r2;
    return (dx*dx + dy*dy) <= (rSum * rSum);
}

進階：矩形與圓形混合碰撞

找出矩形上距離圓心最近的點，再判斷該點是否在圓內：

public boolean rectCircleCollide(int rx, int ry, int rw, int rh,
                                 int cx, int cy, int cr) {
    // 最近點座標
    int nearestX = Math.max(rx, Math.min(cx, rx + rw));
    int nearestY = Math.max(ry, Math.min(cy, ry + rh));
    
    int dx = nearestX - cx;
    int dy = nearestY - cy;
    return (dx*dx + dy*dy) <= (cr * cr);
}

複雜形狀碰撞策略：組合碰撞體

廣階碰撞優化 (Broad Phase)

細節檢測前快速剔除明顯不相交物件：

1. 網格劃分：遊戲世界劃分均勻網格，物件只檢測同格/鄰格物件
2. 四叉樹：動態空間分割，適合物件分佈不均勻場景
3. 掃描線：X/Y 軸排序掃描，適合大量平行移動物件
4. 包圍球/箱快速剔除：先用大尺寸包圍體檢測，通過再精細檢測

J2ME 實作注意事項

• 整數溢位：`dx*dx` 可能超過 `Integer.MAX_VALUE` (座標 > 46340)，長距離場景用 `long` 運算
• 座標系統：螢幕座標原點左上角，Y 軸向下，數學公式不變
• 幀邊界處理：高速物體可能「穿牆」，需掃描軌跡線段或減小時間步長
• 碰撞回應分離：偵測只回傳 true/false，位置修正、速度反彈交由物理系統處理

測試驗證用例

// 矩形重疊
assertTrue(rectCollide(0,0,10,10, 5,5,10,10));
// 矩形相切 (邊界視為碰撞)
assertTrue(rectCollide(0,0,10,10, 10,0,10,10));
// 圓形內含
assertTrue(circleCollide(0,0,10, 0,0,5));
// 圓形外離
assertFalse(circleCollide(0,0,5, 20,0,5));

掌握這些基於整數運算的基礎碰撞算法，是 J2ME 遊戲開發者構建高效物理系統的起點。現代引擎雖封裝了複雜的物理模擬，但核心數學原理始終不變。