前言:
08年的時候, 寫過一個撞球遊戲, 用的是java, 不過代碼真的是用傳說中的神器notepad寫的(你信嗎? 其實是用GVIM寫的, ^_^), 很多類都在同一java檔案中編寫. 可見當時的JAVA水準真的不咋地, 時過進遷, 還是一樣的不咋地.
這邊是當時的CSDN下載下傳連結: java(撞球遊戲), 實作比較簡單. 後來寫過一個版本, 比這個要強大許多, 可惜源碼丢失了.
效果展示入下圖所示:
本文想講述下撞球遊戲中核心算法的實作, 以及遊戲AI的設計技巧. 當然自己也有個小願望, 希望能實作一個html5版的撞球遊戲.
基礎實體知識:
• 摩擦阻力
其滿足牛頓第二定律:
f = m * a
速度與加速度關系公式:
vt = v0 + a * t
地面摩擦力與運動物體的方向相反, 阻礙物體的向前運動.
• 動量守恒
假設物體A品質為m1, 速度為v1, 物體B品質為m2, 速度為v2, 碰撞後速度分别為v1', v2'.
則滿足動量守恒定律:
m1 * v1 + m2 * v2 = m1 * v1' + m2 * v2'
• 碰撞類型和能量守恒定律
1). 完全彈性碰撞
動能沒有損失, 則滿足如下公式:
1/2 * m1 * v1^2 + 1/2 * m2 * v2^2 = 1/2 * m1 * v1'^2 + 1/2 * m2 * v2'^2
注: 前後物體的動能保持均衡, 沒有其他能量的轉化.
結合之前的動量守恒定律, 我們可以進一步得到:
v1' = [(m1-m2) * v1 + 2 * m2 * v2] / (m1 + m2)
v2' = [(m2-m1) * v2 + 2 * m1 * v1] / (m1 + m2)
2). 完全非彈性碰撞
則存在其他能量的轉化, 動能不守恒.
且此時兩物體粘連, 速度一緻, 即v1'=v2', 此時動能損失最大.
3). 彈性碰撞
介于完全彈性碰撞和完全非彈性碰撞兩者之間. 動能有損失的.
實體模型:
撞球遊戲中, 最核心的就是其實體模型的抽象及其碰撞算法的執行過程了.
鑒于是2D版的撞球遊戲, 是以我們對實體模型做下簡化, 球運動的方向必然穿越球的中心.
把每個撞球抽象為圓(x, y, radius), 而撞球桌邊框抽象為線段((x1, y1), (x2, y2)).
• 碰撞檢測
1). 檢測球與球碰撞
我們假定球A(x1, y1, r), 球B(x2, y2, r). 則滿足條件:
(x1 - x2) ^ 2 + (y1 - y2) ^ 2 <= (2*r) ^ 2
則發生碰撞, 否則沒有發生碰撞
2). 檢測球與球台邊框碰撞
相對比較簡單. 求球心到邊框的垂直距離即可, 若小于等于則發生碰撞, 若大于則沒有.
• 碰撞反應
1). 球與球的碰撞反應
動量是向量, 其在正交的兩個方向上, 互相守恒. 我們選取兩球圓心的直線為x軸, 垂直于圓心直線的為y軸. 如上圖所述.
x軸上滿足動量守恒:
m1 * Vx + m2 * Ux = m1 * Vx' + m2 * Ux';
并假定兩球碰撞是完全彈性碰撞, 兩球品質相等m1=m2, 依據基礎實體知識篇的結論.
Vx' = [(m1-m2) * Vx + 2 * m2 * Ux] / (m1 + m2) = Ux;
Ux' = [(m2-m1) * Ux + 2 * m1 * Vx] / (m1 + m2) = Vx;
在X軸方向, 兩球交換速度, 而在Y軸方向, 兩球分速度不變.
Vy' = Vy;
Uy' = Uy;
最終碰撞後的速度公式為:
V' = Vx' + Vy' = Ux + Vy;
U' = Ux' + Uy' = Vx + Uy;
2). 球與邊框的碰撞反應
把撞球邊框視為品質無窮大, 則簡單把運動的球, 其在垂直邊框的分方向反向即可.
假定碰撞碰撞平面為x軸
Vx' = Vx;
Vy' = -Vy;
最終速度公式為:
V' = Vx' + Vy' = Vx - Vy;
碰撞執行算法:
遊戲的主循環往往遵循如下代碼結構:
while ( true ) {
game.update(time_interval);
game.render();
} 這個時間間隔(time_interval), 由遊戲的FPS來确定. 以24幀為例, 每40毫秒重新整理一次.
對于撞球本身而言, 若以該time_interval為更新周期, 使得運動的球體滿足:
Vt = V0 + a * t
運作距離為:
S = V0 * t + 1/2 * a * t^2.
然後來檢測球體是否發生了碰撞, 然後進行碰撞反應處理. 看似沒有問題.
但是當球體初速度很快時, 在time_interval中有可能, 發生穿越現象.
如下圖所展示的現象:
紫色球在t2時刻, 和藍球檢測到碰撞, 但實際上, 在紫球在t1~t2之間的某時刻和藍球發生了碰撞.
為了解決該問題, 在具體的算法中, 需要引入更細的時間分片slice, 該過程在具體的update中進行模拟.
整個撞球場景的更新函數:
void update(time_interval) {
while time_interval > 0:
// 碰撞檢測
if detectionCollide(time_interval, least_time, ball_pairs):
// 遊戲更新least_time
billiards.update(least_time)
// 對碰撞的兩球進行碰撞反應
collideReaction(ball_pairs=>(ball, other))
// time_interval 減少 least_time
time_interval -= least_time
else：
// 遊戲更新least_time
billiards.update(time_interval)
time_interval = 0
} /*
@brief
在time_interval 時間内, 傳回最先碰撞的球或撞球邊, 以及時間點
*/
bool detectionCollide(time_interval, least_time, ball_pairs) {
res = false;
least_time = time_interval;
foreach ball in billiards:
foreach otherBall in billiards:
// 求出兩球的距離
S = distance(ball, otherBall)
// 以某一球作為參考坐标系, 則令一球速度向量變為 U’=U-V
// 在圓心的直線作為x軸
Ux(relative) = Ux(other ball) - Vx(ball)
// 若該方向使得兩球遠離, 則直接忽略
if Ux(relative) < 0：
continue
// 某該方向使得兩球接近, 則可求其碰撞的預期時間點
A' = 2 * A; // 加速度為原來的兩倍
// 取兩者最小的時間點
delta_time = min(time_interval, Ux(relative) / Ax’)
// 預期距離 小于 兩球距離，則在time_interval中不會發生碰撞
if 1/2 * Ax’ * delta_time ^ 2 + Ux(relative) * delta_time < S - 2*r:
continue
// 解一進制二次方程, 使用二分搜尋逼近求解
res_time <= slove(1/2 * Ax’ * x ^ 2 + Ux(relative) * x = S - 2 * r)
if res_time < least_time:
ball_pairs <= (ball, otherBall)
least_time = res_time
res = true
foreach wall in billiards:
S = distance(ball, wall)
// 設垂直于平面的方向為x軸
if Vx < 0:
continue
// 取兩者最小的時間點
delta_time = min(time_interval, Vx / Ax)
// 預期距離 小于 兩球距離，則在time_interval中不會發生碰撞
if 1/2 * Ax * delta_time ^ 2 + Vx * delta_time < S - r:
continue
// 解一進制二次方程, 使用二分搜尋逼近求解
res_time <= slove(1/2 * A * x ^ 2 + Vx * x = S - r)
if res_time < least_time:
ball_pairs <= (ball, walll)
least_time = res_time
res = true
return res
} 原創文章請随便轉載。願和大家分享，并且一起進步。-- 江 coder