Kontinuierlich gewichtete Zufallsverteilung, zu einem Ende hin vorgespannt

28

Ich arbeite derzeit an einem Partikelsystem für unser Spiel und entwickle einige Emitterformen.

Meine gleichmäßige zufällige Verteilung entlang einer Linie oder entlang einer rechteckigen Fläche funktioniert einwandfrei - kein Problem.

Aber jetzt möchte ich so etwas wie einen eindimensionalen Gradienten in dieser Verteilung haben. Dies würde zum Beispiel bedeuten, dass niedrigere Werte häufiger sind als höhere Werte.

Ich weiß nicht, welche mathematischen Begriffe für dieses Problem angemessen wären, daher sind meine Suchfähigkeiten bei diesem eher nutzlos. Ich brauche etwas, das rechnerisch einfach ist, da das Partikelsystem effizient sein muss.

Didito
quelle
Wird niemand Kalkül erwähnen?
Alec Teal

Antworten:

42

Schauen Sie sich dieses Bild an:

Kurvenzuordnung

Es zeigt den Prozess der Abbildung eines (zufälligen) Werts auf eine Kurve. Angenommen, Sie generieren einen gleichmäßig verteilten Zufallswert X im Bereich von 0 bis 1. Indem Sie diesen Wert einer Kurve zuordnen - oder mit anderen Worten f (X) anstelle von X verwenden - können Sie Ihre Verteilung beliebig verzerren .

In diesem Bild macht die erste Kurve höhere Werte wahrscheinlicher; Mit second werden niedrigere Werte wahrscheinlicher. und die dritte macht Werte in der Mitte zu Clustern. Die genaue Formel der Kurve ist nicht wirklich wichtig und kann nach Belieben gewählt werden.

Beispielsweise sieht die erste Kurve ein bisschen wie eine Quadratwurzel und das zweite wie ein Quadrat aus. Dritte ist ein bisschen wie Würfel, nur übersetzt. Wenn Sie die Quadratwurzel für zu langsam halten, sieht die erste Kurve auch wie folgt aus: f (X) = 1- (1-X) ^ 2 - eine Inversion des Quadrats. Oder eine Übertreibung: f (X) = 2X / (1 + X).

Wie eine vierte Kurve zeigt, können Sie einfach eine vorberechnete Nachschlagetabelle verwenden. Sieht hässlich aus wie eine Kurve, ist aber wahrscheinlich gut genug für ein Partikelsystem.

Diese allgemeine Technik ist sehr einfach und leistungsstark. Welche Verteilung Sie auch benötigen, stellen Sie sich einfach eine Kurvenzuordnung vor und Sie werden in kürzester Zeit eine Formel erstellen. Wenn Ihr Motor über einen Editor verfügt, können Sie auch einen visuellen Editor für die Kurve erstellen.

Keine Ursache
quelle
Vielen Dank für Ihre sehr gründliche und verständliche Erklärung. Alle anderen Beiträge waren auch sehr hilfreich, aber ich konnte Ihren Beitrag am einfachsten und schnellsten verstehen. es ragte heraus, weil es wirklich genau das Richtige für mein Verständnis der Dinge war. und die Aspekte, die du erklärst, sind genau das, wonach ich gesucht habe (oder was ich gesucht habe)! es wird mir ermöglichen, dies in Zukunft in vielen Fällen zu verwenden. also nochmals danke !!! Übrigens habe ich mit einigen deiner Kurven herumgespielt und es funktioniert wie Charme.
Didito
5
Zu Ihrer Information: Diese werden Quantilfunktionen genannt: en.wikipedia.org/wiki/Quantile_function
Neil G
8

Eine längere Erklärung:

Wenn Sie eine gewünschte Wahrscheinlichkeitsverteilung haben, z. B. den gewünschten Gradienten @didito, können Sie beschreiben, ob es sich um eine Funktion handelt. Angenommen, Sie möchten eine Dreiecksverteilung, bei der die Wahrscheinlichkeit bei 0 0,0 beträgt, und Sie möchten eine Zufallszahl von 0 bis 1 auswählen. Wir schreiben sie möglicherweise als y = x.

Der nächste Schritt ist die Berechnung des Integrals dieser Funktion. In diesem Fall ist x=1x2 . Bewertet von 0 bis 1, das ist ½. Das macht Sinn - es ist ein Dreieck mit Basis 1 und Höhe 1, also ist seine Fläche ½.

Sie wählen dann einen zufälligen Punkt gleichmäßig von 0 bis zur Fläche (½ in unserem Beispiel). Nennen wir dies z. (Wir wählen einheitlich aus der kumulierten Verteilung aus .)

Der nächste Schritt ist, rückwärts zu gehen, um herauszufinden, welcher Wert von x (wir nennen ihn x̂) einer Fläche von z entspricht. Wir suchen nach x=1x2 , ausgewertet von 0 bis x̂, gleich z. Wenn Sie für1lösen1x̂2=z, Sie erhaltenx̂=2z .

In diesem Beispiel wählen Sie z von 0 bis ½ und dann ist die gewünschte Zufallszahl 2z . Vereinfacht kann man es als schreibenrand(0,1) - genau das, was eBusiness empfohlen hat.

amitp
quelle
Vielen Dank für Ihre wertvolle Eingabe. Ich höre immer gerne, wie qualifizierte Leute Probleme lösen. aber ich muss immer noch meinen Kopf darum wickeln, um ehrlich zu sein ...
didito
das ist fantastisch. Ich habe immer sqrt(random())mein ganzes Leben gemacht, bin aber empirisch dazu gekommen. Der Versuch, eine Zufallszahl an eine Kurve zu binden, hat funktioniert. Jetzt, wo ich ein bisschen besser in Mathe bin, ist es sehr wertvoll zu wissen, warum es funktioniert!
Gustavo Maciel
5

Mit einem exponentiellen System würden Sie wahrscheinlich eine genaue Annäherung an das erreichen, was Sie wollen.

Stellen Sie das x auf der Grundlage von 1- (rnd ^ -Wert) ein (vorausgesetzt, rnd liegt zwischen 0 und 1), und Sie erhalten je nach Verwendung ein paar unterschiedliche Verhaltensweisen bei der Verschiebung von links nach rechts. Ein höherer Wert führt zu einer ungleichmäßigeren Verteilung

Sie können ein Online-Grafiktool verwenden, um einige grobe Ideen zu den Verhaltensweisen zu erhalten, die Ihnen verschiedene Gleichungen vor dem Einfügen geben, oder Sie können einfach mit den Gleichungen direkt in Ihrem Partikelsystem experimentieren, je nachdem, welcher Stil mehr zu Ihrem Geschmack passt.

BEARBEITEN

Bei einem Partikelsystem, bei dem die CPU-Zeit pro Partikel sehr wichtig ist, kann die direkte Verwendung von Math.Pow (oder einer entsprechenden Sprache) zu Leistungseinbußen führen. Wenn mehr Leistung gewünscht wird und der Wert während der Laufzeit nicht geändert wird, sollten Sie in Erwägung ziehen, zu einer äquivalenten Funktion wie x * x anstelle von x ^ 2 zu wechseln.

(Bruchexponenten könnten eher ein Problem sein, aber jemand mit einem stärkeren mathematischen Hintergrund als ich könnte wahrscheinlich einen guten Weg finden, um eine Approximationsfunktion zu erstellen.)

Lunin
quelle
1
Anstatt ein Grafikprogramm zu verwenden, können Sie einfach die Beta-Verteilung zeichnen, da dies ein Sonderfall ist. Für eine gegebene valueist dies Beta (Wert 1).
Neil G
Danke. Ich habe versucht, ein paar Grafiken zu zeichnen, und ich glaube, es könnte mich dahin bringen, wo ich will.
Didito
@Neil G thanks for the tip with "beta distribution" - this sounds interesting and useful ... i'll do some research on that topic
didito
3

Der Begriff, den Sie suchen, ist Weighted Random Numbers, dass die meisten Algorithmen, die ich gesehen habe, Triggerfunktionen verwenden, aber ich denke, ich habe einen Weg gefunden, der effizient sein wird:

Erstellen Sie eine Tabelle / ein Array / eine Liste (was auch immer), die einen Multiplikatorwert für die Zufallsfunktion enthält. Füllen Sie es von Hand oder programmatisch aus ...

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

... dann Multiplizieren randomvon einem zufällig gewähltenrandMulti und schließlich mit dem maximalen Wert der Verteilung ...

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

Ich glaube, dass dies viel schneller als die Verwendung sqrtoder andere komplexere Funktionen sein wird und mehr benutzerdefinierte Gruppierungsmuster zulassen wird.

AttackingHobo
quelle
2
Wenn Sie den Speicher opfern können, ist eine Tabelle mit 100 vorberechneten Werten schneller (und etwas genauer). Ich bezweifle, dass der Benutzer zwischen der vollständigen und der vorberechneten Version unterscheiden kann.
Daniel Blezek
@ Daniel es wäre schneller, aber mit 100 zufälligen Werten ist es ziemlich einfach, sich wiederholende Muster zu sehen.
AttackingHobo
Nur weil es scheinbar ein sich wiederholendes Muster gibt, heißt das nicht, dass es nicht zufällig ist. Die Essenz der Zufälligkeit ist ihre Unvorhersehbarkeit, was wörtlich bedeutet, dass man nicht vorhersagen kann, dass es kein Muster geben wird, und auch nicht vorhersagen kann, dass es eines geben wird (zumindest für kurze Zeit). Sie müssen einige Tests durchführen. Wenn Sie jedoch Muster mit mehreren Tests unter Verwendung verschiedener Startwerte finden, muss Ihr Algorithmus zum Generieren von Pseudozufallszahlen möglicherweise überprüft werden.
Randolf Richardson
@AttackingHobo thx for that trick. i like the use of LUTs. and the formula is quite easy to understand. i did not think of it this way before. not seeing the wood for the trees ... :) also i think repeating patterns should be avoided but probably would not be recognized in this case anyway. still, precomputing all values would hurt the visual experience. anyway, thx for reminding me that this is a factor to consider on the topic of randomness ...
didito
also thanks for bringing up the term Weighted "Random Numbers"!
didito
2

I think what you ask for is the distribution achieved using a square root function.

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

This will give a distribution in the single dimension field [0, 1] where the probability for a position is equivalent to that position, i.e. a "triangular distribution".

Alternate squareroot-free generation:

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

A square root in optimal implementation is just a few multiplication and sum commands with no branches. (See: http://en.wikipedia.org/wiki/Fast_inverse_square_root). Which one of these two functions are faster may vary depending on platform and random generator. On an x86 platform for instance it would take only a few unpredictable branches in the random generator to make the second method slower.

aaaaaaaaaaaa
quelle
The probability of a position won't be equal to the position (that's mathematically impossible - trivially, the domain and range of the function includes both 0.50 and 0.51), nor is it a triangular distribution. (en.wikipedia.org/wiki/Triangular_distribution)
1
While sqrt gives some interesting patterns, particle systems generally need to be very CPU light per particle, so I would recommend avoiding square roots (which are computationally slow) where possible. You can sometimes get away with just pre-computing them, but it can make your particles have noticeable patters over time.
Lunin
1
@Joe Wreschnig, did you read that Wikipedia article yourself, stuff a=0, b=1, c=1 into the generation formula and you get the formula in my post.
aaaaaaaaaaaa
3
@Lunin, why are you complaining about the square root when you have got an exponent in your answer?
aaaaaaaaaaaa
1
@Lunin: Performance theory is a pretty neglected field, a lot of what people think they know where approximately correct 30 years ago when ALUs were big expensive and slow. Even the exponent function which you have just discovered to be a quite slow arithmetic function is rarely a highly significant performance sinner. Branching (using an if statement) and cache misses (reading a piece of data not currently residing in cache) are typically what cost the most performance.
aaaaaaaaaaaa
1

Just use a Beta distribution:

  • Beta(1,1) is flat
  • Beta(1,2) is a linear gradient
  • Beta(1,3) is quadratic

etc.

The two shape parameters need not be integers.

Neil G
quelle
thx for your help. as stated above, beta distribution sounds interesting. but i cannot make sense of the content of the wikipedia page yet. or a formula / code. well, also i don't have time right now to investigate further :s i see that boost has code for beta distributions, but this would be overkill. well, i guess i need to go through it first and then write my own simplified version.
didito
1
@didito: It's not so hard. You just replace your uniform_generator() call with gsl_ran_beta(rng, a, b). See here: gnu.org/software/gsl/manual/html_node/…
Neil G
thx for the hint. i do not use GSL (actually have not heard about it before), but good call. i will check the source!
didito
@didito: In that case, I would go with Lunin's solution. Good luck.
Neil G
0

Even simpler, depending on the speed of your random generator, you can just generate two values and average them.

Or, even more simple, where X is the result of the rng, first double y = double(1/x);, x = y*[maximum return value of rng];. This will weight numbers exponentially to the lower numbers.

Generate and average more values to increase the likelihood of getting values closer to center.

Of course this only works for standard bell curves distributions or "folded" versions thereof*, but with a fast generator, it might be faster and simpler than using various math functions like sqrt.

You can find all sorts of research on this for dice bell curves. In fact, Anydice.com is a good site which generates graphs for various methods of rolling dice. Though you are using an RNG, the premise is the same, as are the results. So it is a good spot for seeing the distribution before even coding it.

*Also, you can "fold" the result distribution along an axis by taking the axis and subtracting the averaged result then adding the axis. For example, you want lower values to be more common, and lets say you want 15 to be your minimum value and 35 to be your max value, a range of 20. So you generate and average together two values with a range of 20 (twice the range you want), which will give a bellcurve centered on 20 (we subtract five at the end to shift the range from 20 to 40, to 15 to 35). Take the generated numbers X and Y.

Final number,

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

If zero is your minimum, even better, do this instead,

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