J2ME 遊戲碰撞檢測算法大全：矩形、圓形、像素級與高速穿透處理

碰撞檢測分層策略

遊戲幀循環中，**廣義檢測 (Broad Phase) → 窄相檢測** 兩級過濾：

1. 空間分區：均勻網格 / QuadTree / Sweep-and-Prune，快速剔除遠離對象對。
2. 包圍體檢測：AABB (軸對齊包圍盒) / 圓形 / 凸多邊形，極廉價數學判斷。
3. 精確檢測：像素級 Alpha 測試 / SAT (分離軸定理) / 連續碰撞 (CCD)，僅在包圍體相交時執行。

矩形 (AABB) 檢測 — 四種寫法效能遞增

// 1. 頂點包含法 (最慢，分支多)
boolean collide1(Rect a, Rect b) {
    return contains(a, b.x, b.y) || contains(a, b.x+b.w, b.y)
        || contains(a, b.x, b.y+b.h) || contains(a, b.x+b.w, b.y+b.h);
}

// 2. 分離軸法 (標準，無分支)
boolean collide2(Rect a, Rect b) {
    return !(a.y > b.y + b.h || b.y > a.y + a.h
          || a.x > b.x + b.w || b.x > a.x + a.w);
}

// 3. 中心距離法 (適合正方形/近似圓)
boolean collide3(Rect a, Rect b) {
    int dx = (a.x + a.w/2) - (b.x + b.w/2);
    int dy = (a.y + a.h/2) - (b.y + b.h/2);
    int rSum = (Math.max(a.w, a.h) + Math.max(b.w, b.h)) / 2;
    return dx*dx + dy*dy < rSum*rSum;
}

// 4. 頂點編碼法 (最快，預計算 min/max)
boolean collide4(int[] r1, int[] r2) { // r=[xMin,yMin,xMax,yMax]
    return !(r1[0] > r2[2] || r1[2] < r2[0] || r1[1] > r2[3] || r1[3] < r2[1]);
}

推薦 collide2 或 collide4：分支預測友好、指令少、無除法/開方。

圓形檢測

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

Sprite 像素級檢測 (LCdui Game API)

// Sprite 自帶方法：pixelLevel=true 僅檢測非透明像素重疊
boolean hit = spriteA.collidesWith(spriteB, true); // true=像素級, false=矩形級
// 注意：像素級極耗 CPU，僅在極少數關鍵對象 (主角 vs Boss) 使用。

高速穿透問題 (Tunneling) 解決方案

現象：子彈速度極快，幀間位移 > 目標厚度，導致單幀檢測錯過碰撞。

方案 1：掃掠體積 (Swept AABB)

// 計算時間區間 [tEntry, tExit] 內兩 AABB 重疊
// 參考：https://www.gamedev.net/tutorials/2d-game-physics/swept-aabb-collision-detection-and-response-r3084/
// 返回碰撞時間 t ∈ [0,1] 與法線
SweptResult sweptAABB(Rect a, Vec2 va, Rect b, Vec2 vb) { ... }

方案 2：子步長 (Sub-stepping)

int steps = Math.max(Math.abs(vx), Math.abs(vy)) / maxSize + 1;
for (int i=0; i