劉宏義，肖 瑜

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

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

1 高斯隨機(jī)性生成算法

中央極限定理指出K個在區(qū)間［－1，1］均勻隨機(jī)數(shù)的和將逼近一個以0為中心、標(biāo)準(zhǔn)偏差為的高斯分布。比如說，如果你將3個均勻隨機(jī)數(shù)相加，它們的分布將以0為中點，標(biāo)準(zhǔn)偏差=1.0(這樣非常便利，因為中點和標(biāo)準(zhǔn)偏差與一個標(biāo)準(zhǔn)的正態(tài)分布一致)。以下的偽代碼通過將3個32位的帶符號隨機(jī)數(shù)(通過一個非?？焖俚漠惢蛞莆籔RNG［4］生成)相加來生成一個高斯分布。

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

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

2 高斯分布

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

圖1 鐘形曲線

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

3 模擬彈道軌跡

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

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

圖2 彈著點的高斯分布圖

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

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

4 高斯隨機(jī)性的其他應(yīng)用

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

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

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

5 結(jié)束語

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

［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.