2010年6月11日 星期五

一個「偽」亂數的演算法

這是前一陣子從 "Game Code Complete" 裡看到的演算法。

說是「偽」亂數,因為它並不夠亂。但是它非常節省效能。

 

需求是這樣:

有某個數量的獎品,我們希望每次亂數取出一個來,不能重複,而且每個都要取到。

演算法是這樣:

假設獎品數量為 member,比 member 大的一個質數為 prime,

首先先取三個亂數 RandomA, RandomB, RandomC

計算

Skip = RandomA * member * member + RandomB * member + RandomC

取得 Skip 數值後,在每次需要取亂數數值時,

nextNumber += Skip

nextNumber %= prime

也就是,每次計算時,把前一次的數值加上 Skip, 然後用這個質數來取餘數, 這樣算出來的 nextNumber 就絕對不會重複。當然餘數可能會比 member 數量還大,那就再計算一次,取下一個。

 

看完之後,霎時間覺得很神奇,一時半刻還想不透,於是用試算表建公式來算,果然,產生了一個不會重複數字的序列。

但是,從這序列也發現了缺點。就是取出來的數值是有某種規律的,而且規律很明顯。不過如果不把數列排出來,也不容易發現就是了。

效能是這個演算法最大的優點,每次取亂數只需要一個加法跟一個取餘數的運算。

 

再深入去看,這演算法還可以多做一些簡化。

Skip 這個數值,只要取小於 prime,大於 0 ( 最好也不要等於 1 ) 的數值就可以,不需要取三個亂數再去加減乘除。

取出的數值的規律是,從第一個取出的 nextNumber 開始,每次遞增 Skip 指定的數量,超過 prime 的時候,再回到 0 繼續算,而之所以會全部都選取到的原因,就是因為質數的特性 -- 只能被 1 與自己整除。

 

這個演算法可以用在什麼地方呢?

分配掉寶當然是不能用啦,這個數列太過規律了。但是任務物品的掉落倒是可以用得上,怪物的重生也可以用,適用的場合應該還不少。

2 則留言:

廖峻漢 提到...

hi!我是醉心於遊戲設計的狂熱份子,目前致力於發展跨引擎架構的遊戲開發平台,希望能有機會交流。

Unknown 提到...

您好:
因為學校實作的關係,想請問您,當您要著手設計打怪扣血的扣血值計算時,您會怎麼寫?

   不能打一次怪就用兩次rand(決定倍率0,2,1,前兩者1/10,後者8/10;再決定扣血值0~6),要建立怎樣的數學公式來算比較快呢?

考量到的是線上玩家可能會同時有十萬筆攻擊要做,要讓系統生成扣血亂數的效能變更好!

   請指教