Continuous weighted random distribution, biased toward one end

Question

I am currently contributing to a particle system for our game and developing some emitter shapes.

My uniform random distribution along a line or along a rectangular area works fine - no problem.

But now I would like to have something like a 1 dimensional gradient in this distribution. This would mean for example lower values are more common than higher values.

I don't know what would be appropriate mathematical terms for this problem, so my search skills are rather useless with this one. I need something that is computationally simple, as the particle system needs to be efficient.

Answer 1

Take a look at this picture:

It shows the process of mapping a (random) value to a curve. Suppose you generate a uniformly-distributed random value X, ranging from 0 to 1. By mapping this value to a curve - or, in other words, using f(X) instead of X - you can skew your distribution in whatever way you like.

In this picture, first curve makes higher values more likely; second makes lower values more likely; and the third one makes values cluster in the middle. The exact formula of the curve is not really important, and can be chosen as you like.

For example, first curve looks a bit like square root, and second - like square. Third one is a bit like cube, only translated. If you consider square root to be too slow, first curve also looks like f(X)=1-(1-X)^2 - an inversion of square. Or a hyperbole: f(X)=2X/(1+X).

As a fourth curve shows, you can simply use a precomputed lookup table. Is looks ugly as a curve, but will probably be good enough for a particle system.

This general technique is very simple and powerful. Whatever distribution you need, just imagine a curve mapping, and you'll devise a formula in no time. Or, if your engine has an editor, just make a visual editor for the curve!

Answer 2

A longer explanation:

If you have a desired probability distribution such as the gradient @didito asked for, you can describe is as a function. Let's say you want a triangular distribution, where the probability at 0 is 0.0, and you want to pick a random number from 0 to 1. We might write it as y = x.

The next step is to calculate the integral of this function. In this case, it's \$\int x=\frac{1}{x^2}\$. Evaluated from 0 to 1, that's ½. That makes sense — it's a triangle with base 1 and height 1, so its area is ½.

You then pick a random point uniformly from 0 to the area (½ in our example). Let's call this z. (We're picking uniformly from the cumulative distribution.)

The next step is to go backwards, to find what value of x (we'll call it x̂) corresponds to an area of z. We're looking for \$\int x=\frac{1}{x^2}\$, evaluated from 0 to x̂, being equal to z. When you solve for \$\frac{1}{x̂^2}=z\$, you get \$x̂ = \sqrt{2z}\$.

In this example, you pick z from 0 to ½ and then the desired random number is \$\sqrt{2z}\$. Simplified, you can write it as \$\sqrt{rand(0, 1)}\$ — exactly what eBusiness recommended.

Answer 3

You'd probably get a close approximation to what you want by utilizing an exponential system.

Make the x based on something like 1-(rnd^value) (Assuming rnd is between 0 and 1) and you'll get a few different behaviors of left to right skewing based on what you use. A higher value will get you a more skewed distribution

You can use an online graphing tool to get some rough ideas on the behaviors different equations will give you before placing them in, or you can just fiddle with the equations directly in your particle system, depending what style is more to your tastes.

EDIT

For something like a particle system where CPU time per particle is very important, using Math.Pow (or language equivalent) directly can lead to a decrease in performance. If more performance is desired, and value isn't being changed in run-time, consider switching to an equivalent function such as x*x instead of x^2.

(Fractional exponents could be more of an issue, but someone with a stronger math background than I could probably come up with a good way to create an approximation function)

Answer 4

The term you are looking for is Weighted Random Numbers, most of the algorithms I have seen use trig functions, but I think I figured out a way that will be efficient:

Create a table/array/List(whatever) that holds a multiplier value for the random function. Fill it out by hand or programatically...

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

...then Multiply random by a randomly chosen randMultiand finally by the max Value of the distribution...

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

I do believe that this will be much faster than using sqrt, or other more computationally complex functions, and will allow for more custom grouping patterns.

Answer 5

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.

Answer 6

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.

Answer 7

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;