劉宏義，肖 瑜

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

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

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

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

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

對(duì)更多的數(shù)值(增加K)求和可使中心極限定理方法更為精確，尤其是在3個(gè)標(biāo)準(zhǔn)偏差之外的尾部。但是，這會(huì)使得算法更慢而又沒有太大的好處，因?yàn)橥ǔ２⒉魂P(guān)心尾部。

2 高斯分布

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

圖1 鐘形曲線

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

3 模擬彈道軌跡

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

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

圖2 彈著點(diǎn)的高斯分布圖

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

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

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

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

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

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

5 結(jié)束語

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