La notion d'aleatoire sous LOD

[Myrdinn]

L'alétaoire étant souvent à l'origine de délires sur Bnet, j'ai décidé de mettre à jour ce post qui en avait bien besoin. Désolé pour le texte original que j'ai modifié mais ca n'a plus trop d'importance vu la date ou il a été écrit. (J'ai laissé la suite comme introduction avant d'apporter les nouveauté)
Je tiens à remercier Jarulf et Hammerman qui m'avaient aiguillé à l'époque. C'est grace à eux si j'ai pu finaliser ce post aujourd'hui

Intro issu du post initial
Avant de commencer un petit rappel historique sur diabloI
Sous DiabloI l'aléatoire utilisait le temps. En bloquant
le temps sur leur PC des petits malins se sont apercu que
le jeu generait toujours le meme resultat pour une action donnée.
Ceci inclus les Drops, mais aussi les chances de toucher ...
La meme erreur n'a pas ete repetée sous DII.

Voila une petite synthese que j'ai faite pour vous
(Attention Joe ne te mets pas contre un mur )
L'aléatoire est une fonction dans laquelle le jeu acceptent
un paramètre. En cela elle reprend la syntaxe des celebres Round.
LA fonction genère un nombre entre 0 et 1 et le multiplie par le paramètre.
C'est important car le résultat final est un entier.
Les résultats sont précalculés. Il n'y a plus d'intervention du temps excepté à l'origine de la première seed.,
A partirde ce seed il est possible de connaitre et de calculer la suite de valeur.

Cette suite bien que previsible est inutilisable. Le jeu utilise l'aléatoire pour une
multitude de paramètre (deplacement des lapins, scorpions, monstres, IA des monstres
, toucher , degat ...) donc meme en connaissant la suite
( a condition que l'on connaise le seed) on ne peut s'en servir pour les drops.

Les valeurs sont reparties de facon uniforme sur l'ensemble des seeds,
mais pour un seed donné la repartition n'est pas homogène.
Résultat il y a des seeds pour lesquels il y a plus de nombres proches de zero que pour d'autres seed
Ceci favorise le drop d'unique, mais il existe d'autre particularité

Bref, l'aléatoire ne tient compte d'aucune de vos actions, et les recettes de grand mère pour le Meme Runs, j'y crois de moins en moins

EDIT ajout de quelques questions réponses en page 2


2) De la pluralité des Seeds

Le jeu n'utilise pas 1 seed mais autant de seed que nécessaire pour que les évenement soit le plus possible indépendant.
LE jeu utilise une architecture pyramidale utilisant des Unit. J'en parle en détail dans mons post sur les Dlls je ne reviendrais pas en détail su celui ci.

La première unité est l'unité JEU que j'appelerais PtGame Pt pour pointeur car on désigne l'unité par son adresse mémoire.
Cette unité contient toutes les informations sur la partie (difficulté, mot de passe, mode ...) ainsi que la liste de toutes les unités enfants : les PtUnit à savoir tout les objets / Monstres / Joueurs / missiles ...
Chaque unité possède sa propre seed dérivée des la seed du PtGame. La seed du PtGame est la première Seed créé (voir formule dans le chapitre suivant)

Il existe d'autres seeds liés à la création des Maps.
Les maps ont leur propres seed créé à partir du PtGame ou (récupérée de la sauvegarde des maps pour le solo. C'est pourquoi en solo les maps sont toujours les mêmes après avoir sauvegardée)
Ensuite les Maps sont divisées en plus petites portions appelés Room (PtRoom)

J'ai quelques détail à vérifier avant de donner la relation exacte entre toutes les seeds


3) Les Seeds Mode D'emploi

Première Seed / PtGame
Comment est calculé la première Seed (Celle du PtGame pour ceux qui suivent)
2 solutions :

[*]Vous avez utilisé la commande -Seed, dans ce cas la seed prend cette valeur
[*] Vous n'intervenez pas c'est ce que nous allonf voir maintenant


La seed est une valeur 64 bits que l'on sépare en 2 parties de 32 Bits.
Seed_Low et Seed_High

SeedHi = 0x000000029a (666 en décimal, amusant ces programmeurs)
Seed_Low=abs( (QueryPerformanceCounter + SecondsSince1900 + 0x7c558180 + GetTickCount) * 0x2f490a95 - 0x2e330917)
LEs 2 sont des valeurs Signées (Positive ou négative)

GetTickCount appelle le Kernel de Windows et retourne le nombre de millisecond depuis le démarrage de l'ordinateur

QueryPerformanceCounter appelle le Kernel de Windows et retourne une valeur qui est mise à jour constamment par le QueryPerformanceFrequency qui est systemDépendant.

deuxième seed MapSeed
Comment est calculé la deuxième seed (LA map seed pour ceux qui suivent) Si nécessaire (En solo la map seed est celle de la map sauvegardée)
Si vous utilisez la commande -Seed xxx alors c'est la même
Autrement c'est la même formule sauf que le QueryPerformanceCounter est remplacé par la Seed suivante du PtGame

Mise à jour de la seed / tirage Aléatoire
Les mises à jour de la seed sont calculées comme ceci :

1. seed_low * 0x6ac690c5
C'est une multiplication 64 Bits, la seed_low est etendue à 64 bits le temps des calculs

2. Ajoute seed_hi à la valeur 64 bit calculé

Bref Seed(64 bits) = SeedLo * 0x6ac690c5 + SeedHi

3. Cette valeur est la nouvelle seed divisé en Seed_low(32 bits de poids faible) et Seed_high(32 Bits fort)

Vous pouvez également utilisé cette génération de seed pour un tirage aléatoire entre 0 et X:

4. Diviser la seed_low par X

5. la retenue est la valeur aléatoire comprise entre 0 et (X-1) le tout en hexa

Bref en math RND[x] = SeedLo mod X

création de nouvelle Seed
En cas de création d'une nouvelle seed (A la création d'une nouvelle unit par exemple) le jeu met à jour la seed du PtGame et donne le résultat suivant pour la nouvelle Seed

Seed_Low = SeedLo (la nouvelle du PtGame)
Seed_High = 0x000000029a

Comme le Seed High est différent, toutes les valeurs futures sont différentes de celles du PtGame et des prochains objets créé par le PtGame

 

[KaLiS]

Myrdinn est de retour.... et ca se voit

 

[tiissa]

Avant tout merci

Provient du message de KaLiS
Myrdinn est de retour.... et ca se voit

Il est pas en forme, il aurait pu nous donner la fonction qui fait passer d'un nombre au suivant

Donc le jeu utilise seulement une random seed. Tu as des precisions sur sa taille ?

Sinon, doit-on comprendre que la fonction aurait tendance a generer des nombres proches ? Ou est-ce seulement pour dire que la distribution generee par la seed n'est pas forcement uniforme (d'ou les fameuses series) mais qu'en general on s'en rapproche ?

De meme si 2 nombres consecutif ont une plus grande chance d'etre proche ca influerait grandement sur le mf. En effet si le premier nombre est petit c'est un objet de classe elevee et si le suivant l'est aussi c'est un unique...

Il pourrait donc etre interessant de continuer a jouer dans une partie "qui droppe bien". Sans pour autant qu'il y ait des certitudes.


Tu as parle de synthese....tu peux rentrer dans de details ou cela reste qualitatif ?

 

[emerson]

Provient du message de Myrdinn
les recettes de grand mère pour le Meme Runs, j'y crois de moins en moins

:biggthum: Myrdinn

sinon les recettes des mémés pour mémé ct koi?

moi je crois (et je suis presque persuadé) que les paramètres du run (perso, niv, equip, % de mf, température extérieure .... mais aussi le jour et l'heure) influence les drops


j'ai l'impression qu'il y a des "jours" pour certains objets: par exemple on ne voit pas de "lame du colosse verte" pendant qq jours et même qq semaines, et d'un seul on en trouve 2 ou 3 le même jour sur le forum (ca s'est passé il y a un mois cet épisode)


pareil: dans tous les runs que j'ai fait, j'ai trouvé que 2 raven et bizarrement c'était le même jour à 10 runs d'écart


mais après tout c'est p'tre tout simplement le hasard .............

 

[jaiin_garr]

Je trouve enfin LE POST que j'attendais....
Traitant de la question qui est a la BASE de tout...
La generation de l'aleatoire sous LOD...

BRAVO et .... je suis tout ouie pour la suite des details...

 

[tiissa]

Provient du message de Emerson

moi je crois (et je suis presque persuadé) que les paramètres du run (perso, niv, equip, % de mf, température extérieure .... mais aussi le jour et l'heure) influence les drops


j'ai l'impression qu'il y a des "jours" pour certains objets: par exemple on ne voit pas de "lame du colosse verte" pendant qq jours et même qq semaines, et d'un seul on en trouve 2 ou 3 le même jour sur le forum (ca s'est passé il y a un mois cet épisode)


pareil: dans tous les runs que j'ai fait, j'ai trouvé que 2 raven et bizarrement c'était le même jour à 10 runs d'écart


mais après tout c'est p'tre tout simplement le hasard .............

Qui sait

 

[Paul Siramy]

La graine aléatoire est codée sur 4 octets, donc il y a 2^32 valeurs possibles (0 à 4294967296). J'avais trouvé ça il y a longtemps dans les fichiers de sauvegarde (d2s), c'était la graine aléatoire qui avait à servi à la génération de la carte. Tu changait ce nombre dans une sauvegarde par un autre tiré d'une autre sauvegarde, et tu obtenias exactement la même carte (mais les objets achetés étaient différents).

 

[tiissa]

Sinon je crois me souvenir qu'en solo du moins la seed est donnee dans le fichier de log...
Faudrait voir si elle est aussi affiche pour B.net...

 

[Myrdinn]

Je n'en suis qu'au debut. Je ne sais pas si vous savez a quoi ressemble un cosinus en hexa, moi j'ai du mal

La formule importe peu, ce que je sais? c'est une suite d'opération mathematique, l'important c'est que la serie n'est pas influencée par le faite de faire Mémé par la gauche en sautant par dessus la lave en criant, ni par le jour, ni par l'heure ... Autrement ayant du mal j'ai demandé de l'aide aux grands lecteurs d'hexa par MP, mais ils ne me donnent jamais de précision avant de poster le resultat; quand il le font.

Sinon, doit-on comprendre que la fonction aurait tendance a generer des nombres proches ?

Non pas forcement

Ou est-ce seulement pour dire que la distribution generee par la seed n'est pas forcement uniforme (d'ou les fameuses series) mais qu'en general on s'en rapproche ?

C'est plutot ca. J'espètre toujours avoir la fonction exacte pour etre plus precis par la suite

 

[tiissa]

J'ai dit merci ? :biggthum:

 

[Fred]

Si on appelle A(i) le ieme nombre aleatoire tire, alors le suivant A(i+1) est donne par :

A(i+1) = b * A(i) modulo (m)

En clair A(i) est un entier entre 0 et m-1, on le multiplie par un autre entier b, et on prend le reste par la division par m (ce que signifie modulo). Ca fait donc toujours un nombre entre 0 et m-1. Apres on divise par m pour avoir un nombre reel entre 0 et 1.

Si on choisit bien b et m ca doit etre distribue de maniere uniforme entre 0 et 1. Dans un bouquin je trouve b = 16807 et m = 2147483647 (sisi 47 et pas 48...). Pour ceux qui connaissent, ca a l'air relie a la transformation du boulanger et au fait que le truc soit chaotique...

Tous les generateurs marchent plus ou moins comme ca avec des raffinements que je vous epargnerai (numerical recipes, chap7 pour les fans...)

Donc si on connait le seed ( A(1) ), on connait toute la suite de la serie (et le seed doit etre donne par l'horloge ou une connerie comme ca). Mais comme le jeu utilise constamment des nombres aleatoires, des qu'on change un tout petit peu ce qu'on fait, il tire des nombres en plus ou en moins et ca "decale" la serie, donc pas moyen de prevoir ce qui va se passer.

Fallait pas demander...

 

[Myrdinn]

Provient du message de Fred

Donc si on connait le seed ( A(1) ), on connait toute la suite de la serie (et le seed doit etre donne par l'horloge ou une connerie comme ca). Mais comme le jeu utilise constamment des nombres aleatoires, des qu'on change un tout petit peu ce qu'on fait, il tire des nombres en plus ou en moins et ca "decale" la serie, donc pas moyen de prevoir ce qui va se passer.

Fallait pas demander... [/b]

Pareil. La serie etant utilisée pour toutes les actions du jeu, on ne peut la reduire au seul Drop.

Conclusion Bis. Rien dans les delires personnels de certains sur les drops ne se retrouve dans le code source

 

[Myrdinn]

Provient du message de tiissa
Avant tout merci


Il est pas en forme, il aurait pu nous donner la fonction qui fait passer d'un nombre au suivant

Donc le jeu utilise seulement une random seed. Tu as des precisions sur sa taille ?

J'allais oublier de repondre au reste

Comment ca je suis pas en forme, si je postais quand j'ai fini il ny aurait pas encore un MOD 1.10, puis vos reponses et questions me permettent d'avancer plus vite. Mes posts ne sont pas innocents

LA taile, j'ai été grillé par Paul

Il pourrait donc etre interessant de continuer a jouer dans une partie "qui droppe bien". Sans pour autant qu'il y ait des certitudes.

Ca me parait bien, le contraire est vrai aussi Comme toute les recettes ca rassure

 

[tiissa]

Le m c'est l'amplitude de l'intervalle, le tien c'est pour avoir un nombre sur 31 bits. D'apres Paul c'est sur 32 bits donc m=4294967295. Sinon on choisi d'habitude b premier (voire premier tout court...) avec m pour cette formule.
Sinon la transformation de base du
boulanger c'est pour b=2 non ?

La question est de savoir si c'est cette formule qui est appliquee. Et comment est calculee la seed. Fait-elle intervenir le temps ? J'ai cru comprendre que non d'apres le post de Myrdinn mais ce n'est pas forcement clair...

 

[tiissa]

Provient du message de Myrdinn

Comment ca je suis pas en forme, si je postais quand j'ai fini il ny aurait pas encore un MOD 1.10, puis vos reponses et questions me permettent d'avancer plus vite. Mes posts ne sont pas innocents

Servirait-on vraiment a quelquechose ? C'est rassurant

 

[Myrdinn]

Je ne sais pas ou se trouve la generation du Seed actuellement.

Effectivement ce n'est pas tres clair, y compris dans les reponses que j'ai eu. A priori non le seed n'est pas basé sur le temps d'après mes contacts.

 

[Fred]

@tiissa : Oui, boulanger c'est b=2 et m=1. Le 31-32 bits doit etre une histoire d'entiers signes ou non.

Il y a probablement plusieurs seeds : un pour la carte qui est sauvegarde pour retrouver la meme carte a la fois suivante, et d'autres separes pour le jeu.
Si ils veulent vraiment rendre le truc aleatoire, il leur suffit de reinitialiser ces seeds de temps a autre en se basant sur la position du joueur a ce moment la ou n'importe quel autre truc...

 

[tiissa]

Je pense que m=1 ca doit pas servir beaucoup
Pour boulanger, (je pense que) m peut etre quelconque. Mais j'ai jamais etudier particulierement donc il y a peut-etre des restriction (probablement sur la parite...)

Si j'ai bien compris vous insinuez que la carte n'est sauvegardee que par la seed qui a servie a sa generation ? Et qu'en est-il de la region explore ?
Sinon pour cette hypothese, il suffirait de generer les cartes avant de laisser le joueur jouer et de continuer avec la meme seed.
Dans ce cas on aurait une seed par joueur (en solo) ce qui n'est pas forcement stupide...
Or il semble qu'il en genere une nouvelle a chaque fois pour le jeu.
Alors a moins qu'ils aient peur que l'on arrive a generer exactement les memes evenements, c'est bizarre, non ?
Ou alors, ils ont eu la flemme de generer toute la carte d'un seul coup...

 

[KaLiS]

z'etes surs que ca donnerait pas de meilleurs drop si on runne une nuit de pleine lune pendant qu'un nain unijambiste fait une danse rituelle au centre d'un cercle formé par des statuettes sacrées enveloppées dans du jambon???..... non z'etes surs....?

 

[Paul Siramy]

Provient du message de tiissa
Si j'ai bien compris vous insinuez que la carte n'est sauvegardee que par la seed qui a servie a sa generation ? Et qu'en est-il de la region explore ?

vas voir là