Minecraft(我的世界)中文論壇

 找回密碼
 注冊(register)
查看: 33567|回復: 587
打印 上一主題 下一主題

[技巧] 地圖種子逆向工程技巧:分區暴力搜索

    [復制鏈接]
microwaver 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
755
鉆石
性別
保密
注冊時間
2017-2-5
查看詳細資料
跳轉到指定樓層
樓主
發表于 2018-8-24 16:13:28 | 只看該作者 |只看大圖 回帖獎勵 |倒序瀏覽 |閱讀模式

您尚未登錄,立即登錄享受更好的瀏覽體驗!

您需要 登錄 才可以下載或查看,沒有帳號?注冊(register)

x
本帖最后由 microwaver 于 2018-8-24 16:16 編輯

前置研究:地圖種子的逆向研究(2)——結構與群系分布
感謝@Vinogradov 提供的思路

由于本文內容疑似涉及作弊,在此我不會給出與實際計算地圖種子相關的代碼,僅解釋技術原理

前人成就回顧:
  • 2^64的搜索空間對一般民用計算設備太大了。
  • 由于村莊坐標只與世界種子的前48位相關,我們可以搜索2^48的范圍使搜索時間落入合理區間.
  • 村莊坐標計算規則:以下代碼源自\net\minecraft\world\gen\structure\MapGenVillage.java
  1. protected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)
  2.     {
  3.         int i = chunkX;
  4.         int j = chunkZ;
  5.         if (chunkX < 0)
  6.         {
  7.             chunkX -= this.distance - 1;                                                 <font color="#ff0000">//this.distance在主世界(Overworld)而且不是超平坦的情況下是32</font>
  8.         }
  9.         if (chunkZ < 0)
  10.         {
  11.             chunkZ -= this.distance - 1;
  12.         }
  13.         int k = chunkX / this.distance;
  14.         int l = chunkZ / this.distance;
  15.         Random random = this.world.setRandomSeed(k, l, 10387312);//LINE_1
  16.         k = k * this.distance;
  17.         l = l * this.distance;
  18.         k = k + random.nextInt(this.distance - 8);
  19.         l = l + random.nextInt(this.distance - 8);
  20.         if (i == k && j == l)
  21.         {
  22.             boolean flag = this.world.getBiomeProvider().areBiomesViable(i * 16 + 8, j * 16 + 8, 0, VILLAGE_SPAWN_BIOMES);//LINE_2
  23.             if (flag)
  24.             {
  25.                 return true;
  26.             }
  27.         }
  28.         return false;
  29.     }
復制代碼



如果我們可以進一步縮小搜索空間,那么計算種子的速度將會很樂觀.

進入正題

一、區塊生成算法的研究
    通過研究村莊生成的代碼,我們可以發現,如果把地圖分為32區塊*32區塊的片段,每個片段之內執行村莊生成檢查時計算得到的k和l都相等.這一對k和l就表示該片段內的一個區塊,這個區塊就是@Vinogradov 所說的擬村莊區塊.

    而取得隨機數的范圍是[0,24),因此所有擬村莊區塊都在24區塊*24區塊的黃框內.


二、隨機數生成器的研究

    我們研究java.util.Ramdom類,發現以下代碼:

  1.     protected int next(int bits) {
  2. long oldseed, nextseed;
  3. AtomicLong seed = this.seed;
  4. do {
  5. oldseed = seed.get();
  6. nextseed = (oldseed * multiplier + addend) & mask;          <font color="#ff0000">//mask=0xFFFFFFFFFFFFL</font>
  7. } while (!seed.compareAndSet(oldseed, nextseed));
  8. return (int)(nextseed >>> (48 - bits));
  9. }
  10. ...
  11. ...
  12. ...
  13. public int nextInt(int bound) {
  14.     if (bound <= 0)
  15.         throw new IllegalArgumentException(BadBound);
  16.     int r = next(31);
  17.     int m = bound - 1;
  18.     if ((bound & m) == 0)  // i.e., bound is a power of 2
  19.         r = (int)((bound * (long)r) >> 31);
  20.     else {
  21.         for (int u = r;
  22.              u - (r = u % bound) + m < 0;                                 <font color="#ff0000">//實際只會執行一次</font>
  23.              u = next(31))
  24.             ;
  25.     }
  26.     return r;
  27. }
復制代碼

    分析上述代碼可知,生成一個新的隨機數時,Java會把當前種子乘以一個常數multiplier,再加上一個常數addend,得到的結果取低48位.這樣得到一個新的種子.取這個新種子較高的31bit,然后返回這個數據除以bound得到的余數.由于當兩個數相乘時,較高位的乘數不會影響較低位的積,只要我們知道種子的低48位,我們就可以確定得出的隨機數.反之,只要我們遍歷2^48范圍,我們就能通過隨機數計算種子的低48位.
但是遍歷48位太長了,能不能再給力點?

    如果能讓新的的隨機數只依賴于這31bit當中的較低幾個bit,那么我們就能只考慮這較低的幾個bit+后面的17個bit.我們已知生成的隨機數是新種子較高的31bit除以bound(值為24)的余數,而我們想要的是31bit中較低的幾個bit,也就是31bit數除以2的整數次冪所得的余數.那么已知一個數除以24得到的余數,能夠計算這個數除以多少得到的余數呢?答案就是24的因數: 2,3,4,6,8,12.因此,我們計算生成的隨機數除以8的余數,并根據它遍歷2^(3+17)的范圍.


    太長不看版:一個簡單的示例可以用來說明,使用Random.nextInt(24)獲取隨機數時,取得的隨機數僅與隨機數種子的低20位相關.
  1. import java.util.Random;
  2. public class Test {
  3.     public static void main(String[] args){
  4.         int fullseed = 0x11de784a;
  5.         int shortseed = 0xe784a;
  6.         Random rand = new Random(fullseed);
  7.         Random rand2 = new Random(shortseed);
  8.         for(int i=0;i<10;i++){
  9.             System.out.println("rand: "+String.valueOf(rand.nextInt(24)%8));
  10.             System.out.println("rand2: "+String.valueOf(rand2.nextInt(24)%8));
  11.         }
  12.     }
  13. }
復制代碼

以上代碼的輸出為:
  1. rand: 4
  2. rand2: 4
  3. rand: 7
  4. rand2: 7
  5. rand: 2
  6. rand2: 2
  7. rand: 2
  8. rand2: 2
  9. rand: 4
  10. rand2: 4
  11. rand: 7
  12. rand2: 7
  13. rand: 0
  14. rand2: 0
  15. rand: 7
  16. rand2: 7
  17. rand: 2
  18. rand2: 2
  19. rand: 4
  20. rand2: 4
復制代碼

結論:通過利用java.util.Random類的缺陷,我們可以將首次搜索的范圍降低到低20位,這幾乎相當于立即完成了.通過使用@Vinogradov 提出的方法進行第二次搜索,我們可以很快地獲取地圖種子.

預防和修復:這個方法的預防仍然需要修改村莊生成的源碼或隨機數生成器,比如把random.nextInt(this.distance - 8)改成random.nextInt(this.distance - 7)就不能用了

其實我原來只想做一個實現來著的...然后不會寫GPU計算就開始找簡易算法233

評分

參與人數 29人氣 +48 金粒 +320 貢獻 +6 收起 理由
719823597 + 4 + 50 + 1 Ssssssssssssssssssss
ZMY_666233 + 1 膜拜大佬
core.exe + 1 神乎其技,不服不行!
ColorsWind + 2 + 8 MCBBS有你更精彩~
黃河 + 1 神乎其技,不服不行!
苦末尸 + 1 MCBBS有你更精彩~
bian_feng + 1 神乎其技,不服不行!
會跑的房子 + 1 MCBBS有你更精彩~
jiangyoudi2022 + 1 神乎其技,不服不行!
lengzu + 2 + 22 神乎其技,不服不行!
2912584425hhh + 10 神乎其技,不服不行!
團子是只豬 + 1 MCBBS有你更精彩~
mmmmmmmm丶淺瞳 + 1 神乎其技,不服不行!
非常你我 + 1 + 10 向算法大佬致敬
迷之老葉 + 1 + 10 神乎其技,不服不行!
2845984686 + 1 神乎其技,不服不行!
cang_33 + 1 + 15 神乎其技,不服不行!
45gfg9 + 2 神乎其技,不服不行!
Zevn + 2 + 30 MCBBS有你更精彩~
langyo_v3 + 2 MCBBS有你更精彩~

查看全部評分

帖子永久鏈接: 

Minecraft中文論壇 - 論壇版權1、本主題所有言論和圖片純屬會員個人意見,與本論壇立場無關
2、本站所有主題由該帖子作者發表,該帖子作者享有帖子相關版權
3、其他單位或個人使用、轉載或引用本文時必須同時征得該帖子作者的同意
4、帖子作者須承擔一切因本文發表而直接或間接導致的民事或刑事法律責任
5、本帖若有內容轉載自其它媒體,不代表本站贊同其觀點和對其真實性負責
6、若本帖涉及任何版權問題,請立即告知本站,本站將及時予以刪除并致以最深的歉意
7、Minecraft(我的世界)中文論壇管理員和版主有權不事先通知發貼者而刪除本文

NoName德里奇 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
6832
鉆石
性別
保密
注冊時間
2018-8-2
查看詳細資料
沙發
發表于 2018-8-24 17:15:32 | 只看該作者
這操作太真實了
神乎其技,不服不行。
回復

使用道具 舉報

丟人素學姐 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
2023
鉆石
性別
保密
注冊時間
2017-3-6
查看詳細資料
板凳
發表于 2018-8-24 21:08:24 | 只看該作者
本帖最后由 Vinogradov 于 2018-8-24 21:30 編輯

這個思路太棒了!我完全沒想到用2的冪次繼續簡化的事情。
以下是我的理解,如果有錯請不吝賜教:
我想你得到的結論是,把每個擬村莊區塊對應的k和l模8以后,得到的結果只和種子的低20位有關對吧?
這樣確實變得快很多,但是你獲得的信息也從48位減少到了20位。
或許可以用你的方法過濾一遍獲得低20位以后,再用我原來的那個粗的辦法再窮舉低第21位-低第48位,這樣還是能獲得低48位。(或許你就是這個意思我沒理解?)。這種組合的辦法比我帖子里那個要好很多了。

至于高16位就很簡單,不提了。
回復

使用道具 舉報

乙烯_中國 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
22670
鉆石
性別
保密
注冊時間
2014-12-16
查看詳細資料
地板
發表于 2018-8-29 18:39:12 | 只看該作者
毫無疑問,精華。
回復

使用道具 舉報

anjiayi123 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
32
鉆石
性別
保密
注冊時間
2017-3-14
查看詳細資料
5#
發表于 2018-8-29 22:52:32 | 只看該作者
哇樓主真厲害啊

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 無意義

查看全部評分

回復

使用道具 舉報

Robert_Liang 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
37
鉆石
性別
保密
注冊時間
2018-8-29
查看詳細資料
6#
發表于 2018-8-30 09:12:39 | 只看該作者
就只有我每個字都認識 拼到一起就聽不懂了嗎

評分

參與人數 3人氣 +3 收起 理由
YBOBZ + 1 +1
2422373056 + 1 +1
殤凌·殘胤 + 1 你不是一個人!

查看全部評分

回復

使用道具 舉報

夕顏初夏 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
663
鉆石
性別
保密
注冊時間
2018-8-21
查看詳細資料
7#
發表于 2018-8-30 13:12:24 | 只看該作者
樓主好厲害啊,根本學不會

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 無意義

查看全部評分

回復

使用道具 舉報

逸之夏 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
57
鉆石
性別
保密
注冊時間
2018-2-26
查看詳細資料
8#
發表于 2018-8-30 14:27:11 | 只看該作者
神乎其技,不服不行!

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
玄素 -1 -10 無意義

查看全部評分

回復

使用道具 舉報

淡然,流逝 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
19
鉆石
性別
保密
注冊時間
2018-8-23
查看詳細資料
9#
發表于 2018-8-31 09:31:33 | 只看該作者
哇!樓主真NB

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 無意義

查看全部評分

回復

使用道具 舉報

沫雨丶 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
137
鉆石
性別
保密
注冊時間
2017-8-16
查看詳細資料
受到警告 10#
發表于 2018-8-31 14:47:41 | 只看該作者
哇,挺厲害的

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 萬用回復

查看全部評分

回復

使用道具 舉報

Alyxiao 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
45
鉆石
性別
保密
注冊時間
2015-3-12
查看詳細資料
11#
發表于 2018-8-31 15:05:09 | 只看該作者
我要頂帖..............

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
玄素 -1 -10 無意義

查看全部評分

回復

使用道具 舉報

風扇滑翔翼 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
4276
鉆石
性別
保密
注冊時間
2016-7-26
查看詳細資料
12#
發表于 2018-8-31 18:45:10 | 只看該作者
所以我們需要一個修改世界產卵器的插件
回復

使用道具 舉報

langyo_v3 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
5580
鉆石
性別
保密
注冊時間
2017-4-5
查看詳細資料
13#
發表于 2018-9-1 00:03:14 | 只看該作者
不會寫GPU計算……

同求GPU的操作接口文檔

評分

參與人數 1金粒 +10 收起 理由
SmallFatCYW + 10 CUDA???

查看全部評分

回復

使用道具 舉報

Sakur9 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
1384
鉆石
性別
保密
注冊時間
2018-9-1
查看詳細資料
受到警告 14#
發表于 2018-9-1 14:29:52 | 只看該作者
厲害啦

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 萬用回復

查看全部評分

回復

使用道具 舉報

Nu_ta 當前離線
帖子
主題
精華
貢獻
最后登錄
1970-1-1
愛心
積分
963
鉆石
性別
保密
注冊時間
2018-7-16
查看詳細資料
受到警告 15#
發表于 2018-9-3 06:06:46 | 只看該作者
給樓主大大的贊,很棒

評分

參與人數 1人氣 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 萬用回復

查看全部評分

回復

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 注冊(register)

本版積分規則

Archiver|小黑屋|Mcbbs.net ( 京ICP備15023768號-1 ) | 京公網安備 11010502037624號 | 手機版

GMT+8, 2019-11-20 06:35 , Processed in 0.054866 second(s), Total 22, Slave 21 queries , Gzip On, MemCached On.

"Minecraft"以及"我的世界"為Mojang Synergies AB的商標 本站與Mojang以及微軟公司沒有從屬關系

© 2010-2019 我的世界中文論壇 版權所有 本站原創圖文內容版權屬于原創作者,未經許可不得轉載

快速回復 返回頂部 返回列表
20码必中