Distribution aléatoire pondérée continue, biaisée vers une extrémité

28

Je contribue actuellement à un système de particules pour notre jeu et je développe des formes d'émetteurs.

Ma distribution aléatoire uniforme le long d'une ligne ou le long d'une zone rectangulaire fonctionne bien - pas de problème.

Mais maintenant, je voudrais avoir quelque chose comme un gradient à 1 dimension dans cette distribution. Cela signifierait par exemple que des valeurs plus faibles sont plus courantes que des valeurs plus élevées.

Je ne sais pas quels termes mathématiques seraient appropriés pour ce problème, donc mes compétences en recherche sont plutôt inutiles avec celui-ci. J'ai besoin de quelque chose de simple sur le plan informatique, car le système de particules doit être efficace.

didito
la source
Personne ne va mentionner le calcul?
Alec Teal

Réponses:

42

Jetez un oeil à cette image:

Cartographie des courbes

Il montre le processus de mise en correspondance d'une valeur (aléatoire) avec une courbe. Supposons que vous générez une valeur aléatoire uniformément distribuée X, allant de 0 à 1. En mappant cette valeur à une courbe - ou, en d'autres termes, en utilisant f (X) au lieu de X - vous pouvez biaiser votre distribution de la manière que vous voulez .

Dans cette image, la première courbe rend les valeurs plus élevées plus probables; le deuxième rend les valeurs plus faibles plus probables; et le troisième fait un cluster de valeurs au milieu. La formule exacte de la courbe n'est pas vraiment importante et peut être choisie à votre guise.

Par exemple, la première courbe ressemble un peu à la racine carrée et la seconde au carré. Le troisième est un peu comme le cube, seulement traduit. Si vous considérez la racine carrée comme trop lente, la première courbe ressemble également à f (X) = 1- (1-X) ^ 2 - une inversion de carré. Ou une hyperbole: f (X) = 2X / (1 + X).

Comme le montre une quatrième courbe, vous pouvez simplement utiliser une table de recherche précalculée. Est laid comme une courbe, mais sera probablement assez bon pour un système de particules.

Cette technique générale est très simple et puissante. Quelle que soit la distribution dont vous avez besoin, imaginez simplement une cartographie de courbe et vous élaborerez une formule en un rien de temps. Ou, si votre moteur a un éditeur, faites simplement un éditeur visuel pour la courbe!

Ça ne fait rien
la source
merci beaucoup pour votre explication très complète et compréhensible. tous les autres messages ont également été très utiles, mais je pouvais vraiment comprendre votre message le plus simple et le plus rapide. il a dépassé car il a vraiment frappé l'endroit pour ma façon de comprendre les choses. et les aspects que vous expliquez sont exactement ce que je cherchais (ou errais)! cela me permettra de l'utiliser dans de nombreux cas à l'avenir. alors merci encore !!! btw, j'ai joué avec certaines de vos courbes et ça fonctionne comme du charme.
didito
5
FYI: Ces fonctions sont appelées fonctions quantiles: en.wikipedia.org/wiki/fonction_quantile
Neil G
8

Une explication plus longue:

Si vous avez une distribution de probabilité souhaitée telle que le gradient demandé par @didito, vous pouvez le décrire comme une fonction. Disons que vous voulez une distribution triangulaire, où la probabilité à 0 est 0,0, et que vous voulez choisir un nombre aléatoire de 0 à 1. Nous pourrions l'écrire comme y = x.

L'étape suivante consiste à calculer l'intégrale de cette fonction. Dans ce cas, c'est X=1X2 . Évalué de 0 à 1, c'est ½. Cela a du sens - c'est un triangle avec la base 1 et la hauteur 1, donc sa superficie est de ½.

Vous choisissez ensuite un point aléatoire uniformément de 0 à la zone (½ dans notre exemple). Appelons cela z. (Nous choisissons uniformément dans la distribution cumulative .)

X=1X21X̂2=zX̂=2z

2zrunen(0,1)

amitp
la source
merci pour votre entrée de valeur. j'aime toujours savoir comment les gens qualifiés résolvent les problèmes. mais j'ai encore besoin d'envelopper ma tête pour être honnête ...
didito
C'est génial. J'ai toujours fait sqrt(random())ma vie entière mais j'y suis venue empiriquement. Essayer de lier un nombre aléatoire à une courbe, et cela a fonctionné. Maintenant que je suis un peu plus qualifié en mathématiques, savoir pourquoi cela fonctionne est très précieux!
Gustavo Maciel
5

Vous obtiendriez probablement une approximation proche de ce que vous voulez en utilisant un système exponentiel.

Faites le x basé sur quelque chose comme 1- (valeur rnd ^) (en supposant que rnd est compris entre 0 et 1) et vous obtiendrez quelques comportements différents de gauche à droite en fonction de ce que vous utilisez. Une valeur plus élevée vous donnera une distribution plus asymétrique

Vous pouvez utiliser un outil graphique en ligne pour obtenir des idées approximatives sur les comportements que différentes équations vous donneront avant de les placer, ou vous pouvez simplement jouer avec les équations directement dans votre système de particules, selon le style qui convient le mieux à vos goûts.

MODIFIER

Pour quelque chose comme un système de particules où le temps CPU par particule est très important, l'utilisation directe de Math.Pow (ou équivalent de langage) peut entraîner une baisse des performances. Si davantage de performances sont souhaitées et que la valeur n'est pas modifiée au moment de l'exécution, envisagez de passer à une fonction équivalente telle que x * x au lieu de x ^ 2.

(Les exposants fractionnaires pourraient être plus problématiques, mais quelqu'un avec une formation en mathématiques plus forte que moi pourrait probablement trouver un bon moyen de créer une fonction d'approximation)

Lunin
la source
1
Au lieu d'utiliser un programme graphique, vous pouvez simplement tracer la distribution bêta car il s'agit d'un cas spécial. Pour une donnée value, c'est Beta (valeur, 1).
Neil G
THX. j'ai essayé de tracer quelques graphiques et je pense que cela pourrait me mener où je veux.
didito
@Neil G merci pour l'astuce avec "distribution bêta" - cela semble intéressant et utile ... je ferai des recherches sur ce sujet
didito
3

Le terme que vous recherchez est Weighted Random Numbers, la plupart des algorithmes que j'ai vus utilisent des fonctions trigonométriques, mais je pense que j'ai trouvé un moyen efficace:

Créez une table / un tableau / une liste (peu importe) qui contient une valeur de multiplicateur pour la fonction aléatoire. Remplissez-le à la main ou par programme ...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

... puis multipliez randompar une valeur choisie au hasard randMultiet enfin par la valeur max de la distribution ...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

Je pense que cela sera beaucoup plus rapide que l'utilisation sqrtou d'autres fonctions plus complexes sur le plan informatique et permettra des modèles de regroupement plus personnalisés.

AttackingHobo
la source
2
Si vous pouvez sacrifier la mémoire, une table de 100 valeurs pré-calculées serait plus rapide (et légèrement plus précise). Je doute que l'utilisateur puisse distinguer les versions complètes et pré-calculées.
Daniel Blezek
@Daniel, ce serait plus rapide, mais avec 100 valeurs aléatoires, il est assez facile de voir des motifs répétés.
AttackingHobo
Ce n'est pas parce qu'il semble y avoir un motif répétitif qu'il n'est pas aléatoire. L'essence du caractère aléatoire est son imprévisibilité, ce qui signifie littéralement que, même si l'on ne peut pas prédire qu'il n'y aura pas de modèle, on ne peut pas non plus prédire qu'il pourrait y en avoir un (au moins pour une courte période). Vous devrez faire des tests, mais si vous trouvez des modèles avec plusieurs tests utilisant différentes graines, alors votre algorithme pour générer des nombres pseudo-aléatoires devra peut-être être revu.
Randolf Richardson
@AttackingHobo thx pour cette astuce. j'aime l'utilisation des LUT. et la formule est assez facile à comprendre. je n'y avais pas pensé de cette façon auparavant. ne pas voir le bois pour les arbres ... :) aussi je pense que les motifs répétitifs doivent être évités mais ne seraient probablement pas reconnus dans ce cas de toute façon. néanmoins, le précalcul de toutes les valeurs nuirait à l'expérience visuelle. de toute façon, merci de me rappeler que c'est un facteur à considérer sur le sujet du hasard ...
didito
merci également d'avoir évoqué le terme "nombres aléatoires" pondérés!
didito
2

Je pense que ce que vous demandez, c'est la distribution obtenue en utilisant une fonction de racine carrée.

[position] = sqrt(rand(0, 1))

Cela donnera une distribution dans le champ de dimension unique [0, 1]où la probabilité d'une position est équivalente à cette position, c'est-à-dire une "distribution triangulaire".

Génération alternative sans racine carrée:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

Une racine carrée dans une implémentation optimale est juste quelques commandes de multiplication et de somme sans branches. (Voir: http://en.wikipedia.org/wiki/Fast_inverse_square_root ). Laquelle de ces deux fonctions est la plus rapide peut varier en fonction de la plate-forme et du générateur aléatoire. Sur une plate-forme x86, par exemple, il ne faudrait que quelques branches imprévisibles dans le générateur aléatoire pour ralentir la deuxième méthode.

aaaaaaaaaaaa
la source
La probabilité d'une position ne sera pas égale à la position (c'est mathématiquement impossible - trivialement, le domaine et la plage de la fonction incluent à la fois 0,50 et 0,51), ni une distribution triangulaire. ( en.wikipedia.org/wiki/Triangular_distribution )
1
Alors que sqrt donne des motifs intéressants, les systèmes de particules doivent généralement être très légers par CPU, donc je recommanderais d'éviter les racines carrées (qui sont lentes sur le plan des calculs) lorsque cela est possible. Vous pouvez parfois vous en sortir en les pré-calculant, mais cela peut rendre vos particules visibles au fil du temps.
Lunin
1
@ Joe Wreschnig, avez-vous lu vous-même cet article Wikipedia, insérez a = 0, b = 1, c = 1 dans la formule de génération et vous obtenez la formule dans mon article.
aaaaaaaaaaaa
3
@Lunin, pourquoi vous plaignez-vous de la racine carrée quand vous avez un exposant dans votre réponse?
aaaaaaaaaaaa
1
@Lunin: La théorie de la performance est un domaine assez négligé, beaucoup de ce que les gens pensent savoir où il y a environ 30 ans était correct lorsque les ALU étaient gros et lents. Même la fonction d'exposant que vous venez de découvrir comme étant une fonction arithmétique assez lente est rarement un pécheur de performance très significatif. Les branchements (à l'aide d'une instruction if) et les échecs de cache (lecture d'un élément de données ne résidant pas actuellement dans le cache) sont généralement ceux qui coûtent le plus de performances.
aaaaaaaaaaaa
1

Utilisez simplement une distribution bêta:

  • La bêta (1,1) est plate
  • La bêta (1,2) est un gradient linéaire
  • La bêta (1,3) est quadratique

etc.

Les deux paramètres de forme n'ont pas besoin d'être des entiers.

Neil G
la source
merci pour votre aide. comme indiqué ci-dessus, la distribution bêta semble intéressante. mais je ne peux pas encore donner un sens au contenu de la page wikipedia. ou une formule / code. eh bien, je n'ai pas le temps pour le moment d'enquêter plus avant: si voyez que boost a du code pour les distributions bêta, mais ce serait exagéré. eh bien, je suppose que je dois d'abord le parcourir, puis écrire ma propre version simplifiée.
didito
1
@didito: Ce n'est pas si difficile. Vous venez de remplacer votre uniform_generator()appel par gsl_ran_beta(rng, a, b). Voir ici: gnu.org/software/gsl/manual/html_node/…
Neil G
merci pour l'astuce. je n'utilise pas GSL (en fait, je n'en ai jamais entendu parler auparavant), mais bon appel. je vais vérifier la source!
didito
@didito: Dans ce cas, j'irais avec la solution de Lunin. Bonne chance.
Neil G
0

Encore plus simple, selon la vitesse de votre générateur aléatoire, vous pouvez simplement générer deux valeurs et les faire la moyenne.

Ou, encore plus simple, où X est le résultat de la RNG, d' abord double y = double(1/x);, x = y*[maximum return value of rng];. Cela pondérera les nombres de façon exponentielle aux nombres inférieurs.

Générez et faites la moyenne de plus de valeurs pour augmenter la probabilité de rapprocher les valeurs du centre.

Bien sûr, cela ne fonctionne que pour les distributions de courbes en cloche standard ou leurs versions "pliées" *, mais avec un générateur rapide, cela pourrait être plus rapide et plus simple que d'utiliser diverses fonctions mathématiques comme sqrt.

Vous pouvez trouver toutes sortes de recherches à ce sujet pour les courbes de cloche de dés. En fait, Anydice.com est un bon site qui génère des graphiques pour différentes méthodes de lancer de dés. Bien que vous utilisiez un RNG, la prémisse est la même, tout comme les résultats. C'est donc un bon endroit pour voir la distribution avant même de la coder.

* De plus, vous pouvez "plier" la distribution des résultats le long d'un axe en prenant l'axe et en soustrayant le résultat moyen puis en ajoutant l'axe. Par exemple, vous voulez que les valeurs inférieures soient plus courantes, et disons que vous voulez que 15 soit votre valeur minimale et 35 soit votre valeur maximale, une plage de 20. Ainsi, vous générez et faites la moyenne ensemble de deux valeurs avec une plage de 20 ( deux fois la plage que vous voulez), ce qui donnera une courbe en cloche centrée sur 20 (nous soustrayons cinq à la fin pour déplacer la plage de 20 à 40, à 15 à 35). Prenez les nombres générés X et Y.

Numéro final,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range

Si zéro est votre minimum, encore mieux, faites-le à la place,

z= (x+y)/2;
If (z<20){z = 20-z;}
else {z = z - 20;}
return z;
TheAlicornSage
la source