Modify random distribution functions :: Make it less likely to get multiple similar values in a sequence

Question

I want to generate a sequence of numbers for procedurally generating planets in a galaxy sector. Each planet should be placed randomly, however it should be very unlikely that two planets are directly next to each other. How can I achieve that?

I know that you can modify the chances by applying a distribution function, but how can I control them in order to make specific values more/less likely?

Answer 1

If you do know the distribution you want, you can use rejection sampling.

Simplest way: In the graph above, pick points at random until you find one is below the curve. Then just use the x-coordinate.

For the actual distribution, there are various plausible approaches. For example, for planet number i at location p, and some strength parameter k (e.g. 0.5), define a function f_i(x)=abs(p-x)^k, then use distribution function g(x)=f_1(x)*f_2(x)*...*f_n(x).

In practice, compute and store results of g(x) to array t (t[x]=g(x)); remember the highest seen value h also. Pick a random position x in t, pick random value y between 0 and h, repeat if y>t[x]; otherwise the return value is x.

Answer 2

I am not sure the problem is fully specified by the question, but I can provide some simple ideas, the second of these will provide numbers roughly in accordance with what your picture indicates you want.

Either way as you may realize the distribution function is changing after each number generated, and has a memory (ie: it is non-Markovian) and either of these method may prove impractical when the 'memory' (number of previously drawn numbers) gets very large.

1. Simple:
   Generate random number form a flat distribution, compare with previously drawn nnumbers, repeat if 'too close'

2. This answer is more like your figure (assuming we want to draw from 0..1):

   • create a new ordered list, insert 0 and 1
   • generate random number from a flat distribution function: N_0
     • add this number to the list
   • on next call, draw a another number N_1,
   • if N_1> N_0
     • draw a new Gaussian Random number with mean=1 and a standard deviation o of whatever you want, a smaller number (compared with 1-N_1) will keep the random numbers further spaced apart. This will not guarantee a minimum distance between draws, but then again your figure doesn't seem to either.
   • opposite case of N_1 < N_0 handled similarly
   • on subsequent draws keep generating a random number (N_i) from a flat distribution
   • traverse your list to see which two previously drawn numbers the new number lies between (N_-, N_+)
   • create a new Gaussian random number with mean (N_- + N_+)/2
   • add the flat distribution number (N_i) to your (ordered list) list

endpoint bins are a special case, but it should be simple enough for you to see how to handle them.

Answer 3

Think of the difference between 1 dice and 3 dice. 1 Dice gives you an even probability for all values, while 3 dice will tend to have a higher probability for the values towards the middle.

The more "dice" in your equation, the stronger your chance to get something towards the centre. So let's define a function that can handle any number evenly:

// Takes a random number between floor and ceil
// pow defines how strongly these results should gravitate towards the middle
// We also define a function TrueRand(floor, ceil) elsewhere where you should substitute your own random function
int CenterRandom(int floor, int ceil, int pow = 3)
{
    if(ceil == floor)
        return ceil; // don't care to compare

    int total = 0;
    for(int x = 0; x < pow; x++)
    {
       total += TrueRand(floor, ceil);
    }
    return total / pow;
}

Now we can define an example function to use this:

// Distribues a number of points between floor and ceil
// We assume a function PlotPoint(int) exists to aid in creating the planet, etc...
void DistributePoints(int floor, int ceil, int numPoints)
{
    // Could easily output this in the function parameters, but language wasn't specified
    int[numPoints] breaks;
    int numBreaks = 0;

    // Special case for first pair
    breaks[0] = CenterRandom(floor, ceil);
    numBreaks++;

    for(int x = 0; x < numPoints - 1; x++)
    {
        // Generate a random number linearly, this will be used for picking
        // This way we have a greater chance of choosing a random value between larger pairs
        int picker = TrueRandom(floor, ceil);

        // Now we first find the pair of points that our picker exists on
        // For simplicity, we handle the first and last pair separately

        if(picker >= floor && picker < breaks[0])
        {
            breaks[x] = CenterRandom(floor, breaks[0] - 1);
        }
        for(int i = 0; i < numBreaks; i++)
        {
            if(picker > breaks[i] && picker < breaks[i+1])
            {
                breaks[x] = CenterRandom(breaks[i] + 1, breaks[i+1] - 1);
            }
        }
        if(picker > breaks[numBreaks] && picker <= ceil)
        {
            breaks[x] = CenterRandom(breaks[numBreaks] + 1, ceil);
        }

        PlotPoint(breaks[x]); // Plot the point
    }
}

Now the first to note is that this code really doesn't check if picker matches one of the points already. If it does then it's just not going to generate a point, possibly something you'd might like.

To explain what's going on here is that CenterRandom generates a bell curve of sorts. This function breaks up the plane into multiple bell curves, one per pair of points existing. The picker tells us which bell curve to generate from. Since we pick linearly, we can ensure that pairs with larger gaps between them will be chosen more often, but we still leave it completely random.

Hope this points you in the right direction.

Answer 4

I know you're asking about a sequence of random positions, but if you aren't restricted to generating the set sequentially, there's another approach: generate a set of points that has the desired spacing.

What I think you want is a set of planets that are reasonably spaced with some randomness. Instead of generating planet positions with a random number generator, generate planet spacing with a random number generator. This will let you directly control the distribution of spacing, by using a random number generator that picks from that distribution. This is straightforward in 1 dimension.

In 2 dimensions, I've seen some approaches that generate “blue noise” but I don't know a way to generate spacing with an arbitrary distribution. This article covers the standard “try placing it and reject if it's too close” approach, but you can generate them all at once, with a “softer” solution by placing all your points, then using Lloyd Relaxation to move all the planets to more desirable positions. It'll move the too-close planets farther apart. Recursive Wang Tiles are another approach that could be useful. This paper extends the problem to generating planets with one density and some other object like asteroids with another density. You might also be able to generate blue noise by using Fourier series; I'm not sure. The Fourier series approach would also let you use arbitrary distributions instead of only blue noise.