基于高斯隨機性的彈道軌跡仿真

劉宏義，肖 瑜

(中國人民解放軍邊防學院信息化研究實驗室，陜西 西安 710108)

一個非常流行的高質量GRNG是polar－rejection［2］。這個算法因被《Numerical Recipes in C》［97年出版］一書采錄而流行，并因為它最費時的操作只有一個對數操作和一個平方根操作而著名(它規避了最初Box－Mueller變換中所需要的sin和cos操作)。雖然這是一個很好的GRNG，但是還有更快的算法。Ziggurat方法［3］是第二流行的GRNG，并經常被列為在速度和質量的平衡上做得最好的算法［6］。它比polar－rejection算法要快，因為它使用了一個大小為1 kB的查詢表并且極少調用超越函數。但是，對于游戲開發來說，訪問這些查詢表會污染數據緩存，從而導致實際運行比使用polar－rejection反而更慢。因為在大多數平臺上相對于CPU的速度，訪問內存的代價很高。舉例來說，當Ziggurat方法在高速執行，它的查詢表就會將游戲程序中的其他數據擠出緩存，從而減緩整個游戲的速度，相對polar－rejection更甚。以上兩種方法對于游戲程序都不太合適，最佳的方法是一種簡單高效的技術，被稱為中心極限定理(central limit theorem)，有時候也被叫作均勻數和(sum－of－uniforms)［6］。這個算法采用一些均勻隨機數，比如，一些由一個像rand()這樣的PRNG產生的隨機數，并將它們相加。根據中央極限定理，這些均勻隨機數的和將產生一個高斯分布隨機數。

1 高斯隨機性生成算法

中央極限定理指出K個在區間［－1，1］均勻隨機數的和將逼近一個以0為中心、標準偏差為的高斯分布。比如說，如果你將3個均勻隨機數相加，它們的分布將以0為中點，標準偏差=1.0(這樣非常便利，因為中點和標準偏差與一個標準的正態分布一致)。以下的偽代碼通過將3個32位的帶符號隨機數(通過一個非常快速的異或移位PRNG［4］生成)相加來生成一個高斯分布。

函數gaussrand()返回一個區間［－3.0，3.0］內的雙精度數。如果想要一個在區間［－1.0，1.0］內的數，只需簡單地將結果除以3.0(這會相應地將標準偏差收縮為0.33)。這個分布大致遵守68－95－99.7法則，但由于分布的尾部丟失，這個特定算法的分布實際是66.7－95.8－100。

對更多的數值(增加K)求和可使中心極限定理方法更為精確，尤其是在3個標準偏差之外的尾部。但是，這會使得算法更慢而又沒有太大的好處，因為通常并不關心尾部。

2 高斯分布

像rand()這樣的隨機數生成器可以產生均勻分布，在給定范圍中任意一個給定數字都將以相同(或者均勻)的概率出現。比如，在區間［0，1］，得到0.3和0.6的概率是一樣的。而高斯分布有時也被稱為正態分布，傾向于以0為中心附近的正負數。當這個分布的標準偏差為1.0時，我稱之為標準正態分布，如圖1所示。這個分布也經常因它的形狀被稱為鐘形曲線。

圖1 鐘形曲線

圖1是以0為中點，標準偏差為1.0的高斯分布。水平軸表示所生成的隨機數值，而豎直軸表示任意特定值的出現概率，這個分布的尾巴是3個偏差之外的極小概率出現的數值(＜－3.0或＞3.0)。為更好地理解該圖，需要了解68－95－99.7法則。根據這個法則，68%的值將落在距離中點一個標準偏差的區間［－1，1］，95%的值落在兩個標準偏差區間［－2，2］，而99.7%的值落在3個標準偏差區間［－3，3］區間。其余的0.3%落在這個區間之外，而得到在±4.0之外的數字只有少于百萬分之一的概率。

3 模擬彈道軌跡

無論是開槍射擊或者是射箭，目標靶上的彈著點總是散布在靶心周圍，只有個別點偏離得很遠。這類彈著點分布不是由rand()產生的，它是一種特殊的隨機性。研究發現有一些隨機數生成器可產生這類散布現象，這就是非常高效的高斯隨機數生成器。

在軍事游戲GRNG的一個理想應用就是為發射軌跡加上隨機變動。如上所述，發射物體，像子彈和箭都遵循高斯分布的變動。但是，所用的高斯分布必須拓展到2D，如圖2所示。

圖2 彈著點的高斯分布圖

在圖2(a)展示了一個在2D中的高斯概率分布。圖2(b)是一個30發子彈 一個高斯分布的擾動圖。因為這些圓環是以一個和兩個標準偏差距離擺放的，所以基本上68%的彈點在最小的環內，而95%的彈點在第二小的環內圖2中的分布是使用極坐標生成的。這樣每個2D點就需要兩個隨機數:一個角度和一個距離。在圖2中的子彈是這樣產生的:先生成一個區間［0，2π］內均勻隨機的角度，然后生成一個區間［－1，1］內的高斯隨機數，取其絕對值作為距離。通過使用一均勻隨機數作為角度，可以確保子彈均勻分布在中心周圍的各個角度上。而使用一個高斯隨機數作為距離，就可以確保子彈都集中在中心附近，遵守一個正態分布和68－95－99.7法則。

圖2中的2D分布從技術上來說并不是一個2D高斯分布。一個真正的2D高斯分布是通過兩個高斯隨機數在笛卡兒坐標下描點繪制出來。這個分布在統計中很有用，但并不適合彈道軌跡的建模。

4 高斯隨機性的其他應用

高斯隨機性不僅可應用于彈道軌跡變化，也可以應用在其他游戲領域。比如說，有多個人物或者車輛在一起移動，可能會看見步調一致的移動，這時可以將各個個體的加速度、最大速度或者動畫速度通過使用一個GRNG來擾亂開從而避免。這樣就可以產生一些在平均值附近的小差異來破壞同步的移動或者動畫。結果只會產生很小的差異，并且極少的例外。

GRNG的另一個應用是用來擾亂各個人物、樹或者建筑的高度。如果通過算法控制游戲中的幾何物體，那使用一個GRNG就可以產生很真實的差異。當游戲每時每刻都可以看見的很多物體，你又需要很自然的差異化時，這個方法就非常有用。通常，許多物理特性或者屬性都是在一個平均值附近隨機變化的。如果使用高斯分布來模擬，都會有較好的效果。

為什么許多自然中的分布都遵循高斯分布呢?比如人類智商或者樹的高度?中心極限定理給了暗示。當有許多均勻的隨機因素作用于一個給定的屬性時，這個屬性的分布將變得更為正態。雖然這只是自然界中大多數系統的一個粗略簡化，但這闡明了這么多屬性和系統大致展現出高斯分布的原因。可以將自然界中的許多屬性大致歸結為許多小的、相對獨立的因素疊加作用于一個給定的屬性。

5 結束語

通過中心極限定理為游戲生成高斯隨機性是相當簡單和高效的。但許多游戲程序員甚至都不知道這類隨機數生成器，因此，最大的挑戰在于簡單地將方法描述出來，并讓開發人員了解到這個工具的存在。許多傾向于具有正態分布的物理系統和特性都可以使用高斯隨機性來建模。通過在極坐標中組合均勻隨機性和高斯隨機性，仿真像彈道軌跡的變動是可以輕松實現的。

［1］BOX G E P，MULLER M E.A note on the generation of random normal deviates［J］.The Annals of Mathematical Statistics，1958，9(2):610 －611.

［2］KNOP R.Remark on algorithm 334［g5］:normal random deviates［J］.Commun.ACM，1969，12(5):31 －36.

［3］MARSAGLIA G，TSANG W W.The ziggurat method for generating random variables［J］.Journal of Statistical Software，2000(5):1001－1008.

［4］MARSAGLIA，GEORGE.Xorshift RNGs［J］.Journal of Statistical Software，2003(8):291 －294.

［6］PRESS W H，TEUKOLSKY S A，VETTERLING W T，et al.Numerical recipes in C［M］.2nd edition.Cambridge:Cambridge University Press，1997.

［6］THOMAS D B，LEONG P G W，LUK W，et al.Gaussian random numbergenerators ［C］.ACM ComputingSurveys 39，2007.