[程式] 亂數、線性同餘、perlin noise

[cowbaying (是在靠北喔)]

標題打這麼多是因為去年的某篇文章導致的...

除了騙還是騙

這個世界充滿了欺騙...



目前還在研究亂數這東西

http://rosettacode.org/wiki/Linear_congruential_generator

有興趣可以先閱讀上面的文章

目前基本的亂數產生都是用線性同餘法來達成

覺得不夠亂的話就是要自己寫了

方法似乎百百種

接著再閱讀這篇

http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

應該許多人研究過這東西

許多沙盒遊戲也都是使用perlin noise來達到理論上無限大的地圖

使用種子碼來減少資料儲存量

產生看似隨機生成的世界

不過理論跟實際要使用差距蠻大的

網路上能找的資料都是很基本的東西

要實際使用還需要琢磨一番

如果照著網路上的文獻來實作會發現一個範圍的perlin noise的產生

跟即時產生差異還頗大的

因為還牽扯到圖塊接合等等問題(map tile)

需要做內插法平順等等處理

說到這裡

可以參考minecraft spigot-api裡頭的perlin noise

github.com/SpigotMC/Spigot-API/tree/master/src/main/java/org/bukkit/util/noise
(太長了把http截掉)



=======吃完飯之後突然忘了自己要說什麼========

說點比較不容易看懂的地方

如果照著第二篇的公式來看

很快就會發現過了一定數值後結果會一直是1.0

我想這應該是同餘法的極限吧

如果SEED一直不變

完全無法產生夠大範圍的亂數

(1.0-((x*(x*x*15731+789221)[phone])&7fffffff)/1073741824.0);

來分析一下上面的算式

基本上的目的就是要讓1.0後面那串結果在0.0與2.0之間

這樣相減才能產生正負

注意綠色的符號

那是位元運算子後面的7fffffff應該是0x7fffffff

也就是整數最大值2,147,483,647

位元運算子的用處就是確保計算後的直為正數且在該範圍內

位元運算子算相當好用

接下來可以參考C或者C++的RAND與SRAND之header

在stdlib.h裡

利用第一個種子碼計算出下一個數值後(可能為長整數時期)

將其當成下次的種子碼如此反覆執行到我們指定的次數

不過這種作法我們發現每次亂數的順序都是一樣的

所以現在改善的做法都是用系統時間來當種子碼(準度到秒)

不過還是有不夠隨機的情況產生

所以第一個種子碼很重要


接下來就是我們想控制的部分了

由於PERLIN NOISE是有規律的

因此需要使用不同的頻率與放大的倍率將數個階(octave)合成起來

這邊可以另外參考SIVI的作品

https://github.com/philfrei/SiVi


我目前的想法是

如果之後要帶入計算的座標極大時

是否會降低運算的效能

目前還在測試

所以猜測把座標加入seed的產生

或許是個效率較高的作法

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.44.146
※ 文章網址: http://www.ptt.cc/bbs/GameDesign/M.1412747077.A.1B2.html
推 LayerZ: 先推，不過超過我理解範圍了XDD 對我而言，用時間，頂多把
→ LayerZ: 時間攤開來到整個活動期間都不一樣就好了，根據測不準原理
→ LayerZ: 再去過度追求隨機的隨機性，因為永遠無法確定玩家此時此刻
→ LayerZ: 抽福袋是否會合乎設計的理論..
→ LayerZ: 第三行前面少個不用，不用再去..
→ LayerZ: 唔...我發現我又再說廢話了(死)，可以幫我把推文刪掉嗎，
→ LayerZ: 我找時間看完再來回好了.這麼方便的推文真是個糟糕的發明
推 AmosYang: http://xkcd.com/221/
推 LayerZ: 樓上害我上班大笑XDDD 如果一個玩家只能骰一次，並且不能
→ LayerZ: 跟別人比較的話...他是成立的XDD
推 LayerZ: ...PS3 ESCDA Code!?