昨天我們學會了怎麼用內積檢測角色圓與彈道的碰撞,用這個方法可以完整搜集一個飛得很快的物件和遊戲中一般物件的碰撞事件。
不過在一些較為少見的情況下,遊戲也可能需要知道兩個速度飛快的物件之間的碰撞,比如森林勇士的強弓要能夠把火箭炮擊落,就需要更強大的碰撞檢測法。
想要讓兩個速度很快的物件進行碰撞檢測,就需要把這些物件在每一幀更新時的位置變化先儲存為線段,然後在這一串線段之間兩兩互找,看看其中有沒有一對相交,線段相交就代表碰撞的發生。
昨天我們運用了向量內積的力量,而今天為了要檢測線段有沒有相交,就需要藉助向量的另外一個運算-平面向量的行列式。
平面向量的行列式也稱為平面向量的外積,不過外積在其他維度的向量上有別的意義,為了不混淆,我們還是用行列式來稱呼這個運算。
兩個向量 和 的行列式可以這樣表示:
而行列式計算出來的結果是一個數值,計算方法是將行列式中的四個數字,依對角線兩兩相乘,再把兩個對角線相乘的結果相減。
/** 計算兩個向量的行列式 */
function vectorsDeterminant(vec1: Point, vec2: Point): number {
return vec1.x * vec2.y - vec2.x * vec1.y;
}
接著同學們可能又要問了「小哈,你不是說幾何數學的公式都有它在幾何上的意義嗎?那外積行列式又代表著這兩個向量的什麼關係?」
有的!兩個向量的行列式產出的數值,就是第二個向量在第一個向量上滑動所掃過的平行四邊形的有向面積(上圖綠色面積)。面積就面積,為什麼說是有向面積呢?因為行列式產出的值有正有負,如果向量a轉至向量b的夾角大於0,則行列式的值是正的,反之為負。所以如果 是正的,那麼 就必定是負的。
正確地說,行列式的正負號是由sin(θ)的正負號所支配。
那問題又來了!這個行列式的有向面積跟兩條線是否相交又有啥關係?
我們用上圖的向量AB和CD來介紹行列式是怎麼幫助我們檢測兩線的相交。假設這兩條線有一個交點T,那麼兩線相交的條件有三個:
後面兩個條件看字面就知道是同一套檢查方法,只是檢查時使用不同的向量順序而已。我們還需要在上圖加一條綠色的輔助線CA,這個向量CA在檢測的過程中占有舉足輕重的地位。
既然我們已經被劇透了要使用向量的行列式,那麼就來取個向量AB和CD的行列式,看看他們夾住的灰色面積能派上什麼用場。
有了灰色面積,我們就可以檢查第一項相交的條件,若灰色面積等於0,代表兩條向量平行,也就不可能有交點。
事實上,兩線平行也有可能代表兩線重疊,不過這種情況不多見,除非遊戲對這種情況很敏感,不然可以省略重疊的檢測。
然後看好接下來的操作喔!
我們沿著向量CA的方向切掉這塊面積的一小塊,接著平移向量CA到右側的D點,也沿著向量切開一小塊。然後移動這兩小塊面積到各自的另一邊,重新組合成另一個面積完全相同的平行四邊形,這個新的四邊形的面積仍然是 。
接著我們再用另一個行列式 算出另一塊面積(紅色陰影)。
按上圖,很容易就能看得出,紅色陰影和灰色面積的比例,就是AT長度與AB長度的比例,這個比例只要介於0到1之間,就表示T在AB之間了,對吧!
我們把這個想法寫成程式碼看看。
/** 先定義一個線段的類別 */
class Line {
constructor(
public start: Point, // 起點
public end: Point // 終點
) { }
// 計算這個線段的向量
get vector(): Point {
// 向量 = 終點 - 起點
return this.end.sub(this.start);
}
}
/** 檢查交點是不是在第一個向量的中間 */
function isIntersectionWithinVector1(
AB: Line, // 第一條線段
CD: Line // 第二條線段
): boolean {
// 輔助線CA
let CA = new Line(CD.start, AB.start);
// ABxCD行列式
let ABxCD = vectorsDeterminant(AB.vector, CD.vector);
if (ABxCD == 0) {
// ABxCD==0的話,代表兩線平行,沒交點
return false;
}
// CDxCA行列式
let CDxCA = vectorsDeterminant(CD.vector, CA.vector);
// 兩個面積的比值
let areaRatio = CDxCA / ABxCD;
// 這個比值要介於0到1之間,才可能有交點
return areaRatio >= 0 && areaRatio <= 1;
}
我們把遊戲中兩個快速移動的物件,以上一幀的位置和目前位置變成兩個線段,再把這兩個線段放入剛剛寫好的檢測函式,就能知道碰撞是不是發生了。
/** 假設我們有兩條線,分別代表兩個物件的移動軌跡
* 這裏的obj1LastPos,obj1CurrentPos等等是虛構的變數
* 用來代表物件上一幀的位置與目前的位置
*/
let line1 = new Line(obj1LastPos, obj1CurrentPos);
let line2 = new Line(obj2LastPos, obj2CurrentPos);
// 先檢查交點是不是在line1上
let isTonLine1 = isIntersectionWithinVector1(line1, line2);
// 再檢查交點是不是在line2上
let isTonLine2 = isIntersectionWithinVector1(line2, line1);
if (isTonLine1 && isTonLine2) {
console.log('火箭炮被飛箭射爆啦!');
}
再次感謝幾何向量的魔法,賜給我們遊戲強大的力量!
CG示範專案
示範程式中,移動滑鼠來畫線,滑鼠左鍵可改變畫線的起點。