作者Alimen (狂人)
看板GameDesign
標題[程式] 使用亂數種子確保雙方獲得相同高度圖
時間Sun Nov 3 23:32:23 2013
回應cowbaying：
1F：推 Alimen:如果你的高度圖是自動產生的 不妨用只傳送亂數種子的策略 11/03 21:51
2F：→ Alimen:壓縮的方法很多 主要跟資料特性有關 要不要開新串來討論？11/03 21:52
3F：→ cowbaying:亂數種子有辦法還原成一整塊地圖?11/03 22:23
4F：→ cowbaying:我有研究了minecraft的seed 無法100%阿11/03 22:30
5F：→ cowbaying:因此我才需要將資料無損編碼後再還原11/03 22:31
我先敘述一下我所謂的「只傳送亂數種子」是什麼：
假設亂數產生函數為 r(n+1) = (r(n)*3+1) % 5
則亂數種子r(0) = 0的情況，連續使用亂數函數會得出以下數列：
0, 1, 4, 3, 0, 1, 4, 3, 0
再假設你的地形生成演算法是橫向排列，
也就是利用剛才產生的亂數數列，排成
0, 1, 4,
3, 0, 1,
4, 3, 0
換句話說，由於產生亂數的函數、以及產生地形的演算法是固定的，
所以亂數種子"0"，只要是同一套程式，不管到誰的電腦上(除非有硬體問題)，
產生的永遠都是
0, 1, 4,
3, 0, 1,
4, 3, 0
這裡講得是簡化過的例子，
但只要是Pseudo-random(偽亂數)，都是一樣的道理
而且就算地形生成演算法複雜很多，也不妨礙。
經典的例子應該算是新接龍牌局，
程式並沒有實際地儲存65535種牌局，
而是利用亂數種子來存。
所以我可以對朋友說「新接龍#1941超難的，你試試看」
而不用把整個牌局抄起來給他。
這裡要注意一件事，
這個方法並不適用於「我預先手動產生一張地形圖」的場合，
因為你很難去找到一組函數，可以恰好產生與你事先畫的圖一模一樣的地形圖。
至於cowbaying你提到你去拿了minecraft的seed出來，
卻還原不出一模一樣的地形圖，
我覺得有可能有幾個因素：
1. 你的地形生成演算法，跟minecraft的地形生成演算法不一樣。
換句話說，以剛剛那個例子來講，
可能你產生出來的是
0, 1, 4,
3, 0, 1,
4, 3, 0
而minecraft的演算法產生出來的是
0, 1, 1,
4, 0, 4,
3, 3, 0 (zig-zag)
2. 取亂數的途中多做了什麼事
可能minecraft在取亂數的時候，為了要回應使用者的輸入，多取了幾個
例如種子 = 0，minecraft實際取用的卻是
0, 1, 4, 3, 0, 1, (4), 3, 0, 1
^被拿去做動畫效果
生成
0, 1, 4,
3, 0, 1,
3, 0, 1
3. 亂數函數根本就不同
你用 r(n+1) = (r(n)*3+1) % 5
minecraft用 r(n+1) = (r(n)*7+0) % 5
以上是一點淺見，歡迎討論 ^^;
p.s. 我印象中planetary annihilation的星球好像也是只存亂數種子？
不知道釣不釣得到cjcat XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 27.105.12.240
6F：推 akilight:存seed算滿常見的手法,特別是很多4x類型的策略遊戲 11/03 23:38
7F：→ akilight:地圖產生都是直接存一組seed,存檔讀取就靠seed重建地圖 11/03 23:38
8F：推 cowbaying:但是要怎麼做到真的隨機呢? 11/04 00:17
9F：→ azureblaze:除非做賭博程式要真隨機做什麼? 11/04 00:20
10F：→ Alimen:「真正的亂數」成本很高 通常是用硬體來讀環境噪音來做 11/04 00:25
11F：→ Alimen:例如PuTTYgen是用滑鼠移動的軌跡來產生亂數金鑰 11/04 00:31
12F：→ elenya:用真正亂數產生seed,再把seed記下來並不衝突啊 11/04 00:36
13F：→ Alimen:樓上也是個方法 不過跟srand(time())不就差不多了？ XDa 11/04 00:39
14F：推 rofellosx:怎樣驗證 「真正的亂數」? 11/05 10:28
15F：→ Alimen:兩者在統計學上是等價的 只是偽亂數"有可能"會被抓到規律 11/05 12:11
16F：→ Alimen:但除了Shakuntala Devi 應該沒人能單看數列抓出算式吧.. 11/05 12:13
18F：→ elenya:英文頁講得比較詳細 11/05 22:09
19F：推 cowbaying:受益良多 原來從理論著手能夠得到更多訊息 11/05 22:48
20F：推 cowbaying:意外發現用SEED產生地圖的演算法還挺多的... 11/08 22:33