Generation of uniformly distributed random noise

问题:

I've been working on generating Perlin noise for a map generator of mine. The problem I've run into is that the random noise is not distributed normally, and is more likely a normal distribution of kinds.

Given two integers X and Y, and a seed value, I do the following:

• Use MurmurHash2 to generate a random number (-1,1). This is uniformly distributed.
• Interpolate points between integer values with cubic interpolation. Values now fall in the range (-2.25, 2.25) because the interpolation can extrapolate higher points (by 1.5 in every dimension) between similar values, and the distribution is no longer uniform.
• Generate these interpolated points, summing them together while halving the amplitudes (See: Perling noise) As the number of sums approaches infinity, the limit of the range now approaches twice the previous values, or (-4.5, 4.5) and is now even less uniform.

This obviously doesn't work when I want a range from (-1, 1), so I divide all final values by 4.5. Actually, I divide them along the way (by 1.5 after interpolating each dimension, then by 2 after summing the noise.)

After the division, I'm left with a theoretical range of (-1, 1). However, the vast majority of the values are (-0.2,0.2). This doesn't work well when generating my maps, since I need to determine the percentage of the map filled. I also cannot use histograms to determine what threshold to use, since I'm generating the squares on demand, and not the entire map.

I need to make my distribution uniform at two points - after the interpolation, and after the summing of the noise functions. I'm not sure how to go about this, tho.

My distribution looks like this:

I need it to look like this:

(Both images from Wikipedia.)

Any solutions are appreciated, but I'm writing in C#, so code snippets would be extremely helpful.

回答1:

Combine the resulting sample with the CDF for the gaussian, which is 0.5*erf(x) + 1 (erf = error function).

Note that in virtue of the Central Limit Theorem, whenever you make sums of random variables, you get gaussian laws.

回答2:

This is an answer to your final comment, rather than your question as asked. I don't necessarily think you can scale your resulting distribution back into a uniform distribution, and I'm not sure you would want to if you could. But if your goal is to get, say, all the values under 50% to be grass, it may be easier and less error prone to measure (or estimate) the median of your output, and call that 50%.

The result is the same, and you don't have to deal with any complicated (and therefore error-prone) scaling functions.

回答3:

This is a simple scaling problem. And all simple scaling problems are just manifestations of a straight line in Cartesian geometry:

You have a line:

       |   /
     1 + -/,
       | / ,
____,__|/__,____
 -4.5 /|   4.5
    ,/ |
    /- + -1
   /   |

on that line, when x=4.5, y=1 and when x=-4.5 y=-1. Now I'm sure that once you realize this you know the solution. y=mx + c. Since the line is symmetric on both positive and negative sides then you can assume that it crosses at zero so c=0. Now to find the slope:

m = dy/dx
m = (1 - -1)/(4.5 - -4.5)
m = 2/9

therefore:

y = 2/9 x + 0
y = 2x / 9

so, now you can plug this in. What is y when x = 3?:

y = 2*3 / 9
y = 6/9
y = 2/3

and what is y when x = 4?:

y = 2*4 / 9
y = 8/9

---

additional notes:

The assume-the-line-crosses-at-zero thing I'm doing because my experienced eye tells me it's right. But if I were doing this for a high school math exam I'd likely lose credits (even if my answer is right). For the proper formulaic solution, to find c you have to first find m and then substitute the x and y values of a known coordinate:

y = 2/9 x + c

given that (4.5,1) and (-4.5,-1) are known coordinates, substitute x and y for 4.5 and 1:

1 = 2*4.5/9 + c
1 = 9/9 + c
1 = 1 + c
c = 1 - 1
c = 0

All this can be enshrined in a scaling function:

// example code in javascript:
function makeScaler (x1, y1, x2, y2) {
    var m = (x2-x1)/(y2-y1);
    var c = y1 - m*x1;

    // return a scaling function:
    return function (x) {
        return m*x + c;
    }
}

var f = makeScaler(-4.5,-1,4.5,1);
alert(f(4)); // what y is when x is 4

// or if you prefer:
var g = makeScaler(-4.5,0,4.5,1); // scale from 0 to 1
alert(g(4));