[程式] 使用亂數種子確保雙方獲得相同高度圖

[Alimen (狂人)]

回應cowbaying：
推 Alimen:如果你的高度圖是自動產生的 不妨用只傳送亂數種子的策略
→ Alimen:壓縮的方法很多 主要跟資料特性有關 要不要開新串來討論？
→ cowbaying:亂數種子有辦法還原成一整塊地圖?
→ cowbaying:我有研究了minecraft的seed  無法100%阿
→ cowbaying:因此我才需要將資料無損編碼後再還原
我先敘述一下我所謂的「只傳送亂數種子」是什麼：

假設亂數產生函數為 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
推 akilight:存seed算滿常見的手法,特別是很多4x類型的策略遊戲
→ akilight:地圖產生都是直接存一組seed,存檔讀取就靠seed重建地圖
推 cowbaying:但是要怎麼做到真的隨機呢?
→ azureblaze:除非做賭博程式要真隨機做什麼?
→ Alimen:「真正的亂數」成本很高 通常是用硬體來讀環境噪音來做
→ Alimen:例如PuTTYgen是用滑鼠移動的軌跡來產生亂數金鑰
→ elenya:用真正亂數產生seed,再把seed記下來並不衝突啊
→ Alimen:樓上也是個方法 不過跟srand(time())不就差不多了？ XDa
推 rofellosx:怎樣驗證 「真正的亂數」?
→ Alimen:兩者在統計學上是等價的 只是偽亂數"有可能"會被抓到規律
→ Alimen:但除了Shakuntala Devi 應該沒人能單看數列抓出算式吧..
→ elenya:http://goo.gl/1WXol9 可以使用這個演算法推得算式
→ elenya:英文頁講得比較詳細
推 cowbaying:受益良多  原來從理論著手能夠得到更多訊息
推 cowbaying:意外發現用SEED產生地圖的演算法還挺多的...