Random Numbers with the Distribution You Want

The Problem

I was playing around with game prototyping and when the user tapped the touchscreen (I was messing around with DS Homebrew), I wanted to spawn a bunch of particles distributed randomly within some radius around where he tapped. So my first approach was to take my existing random number generator to get a value for my offset, then take a random direction to apply that offset in and I would have my point.

Now most random number generators you'll find try to give you a value from 0 to some maximum, with the chance for any one number in that range being as close as possible to the chance for any other number. From here on out I'm going to be assuming that all possible values of our random number generator come up with equal probability, and to make things easier, I'm going to sort of "normalize" the range and treat it as though these values came back in the range instead of whatever range they actually fall in.

So we will get random numbers along the offset looking something like this:

(100 faded-out dots distributed along a line segment with such a distribution)

And if we rotate that offset a random amount around the point the user tapped, we get them distributed something like this:

(400 faded-out dots distributed within a circle this way)

But we have something undesirable happening here. The points are much more crowded together in the center of the circle. We would want them distributed more evenly; something more like this:

(400 faded-out dots distributed using the tricks described here)

What Do We Want?

Let's get into some math to get a better idea of what's happening here. Before we rotated them, we got our points at any radius distributed pretty evenly, but something happened when we rotated. For each value of , the points that (potentially) ended up there were now spread around a circle with perimeter . Since the perimeter increases in direct proportion to the offset distance, we want the "density" of our random values points at a radius to also be in direct proportion to .

So far I've been talking about the "distribution" and "density" of random numbers, but I should be more precise about what I mean. There is a concept in statistics used for exactly for what I mean here, called Probability Density. Statistics.com has a pretty good summary of the concept here, and Wikipedia goes a bit more in-depth here. The core of the idea is that for some continuous random variable and its probability density function , the probability that lies between some and is .

As previously mentioned, we want to choose our random offset from the point tapped so that the "density" increases in direct proportion to the offset. For example, we want to get values near twice as often as values near . We can now state that as

.

So a very easy solution for is . But what is ? Well, since we're dealing with numbers between one and zero, the probability of getting a number in that range needs to be one. This means that

How To Get Numbers With That Probability Density

Now we know what the probability density should be, but how do we get random numbers matching that distribution? The solution I am going to present is to find some function to apply to the numbers we get back from our standard random number generators, so that the result will have the probability density we desire. I'm going to do this the hard way and work out the more general case first, then apply it here.

Transforming From One Probability Distribution To Another

In the more general problem, we are sampling some continuous random variable in the range with a probability density function of . We are looking for a transformation we can apply to those numbers such that the resulting set of values is in and has probability density .

So for any range within we are getting random values in that range with probability and we are looking for a function that will transform our random values so that the probability of the transformed value lying between and is . The range that will map to is .

Putting it together now, the two functions over the two ranges should give the same probability, so now we have our equation from which we can deduce :

Applying This To Our Problem

In the particular problem we are working on, . (The "source" random values are distributed evenly) So we can substitute that in to the equation we just found:

which means the derivative of is !

And we determined above that the probability density we want is , so let's substitute that in.

So works for us, and we see that .
We want the positive square root because it needs to map onto .

The End

So to get the sprites distributed the way we want, we can do (pseudocode)

radius = sqrt( rand() / RAND_MAX ) * MAX_RADIUS;
angle = rand() * 2 * PI / RAND_MAX;

(and pretend this is floating point so that dividing by RAND_MAX doesn't screw you over)

So now it distributes the sprites like this:

(1000 dots distributed throughout a circle. Dots are 30% opaque.)

Here's the actual actionscript used to generate this last image in Flash:
(of course, you'd need an mcCircle on the stage and a movieclip in the library with the linkage "Dot")

var centerX:Number = mcCircle._x;
var centerY:Number = mcCircle._y;
var maxOffset:Number = mcCircle._width / 2;

var NUM_DOTS:Number = 1000;
for (var i:Number = 0; i<NUM_DOTS; ++i)
{
	var Dot:MovieClip = this.attachMovie("Dot", "Dot" + i, 100+i);
	var angle:Number = Math.random() * 2 * Math.PI;
	var offset:Number = Math.sqrt(Math.random()) * maxOffset;
	Dot._x = centerX + ( offset * Math.cos(angle) );
	Dot._y = centerY + ( offset * Math.sin(angle) );
}