Fonction de graine aléatoire pour la génération de cartes?

28

Je recherche une fonction pour générer une carte aléatoire basée sur des tuiles à mesure que les limites visuelles de la carte changent (en parcourant la carte). Je veux que la carte soit infiniment grande et ait une structure semblable à un labyrinthe.

Cependant, si le monde est infini, revenir à l'endroit où un joueur était déjà auparavant pose un problème. Le jeu doit se rappeler à quoi ressemblait tout à l'arrière.

Donc, je pensais - "Comment Minecraft résout-il ce problème?" et je me suis dit qu'ils devaient utiliser une sorte de fonction de nombre aléatoire avec une graine, qui peut à la fois avancer et reculer, et de cette façon, recréer les vieilles tuiles exactement comme elles étaient, mais dans de nouveaux cas.

Que pensez-vous de ceci?

Mathias Lykkegaard Lorenzen
la source
Comment se fait-il que ma réponse soit à +5 et que la question ne soit qu'à +2? C'est l'une des meilleures questions en première page en ce moment.
2
Minecraft ne stocke- t-il pas simplement les morceaux que vous avez déjà visités / modifiés?
FxIII
@FxIII: Minecraft doit, car vous pouvez modifier le paysage. Si vous ne pouvez pas le faire, le stockage des morceaux est probablement un gaspillage, ou du moins une surcompensation.
@Joe Wreschnig: D'accord, d'accord ... j'avais peur de rater quelque chose de vraiment gros!
FxIII

Réponses:

20

Ce que vous avez remarqué, c'est la différence entre un générateur de nombres aléatoires et une fonction de bruit . Un générateur de nombres aléatoires crache un numéro différent chaque fois que vous l'appelez. Une fonction de bruit prend quelques arguments - disons une carte x et y - et crache des nombres avec des propriétés statistiques de type aléatoire , mais à chaque fois la même valeur pour les mêmes arguments , c'est-à-dire que c'est une fonction mathématique appropriée.

Les deux sont étroitement liés. Une fonction de bruit peut simuler un générateur de nombres aléatoires, en faisant passer à une valeur différente à chaque fois - par exemple noise(1), noise(2)et ainsi de suite. Et un générateur de nombres aléatoires, jeté dans une table géante, peut agir comme une fonction de bruit. Dans les deux cas, vous utilisez le mauvais outil pour le travail.

Minecraft en particulier les utilisations du bruit Perlin , un type de bruit qui ne coûte pas cher à calculer, et a une propriété souhaitable d'être continue en autant de dimensions que vous avez besoin - si vous représenter graphiquement f(x)à f(x + 1), il n'y aura pas de sauts brusques. Cela le rend très utile pour de nombreuses choses comme la modulation de texture, les nuages ​​et les gaz volumétriques et la génération de terrain.

Si vous cherchez une implémentation pour commencer à jouer, le générateur de bruit Perlin amélioré de Ken Perlin est l'une des implémentations les plus simples.


la source
3
Notez que beaucoup de générateurs de nombres aléatoires utilisent une graine et généreront le même ensemble de nombres pour la même graine.
thedaian
3
@thedaian: Ce qui n'est pas particulièrement utile dans ce cas, sauf si vous voulez régénérer chaque nombre; une fonction de bruit vous permet d'obtenir le 500e nombre sans avoir à en générer 499 auparavant.
Étant donné l'algorithme Perlin Noise, est-il possible de le calibrer? Considérez que je veux que l'algorithme soit plus susceptible de générer un pack de tuiles murales, puis un pack de tuiles spatiales.
Mathias Lykkegaard Lorenzen
3
Vous n'avez pas lu et compris les liens que j'ai donnés en six minutes.
1
Cette réponse aurait été complète avec le billet de blog de Notch: notch.tumblr.com/post/3746989361/terrain-generation-part-1
deceleratedcaviar
3

La façon dont Minecraft contrôle sa génération est de créer une graine de niveau qui est utilisée pour ensemencer toute la génération de nombres aléatoires pour le jeu. Si un morceau n'existe pas sur le disque quand il est demandé, il sera généré en utilisant la fonction de génération de Notch basée sur la graine du niveau; il est ensuite enregistré sur le disque pour plus tard.

Il semble que vous cherchiez à obtenir un comportement similaire, c'est donc une façon sûre de procéder.

Keeblebrox
la source
2

Comme Joe l'a souligné, vous recherchez une fonction de hachage. En règle générale, les fonctions aléatoires ne sont que des fonctions de hachage prédéfinies avec le dernier nombre renvoyé. Donc, si Random()renvoyé Hash(seed)=1234, un deuxième appel Random()reviendrait Hash(1234), etc.

Si vous recherchez une fonction de hachage simple pour les nombres pseudo-aléatoires, consultez MurMurHash . Je l'ai implémenté en C # et je peux le publier quelque part si cela vous intéresse. Des informations plus détaillées sur Perlin Noise, qui utilise une telle fonction de hachage, peuvent être trouvées ici , et une implémentation de celui-ci en C # est ici .

Toutes ces informations proviennent d'une question que j'ai posée il y a un an ici sur Stack Overflow. Ce que vous examinez s'appelle la génération de contenu procédural, donc si vous avez besoin de plus d'informations, faites une recherche pour cela. Générateur de terrain heureux!

dlras2
la source
-1. Le hachage du bruit Perlin, en l'occurrence, ne ressemble en rien aux techniques utilisées dans MMH ou d'autres routines de hachage cryptographiques; ce code C # est une ordure qui semble juste faire une interpolation linéaire entre des valeurs aléatoires; il nécessite beaucoup plus de mémoire que le bruit Perlin approprié et s'exécute probablement plus lentement.
1
@Joe - Je suis désolé que vous pensiez tellement à votre implémentation de Perlin Noise. Perlin Noise est en soi un concept de transformation d'une fonction de hachage en fonction de bruit continu. J'ai généré beaucoup de bruit Perlin très efficacement avec MurMurHash. Quant au code C #, c'est un exemple de la façon de déterminer par programme la valeur d'un seul point dans le bruit Perlin 2D. Je ne l'utiliserais jamais en production, mais il est, à mon avis, plus facile à parcourir que le code que vous avez posté.
dlras2
1
Le PO n'avait aucune connaissance du bruit ou du hachage, alors j'ai simplement essayé de fournir des références dans l'espoir qu'ils approfondiraient et décideraient par eux-mêmes comment mettre en œuvre tout ce qu'ils devaient faire.
dlras2
"Perlin Noise est en soi un concept de transformation d'une fonction de hachage en fonction de bruit continu." Non, le bruit de Perlin est l'une des fonctions de bruit continu inventées par Ken Perlin (et non celle qu'il a appelée "bruit simplex"). Toutes les fonctions de bruit continu ne sont pas du bruit Perlin; toutes les fonctions de bruit continu ne sont même pas un bruit de gradient, dont le bruit de Perlin est un exemple particulier; la chose à laquelle vous avez lié n'est pas un bruit de gradient, mais un bruit de valeur.
Le code dans votre lien est "plus facile à parcourir" car ce n'est pas du bruit Perlin; ce n'est pas aussi lisse; il utilise beaucoup plus de ressources; bref, il est plus facile de s'y promener car c'est plus bête.