Discussion :

[liouan]

Bonjour,

Je cherche à générer un terrain en 2D. Pour ça, j'ai trouvé un très bon tuto sur ce site, que je suis parvenu à appliquer sans souci.

Maintenant, je voudrais que le terrain généré soit déterministe. cad, pour un seed donné, j'obtiens toujours le même terrain.

J'ai bien sûr trouvé des algorithmes connus permettant de générer une suite de nombres pseudo-aléatoires (Mersenne twister) mais je veux en plus pouvoir accéder à n'importe quelle valeur du terrain sans avoir besoin de recalculer toutes les autres. (Avec le Mersenne twister, si je veux connaître la 10ème valeur, je dois calculer les 9 précédentes, ce que je veux éviter).

J'aimerais avoir ce genre d'API :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Randomizer randomizer(seed);
int x=24,y=42;
int val=randomizer.random(x,y)

Connaissez-vous un algo répondant à ce besoin?
Merci d'avance.

[Ekleog]

Si tout est généré autour de (0, 0) tu peux déjà générer avec des nombres dans l'ordre : (0, 0), (1, 0), (0, 1), (-1, 0), (0, -1), ...
Ceci permet déjà d'éviter les soucis de recalcul vraiment trop long.

Sinon, il est possible d'étudier l'algorithme inhérent aux générateurs de nombres aléatoires pour en déduire une formule pour calculer le N-ième élément en connaissant la graine initiale et les paramètres. Mais il faut avouer que ça risque d'être un travail assez mathématisé !

[Ekleog]

Tiens, j'ai trouvé !
Une fois que tu as ta fonction qui associe un entier à une position, tu peux aller voir http://www.math.sci.hiroshima-u.ac.j...UMP/index.html .

Bon courage pour adapter à ton code !

[Matthieu Brucher]

Si tout est généré autour de (0, 0) tu peux déjà générer avec des nombres dans l'ordre : (0, 0), (1, 0), (0, 1), (-1, 0), (0, -1), ...
Ceci permet déjà d'éviter les soucis de recalcul vraiment trop long.

Sinon, il est possible d'étudier l'algorithme inhérent aux générateurs de nombres aléatoires pour en déduire une formule pour calculer le N-ième élément en connaissant la graine initiale et les paramètres. Mais il faut avouer que ça risque d'être un travail assez mathématisé !

Très facile, il suffit de ne pas prendre un générateur comme un Mersenne Twister qui génère un nombre à partir du précédent. Il faut prendre un générateur aléatoire basé sur un compteur et une fonction de cryptage (par exemple). Regarde du côté de Random123.

P.S. : c'est plus rapide qu'un MT quand on est sur du Sandy Bridge et supérieur, c'est parallélisable à l'infini, sans état, et c'est Crush résistant, contrairement à MT. Que des avantages.

[Ekleog]

Je ne connaissais pas de générateur de nombres aléatoires sans état, merci !

[liouan]

Salut,

Je viens de récupérer la librairie Random123 et de faire quelques tests.

C'est juste parfait ça correspond exactement à ce que je cherchais.

Merci

[JolyLoic]

Si j'ai bien compris ta problématique, tu ne veux pas calculer toutes les valeurs aléatoires de ton terrain une bonne fois pour toutes puis les stocker dans une structure de donnée adaptée, mais les calculer au fur et à mesure. Probablement parce qu'il y en a trop.

Si c'est le cas, je te propose la stratégie suivante : Tu découpes ton terrain en cellules d'une certaine taille. A partir de ta graine, tu génère et stocke une valeur aléatoire pour chaque cellule.

Ensuite, tu considères que valeur devient la graine pour toutes les valeurs aléatoires contenues dans cette cellule, que tu calculeras toutes dès que tu seras intéressé par le contenu de la cellule.

Comme ça, tu n'as pas besoin de générateur particulier, tu utilises un générateur classique, mais sans exploser ta mémoire puisque tu as juste besoin de te souvenir d'un nombre par cellule plus un nombre par élément des cellules actives (probablement 4 au maximum pour des cellules carrées).

Et si même ça c'est trop, tu peux ajouter un niveau supplémentaire, avec des super-cellules...

[Ekleog]

L'avantage de la solution que je propose, c'est qu'elle nécessite un peu de travail pour faire fonctionner le jump ahead, mais ensuite c'est tout gagné : il n'y a plus qu'à utiliser le résultat sans avoir à se soucier d'un seul octet mémoire consommé de plus.
Parce que si le terrain est potentiellement infini, on aurait des problèmes avec la mémoire, même avec des super-super-super-super-cellules. Bon, on aurait aussi des problèmes pour stocker les coordonnées, mais même.

[JolyLoic]

Je n'ai pas lu l'article que tu références, mais j'ai peur que bien que plus efficace que l'approche classique, l'algorithme soit quand même assez lent, surtout si on repars systématiquement de la seed pour tout recalculer.

Et puis, un terrain infini me semble irréaliste, notre univers lui même étant fini

[liouan]

Le terrain généré est en effet pseudo-infini

Sa hauteur est finie (disons 256 ou 512). En revanche, en longueur et en largeur, il s'auto-génère au fur et à mesure que l'on atteint sa limite. Il est donc infini, tant que les coordonnées sont codables sur un long...

Je vais effectivement diviser mon terrain en cellules et le générer par cellule.
-> l'idée de réutiliser le résultat comme seed, c'est pas con du tout.

Par contre, pour générer les seeds des cellules, j'ai un souci :
si on va tout de suite en (0,1000), je ne veux pas avoir à calculer les seeds allant de -999,-999 jusqu'à (1000,1000).

Par contre, je peux éventuellement calculer tous les seeds qui se trouvent sur le chemin en ligne droite. Dans ce cas, l'idéal serait d'avoir un générateur de nombre aléatoires dont la valeur suivante serait calculée en fonction des quelques valeurs précédentes.

Ex: pour calculer le seed de (100,100), j'utilise les valeurs des seeds de (99,99), (98,98) et (97,97) dans une formule...

Sur l'heure de midi, je vais lire le lien donné par Ekleog pour voir si ça peut répondre à cette problématique