Voici la traduction perfectible mais néanmoins complète des explications sur la génération du terrain dans Minecraft.
J'ai vu dans l'article de Minecraft.fr qui traitait des Seeds, que Polpopolitan envisageait une traduction de ce post de Notch, alors pour gagner du temps j'ai commencé. Il y a certains aspects de l'explication que je n'ai pas totalement compris, mais j'ai tenté de traduire au mieux. Pour des suggestions d'amélioration de la traduction, contactez-moi par MP.
Trêve de bavardages, voici le texte.
------------------------------------------------------------------------
J'ai promis d'écrire un article technique sur Minecraft depuis un moment, mais je n'ai jamais trop eu le temps de le faire. Je suis maintenant dans un petit avion, même si je n'ai nulle part où aller, donc c'est parti !
Une des parties les plus complexes de Minecraft est la génération du terrain. Quand j'ai modifié le jeu en passant de simples zones d'une carte à une carte infinie, la génération du terrain est devenue vraiment compliquée, comme le terrain a besoin d'être généré à la volée à mesure que le joueur explore, et cela doit rester pareil peu importe la direction que le joueur vise.
1) En quoi est-ce infini ?
Avant tout, laissez-moi clarifier certaines choses à propos des cartes "infinies" : Elles ne sont pas infinies, mais il n'y a pas de limite dure non plus. Plus vous vous éloignerez, plus les bugs commenceront à apparaître. Le terrain est généré, sauvegardé et chargé, et (en sorte) est restitué en tronçons de 16*16*128 blocs. Ces tronçons ont une valeur de décalage qui est un entier sur 32 bits grossièrement situé dans l'intervalle ["moins" 2 milliards ; "plus" 2 milliards]. Si vous vous trouvez en dehors de cet intervalle (environ 25% de la distance de l'endroit où vous êtes maintenant au soleil), le chargement et la sauvegarde des tronçons commenceront à écraser les tronçons plus anciens. Au 1/16ème de cette distance, les choses qui utilisent des entiers pour les positions des blocs, tels que l'utilisation des items et la recherche de chemin, commenceront à déborder et agir bizarrement.
Ce sont les deux limites "dures".
La plupart des autres choses, comme les graines de génération de terrain et entités de lieux utilisent des 64 bits doubles pour les lieux, et elles réalisent des choses beaucoup plus subtiles. Par exemple, à des distances extrêmes, le joueur bougerait plus doucement qu'au centre de la carte, à cause des erreurs d'arrondi (la position possède une énorme mantisse, le delta du mouvement en possède un petit, alors c'est interrompu plus vite). Le générateur de terrain peut également commencer à générer des structures bizarres, tels que des énormes blocs en matériau solide, mais je n'ai vu cela ni récemment ni examiné en détail
le comportement pour que cela se produise. Un problème majeur à des longues distances est l'engin physique qui se met à bugger, causant des chutes hasardeuses à travers le sol ou le blocage physique du joueur le long d'un mur durant la marche.
Beaucoup de ces problèmes peuvent être résolus en changeant la mathématique en un modèle local centré autour du joueur ainsi les nombres ont tous vaguement la même ampleur. Pour la restitution, Minecraft utilise déjà des coordonnées locales avec le bloc et décale la position du bloc relative au joueur pour donner l'impression de mouvement au joueur. C'est en majeure partie dû à OpenGL et son utilisation de nombres réels pour les positions, mais aussi parce que les erreurs d'arrondi sont extrêmement visibles lorsque affichées sur un écran.
Nous ne prévoyons pas de corriger ces bugs tant qu'ils ne sont pas communs pour les joueurs pendant leur expérience de jeu légitime. Mon instinct me dit que personne n'est allé aussi loin, et personne n'ira. Marcher aussi loin prendra vraiment beaucoup de temps. D'ailleurs, les bugs ajoutent du mystère et du charisme aux Contrées Lointaines.
2) N'est-ce pas impressionnant, cette forme de terrain ?
Dans la toute première version de Minecraft, j'ai utilisé un bruit heightmap Perlin 2D pour paramétrer la forme de la carte. Ou, plutôt, j'ai utilisé un bon nombre d'entre eux. Un pour l'élévation globale, un pour la rugosité du terrain, et un pour les détails locaux. Pour chaque colonne de blocs, la hauteur était (élévation + (rugosité*détail))*64*64. L'élévation et la rugosité étaient lisses, les bruits à grande échelle, et le détail était plus complexe. Cette méthode avait le gros avantage d'être très rapide comme il y avait seulement des échantillons de 16*16*(bruitNum) par tronçons à générer, mais l'inconvénient est que c'était plutôt triste. Spécifiquement, il n'existe aucun moyen pour que cette méthode ne génère pas de surplombs.
Ainsi j'ai modifié le système en un système similaire basé sur le bruit Perlin 3D. Au lieu d'échantillonner la "hauteur de sol", j'ai traité la valeur du bruit comme la "densité", où tout ce qui est en-dessous de 0 serait de l'air, et tout ce qui est au-dessus ou égal à 0 serait le sol. Pour s'assurer que le calque inférieur est solide et le supérieur non, j'ai simplement ajouté la hauteur (décalage par rapport au niveau de l'eau) au résultat échantillonné.
Malheureusement, j'ai tout de suite connu des problèmes de performances et de jouabilité. De performance à cause de la quantité énorme d'échantillons à produire, et de jouabilité parce qu'il n'y avait aucune aire plate ou colline lisse. L'échantillonnage à une résolution plus faible (une échelle de 8 fois le long des horizontales, 4 fois le long des verticales) et faire une interpolation linéaire s'est révélé comme la solution aux deux problèmes. Subitement, le jeu avait des aires plates, des collines lisses, et également la majorité des blocs flottants solitaires étaient partis.
La formule exacte que j'utilise est un peu compliquée (et secrète !), mais a doucement évoluée dans le temps alors que je travaillais sur le jeu. Les cartes à élévation 2D et bruitage sont toujours utilisées pourtant.
TOUJOURS A VENIR, SUR LA GENERATION DU TERRAIN :
* Biomes !
* Grottes et Grandes Caractéristiques
* Arbres, Lacs et Petites Caractéristiques
* Le Nether (les enfers)
Maintenant je vais me préparer à atterrir, je vais changer d'avion !
J'ai vu dans l'article de Minecraft.fr qui traitait des Seeds, que Polpopolitan envisageait une traduction de ce post de Notch, alors pour gagner du temps j'ai commencé. Il y a certains aspects de l'explication que je n'ai pas totalement compris, mais j'ai tenté de traduire au mieux. Pour des suggestions d'amélioration de la traduction, contactez-moi par MP.
Trêve de bavardages, voici le texte.
------------------------------------------------------------------------
J'ai promis d'écrire un article technique sur Minecraft depuis un moment, mais je n'ai jamais trop eu le temps de le faire. Je suis maintenant dans un petit avion, même si je n'ai nulle part où aller, donc c'est parti !
Une des parties les plus complexes de Minecraft est la génération du terrain. Quand j'ai modifié le jeu en passant de simples zones d'une carte à une carte infinie, la génération du terrain est devenue vraiment compliquée, comme le terrain a besoin d'être généré à la volée à mesure que le joueur explore, et cela doit rester pareil peu importe la direction que le joueur vise.
1) En quoi est-ce infini ?
Avant tout, laissez-moi clarifier certaines choses à propos des cartes "infinies" : Elles ne sont pas infinies, mais il n'y a pas de limite dure non plus. Plus vous vous éloignerez, plus les bugs commenceront à apparaître. Le terrain est généré, sauvegardé et chargé, et (en sorte) est restitué en tronçons de 16*16*128 blocs. Ces tronçons ont une valeur de décalage qui est un entier sur 32 bits grossièrement situé dans l'intervalle ["moins" 2 milliards ; "plus" 2 milliards]. Si vous vous trouvez en dehors de cet intervalle (environ 25% de la distance de l'endroit où vous êtes maintenant au soleil), le chargement et la sauvegarde des tronçons commenceront à écraser les tronçons plus anciens. Au 1/16ème de cette distance, les choses qui utilisent des entiers pour les positions des blocs, tels que l'utilisation des items et la recherche de chemin, commenceront à déborder et agir bizarrement.
Ce sont les deux limites "dures".
La plupart des autres choses, comme les graines de génération de terrain et entités de lieux utilisent des 64 bits doubles pour les lieux, et elles réalisent des choses beaucoup plus subtiles. Par exemple, à des distances extrêmes, le joueur bougerait plus doucement qu'au centre de la carte, à cause des erreurs d'arrondi (la position possède une énorme mantisse, le delta du mouvement en possède un petit, alors c'est interrompu plus vite). Le générateur de terrain peut également commencer à générer des structures bizarres, tels que des énormes blocs en matériau solide, mais je n'ai vu cela ni récemment ni examiné en détail
le comportement pour que cela se produise. Un problème majeur à des longues distances est l'engin physique qui se met à bugger, causant des chutes hasardeuses à travers le sol ou le blocage physique du joueur le long d'un mur durant la marche.
Beaucoup de ces problèmes peuvent être résolus en changeant la mathématique en un modèle local centré autour du joueur ainsi les nombres ont tous vaguement la même ampleur. Pour la restitution, Minecraft utilise déjà des coordonnées locales avec le bloc et décale la position du bloc relative au joueur pour donner l'impression de mouvement au joueur. C'est en majeure partie dû à OpenGL et son utilisation de nombres réels pour les positions, mais aussi parce que les erreurs d'arrondi sont extrêmement visibles lorsque affichées sur un écran.
Nous ne prévoyons pas de corriger ces bugs tant qu'ils ne sont pas communs pour les joueurs pendant leur expérience de jeu légitime. Mon instinct me dit que personne n'est allé aussi loin, et personne n'ira. Marcher aussi loin prendra vraiment beaucoup de temps. D'ailleurs, les bugs ajoutent du mystère et du charisme aux Contrées Lointaines.
2) N'est-ce pas impressionnant, cette forme de terrain ?
Dans la toute première version de Minecraft, j'ai utilisé un bruit heightmap Perlin 2D pour paramétrer la forme de la carte. Ou, plutôt, j'ai utilisé un bon nombre d'entre eux. Un pour l'élévation globale, un pour la rugosité du terrain, et un pour les détails locaux. Pour chaque colonne de blocs, la hauteur était (élévation + (rugosité*détail))*64*64. L'élévation et la rugosité étaient lisses, les bruits à grande échelle, et le détail était plus complexe. Cette méthode avait le gros avantage d'être très rapide comme il y avait seulement des échantillons de 16*16*(bruitNum) par tronçons à générer, mais l'inconvénient est que c'était plutôt triste. Spécifiquement, il n'existe aucun moyen pour que cette méthode ne génère pas de surplombs.
Ainsi j'ai modifié le système en un système similaire basé sur le bruit Perlin 3D. Au lieu d'échantillonner la "hauteur de sol", j'ai traité la valeur du bruit comme la "densité", où tout ce qui est en-dessous de 0 serait de l'air, et tout ce qui est au-dessus ou égal à 0 serait le sol. Pour s'assurer que le calque inférieur est solide et le supérieur non, j'ai simplement ajouté la hauteur (décalage par rapport au niveau de l'eau) au résultat échantillonné.
Malheureusement, j'ai tout de suite connu des problèmes de performances et de jouabilité. De performance à cause de la quantité énorme d'échantillons à produire, et de jouabilité parce qu'il n'y avait aucune aire plate ou colline lisse. L'échantillonnage à une résolution plus faible (une échelle de 8 fois le long des horizontales, 4 fois le long des verticales) et faire une interpolation linéaire s'est révélé comme la solution aux deux problèmes. Subitement, le jeu avait des aires plates, des collines lisses, et également la majorité des blocs flottants solitaires étaient partis.
La formule exacte que j'utilise est un peu compliquée (et secrète !), mais a doucement évoluée dans le temps alors que je travaillais sur le jeu. Les cartes à élévation 2D et bruitage sont toujours utilisées pourtant.
TOUJOURS A VENIR, SUR LA GENERATION DU TERRAIN :
* Biomes !
* Grottes et Grandes Caractéristiques
* Arbres, Lacs et Petites Caractéristiques
* Le Nether (les enfers)
Maintenant je vais me préparer à atterrir, je vais changer d'avion !
