Notch l’avais dit il y a un certain temps, et il l’a enfin fait (enfin le 09 Mars =° ) : Il a expliqué la génération du terrain sur son blog. Enfin juste une partie, les autres devraient arriver prochainement.

L’Anglais ici n’est pas facile à traduire, j’ai fait ce que j’ai pu et la traduction n’est pas forcément totalement juste.
C’est une traduction directe de l’article qui se trouve à l’adresse http://notch.tumblr.com/.

J’avais promis d’écrire un article technique sur minecraft depuis un moment, mais jamais pris le temps de le faire, en fait. Je suis dans un petit avion, en ce moment et n’ai rien d’autre à faire. Allons-y donc !

Une des parties de Minecraft les plus complexes est la génération du terrain. Lorsque j’ai modifié le jeu depuis de petites zones d’une map vers une map infinie, la génération du terrain se compliqua beaucoup, les terrains nécessitant d’être générés au fur et à mesure que le joueur avance, sans se soucier de part où le joueur approche.

1) Est-ce infini ?

Premièrement, laissez-moi clarifier quelques points par rapport aux maps « infinie » :
Elles ne sont pas vraiment infinies, mais les limites sont imposantes. La map devient juste de plus en plus buggée lorsqu’on avance. Le terrain est généré, sauvegardé et chargé, et rendu en chunks de 16*16*128 blocks. Ces chunks ont une valeur de décalage d’un nombre de 32bits qui a une portée de moins deux milliards a plus deux milliards. Si vous allez en dehors de cette portée (environ 25% de la distance depuis le spawn vers le soleil), charger et sauvegarder des chunks va commencer à supprimer les vieux. A un 16e de cette distance, les choses qui usent des nombres pour la position des blocs, comme l’utilisation des objets et la recherche de chemin, vont commencer à « déborder » (en mémoire) et à fonctionner bizarrement.

Ce sont les deux « grosses » limites.

Beaucoup d’autres choses, comme les seeds (de génération de terrain) et la localisation d’entités utilisent des doubles (nombres décimaux) de 64 bits pour les emplacements, et font d’autres choses bien plus subtiles. Par exemple, à des distances extrêmes, le joueur peut se déplacer moins rapidement que près du centre de la map en raison des erreurs d’arrondissement (de valeurs). La position a une mantisse énorme, le mouvement en a une minuscule, elle est donc coupée plus rapidement.
(Allez sur http://www.laissemoichercherca.com/?q=define%3Amantisse pour connaitre la définition de mantisse).

Le générateur de terrain peut aussi commencer à générer des choses bizarres, comme d’énorme blocs solides, mais je n’ai pas vu ça récemment ni examiné à quel comportement exact cela est dû.

Un majeur problème à de longues distances est que la physique commence à bugger, donc le joueur peut tomber aléatoirement dans des blocs du sol ou se retrouver coincé en marchant vers un mur.
Beaucoup de ces problèmes peuvent être résolus en changeant les mathématiques dans un modèle local centré autour du joueur, de telle sorte que tous les nombre aient vaguement la même magnitude. Pour le rendu, minecraft utilise déjà des coordonnées locales dans et en dehors de la position du bloc (relative au joueur) pour donner l’impression que le joueur bouge. C’est la plupart du temps du à OpenGL en utilisant un float (nombre décimal) de 32bits pour les positions, mais aussi parce-que les erreurs d’arrondi sont très visibles lorsque montrées sur un écran.

Nous n’allons probablement pas fixer ces bugs avant que devienne commun pour les joueurs de jouer avec. Mon instinct me dit que personne n’y est habitué, et personne ne le sera jamais. Marcher si loin prendrait un temps fou. Aussi, ce bug ajoute du mystère et du charisme aux terres lointaines.

2) La forme du terrain n’est-elle pas impressionnante ?


Dans la toute première version de Minecraft, j’ai utilisé une 2D « perlin noise heightmap » 2D pour définir la forme du terrain ou, plutôt, j’ai utilisé un peu de ceux-là. 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. Ensemble, l’élévation et la rugosité étaient lisses, (large scales noises ?), Et le détail était plus complexe. Cette méthode avait l’avantage d’être très rapide car il y avait juste 16*16*(NoiseNum) échantillons par chunk à générer, mais le désavantage d’être plutôt ennuyeux. Plus précisément, il n’y avait pas de moyen avec cette méthode de créer des zones en surplombant d’autres.

Donc j’ai changé cela en un système similaire basé sur un « Perlin noise » 3D. Au lieu de prélever un échantillon de la profondeur du sol, j’ai traité la valeur de bruit en tant que « densité », où quelque chose d’inférieur à 0 serait de l’air, et quelque chose d’inférieur ou d’égal à 0 serait de l’air. Pour être sûr que la layer la plus basse est solide et que la plus haute ne le sois pas, j’ai juste ajouté la hauteur (décalée par rapport au niveau de l’eau) à l’échantillon résultat.
Malheureusement, j’ai immédiatement connu des problèmes de performances et de jeu.
Des problèmes de performance car il fallait beaucoup d’échantillons, et des problèmes de jouabilité car il n’y avait pas de zones plates, de plateformes, et aussi tous les blocs flottants seuls étaient partit

A VENIR DANS LA GENERATION DES TERRAINS
– Biomes !
– Caves et choses énormes
– Arbres, lacs, petites choses
– Le nether !

Maintenant, je me prépare à atterrir !

Voilà. Je sais que la traduction n’est pas parfaite mais je fais de mon mieux. De prochains articles seront faits là-dessus quand Notch aura bossé sur son blog.

A plus les amis !