ทุกครั้งที่บล็อกพังใน Minecraft เวอร์ชันเบต้า 1.8 ถึง 1.12.2 พิกัดที่แม่นยำของไอเท็มที่ดรอปสามารถ เปิดเผยตำแหน่งของผู้เล่นคนอื่นได้
"Randar" เป็นช่องโหว่สำหรับ Minecraft ซึ่งใช้การลด LLL lattice เพื่อถอดรหัสสถานะภายในของ java.util.Random ที่นำมาใช้ซ้ำอย่างไม่ถูกต้องในเซิร์ฟเวอร์ Minecraft จากนั้นทำงานย้อนกลับจากนั้นเพื่อค้นหาผู้เล่นอื่นที่โหลดเข้ามาในโลก
คลิกที่นี่เพื่อเรียนรู้เกี่ยวกับ Randar ในรูปแบบวิดีโอ YouTube แทน
ชมไทม์แลปส์:
ดูไทม์แลปส์เพิ่มเติมได้ที่นี่ (ในรูปแบบไฟล์) หรือที่นี่ (ในรูปแบบ YouTube)
เป้าหมาย คือการกำหนดตำแหน่งในเกม (เช่น พิกัด) ของผู้เล่นคนอื่นๆ ในโลก ไม่ว่าพวกเขาจะอยู่ห่างไกลแค่ไหนก็ตาม เรากำลังเล่นบน 2b2t ซึ่งเป็นเซิร์ฟเวอร์ Minecraft "อนาธิปไตย" ที่เก่าแก่และมีชื่อเสียงที่สุด (ซึ่งหมายความว่าไม่มีกฎเกณฑ์ กล่าวคือ ผู้เล่นไม่ถูกแบนไม่ว่าด้วยเหตุผลใดก็ตาม) การทำสิ่งนี้ถือเป็น "ประเด็น" บนเซิร์ฟเวอร์นี้ บนเซิร์ฟเวอร์นี้ สิ่งเดียวที่ทำให้สิ่งของของคุณปลอดภัยก็คือแผนที่มีขนาดใหญ่มาก (3.6 พันล้านล้านสี่เหลี่ยม) และไม่มีใครรู้ว่าคุณอยู่ที่ไหน ดังนั้นจึงเป็นเรื่องใหญ่ (ข้อตกลงทำลายเกม) ที่จะใช้ประโยชน์จากการประสานงาน (พูดถึง ก่อนที่ Randar เราก็มีการหาประโยชน์จาก coord อีกครั้งบน 2b2t, Nocom ตั้งแต่ปี 2018 ถึง 2021 ดูบทความได้ที่นี่ กระทู้ HackerNews, YT)
ข้อผิดพลาด ในโค้ดของ Minecraft มีตั้งแต่เวอร์ชันเบต้า 1.8 (เปิดตัวปี 2011) ถึง 1.12.2 (เปิดตัวปี 2017 แต่ 2b2t ยังคงอยู่ในเวอร์ชันนี้จนถึงวันที่ 14 สิงหาคม 2023) ข้อผิดพลาดคืออินสแตนซ์ต่างๆ ของตัวสร้างตัวเลขสุ่ม java.util.Random ถูกนำมาใช้ซ้ำอย่างเลอะเทอะในส่วนต่างๆ ของโค้ด (และพวกมันไม่ปลอดภัยในการเริ่มต้น) โดยเฉพาะอย่างยิ่ง มีการนำ RNG มาใช้ซ้ำระหว่างการสร้างภูมิประเทศและการกระทำในเกม เช่น บล็อกการขุด
การใช้ประโยชน์ สรุป:
World.rand ทั่วโลกมีการรีเซ็ตค่าเริ่มต้นเป็นฟังก์ชันของพิกัดก้อน เพื่อตรวจสอบว่าคฤหาสน์ Woodland ที่อยู่ใกล้เคียงควรอยู่ที่ไหน (และโดยเฉพาะคือส่วนนี้หรือไม่)World.rand.nextFloat() สามครั้งติดต่อกันเพื่อเลือกพิกัด XY และ Z ระหว่าง 0 ถึง 1 บอทจะบันทึกการประทับเวลาและค่า XYZ ที่แม่นยำWorld.rand ที่ทำให้เกิดการลอยตัวทั้งสามได้ พูดอย่างกว้างๆ (รายละเอียดเพิ่มเติมจะมาในภายหลัง) การสังเกตหนึ่งเอาท์พุตของ RNG อาจบ่งบอกถึงสถานะภายในที่เป็นไปได้ของ RNG ประมาณ 16 ล้านสถานะ อย่างไรก็ตาม เราได้สุ่มตัวอย่างผลลัพธ์ของ RNG ไม่ใช่แค่ครั้งเดียวแต่สามครั้งติดต่อกัน (พิกัด X, Y และ Z ของรายการที่ดร็อป) และเรารู้ว่าสถานะภายในได้รับการอัปเดตอย่างไรระหว่างการโทรแต่ละครั้ง (การคูณอย่างง่าย เพิ่มแล้วดัดแปลง); ดังนั้นเราจึงสามารถใช้วิธีขัดแตะเพื่อจำกัดให้แคบลงเหลือความเป็นไปได้เพียงอย่างเดียวในทันทีjava.util.Random สามารถก้าวถอยหลังได้อย่างง่ายดายพอๆ กับการก้าวไปข้างหน้า และโดยการก้าวถอยหลังเราจะพบมันได้ภายในไม่กี่พันก้าว (แม้แต่บนเซิร์ฟเวอร์ที่ยุ่งอย่าง 2b2t ที่มีผู้เล่นจำนวนมากและดังนั้นจึงหนักหน่วง การใช้ RNG) ซึ่งระบุเวลาล่าสุดที่มีการรีเซ็ตสถานะภายในของ RNG และตำแหน่งของชิ้นส่วนล่าสุดที่โหลดบนเซิร์ฟเวอร์แม้ว่าคุณจะเล่นบนเซิร์ฟเวอร์ที่อัปเดตเป็น Minecraft เวอร์ชันใหม่กว่า หรือมีแพตช์การจัดการ RNG พิกัดของคุณยังคงมีความเสี่ยงจาก Randar เนื่องจากความสามารถในการใช้ประโยชน์จากข้อมูล RNG ย้อนหลัง ผู้เล่น Minecraft บางรายใช้ม็อด เช่น ReplayMod ที่บันทึกแพ็กเก็ต และพวกเขาอาจยังมีไฟล์บันทึกอยู่รอบๆ หากใครก็ตามใช้ม็อดดังกล่าวในขณะที่คุณอยู่ที่ฐานของคุณ พวกเขาอาจมีข้อมูล RNG ที่บันทึกไว้ (โดยไม่รู้ตัว) ซึ่งสามารถเปิดเผยตำแหน่งของคุณได้ เนื่องจากการทำลายบล็อกเป็นการกระทำทั่วไปอย่างยิ่งที่มีแนวโน้มที่จะเกิดขึ้นในการบันทึกดังกล่าว และทุกๆ บล็อกดังกล่าว break แสดงสถานะ RNG ของเซิร์ฟเวอร์และตำแหน่งของชิ้นส่วนที่โหลดล่าสุด ซึ่งหมายความว่า Randar ถือเป็นเรื่องใหญ่ เนื่องจากมีความเสี่ยงในการหาประโยชน์ย้อนหลัง บนเซิร์ฟเวอร์ Minecraft ทุกตัว ทุก ตำแหน่งที่ใช้งานในเวอร์ชันเบต้า 1.8 ถึง 1.12.2 ควรได้รับการพิจารณาว่าถูกบุกรุก แม้ว่า เซิร์ฟเวอร์จะอัปเดตเกิน 1.12 มานานแล้ว .2 หรือการจัดการ RNG ที่มีแพตช์
หากคุณต้องการใช้ Randar หาประโยชน์ด้วยตัวเอง ไปที่นี่ โดยที่ rebane2001 ได้สร้างเว็บไซต์ที่คุณสามารถลากไฟล์ ReplayMod จาก 1.12.2 และดูพิกัดของผู้เล่นอื่นได้ มันทำงานฝั่งไคลเอ็นต์ดังนั้นการบันทึกของคุณจะไม่ออกจากเบราว์เซอร์ของคุณ ต่อไปนี้คือวิดีโอที่แสดงให้เห็นว่าเว็บไซต์นั้นมีลักษณะอย่างไร และคุณสามารถเรียกใช้ไฟล์ ReplayMod ตัวอย่างจากวิดีโอนั้นได้โดยการดาวน์โหลดที่นี่
Randar ถูกค้นพบโดย n0pf0x (pcm1k) บทความนี้เขียนโดย leijurv โดยมีคำอธิบายเพิ่มเติมในตอนท้ายที่เขียนโดย n0pf0x ผู้โจมตีได้แก่ 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy และ rebane2001 ดูวิดีโอของ TheLampGod ที่นี่ ดูวิดีโอข้อเท็จจริง 0% ที่มีอารมณ์ขัน 100% ของ HermeticLock ที่นี่
สารบัญ: คลิกที่นี่เพื่อเรียนรู้เพิ่มเติมเกี่ยวกับโค้ดที่สามารถหาประโยชน์ได้โดยละเอียด ที่นี่เพื่อเรียนรู้เกี่ยวกับวิธีการใช้ Lattice Reduction ที่นี่เพื่อดูว่าเราปกป้องคลังข้อมูลของเราเองจาก Randar ได้อย่างไร ที่นี่ หากคุณต้องการดูโค้ดการหาประโยชน์โดยสมบูรณ์ ที่นี่ หากคุณใช้งานเซิร์ฟเวอร์ที่ยังอยู่ในเวอร์ชันระหว่างเบต้า 1.8 ถึง 1.12.2 และคุณต้องการแพตช์ Randar หรือที่นี่ สำหรับรายละเอียดเกี่ยวกับสิ่งที่ n0pf0x ทำแตกต่างจากเรา
แผนภาพข้อผิดพลาด (เป็น PDF):
แผนผังของการใช้ประโยชน์ (เป็น PDF):
แผนภาพตัวอย่างการทำงานของการหาประโยชน์ (เป็น PDF):
Minecraft อาศัยตัวเลขสุ่มตลอดทั้งเกม ส่วนใหญ่เราคาดหวังว่าจะเป็นแบบสุ่ม เช่น การสุ่มที่ใช้สำหรับการวางไข่ของฝูงสัตว์และสภาพอากาศ แต่บางส่วนเราคาดว่าจะสามารถคาดเดาได้ เช่น เราคาดหวังว่าเมล็ดพันธุ์โลกเดียวกันในตำแหน่งเดียวกันเพื่อสร้างภูมิประเทศเดียวกัน ในปี 2011 เมื่อ Notch เพิ่มโครงสร้างในเกมเป็นครั้งแรกในช่วงเบต้า 1.8 เขานำ RNG มาใช้ซ้ำโดยไม่ได้ตั้งใจซึ่ง ควร จะคาดเดาไม่ได้เพื่อที่จะวางหมู่บ้านไว้ในโลก ตั้งแต่นั้นเป็นต้นมา จนถึงเวอร์ชัน 1.13 รหัสที่เลอะเทอะนี้ได้ก่อให้เกิดการสร้างโลกมีอิทธิพลต่อเหตุการณ์ สุ่ม อื่นๆ เกือบทั้งหมดในเกม Earthcomputer และเพื่อนๆ ใช้เวลาประมาณเดือนพฤษภาคม 2018 เพื่อค้นหาข้อผิดพลาดนี้ โดยตระหนักว่าการโหลดจำนวนมากส่งผลต่อ RNG ของเกมในลักษณะที่สังเกตได้ โปรดดูคำอธิบายนี้ อย่างไรก็ตาม พวกเขาไม่ได้ตระหนักหรือไม่เคยเปิดเผยต่อสาธารณะว่าคุณสามารถดำเนินการย้อนกลับได้ โดยพิจารณาจากการตรวจสอบ RNG ที่โหลดล่าสุด การค้นพบนั้น Randar จัดทำโดย n0pf0x (หรือที่รู้จักกันในชื่อ pcm1k) เมื่อวันที่ 7 ตุลาคม 2022 เขาโพสต์คำอธิบายสั้นๆ ที่เข้ารหัสเกี่ยวกับการหาประโยชน์บน Pastebin ประมาณสองสัปดาห์หลังจากนั้น เพื่อพิสูจน์ว่าเขาค้นพบมันในตอนนั้น เขาใช้การหาประโยชน์ส่วนใหญ่บน 9b9t และเพียงเล็กน้อยบน 2b2t และเซิร์ฟเวอร์อื่นๆ ในวันที่ 2b2t n0p ได้ค้นพบและสำรวจสถานที่ต่างๆ และในที่สุดก็มาถึงสถานที่ซ่อนของกริงกอตส์ เขาถูกพบเห็นโดย rebane2001 และในตอนแรกเงียบๆ ว่าเขาพบสถานที่นี้ได้อย่างไร อย่างไรก็ตาม ประมาณหนึ่งเดือนต่อมา เขาเริ่มพูดคุยกับ SpawnMasons เกี่ยวกับเรื่องนี้ n0p เปิดเผยว่าเขาได้ใช้การหาประโยชน์จากพิกัดอันทรงพลังและตัดสินใจแบ่งปันคำอธิบายกับเราในเดือนเมษายน 2023 เนื่องจากช่างก่ออิฐเคยมีประสบการณ์ในการใช้ประโยชน์จากการหาประโยชน์จาก 2b2t ในสเกลที่ใหญ่กว่า ดังนั้นคงจะสนุกถ้าได้เห็นสิ่งนั้นเกิดขึ้นอีกครั้ง และ n0p แม้จะรู้สึกเบื่อกับมันบ้างแล้วก็ตาม เรายอมรับและเริ่มบันทึกพิกัดดรอปไอเทมในหลายบัญชีที่ทำการขุดหิน/หินกรวดแล้วทุกวันตลอด 24 ชั่วโมงสำหรับโครงการที่ไม่เกี่ยวข้องกัน (ดังนั้นจึงไม่มีการเปลี่ยนแปลงพฤติกรรม) เราใช้ระบบ Minecraft ที่ไม่มีหัวจาก nocom และเพิ่มฐานข้อมูล Postgres เพื่อบันทึกการวัด ตามที่กล่าวไว้ในภายหลังใน readme นี้ เราได้ผ่านการวนซ้ำของซอฟต์แวร์หลายครั้งเพื่อถอดรหัสการวัด RNG และในที่สุดก็ตกลงกับงานแบตช์ async Cuda เมื่อมีการเพิ่มการวัดการแคร็กลงในฐานข้อมูล เรายังได้อัปเดตตารางการวิเคราะห์ด้วยข้อมูลแผนที่ความร้อนที่นับจำนวนการเข้าชมในแต่ละพิกัดตามช่วงเวลาทั้งหมด รายวัน และรายชั่วโมง ซึ่งช่วยให้ Plotly Dash UI แบบธรรมดาสามารถเลือกข้อมูลแผนที่ความร้อนจากช่วงเวลาและรายละเอียดเฉพาะสำหรับแสดงในเบราว์เซอร์ และช่วยให้เราลบสแปมโหลดก้อนของ Elytra ที่ดักจับข้อมูลทั้งหมดออกโดยพิจารณาเฉพาะพิกัดที่โหลดในชั่วโมงที่แตกต่างกันมากกว่าสองสามชั่วโมงเท่านั้น เราได้เพิ่มระบบคำอธิบายประกอบที่ใช้ร่วมกันแบบง่ายๆ เพื่อติดตามสิ่งที่เราพบในแต่ละฮอตสปอตบนแผนที่ การนำ Nocom กลับมาใช้ซ้ำอีกครั้ง เรามีบอท Baritone ที่ทำให้กระบวนการทั้งหมดของการขโมยไอเทมที่ซ่อนและเรียงลำดับผลลัพธ์เป็นแบบอัตโนมัติ AFK อย่างสมบูรณ์ ช่างก่อสร้างจำนวนมากช่วยในส่วนนี้โดยไม่ทราบถึงช่องโหว่ โดยใช้บัญชี เช่น munmap และ 1248_test_user คลังเก็บของ Gringotts ทั้งหมดรวมกันในที่สุดก็เพิ่มขึ้นเป็น 1.3 พันล้านรายการ โดยครึ่งหนึ่งเป็นของ Nocom และอีกครึ่งหนึ่งเป็นของ Randar
ประวัติทั้งหมดอธิบายไว้ในวิดีโอ FitMC
แผนที่ของ Minecraft ได้รับการสร้างขึ้นตามขั้นตอนและกำหนดโดยพื้นฐานโดยอิงจากเมล็ดพันธุ์เริ่มต้นของโลก ขณะที่ผู้เล่นสำรวจแผนที่ พื้นที่ใหม่จะถูกสร้างขึ้นตามความต้องการเมื่อผู้เล่นเข้ามาใกล้ เนื่องจากทุกรุ่นมีไว้เพื่อให้สามารถทำซ้ำได้ (กำหนดไว้) จึงสมเหตุสมผลอย่างยิ่งสำหรับพวกเขาที่จะใช้ java.util.Random ในหลาย ๆ ที่ พวกเขา ต้องการ ให้มันคาดเดาได้ นี่คือเหตุผลว่าทำไมจึงใช้ java.util.Random เนื่องจากเป็น PRNG (ไม่ใช่ RNG จริงๆ) P ในทางเทคนิคหมายถึง "หลอก" แต่คิดว่ามัน "คาดเดาได้" RNG ที่คาดการณ์ได้ มันสร้างตัวเลขที่ดูเหมือนสุ่ม แต่จริงๆ แล้วพวกมันสามารถทำซ้ำได้เมื่อมีเมล็ดเริ่มต้นที่เหมือนกัน
Minecraft มีโครงสร้างต่างๆ ที่สร้างขึ้นในโลก เช่น หมู่บ้าน อนุสาวรีย์ในมหาสมุทร ฐานที่มั่น ฯลฯ โครงสร้างเหล่านี้เป็นส่วนหนึ่งของการสร้างตามขั้นตอน ดังนั้น โครงสร้างเหล่านี้จึงถูกวางและสร้างตามที่กำหนดเช่นกัน
จำเป็นต้องมีโค้ด Minecraft เพียงสิบบรรทัดเพื่อทำความเข้าใจสิ่งนี้ และฉันได้ทำให้ง่ายขึ้นและแสดงความคิดเห็นอย่างหนัก:
// (chunkX,chunkZ) is being loaded, and this function checks if it should generate a Woodland Mansion
protected boolean canSpawnStructureAtCoords ( int chunkX , int chunkZ ) {
// divide by 80, rounding down, to determine which "Woodland region" (my made up term) we're considering
int woodlandRegionX = Math . floorDiv ( chunkX , 80 );
int woodlandRegionZ = Math . floorDiv ( chunkZ , 80 );
// seed the random number generator deterministically in a way that's unique to this Woodland region
Random random = this . world . setRandomSeed ( woodlandRegionX , woodlandRegionZ , 10387319 );
// pick which chunk within this region will get the Woodland Mansion
int woodlandChunkX = woodlandRegionX * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
int woodlandChunkZ = woodlandRegionZ * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
// but is it *this* chunk, that we're loading right now?
if ( chunkX == woodlandChunkX && chunkZ == woodlandChunkZ ) {
// and, is this chunk in a biome that allows Woodland Mansions? (e.g. roofed forest)
if ( this . world . getBiomeProvider (). areBiomesViable ( chunkX * 16 + 8 , chunkZ * 16 + 8 , 32 , ALLOWED_BIOMES )) {
return true ;
}
}
return false ;
}
// and here's what it calls in World.java:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ; // this.getWorldInfo().getSeed() is the overall seed of the entire map, which has been cracked long ago for 2b2t (it's -4172144997902289642)
}ข้างต้นได้รับการแสดงความคิดเห็นและแก้ไขเล็กน้อยเพื่อความชัดเจน แต่มีความแม่นยำในการใช้งานกับโค้ดจริง
แนวคิดคือการตัดสินใจว่าคฤหาสน์วูดแลนด์ควรไปที่ใดในภูมิภาควูดแลนด์ (ซึ่งมีขนาด 80 x 80 ชิ้น) ตรวจสอบว่าสถานที่นั้นอยู่ ที่นี่หรือไม่ และหากเป็นเช่นนั้น ให้สร้างคฤหาสน์วูดแลนด์โดยเริ่มต้นที่นี่
โค้ดนี้อาจดูงี่เง่านิดหน่อย คุณอาจกำลังคิดว่า "มันไร้สาระที่จะตรวจสอบทุกๆ ชิ้น เพียงเลือกว่า Woodland Mansions ควรไปที่ไหนต่อภูมิภาคแล้วดำเนินการให้เสร็จสิ้น" เหตุผลก็คือชิ้นส่วน Minecraft นั้นถูกสร้างขึ้นโดยแยกจากกันและอยู่ในลำดับที่ไม่ทราบ แต่เรายังคงต้องการสร้างโลกที่กำหนดขึ้นจากเมล็ดพันธุ์ที่กำหนด เราไม่รู้ว่าผู้เล่นจะเดินไปรอบโลกตามลำดับอะไร และเป็นเรื่องดีที่สามารถสร้างชิ้นส่วนตามความต้องการในลักษณะไร้สัญชาติได้ มันเป็นประสบการณ์การเล่นเกมที่ดี ดังนั้นโค้ดที่ดูแปลก ๆ เช่นนี้
อย่างไรก็ตาม โค้ดนั้นจะถูกเรียกใช้ในทุก ๆ ก้อนโหลด สำหรับทุก ๆ ก้อนในสี่เหลี่ยมขนาดใหญ่รอบ ๆ ก้อนที่ถูกโหลด มันซับซ้อนเล็กน้อยที่จะอธิบายว่าทำไม ฉันจึงข้ามมันไปเป็นส่วนใหญ่ (แนวคิดพื้นฐานคือโครงสร้างเหล่านี้ (มาก) มีขนาดใหญ่กว่าหนึ่งชิ้น ดังนั้นเราจำเป็นต้องตรวจสอบต้นกำเนิดของโครงสร้างในชิ้นใกล้เคียงหลายๆ ชิ้นเพื่อสร้าง ปัจจุบันนี้อย่างถูกต้อง)
โปรดทราบว่าสิ่งนี้จะส่งผลต่อ Overworld เท่านั้น Nether นั้นปลอดภัย เนื่องจากการสร้างโครงสร้างทั้งหมดจะใช้ RNG ที่ปลอดภัยอยู่เสมอ การโหลดชิ้นส่วนใน The End ได้รับผลกระทบเนื่องจากเมืองสุดท้าย แต่เฉพาะในรุ่นเริ่มแรกเท่านั้น ไม่ใช่ทุกครั้งที่โหลด ดังนั้น The End จึงค่อนข้างปลอดภัยเพราะแต่ละชิ้นส่วนที่ฐานของคุณส่งผลต่อ RNG เพียงครั้งเดียวเมื่อคุณโหลดครั้งแรก มัน. อย่างไรก็ตาม การดำเนินการนี้ไม่สามารถป้องกันความผิดพลาดได้โดยสิ้นเชิง เนื่องจากผู้เล่นมักจะสร้างชิ้นส่วนใหม่ทุกครั้งในขณะที่เดินทางไปยังฐานของตน และสร้างชิ้นส่วนใหม่เป็นครั้งคราวในขณะที่อยู่ที่ฐานอยู่แล้ว
ปัญหาคือมันปรับเปลี่ยนเมล็ดพันธุ์ของ World.rand ทั่วโลก นี่เป็นเพียงการเข้ารหัสแบบขี้เกียจ สิ่งที่พวกเขาทำคือเรียก nextInt สี่ครั้งเพื่อเลือกพิกัด X และ Z พวกเขาสามารถแทนที่ Random random = this.world.setRandomSeed(... ด้วย Random random = new Random(the same stuff) (หรืออีกนัยหนึ่งคือสร้าง Random ใหม่ที่นี่ แทนที่จะไปยุ่งกับอันที่มีอยู่ซึ่งถูกใช้โดยทุกสิ่งทุกอย่าง? ??)
สิ่งที่สำคัญที่สุดคือการเรียก setRandomSeed เพื่อตรวจสอบว่า Woodland Mansion ควรไปที่ไหน มันเกิดขึ้นได้ไม่ว่าจะเกิดอะไรขึ้น ในทุกก้อนโหลด ทุกที่ คุณไม่จำเป็นต้องยืนอยู่ใน/ใกล้คฤหาสน์วูดแลนด์หรืออะไรทำนองนั้น
ปรากฎว่า World.rand ถูกใช้ในสถานที่หลายร้อยแห่ง และหลายแห่งสามารถสังเกตได้ง่าย ๆ ด้วยการเล่นเกมตามปกติ ตัวอย่างเช่น เมื่อคุณขุดบล็อก:
/**
* Spawns the given ItemStack as an EntityItem into the World at the given position
*/
public static void spawnAsEntity ( World world , BlockPos pos , ItemStack stack ) {
double xWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double yWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double zWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
EntityItem entityitem = new EntityItem ( world , pos . getX () + xWithinBlock , pos . getY () + yWithinBlock , pos . getZ () + zWithinBlock , stack );
world . spawnEntity ( entityitem );
}อีกครั้ง มีการปรับเปลี่ยนเล็กน้อย แต่มีความแม่นยำในการใช้งานสำหรับสิ่งที่เรากำลังพูดถึง
แนวคิดก็คือใน Minecraft เมื่อคุณขุดบล็อก มันจะดรอปไอเท็ม ไอเทมจะดรอปในตำแหน่งสุ่มภายในบล็อก ตัวอย่างเช่น หากบล็อกอยู่ที่ (10, 20, 30) รายการจะปรากฏที่ไหนสักแห่งระหว่าง (10.25, 20.25, 30.25) และ (10.75, 20.75, 30.75)
และเลือกตำแหน่งที่แน่นอนของรายการนั้นโดยการเรียก world.rand.nextFloat() สามครั้งติดต่อกันสำหรับ X, Y และ Z
นั่นคือโค้ด Minecraft ทั้งหมดที่จำเป็น!
ตอนนี้ฉันบอกว่าเราสามารถทำอะไรบางอย่างกับการโทร nextFloat เหล่านี้ได้ ก่อนอื่น มาดูกันว่าเราสามารถ "ทำงานย้อนหลัง" เพื่อดูว่าการเรียก nextFloat คืออะไร มันค่อนข้างโชคดี แต่จริงๆ แล้วเราทำได้ หมายเหตุในโค้ดด้านบน: การสุ่มทศนิยมจะถูกคูณด้วย 0.5 แล้วบวกเข้ากับ 0.25 แนวคิดคือการย้ายจากตัวเลขสุ่มระหว่าง 0 ถึง 1 ไปเป็นตัวเลขสุ่มระหว่าง 0.25 ถึง 0.75 คุณอาจกังวล เพราะหากคุณหารจำนวนเต็มด้วยสอง คุณจะสูญเสียข้อมูลไปเล็กน้อยเนื่องจากผลลัพธ์จะถูกปัดเศษลง โชคดีที่การคูณทศนิยมด้วย 0.5 นั้นสามารถย้อนกลับได้โดยสิ้นเชิง เนื่องจากมันเพียงแค่ลดเลขชี้กำลังลงในขณะที่ปล่อยแมนทิสซาไว้โดยไม่มีใครแตะต้อง จากนั้นทุ่นจะถูกหล่อเป็นสองเท่าซึ่งมีความแม่นยำมากกว่ามาก เพิ่ม 0.25 แล้วจึงเพิ่มพิกัดบล็อก จากนั้นจะถูกส่งไปยังไคลเอนต์ผ่านเครือข่ายอย่างแม่นยำ ผลลัพธ์: กระบวนการทั้งหมดนี้สามารถย้อนกลับได้ ดังนั้นเราจึงได้โฟลตสามตัวที่ World.rand.nextFloat() สร้างขึ้น
java.util.Random สร้างโฟลตได้อย่างไร ที่จริงแล้วมันค่อนข้างง่าย สร้างจำนวนเต็มระหว่าง 0 ถึง 2^24 จากนั้นหารด้วย 2^24 (ส่งผลให้ได้ตัวเลขระหว่าง 0 ถึง 1) มันได้จำนวนเต็มสุ่มนั้นมาได้อย่างไร? แถมยังเรียบง่ายอีกด้วย! มันเป็นเครื่องกำเนิดคอนกรูเชียลเชิงเส้น (LCG) นั่นหมายความว่าเมล็ดพันธุ์ถัดไปคือเมล็ดพันธุ์ก่อนหน้าคูณบางสิ่งบางอย่าง บวกอย่างอื่น โมดูโลอย่างอื่น
public float nextFloat () {
this . seed = ( this . seed * multiplier + addend ) % modulus ; // update the seed
int randomInteger = ( int ) ( this . seed >> 24 ); // take the top 24 bits of the seed
return randomInteger / (( float ) ( 1 << 24 )); // divide it by 2^24 to get a number between 0 and 1
}ในกรณีนี้ ตัวคูณคือ 25214903917 ตัวบวกคือ 11 และโมดูลัสคือ 2^48
ด้วยการทศนิยมที่ออกมาจากสิ่งนี้ เราสามารถคูณมันด้วย 2^24 เพื่อคืนค่า RandomInteger อีกครั้ง ดังนั้นจึงได้ "ครึ่งบน" (24 บิตที่สำคัญที่สุด) ของเมล็ด 48 บิต
กล่าวโดยย่อ จากการวัดของเรา เราเรียนรู้ว่าเมล็ดอยู่ระหว่าง measuredRandomInteger * 2^24 และ (measuredRandomInteger + 1) * 2^24
และเราทำได้สามครั้งติดต่อกัน สำหรับ X, Y และ Z
และเรารู้ว่าระหว่าง X และ Y และระหว่าง Y และ Z เมล็ดได้รับการอัปเดตตาม newSeed = (oldSeed * 25214903917 + 11) mod 2^48
ฉันต้องพูดถึงว่าตัวเลือกที่ถูกต้องตัวหนึ่งคือ for-loop ที่ลองบิตที่ต่ำกว่าที่เป็นไปได้ทั้งหมด 2^24 บิต สำหรับโปรแกรมเมอร์ที่อ่านข้อความนี้ ฉันหวังว่าสิ่งนี้จะทำให้ชัดเจนว่าปัญหาคืออะไร:
for ( long seed = firstMeasurement << 24 ; seed < ( firstMeasurement + 1 ) << 24 ; seed ++) {
// all these seeds will match the first measurement
if ( nextSeed ( seed ) >> 24 == secondMeasurement && nextSeed ( nextSeed ( seed )) >> 24 == thirdMeasurement ) {
// if nextSeed(seed) matches secondMeasurement, and nextSeed(nextSeed(seed)) matches thirdMeasurement
// then we found a seed that matches all three measurements! yay!
return seed ;
}
}สิ่งนี้จะได้ผลและได้ผล แต่มันไม่เร็วและไม่สนุกขนาดนั้น ดังนั้นเราจึงใช้โครงตาข่ายแทน!
อย่างไรก็ตาม ฉันรู้สึกว่าฉันต้องทำอะไรไม่ถูกไปสักหน่อย ส่วนการลดขนาดขัดแตะเกิดขึ้นที่นี่ แต่มันซับซ้อนมาก และฉันพนันได้เลยว่ามันจะทำให้การรักษาผู้อ่านต่ำ และฉันไม่อยากเสียคุณไป ดังนั้นฉันจะให้วิธีแก้ปัญหา for-loop แก่คุณ (ซึ่งใช้ได้ผล) และดำเนินการในขั้นตอนต่อไปของการหาประโยชน์ คำอธิบายของวิธีการลดตาข่ายจะมาภายหลัง :)
เราจะทำอย่างไรกับเมล็ดพันธุ์นี้เมื่อเรามีมัน?
ก่อนอื่น โปรดทราบว่าเราสามารถก้าว LCG ถอยหลังได้ แน่นอนว่าการบวกสิบเอ็ดสามารถย้อนกลับได้ แต่การคูณด้วยจำนวนมหาศาลนั้นกลับด้านได้หรือไม่ ตัวคูณ 25214903917 ของเราเป็นเลขคี่ หมายความว่าหารด้วย 2 ไม่ลงตัว ดังนั้นจึงไม่มีตัวประกอบใดๆ ร่วมกับโมดูลัส 2^48 ของเรา (เนื่องจาก 2^48 เป็นเพียงกลุ่มของสองเท่านั้น) เนื่องจากมันค่อนข้างเป็นจำนวนเฉพาะของมอดุลัส เราจึงสามารถกลับค่าได้ ซึ่งหมายความว่าต้องหาจำนวน x อีกจำนวนหนึ่งที่ตรงกับ x * 25214903917 - 1 หารด้วย 2^48 ลงตัว หรือกล่าวอีกนัยหนึ่ง 25214903917 * x mod 2^48 = 1 หมายเลขนั้นคือ 246154705703781 . สิ่งนี้จะช่วยกลับด้านการคูณเพราะถ้าเรามี เช่น secret * 25214903917 และเราต้องการหา secret เราก็สามารถคำนวณ secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret
ตกลง เพื่อให้เราสามารถก้าวเมล็ดภายในของ java.util.Random ทั้งไปข้างหน้าและข้างหลัง การส่งต่อคือ newSeed = (oldSeed * 25214903917 + 11) mod 2^48 และย้อนกลับคือ oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 และสิ่งนี้ได้ผลเพราะตัวเลขเหล่านั้น 25214903917 และ 246154705703781 เมื่อคูณกันแล้วออกมาเป็น 1 เมื่อคุณใช้ mod 2^48
ตอนนี้ เมื่อเราก้าวถอยหลัง เราต้องการตรวจสอบในแต่ละขั้นตอนว่าเมล็ดพันธุ์นี้อาจหมายความว่ามีการดำเนินการตรวจสอบ Woodland Mansion ที่ไหนสักแห่งในโลกเมื่อเร็ว ๆ นี้ (จุดรวมของการแสวงหาประโยชน์) เราจะทำอย่างไร?
โลกของ Minecraft มีตั้งแต่ -30 ล้านถึง +30 ล้านบล็อก แต่ละ "ภูมิภาควูดแลนด์" (พื้นที่ของโลกที่มีการสุ่มคฤหาสน์วูดแลนด์หลังเดียวตามรหัสที่แสดงไว้ก่อนหน้านี้) มีขนาด 80 x 80 ชิ้น ซึ่งเท่ากับบล็อก 1280 x 1280 นี่คือ 23437.5 ภูมิภาค Woodland แต่สำหรับโค้ดทั้งหมดของเรา เราปัดเศษขึ้นเป็น 23440 เนื่องจากเป็นตัวเลขแบบกลม และแม้ว่าผู้เล่นของคุณจะเดินทางเกิน 30 ล้านไม่ได้ แต่คุณโหลดส่วนที่เกินมาเพียงแค่ยืนใกล้มัน และเราก็แค่ ไม่อยากให้ต้องกังวลเรื่องนั้นทั้งหมด
ดังนั้น -23440 ถึง +23440 ทั้งบนแกน X และ Z นั่นคือ (23440*2+1)^2 (หรือที่เรียกว่า 2197828161 ) ภูมิภาควูดแลนด์ที่เป็นไปได้ ซึ่งแต่ละภูมิภาคจะสร้าง "เมล็ดพันธุ์คฤหาสน์" ที่เป็นเอกลักษณ์ (หมายถึงเมล็ดพันธุ์ที่เผยให้เห็นว่ามีใครบางคนเพิ่งขนของชิ้นหนึ่งไปยังภูมิภาควูดแลนด์บางแห่ง) เราต้องสามารถตรวจสอบได้ว่ามีบางอย่างที่เป็นเมล็ดพันธุ์คฤหาสน์หรือไม่ เราสามารถทำซ้ำเมล็ดพันธุ์คฤหาสน์ทั้งหมด 2.2 พันล้านเมล็ดเพื่อตรวจสอบแต่ละเมล็ดได้หรือไม่? คงจะช้าเกินไป สามารถสร้าง HashSet ด้วย 2.2 พันล้านรายการได้หรือไม่ จะใช้ RAM มากเกินไปแม้จะใช้ Chronicle Map เหมือนที่เราทำใน nocom และแม้แต่ใน C++ ที่ใช้ abseil-cpp มันก็ใช้เหมือน RAM 50GB และนั่นยังไม่ต้องพูดถึงอีกส่วน: เราต้องการเรียนรู้ว่าพวกเขาอยู่ที่ไหนในโลก (นั่นคือประเด็นทั้งหมด) ดังนั้นจึงไม่ดีพอที่จะเรียนรู้ว่านี่คือเมล็ดพันธุ์คฤหาสน์ เรายังต้องการ (อย่างมีประสิทธิภาพ) เรียนรู้ด้วยว่าภูมิภาค Woodland เป็นสาเหตุใด
จำฟังก์ชันที่เปลี่ยนจาก Woodland Region ไปสู่ Mansion Seed (หมายเหตุ: ตอนนี้ฉันได้รวมค่าคงที่บางส่วนตั้งแต่โค้ดด้านบนเพื่อความเรียบง่าย ตอนนี้สมการนี้มีความเชี่ยวชาญเฉพาะสำหรับ 2b2t's seed ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(หมายเลข -4172144997891902323 มาจาก -4172144997902289642 + 10387319 ซึ่งเป็นเมล็ดพันธุ์โลก 2b2t + ค่าวิเศษที่ใช้สำหรับการเพาะในภูมิภาควูดแลนด์ (ดังที่แสดงไว้ก่อนหน้านี้) สำหรับโลกอื่น ๆ คุณเพียงแค่ใส่เมล็ดพันธุ์ของคุณเองลงในสมการนี้แทน .)
เราทำอะไรไม่ได้มากกับพิกัด x เนื่องจากมันคูณด้วยเลขคู่ แต่สัมประสิทธิ์บนพิกัด z คืออะไร? ดูเหมือนเลขคี่!!! ลองใช้เคล็ดลับเดิมเพื่อกลับด้านอีกครั้ง และเราจะได้ 211541297333629
ลองจินตนาการว่าเรามีเมล็ดพันธุ์ที่ให้มา จะเป็นอย่างไรถ้าเราสามารถวนซ้ำพิกัด X ที่เป็นไปได้ทั้งหมดตั้งแต่ -23440 ถึง +23440 และสำหรับแต่ละพิกัด ให้คำนวณว่าพิกัด Z ของภูมิภาควูดแลนด์จะเป็นอย่างไร หากมันมีเมล็ดคฤหาสน์นี้ กล่าวอีกนัยหนึ่ง สมการข้างต้นทำให้เรามี seed ถ้าเรารู้ x และ z แต่เราจะสร้างสมการที่ให้ z แก่เราได้หรือไม่ ถ้าเรารู้จัก seed และ x ? คำตอบ: ใช่ เราเพิ่งจัดเรียงสมการข้างต้นใหม่ และใช้ข้อเท็จจริงที่ว่าสัมประสิทธิ์ของ Z สามารถแปลงค่าได้เป็น mod 2^48 เนื่องจากเป็นเลขคี่
สมการคือ:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
นี่เป็นวิธีแก้ปัญหาที่ดีทีเดียว เพราะแทนที่จะเป็นสองลูปที่ซ้อนกัน (หนึ่งสำหรับ X และอีกหนึ่งสำหรับ Z) ที่ทำการวนซ้ำทั้งหมด 2.2 พันล้านครั้ง เราสามารถมี for-loop เดียวสำหรับ X ที่ทำการวนซ้ำเพียง 46,881 ครั้ง นี่คือใน Java:
private static WoodlandRegionCoord woodlandValid ( long internalSeed ) {
long seed = 25214903917 ^ internalSeed ; // java.util.Random XORs in the multiplier while doing setSeed, so XOR that back out to go from a "this.seed" to what the input to setSeed() would be
for ( int x = - 23440 ; x <= 23440 ; x ++) {
long z = (( seed + 4172144997891902323L - x * 341873128712L ) * 211541297333629L ) << 16 >> 16 ;
if ( z >= - 23440 && z <= 23440 ) {
return new WoodlandRegionCoord ( x , z );
}
}
return null ;
} (หมายเหตุ: สิ่งแปลก ๆ << 16 >> 16 กำลังทำ mod 2^48 แต่จริงๆ แล้วเราต้องการทำโดยใช้ประเภทที่เซ็นชื่อ เพื่อที่เราจะได้คำตอบที่ถูกต้องเมื่อ z อยู่ระหว่าง -23440 ถึง 0 นี่เป็นวิธี sign- ขยายตัวเลข 48 บิตเป็น 64 บิต โดยเติม 16 บิตบนด้วยบิตเครื่องหมายที่ถูกต้องสำหรับส่วนเสริมของ two)
วิธีนี้ได้ผลและเร็วพอสมควร.... สำหรับเมล็ดเดียว แต่จำไว้ว่าเรากำลังถอย RNG ออกไปหลายพันก้าว และดำเนินการตรวจสอบนี้ในแต่ละขั้นตอนจนกว่าเราจะพบรายการที่ตรงกัน ในเวลานั้น เราใช้ DigitalOcean droplet อันห่วยๆ ที่ระดับต่ำสุด และนี่ทำให้ทุกอย่างล้าหลังและไม่สามารถตามทันเรียลไทม์ได้ (บอทขุดหลายบล็อกต่อวินาที แต่ละบล็อกใช้ rng หลายพันก้าวในการถอดรหัส และแต่ละขั้นตอน rng ต้องใช้การดำเนินการ 23440*2+1 เพื่อตรวจสอบ คูณเข้าด้วยกัน และคุณจะเข้าสู่การดำเนินงานนับร้อยล้านต่อวินาที ดังนั้นคุณจะเห็นว่าทำไมถึงมีปัญหากับ VPS ที่เส็งเคร็ง โดยเฉพาะอย่างยิ่งเมื่อ VPS นั้นพยายามเรียกใช้ Minecraft ที่ไม่มีหัวหลายตัว)
อย่างไรก็ตาม เราจึงเปลี่ยนมาใช้วิธีตารางการค้นหาและเขียนใหม่ใน Cuda เพื่อให้ทำงานบนเดสก์ท็อปของฉันเป็นงานแบทช์ทุกๆ สองสามนาที สามารถทำได้นับล้านต่อวินาทีอย่างแท้จริง เนื่องจากคอร์ cuda แต่ละคอร์จากหลายพันคอร์สามารถทำงานบนเมล็ดของตัวเองแบบขนานได้ แนวคิด: คีย์ของตารางค้นหาคือ 32 บิตล่างของเมล็ดพันธุ์คฤหาสน์ และค่าคือพิกัด X ของภูมิภาควูดแลนด์ ตารางค้นหานี้ทำงานได้โดยไม่มีการชนกัน เนื่องจากแต่ละแมนชั่นซีดมีค่าต่ำกว่า 32 บิต ไม่ซ้ำกัน ฉันไม่เข้าใจว่าทำไมถึงเป็นอย่างนั้น มันช่างน่าหลงใหล คุณคงคิดว่ามันใช้งานไม่ได้ แต่ฉันคิดว่าค่าสัมประสิทธิ์ 341873128712 และ 132897987541 อาจถูกเลือกมาเป็นพิเศษเพื่อให้งานนี้? เช่น ถ้าคุณมีลูกหิน 2.2 พันล้านลูก และถัง 4.3 พันล้านถัง และคุณใส่ลูกหินแต่ละลูกลงในถังแบบสุ่ม โดยแยกจากกัน โอกาสที่ลูกหินแต่ละลูกจะได้รับถังของตัวเองเป็นเท่าใด โดยพื้นฐานแล้วเป็นศูนย์ ใกล้ถึงจุดสิ้นสุด ลูกแก้วใหม่แต่ละลูกมีโอกาสมากกว่า 50% ที่จะโดนถังที่เต็มไปแล้ว แต่เห็นได้ชัดว่าสิ่งเหล่านี้ไม่ได้สุ่มตัวอย่างอิสระ ดังนั้นมันจึงได้ผล น่าแปลกที่ถ้าคุณอ่านข้อความนี้และเข้าใจว่ามันทำงานอย่างไร หรือเหตุใดสัมประสิทธิ์เฉพาะสองตัวนี้จึงได้ผล โปรดบอกฉันด้วย ยังไงก็ตามมันได้ผล ตารางค้นหามี 2^32 รายการ และแต่ละรายการมีขนาด 2 ไบต์ (เนื่องจากเป็นเพียงตัวเลขระหว่าง -23440 ถึง +23440) ดังนั้นจึงต้องใช้ VRAM ประมาณ 9 กิกะไบต์บน GPU ของคุณ
ฟังก์ชั่นตรวจสอบป่าไม้ตอนนี้ดูเหมือนว่า (อีกครั้ง นี่คือรหัสจริง แต่ทำให้ง่ายขึ้น ตัวช่วยและค่าคงที่ทั้งหมดอยู่ในบรรทัด ฯลฯ ):
__global__ void computeSteps ( const int16_t * mansionTable, const int64_t * seedsArr, Result* resultArr, size_t numData) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
[[unlikely]] if (tid >= numData) {
return ;
}
auto seed = seedsArr[tid];
int steps = 0 ;
while ( true ) {
auto externalSeed = seed ^ 25214903917 ;
const auto x = mansionTable[externalSeed & (( 1LL << 32 ) - 1 )];
const auto z = ((externalSeed + 4172144997891902323LL - ( int64_t ) x * 341873128712LL ) * 211541297333629LL ) << 16 >> 16 ;
if (z >= - 23440 & z <= 23440 ) {
resultArr[tid] = {. startSeed = seedsArr[tid], . x = ( int16_t ) x, . z = ( int16_t ) z, . steps = steps};
return ;
}
seed = ((seed - 0xBLL ) * 0xdfe05bcb1365LL ) & (( 1LL << 48 ) - 1 ); // prevSeed(seed)
steps++;
}
}
// and that mansionTable was generated like this
// note: mansionTable must be calloc'd before this function because not every entry will be written to, and an x value outside -23440 to 23440 bounds could create a false positive later on while using the table
__global__ void writeToSeedTable ( int16_t * mansionTable) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
if (tid >= ( 23440 * 2 + 1 ) * ( 23440 * 2 + 1 )) return ;
auto x = tid / ( 23440 * 2 + 1 ) - 23440 ;
auto z = tid % ( 23440 * 2 + 1 ) - 23440 ;
auto seed = (( int64_t ) x * 341873128712LL + ( int64_t ) z * 132897987541LL - 4172144997891902323LL ) & (( 1LL << 48 ) - 1 );
mansionTable[seed & (( 1LL << 32 ) - 1 )] = ( int16_t ) x;
}สิ่งนี้ใช้งานได้ดีในแบตช์ขนาดยักษ์และสามารถแคร็กได้ลำดับสิบล้านเมล็ดต่อวินาทีใน 3090 ปรากฏว่าไม่ใช่เรื่องใหญ่เกินไปเมื่อเธรดบางเธรดในวาร์ปยุติก่อนกำหนด และเราไม่สามารถทำได้จริงๆ มันเร็วกว่านี้อีก (เหตุผลก็คือโดยพื้นฐานแล้วเราไม่สามารถรู้ล่วงหน้าได้ว่าเมล็ดพันธุ์ไหนจะก้าวมากหรือน้อย)
ก็ประมาณนั้นแหละ เมื่อพิจารณาจากเมล็ดพันธุ์แล้ว นั่นเป็นวิธีที่เราได้พื้นที่วูดแลนด์ในโลกที่เกิดก้อนเนื้อจำนวนมากครั้งล่าสุด กล่าวอีกนัยหนึ่ง เราเพิ่งทราบว่าครั้งล่าสุดที่มีคนเดินไปรอบๆ บน 2b2t และบรรทุกพื้นที่ใหม่ของโลกนั้น อยู่ที่ไหน สัก แห่งภายในขอบเขต Woodland ขนาด 1280 x 1280 ที่เราเพิ่งระบุ (ซึ่งแม่นยำมากพอที่จะค้นหาได้โดยใช้เวลาเพียงไม่กี่นาทีในการค้นหา)
ในทางปฏิบัติ จำเป็นต้องมี RNG กี่ขั้นตอน? การวัดที่เชื่อถือได้เริ่มต้นที่ 4 RNG ขั้นตอนด้านล่างทั้งหมดคือข้อผิดพลาดในการวัด / สัญญาณรบกวนแบบสุ่ม ซึ่งเราทราบเนื่องจากรหัส Woodland Mansion เรียก rand.nextInt ทันทีสี่ครั้งก่อนที่เราจะวัดได้ โดยเฉลี่ยแล้ว แต่ละเมล็ดของ Woodland แต่ละเมล็ดจะมีขั้นตอนประมาณ 128,000 ขั้น แต่ในทางปฏิบัติ ส่วนใหญ่แล้วบน 2b2t เราพบเมล็ดของ Woodland ภายในไม่กี่สิบก้าว นี่เป็นเพราะรายละเอียดของสิ่งที่เกิดขึ้นตามลำดับในขีด Minecraft ในทางเทคนิคแล้ว การวัดผลของเราเกิดขึ้นที่จุดเริ่มต้นของ Tick เนื่องจากนั่นคือที่ที่แพ็กเก็ตสำหรับการทำลายบล็อกได้รับการประมวลผล โดยทั่วไปแล้ว มีการโหลดก้อนข้อมูลในประวัติล่าสุดระหว่างขีดก่อนหน้า อย่างไรก็ตาม บางครั้งเหตุการณ์อาจทำให้เกิดขั้นตอน RNG มากมายในระหว่างนั้น เราเชื่อว่าเหตุการณ์นี้คือการระเบิด เช่น มีคนระเบิดเอนด์คริสตัลด้วยการต่อยมัน หรืออาจทำให้กะโหลกเหี่ยวเฉา การระเบิดของคริสตัลตอนท้ายจะเกิดขึ้นในระหว่างการประมวลผลแพ็กเก็ตจากแพ็กเก็ตหมัดของผู้เล่น และจำนวนขั้นตอน RNG ก็เรียงกันที่ 1,354 ขั้นตอน (1,352 จากการคำนวณความเสียหายของบล็อกในรูปลูกบาศก์
และบนพิกัดที่ใช้เป็นตัวอย่างในแผนภาพนี้ นี่คือสิ่งที่โค้ดด้านบนแสดงออกมา:
jshell> crackItemDropCoordinate(0.730696, 0.294929355, 0.634865435)
Item drop appeared at 0.730696 0.294929355 0.634865435
RNG measurements are therefore 16129481 1507579 12913941
This indicates the java.util.Random internal seed must have been 270607788940196
Found a woodland match at woodland region 123 456 which would have set the seed to 261215197308064
Located someone between 157312,583552 and 158591,584831
jshell>
สังเกตว่ามันค้นหาตำแหน่งของ Woodland Region 123,456 ได้อย่างไร และสังเกตว่า "ระบุตำแหน่งใครบางคนระหว่าง" สุดท้ายจะรวมพิกัดจริงที่เราป้อนไว้ในตอนแรก ซึ่งก็คือ x=157440 z=583680 นอกจากนี้ การวัด RNG จะจับคู่เลขฐานสิบหกที่เป็นสีแดง: 0xf61dc9 เท่ากับ 16129481 , 0x1700fb เท่ากับ 1507579 และ 0xc50d15 เท่ากับ 12913941 และสำหรับเมล็ดพืช 0xed92e70ba4a0 เท่ากับ 261215197308064 และ 0xf61dc9221ba4 เท่ากับ 270607788940196
คุณอาจพบตัวเลือกแพตช์หรือการกำหนดค่าสำหรับการปิดใช้งานการจัดการ RNG บางอย่างเช่นนั้นจะใช้ได้กับแพตช์ Randar และอาจเป็นวิธีที่ง่ายที่สุด หากคุณไม่พบวิธีง่ายๆ ในการปิดการใช้งานการจัดการ RNG นี่คือโค้ดที่ต้องปรับแต่งในระดับ World :
เวอร์ชันที่มีช่องโหว่:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}เพียงเปลี่ยนฟังก์ชันนี้เพื่อส่งคืนการสุ่มที่แตกต่างกันในแต่ละครั้งแทน หากคุณต้องการการป้องกันที่สมบูรณ์แบบ:
เวอร์ชันที่ได้รับการแก้ไข:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} นั่นอาจไม่ได้ประสิทธิภาพที่ยอดเยี่ยม ดังนั้นหากคุณต้องการคุณสามารถแนะนำฟิลด์ใหม่ separateRandOnlyForWorldGen ซึ่งจะไม่แชร์กับสิ่งอื่นใด เช่น:
private final Random separateRandOnlyForWorldGen = new Random (); // new field on the World class
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . separateRandOnlyForWorldGen . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . separateRandOnlyForWorldGen ;
}หากคุณใช้ PaperMC สำหรับ 1.12.2 นี่คือแพตช์ที่คุณสามารถใช้ได้ ลิงค์สำรอง.
นี่จะเป็นส่วนเพิ่มเติมที่ฉันพูดถึงสิ่งพิเศษบางอย่างที่สมเหตุสมผลกว่าที่จะอธิบายจากมุมมองของฉัน นอกเหนือจากแนวคิดพื้นฐานแล้ว ส่วนใหญ่แล้วเราพัฒนาสิ่งต่าง ๆ อย่างเป็นอิสระ
สิ่งแรกที่ฉันอยากจะพูดถึงคือระบบการหาพิกัดจากเมล็ด Mason ใช้ตารางการค้นหาขนาดใหญ่และการประมวลผล GPU ฉันพึ่งแคชเพื่อความเร็วแทน เมื่อใดก็ตามที่เกิดการปะทะ พิกัดของมันและพิกัดทั้งหมดภายในรัศมีจะถูกใส่ลงใน HashMap เมล็ดจะถูกประมวลผลในสองรอบ การส่งผ่านครั้งแรกจะไล่ RNG กลับไป และตรวจสอบว่ามี Seed อยู่ในแคชหรือไม่ หรือเป็น Seed เดียวกันที่ประมวลผลครั้งล่าสุด ซึ่งถือว่าแตกต่างออกไป การส่งครั้งที่สองจะเกิดขึ้นก็ต่อเมื่อการส่งครั้งแรกล้มเหลว ช้ากว่ามาก และใช้อัลกอริธึมที่ค่อนข้างแพงตามที่อธิบายไว้ก่อนหน้านี้ ผลข้างเคียงที่น่าพึงพอใจของระบบนี้คือการส่งบอลครั้งแรกมีศักยภาพที่จะ "ข้าม" อย่างอื่นที่ "ถูกต้อง" แต่มีแนวโน้มน้อยกว่าที่จะเป็นตำแหน่งที่ถูกต้อง ซึ่งจะช่วยในเรื่องผลบวกลวง
นี่คือรหัสนั้น:
public class RandarCoordFinder
{
public static final long X_MULT = 341873128712L ;
public static final long Z_MULT = 132897987541L ;
public static final long Z_MULT_INV = 211541297333629L ;
public static final int MANSION_SALT = 10387319 ;
public static final int MANSION_SPACING = 80 ;
public static final int CITY_SALT = 10387313 ;
public static final int CITY_SPACING = 20 ;
// the last seed we processed
public long lastSeed = - 1 ;
// a mapping of seed -> x,z that is updated everytime we get a hit
public final HashMap < Long , Long > hitCache = new HashMap <>();
// set this according to the server's seed
public long worldSeed ;
// change these if you need to use different structures
public int salt = MANSION_SALT ;
public int spacing = MANSION_SPACING ;
public RandarCoordFinder ( long worldSeed )
{
this . worldSeed = worldSeed ;
}
// a simple class that extends java.util.Random and provides some extra methods and constants we need
public static class RandarRandom extends Random
{
public static final long MULT = 0x5DEECE66DL ;
public static final long ADDEND = 0xBL ;
public static final long MASK = ( 1L << 48 ) - 1 ;
public static final long MULT_INV = 0xDFE05BCB1365L ;
public long seed ;
public RandarRandom ( long seed )
{
this . seed = seed ;
}
@ Override
public void setSeed ( long seed )
{
this . seed = seed ;
}
@ Override
public int next ( int bits )
{
seed = ( seed * MULT + ADDEND ) & MASK ;
return ( int )( seed >> 48 - bits );
}
public int prevInt ()
{
seed = (( seed - ADDEND ) * MULT_INV ) & MASK ;
return ( int )( seed >> 16 );
}
}
public enum FindType
{
HIT ,
SKIP ,
FAIL ;
}
public record FindResult ( FindType type , int xCoord , int zCoord , int steps )
{
}
public FindResult findCoordsSeed ( long seed , int maxSteps )
{
seed &= RandarRandom . MASK ;
// remember and update lastSeed
long last = lastSeed ;
lastSeed = seed ;
RandarRandom random = new RandarRandom ( seed );
// first pass - this is meant to be quick
for ( int i = 0 ; i < maxSteps + 100000 ; i ++)
{
if ( random . seed == last && i > 0 )
{
// we encountered the last processed seed while stepping back, skip
return new FindResult ( FindType . SKIP , 0 , 0 , i );
}
else
{
Long hashValue = hitCache . get ( random . seed );
if ( hashValue != null )
{
// we found a hit in our cache
int xCoord = ( int )(( hashValue >> 32 ) & 0xFFFFFFFF );
int zCoord = ( int )( hashValue & 0xFFFFFFFF );
cacheNearby ( xCoord , zCoord , 8 );
return new FindResult ( FindType . HIT , xCoord , zCoord , i );
}
}
random . prevInt ();
}
random . seed = seed ;
// second pass - this is slow and should only happen if the first pass fails
for ( int i = 0 ; i < maxSteps ; i ++)
{
// undo worldSeed and salt
long seedValue = ( random . seed ^ RandarRandom . MULT ) - worldSeed -
( long ) salt ;
Coords coords = findCoords ( seedValue , 1875000 / spacing + 8 );
if ( coords != null )
{
// we found a hit
cacheNearby ( coords . x , coords . z , 8 );
return new FindResult ( FindType . HIT , coords . x , coords . z , i );
}
random . prevInt ();
}
// we could not find anything
return new FindResult ( FindType . FAIL , 0 , 0 , - 1 );
}
public static long getRandomSeed ( int x , int z , int salt , long seed )
{
return (( long ) x * X_MULT + ( long ) z * Z_MULT ) + seed + ( long ) salt ;
}
private void cacheNearby ( int x , int z , int radius )
{
for ( int xOff = - radius ; xOff <= radius ; xOff ++)
{
for ( int zOff = - radius ; zOff <= radius ; zOff ++)
{
int cacheX = x + xOff ;
int cacheZ = z + zOff ;
long cacheSeed = ( getRandomSeed ( cacheX , cacheZ , salt ,
worldSeed ) ^ RandarRandom . MULT ) & RandarRandom . MASK ;
hitCache . put ( cacheSeed , ( long ) cacheX << 32 | cacheZ &
0xFFFFFFFFL );
}
}
}
public record Coords ( int x , int z )
{
}
public static Coords findCoords ( long value , int distance )
{
value &= RandarRandom . MASK ;
for ( int x = - distance ; x <= distance ; x ++)
{
long testValue = ( value - X_MULT * x ) & RandarRandom . MASK ;
long z = ( testValue * Z_MULT_INV ) << 16 >> 16 ;
if ( Math . abs ( z ) <= distance )
{
return new Coords ( x , ( int ) z );
}
}
return null ;
}
}อีกสิ่งหนึ่งที่ฉันอยากจะพูดถึงคือวิธีที่ฉันใช้สิ่งนี้ใน The End ตามที่กล่าวไว้ก่อนหน้านี้ ชิ้นส่วนใน The End จะส่งผลต่อ RNG เพียงครั้งเดียวเท่านั้นเมื่อสร้างขึ้นครั้งแรก สิ่งนี้ทำให้สิ่งต่าง ๆ ซับซ้อนมากขึ้น ไม่เหมือนใน Overworld ตรงที่ไม่สามารถค้นหาผู้เล่นได้โดยเพียงแค่โหลดชิ้นส่วนที่ฐานของพวกเขา
แต่มีสถานการณ์หลักอีกสองสถานการณ์ที่เราต้องพึ่งพา:
สถานการณ์แรกโดยพื้นฐานแล้วหมายความว่าเรายังคง สามารถ ใช้วิธีไร้เดียงสาในการนับจำนวนครั้งที่แตกต่างกันของภูมิภาคที่ถูกโจมตี อย่างไรก็ตาม เราจะถูกจำกัดอย่างมากเนื่องจากการโจมตีอาจไม่บ่อยนัก และอาจทำให้สับสนโดยใครบางคนที่บินผ่านพื้นที่ใน ชัดเจนไม่กี่ครั้ง สถานการณ์ที่สองกำหนดให้เราต้องระบุและติดตามเส้นทางเหล่านี้
แล้วเราจะติดตามเส้นทางได้อย่างไร? ตามทฤษฎีแล้ว คุณสามารถสร้างระบบเพื่อระบุและติดตามเส้นทางได้โดยอัตโนมัติ อย่างไรก็ตาม ฉันไม่เคยใช้สิ่งนี้เลยและเพียงแค่ติดตามเส้นทางด้วยตนเองด้วยสายตา เมื่อติดตามเส้นทาง มีแนวคิดบางประการที่สามารถช่วยได้ ตัวอย่างเช่น เส้นทางหลายเส้นทางที่นำไปสู่สถานที่เดียวกันน่าจะหมายความว่ามีฐาน การรู้ว่าการชนหรือการตามรอยนั้นเกิดจากผู้เล่นคนใดคนหนึ่งสามารถช่วยได้เช่นกัน โดยจะอธิบายเพิ่มเติมในภายหลัง
แล้วเราจะบอกได้อย่างไรว่าผู้เล่นคนไหนที่ทำให้เกิดการโจมตี? ใน Overworld เราสามารถมองหาการโจมตีที่ "แตกต่าง" ที่เกิดขึ้นทันทีหลังจากที่ผู้เล่นเข้าร่วม อย่างไรก็ตาม นั่นไม่น่าจะได้ผลที่นี่ ดังนั้นเราจึงต้องทำอย่างอื่น จริงๆ แล้วมีระบบที่เรียบร้อยสำหรับสิ่งนี้ มันขึ้นอยู่กับสมมติฐานว่ามีผู้เล่นไม่มากนักที่ออนไลน์จริง ๆ ใน The End พร้อม ๆ กัน และแนวคิดที่เราสามารถบอกได้ว่าผู้เล่นเหล่านี้คือใคร แนวคิดก็คือจำนวนการเรียก RNG ต่อ Tick ส่วนหนึ่งมีความสัมพันธ์กับจำนวนชิ้นที่โหลดในปัจจุบัน ดังนั้นจำนวนผู้เล่นในมิตินั้น ด้วยการเฝ้าดูการเพิ่มขึ้นหรือลดลงอย่างฉับพลันของจำนวนการโทรเหล่านี้ทันทีหลังจากที่ผู้เล่นเข้าร่วมหรือออกตามลำดับ เราสามารถระบุผู้เล่นที่อยู่ในจุดจบได้ เราจะเรียกระบบนี้ว่า "End Occupancy Tracker" (EOT)
EOT จะดูแลรักษาสองชุด ตอนแรกจะติดตามว่าเราคิดว่าใครคือใครใน The End "ตอนนี้" สิ่งนี้อาจทำให้ผู้เล่นพลาดได้ ดังนั้นจึงถือว่ามีแนวโน้มที่จะเกิดผลลบลวงมากกว่า ส่วนที่สองติดตามว่าเราคิดว่าใคร เป็น ใครใน The End "โดยรวม" ย้อนกลับและส่งต่อในระยะเวลาหนึ่ง สิ่งนี้จะรวมกับผู้เล่นที่กำลังออนไลน์อยู่ และถือว่ามีแนวโน้มที่จะเกิดผลบวกลวงมากกว่า เมื่อพิจารณาชุดเหล่านี้เมื่อเกิดการโจมตี และทำการอนุมานด้วยตนเอง เราจะทราบคร่าวๆ ว่าใครคือผู้ที่ทำให้เกิดการโจมตีดังกล่าว
ควรสังเกตว่า EOT ได้รับการทดสอบใน 9B9T เท่านั้นและในปัจจุบันอาจพึ่งพาเงื่อนไขที่อาจไม่เป็นจริงในเซิร์ฟเวอร์อื่น ๆ เช่น 2B2T สันนิษฐานว่า RNG สามารถสุ่มตัวอย่างทุกเห็บได้โดยไม่มีความผันผวนมากซึ่งอาจเป็นเรื่องยากสำหรับ 2b2t เนื่องจากขีด จำกัด ความเร็วของบล็อก สิ่งต่าง ๆ อาจจะทำให้ยุ่งยากหากมีกิจกรรมของผู้เล่นมากขึ้นในตอนท้ายบนเซิร์ฟเวอร์ซึ่งอาจเป็นจริงสำหรับ 2B2T เนื่องจากเป็นเซิร์ฟเวอร์ที่ใหญ่กว่ามาก
