[JAVA] Minecraft 1.12.2 Retour calcul des graines du monde à partir de la carte du monde

environnement

Contexte

Que se passe-t-il si la valeur de départ est divulguée dans le multijoueur Minecraft? Vous pouvez faire ce qui suit avec une idée simple.

Cela ne nécessite pas que le client ait un MOD, donc même si la version du client, le MOD et la non-modification sont spécifiés au niveau de la règle du serveur, aucune contre-mesure ne peut être prise.

Avec les restrictions MOD client - Si un seul joueur spécifique connaît la graine sur un serveur privé et que ce joueur utilise la graine, même la spécification des coordonnées du minerai de diamant entraînera une destruction considérable de l'équilibre.

Je me suis donc demandé si un joueur multi-joueurs non-saba can pouvait rechercher des graines en utilisant uniquement les informations disponibles par des moyens légitimes sans casser le serveur. Si cela est possible, quel que soit le degré de confidentialité de la graine par l'administrateur du serveur, il peut être physiquement connu, donc ** la surveillance du comportement et les règles locales doivent être prises séparément **.

règle

Connaissez la graine du monde lorsque vous avez un serveur Minecraft 1.12.2 Java Edition qui produit le même terrain que la vanille avec quelques MOD Forge.

conditions

supposition

Interdire

Possible

stratégie

La stratégie sous-jacente consiste à utiliser "tester tous les candidats potentiels pour voir si une graine produit un terrain particulier". Cependant, dans l'état actuel des choses, 2 ^ 64 graines peuvent être prises en compte, donc même si la partie de jugement est considérablement accélérée, cela prendra environ 10 000 ans pour un PC privé ordinaire. Il semble que ce sera bientôt fini si vous utilisez Spacon, mais il est difficile de dire qu'il est possible de le savoir.

«Essayer pour tous les candidats de départ possibles de voir si une graine produit un terrain particulier» est écrit en pseudo-code comme suit:

for (long seed = 0; seed != 0xFFFFFFFFFFFFFFFFL; seed++) { // (1)
    if (f(seed)) System.out.println(seed);
}

/**
 *Une fonction qui renvoie si une graine crée ou non ce monde.
 */
abstract boolean f(long seed); // (2)

Ici, les points à améliorer sont (1) et (2). À l'heure actuelle, le nombre de boucles pour (1) est trop grand et cela prend environ 10 000 ans, il est donc nécessaire d'utiliser une méthode de boucle qui peut économiser plus de calculs. (2) doit être réduit par la formule la plus simple possible.

(2) peut également être à plusieurs étages.

for (long seed = 0; seed != 0xFFFFFFFFFFFFFFFFL; seed++) {
    if (f1(seed) && f2(seed) && f3(seed)) System.out.println(seed);
}

/**
 *Une fonction rapide qui réduit à peu près les candidats
 */
abstract boolean f1(long seed);

/**
 *Fonction à vitesse moyenne qui réduit les candidats à quelques
 */
abstract boolean f2(long seed);

/**
 *Une fonction lente qui réduit les candidats à un
 */
abstract boolean f3(long seed);

Cette fois, nous identifierons la graine avec une stratégie comme celle-ci.

f1 Fonction haute vitesse qui réduit approximativement les candidats

Puisque f1 doit de toute façon être rapide, je vais en faire une fonction qui peut être gérée par GPGPU. Pour ce faire, certaines des conditions suivantes doivent être remplies.

Par exemple, x-> x + 700 == 4 est simple, donc ça va. x-> Math.sin (x * 0.001) == 1 doit faire quelque chose à propos de Math.sin. x-> world.getBiome (new BlockPos (x, 65, 0)) == Biome.FOREST n'est pas possible.

Aparapi est utilisé pour le GPU.

--J'ai essayé le fonctionnement GPU (Aparapi) avec le journal de Java --ka-ka_xyz http://ka-ka-xyz.hatenablog.com/entry/20180129/1517152510

Je l'ai utilisé pour le GPU.

Il y a de la place pour un raccourcissement supplémentaire avec un meilleur GPU.

Ici, la position de génération du village est utilisée pour f1.

--Minecraft 1.12.2 Algorithme de partie de détermination des coordonnées du village --Qiita https://qiita.com/MirrgieRiana/items/0a3baee86bb661dc5f99

En utilisant les coordonnées générées par le village, vous pouvez affiner approximativement les candidats par la procédure suivante.

--Découvrez environ 8 villages

Le fait qu'une graine mondiale crée ou non un village à une certaine coordonnée de bloc est calculé par la fonction suivante test.

int distance = 32;

boolean test(long seed, int chunkX, int chunkZ)
{
	seed += (long) getRegionIndex(chunkX) * 341873128712L + (long) getRegionIndex(chunkZ) * 132897987541L + 10387312L;
	seed = seed ^ 0x5DEECE66DL;
	seed = next(seed);
	if (!test2(seed, chunkX)) return false;
	seed = next(seed);
	if (!test2(seed, chunkZ)) return false;
	return true;
}

boolean test2(long s, int chunkIndex)
{
	return (s >> 17) % 24 == getChunkIndexInRegion(chunkIndex);
}

int getRegionIndex(int chunkIndex)
{
	if (chunkIndex < 0) chunkIndex -= 31;
	return chunkIndex / 32;
}

int getChunkIndexInRegion(int chunkIndex)
{
	return chunkIndex - getRegionIndex(chunkIndex) * 32;
}

long next(long s)
{
	return (s * 0x5DEECE66DL + 0xBL) & 0xffffffffffffL;
}

long prev(long s)
{
	return ((s - 0xBL) * 0xdfe05bcb1365L) & 0xffffffffffffL;
}

Ce code s'étend à l'intérieur de Random. Voir ci-dessous pour le traitement interne de Random.

Cette fonction est disponible auprès d'Aparapi car elle est indépendante de l'instance JRE ou Minecraft.

Dans ce qui suit, nous supposerons que la distance est fixée à 32, qui est la valeur par défaut. Ensuite, il y a 24 coordonnées de génération de village différentes dans la zone par axe de coordonnées.

Vous pouvez réduire grossièrement les graines en appelant la fonction ci-dessus pour le nombre de villages étudiés.

Cependant, en raison de la troncature des 16 bits supérieurs de Random, cette fonction ne peut pas, en principe, réduire le nombre de candidats de départ à un, quel que soit le niveau d'investigation du village. Donc, je vais réduire à environ 1000 des 2 ^ 48 façons comme suit, puis réduire à nouveau environ 65536 * 1000 candidats.

for (long seed = 0; seed != 0xFFFFFFFFFFFFL; seed++) {
    if (!test(seed, -16, -18)) continue; //Village de placement de semences 1251341
    if (!test(seed, 12, -49)) continue;
    if (!test(seed, -77, 19)) continue;
    if (!test(seed, 21, -80)) continue;
    System.out.println(seed);
}

Si 2 ^ 64 voies prennent 10 000 ans, 2 ^ 48 ≒ 2.8E + 14 voies prendront environ 50 jours par simple calcul. Le rétrécissement ultérieur de 65536000 ≒ 6,5E + 7 voies est bien moins que cela.

(1) Optimisation de la partie boucle

J'ai pu réduire le nombre de calculs à environ 50 jours, mais il est encore difficile de dire qu'il est possible de calculer. Cependant, il existe en fait un moyen simple de le réduire à 1/24. Pour ce faire, utilisez l'algorithme de génération de village et les spécifications aléatoires répertoriés ci-dessus. Les coordonnées générées d'un village ont une performance de rétrécissement de 1 / (24 * 24) pour un village et de 1/24 pour un seul côté des coordonnées. Le code ci-dessous est une compilation de «test» et «test2». Ici, la graine au moment de (3) peut être prédite dans une certaine mesure.

boolean test(long seed, int chunkX, int chunkZ)
{
	seed += (long) getRegionIndex(chunkX) * 341873128712L + (long) getRegionIndex(chunkZ) * 132897987541L + 10387312L;
	seed = seed ^ 0x5DEECE66DL;
	seed = next(seed);
	// (3)
	if (!((seed >> 17) % 24 == getChunkIndexInRegion(chunkX))) return false; // (4)
	seed = next(seed);
	if (!((seed >> 17) % 24 == getChunkIndexInRegion(chunkZ))) return false;
	return true;
}

Si la partie getChunkIndexInRegion (chunkX) était de 20, la formule de jugement dans (4) serait (seed >> 17)% 24 == 20. Décalez vers la droite de 17 et faites une boucle pour les nombres où la valeur divisée par 24 est 20.

La structure binaire de la graine est la suivante.

-------- -------- 00000000 00000000 00000000 0000000? ???????? ????????

Ici, - est la partie qui est ignorée par les spécifications de Random (cela n'affecte pas le placement du village), et? Est la partie qui est rejetée par le décalage de droite 17 (cela affecte le placement du village, mais le morceau X du premier village). N'affecte pas). Pour fixer le bloc X du premier village, le reste du «0» restant divisé par 24 doit être une valeur spécifique. De plus, la partie ? Peut être n'importe quoi, alors faites une boucle à l'intérieur pour qu'il y ait 17 bits de liberté. La version codée est la suivante.

int chunkX1 = 20;
int chunkZ1 = 20;

for (long j = getChunkIndexInRegion(chunkX1); j <= 0x7FFFFFFFL; j += 24) {
    for (long i = 0; i <= 0x1FFL; i++) {
        long s = (j << 17) | i; // (5)
        
    }
}

** Addendum: for (long i = 0; i <= 0x1FFL; i ++) { est un mystère. Il existe une théorie selon laquelle for (long i = 0; i <= 0x1FFFFL; i ++) { est correct. ** **

«chunkX1» et «chunkZ1» sont les coordonnées du bloc du premier village dans la liste des coordonnées du village.

Cependant, le «s» dans (5) représente la «graine» au moment de (3), vous devez donc calculer un peu pour obtenir la graine du monde lui-même. Pour changer «s» en «seed»:

long seed = s;
seed = prev(seed);
seed = seed ^ 0x5DEECE66DL;
seed -= (long) getRegionIndex(chunkX1) * 341873128712L + (long) getRegionIndex(chunkZ1) * 132897987541L + 10387312L;
seed = seed & 0xFFFFFFFFFFFFL;

Maintenant, nous pouvons boucler la graine du monde où le village est généré à une certaine coordonnée X dans une certaine zone. Cela porte le nombre de boucles à 2 ^ 48/24. C'est un calcul qui prend environ deux jours, donc c'est assez réaliste. Dans l'expérience, les coordonnées de huit villages ont été étudiées, le calcul a été effectué en environ 27 heures en utilisant le GPGPU (performances médiocres), et les modèles de 48 bits inférieurs ont pu être réduits à environ 250 candidats.

f2 Fonction à vitesse moyenne qui réduit les candidats à quelques

Connaissances antérieures

Dans cette fonction, f1 spécifie jusqu'à un candidat parmi les 48 bits inférieurs, qui est réduit à environ 1000 candidats.

Dans l'expérience, 8 villages ont été étudiés, donc il devrait y avoir une performance de rétrécissement (73 bits) de 24 ^ (2 * 8), mais en réalité, environ 250 candidats sont nés. Par conséquent, il est peu probable que f1 puisse en identifier jusqu'à un. On considère qu'un grand nombre de motifs de 48 bits inférieurs correspondent à un agencement.

f2 est utilisé pour identifier le modèle de 48 bits inférieur comme un. f2 semble avoir autant de capacité. Si vous passez des centaines de fois plus de temps avec f3, vous n'avez pas besoin de f2, mais f3 est assez lourd, donc je veux le sauvegarder.

stratégie

Nous utiliserons également des villages ici, mais cette fois, nous nous concentrerons sur la structure plutôt que sur le placement.

--Minecraft 1.12.2 Algorithme de partie de détermination des coordonnées du village --Qiita https://qiita.com/MirrgieRiana/items/0a3baee86bb661dc5f99 --Minecraft 1.12.2 Liste des bâtiments du village --Qiita https://qiita.com/MirrgieRiana/items/b5d56b4d78c503ddb7a0

Le village est composé de parties autres que des bâtiments tels que des puits, des routes et des rues, et des parties de bâtiments telles que des maisons, des champs et des églises. Ici, nous prêtons attention au nombre de bâtiments faciles à comprendre visuellement.

Par exemple, le village suivant est composé des bâtiments suivants.

2018-09-22_22.03.33.png

--Maison1 3 maisons étagères --Maison2 2 forgerons --Maison3 Salle de danse 1 --House4Garden Cube 6 pièces --WoodHut 5 toilettes

Par exemple, organisons cela par le bas et montrons-le avec une valeur de hachage de 0x422356123L. Exprimant la structure du village comme une valeur de hachage basée sur le nombre de bâtiments, le problème est simple car == peut être utilisé pour juger si les formes sont presque les mêmes. De plus, il est facile de collecter des informations car elles peuvent être facilement calculées à partir des informations qui peuvent être visuellement confirmées en exprimant le nombre de bâtiments dans le village. Même avec cela, il a la capacité de réduire le modèle des 48 bits inférieurs de la graine de 1000 à 1 dans une enquête d'environ 1 ou 2 villages.

Puisque les coordonnées de bloc générées de ce village sont -16, -18, cela s'appelle "* Seed 1251341 génère un village de 0x422356123L aux coordonnées de bloc -16, -18 *".

Les nombres aléatoires qui déterminent la structure du village sont générés par MapGenBase # generate, légèrement modifiés par MapGenStructure # recursiveGenerate, et utilisés dans MapGenVillage.Start # new. Si cela est transformé en code, cela ressemblera à ceci.

World worldIn =Instance mondiale donnée de quelque part;
int size = 1;

Random rand = new Random(getSeedInChunk(1251341, -16, -18));
rand.nextInt();
new MapGenVillage.Start(worldIn, rand, -16, -18, size);

/**
 *Une fonction qui renvoie une graine pour une structure de village avec une graine mondiale et des coordonnées de bloc de village
 */
long getSeedInChunk(long seed, long chunkX, long chunkZ)
{
    Random rand = new Random(seed);
    long j = rand.nextLong();
    long k = rand.nextLong();
    (chunkX * j) ^ (chunkZ * k) ^ seed;
}

MapGenVillage.Start # new prend également le Monde, les coordonnées du bloc de base et la taille du village. La taille du village est de 1 par défaut.

La structure du village dépend de la graine du monde et des coordonnées des morceaux générés. Il semble qu'il n'y ait pas de boucle de motif contrairement à la forteresse du Nether.

--Minecraft 1.12.2 Algorithme pour déterminer les coordonnées d'apparition pour Nether Fortress --Qiita https://qiita.com/MirrgieRiana/items/e01a3db6fd7bf183fbbb

La valeur de hachage de la structure du village est calculée en simulant l'intérieur de MapGenVillage.Start # new, mais ce constructeur est à peu près comme suit.

List<structurecomponent> components = new ArrayList<>();

MapGenVillage.Start(World worldIn, Random rand, int x, int z, int size)
{
    List<PieceWeight> list =Une méthode pour obtenir une liste des types de bâtiments, des poids et des paires de limites supérieures();
    StructureVillagePieces.Start start = new StructureVillagePieces.Start(
        worldIn.getBiomeProvider(), 0, rand, (x << 4) + 2, (z << 4) + 2, list, size);
    components.add(start); // (7)
    start.buildComponent(start, components, rand); // (8)
    List<StructureComponent> list1 = start.pendingRoads;
    List<StructureComponent> list2 = start.pendingHouses;

    while (!list1.isEmpty() || !list2.isEmpty()) { // (9)
        if (list1.isEmpty()) {
            int i = rand.nextInt(list2.size());
            StructureComponent structurecomponent = list2.remove(i);
            structurecomponent.buildComponent(start, components, rand);
        } else {
            int j = rand.nextInt(list1.size());
            StructureComponent structurecomponent2 = list1.remove(j);
            structurecomponent2.buildComponent(start, components, rand);
        }
    }

    // (6)
}

Au moment de (6), «composants» contient une liste des parties qui composent le village. StructureVillagePieces.Start # new semble représenter le premier puits, qui a été ajouté aux composants dans (7). Dans (8), il semble que buildComponent génère quatre chemins dérivés du puits. Puis, tout en dérivant la structure générée en (9) l'une après l'autre, elle plonge dans les «composants». Il sera terminé quand il sera enfin question (6). En fait, le processus continue après cela, mais il n'est pas utilisé pour calculer la valeur de hachage, alors ignorez-le.

Autour de (6), si vous recherchez le contenu de composants, comptez les bâtiments, écrivez le code pour créer la valeur de hachage et retournez, vous aurez une fonction qui retourne la structure du village générée à partir de coordonnées aléatoires et de bloc. .. Cependant, cette fonction ne peut pas être placée dans main car elle dépend du monde qui nécessite un traitement d'initialisation de Minecraft. Cette fonction peut être appelée à partir du code de Minecraft disponible pour World. Par exemple, vous pouvez écrire du code qui appelle cette fonction en écrasant le traitement du clic droit de la flèche.

Grâce à la discussion jusqu'à présent, nous avons créé une «fonction qui renvoie la valeur de hachage de la structure du village étant donné les coordonnées de départ et de bloc». F2 est complété en réécrivant ceci dans la condition "Une graine génère-t-elle un village avec une valeur de hachage à une certaine coordonnée de bloc?". En conséquence, la graine atteint le point où les 16 bits supérieurs sont inconnus et les 48 bits inférieurs sont confirmés. Cela peut être fait en sondant au plus un ou deux villages. Le temps de calcul est de quelques secondes dans un seul thread.

f3 Fonction lente qui réduit les candidats à un

Ici, les candidats de départ sont réduits de 65 536 motifs pour les 16 bits supérieurs à un motif. Utilisez le biome pour cela. L'expression conditionnelle est "La graine génère-t-elle un biome spécifique à une coordonnée XZ spécifique?"

Le village ignore les 16 premiers bits, mais le biome semble le voir. Je ne connais pas l'algorithme de détermination du biome, mais il suffit de connaître le biome des coordonnées avec getBiome fourni par BiomeProvider dérivé de WorldInfo obtenu de World.

Le problème ici est de savoir comment passer la graine à BiomeProvider, ce qui peut être fait en réécrivant le champ randomSeed que WorldInfo passe au constructeur de BiomeProvider stocke en privé. Cependant, puisque randomSeed est privé, il doit être réécrit en public.

Ce processus nécessite également World. Lorsque j'ai initialisé Minecraft par moi-même et généré World sans démarrer correctement Minecraft, il semblait qu'un terrain légèrement différent avait été généré et cela n'a pas réussi. Par conséquent, cette fonction modifie également le traitement par clic droit d'un élément d'horloge ou de quelque chose de sorte qu'il y soit appelé.

La liste des coordonnées et des biomes à passer par ce processus doit être soigneusement élaborée. Étant donné que le relevé du terrain est propulsé par l'homme, je suis toujours inquiet, donc j'aimerais prendre les coordonnées au milieu du biome si possible. Je voudrais poursuivre le travail tout en effectuant une confirmation séquentielle telle que l'énumération et le tri de 8 correspondances ou plus, au lieu d'essayer de faire correspondre les 10 si 10 autres sont passées.

Dans ce processus, nous avons réussi à identifier de 65536 modèles à 1 modèle en parcourant 10 biomes, en notant les coordonnées près du centre et en les versant dans la fonction. La spécification prend quelques minutes.

Tout au long, nous avons pu identifier une seule graine dans la plage de 64 bits en utilisant les coordonnées de huit villages, la valeur de hachage structurelle d'un village et les dix biomes. Cela a pris environ 27 heures dans mon environnement.

Résumé

** Le monde de génération de terrain par défaut de Minecraft 1.12.2 Java Edition Vanilla peut rassembler suffisamment d'informations pour calculer à nouveau les graines simplement en marchant autour de la surface. Vous pouvez ensuite utiliser ces informations pour recalculer la valeur de départ en deux jours maximum. ** De plus, si la carte du monde et la position de l'origine sont données sans connexion réelle, les informations seront collectées.

Cette fois, il a fallu 2 jours pour calculer car on supposait que la graine était dans la longue portée (2 ^ 64), mais si la graine était définie sur int, cela prendrait environ 4 secondes si les coordonnées de 4 villages étaient connues. Est fini. ʻObject # hashCode () `est la valeur de retour de int, donc si vous donnez une graine à partir de la chaîne, ce sera comme ça.

Il est efficace de modifier un peu les paramètres de génération de terrain pour cette attaque. Cependant, comme la graine du monde affecte divers endroits, il sera toujours possible de calculer à rebours en utilisant d'autres parties que celles utilisées cette fois. Le facteur décisif cette fois est le fait que les 16 bits supérieurs de la valeur de départ donnée par java.util.Random sont tronqués. Au moment où vous mettez la valeur de départ dans Aléatoire, il n'y a que 2 ^ 48 modèles dans le monde. À ce stade, si vous disposez déjà de 50 jours, vous pouvez effectuer une recherche complète afin de pouvoir calculer facilement avec plusieurs ordinateurs.

À l'heure actuelle, ** dans un monde qui remplit déjà les conditions du calcul rétroactif, quelle que soit l'attention portée à la sécurité du serveur, la graine est théoriquement bâclée **.

Recommended Posts

Minecraft 1.12.2 Retour calcul des graines du monde à partir de la carte du monde
Calcul à rebours de la transition de la graine interne de Random