Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

Gif showing the idea of modifying a probability curve depending on the already generated values.

share|improve this question
2  
Simply adding a minimum distance would make sure a planet is not next to another. I estimate this is to simple so could you elaborate some more? –  Menno Gouw Mar 3 at 15:57
    
@MennoGouw Yes, that would solve it for this specific case, though I want to improve my understanding of probability so I am looking for a "softer" solution without hard limits/discarding generated numbers. –  API-Beast Mar 3 at 16:14
    
Clarify the "softer" solution. It's all about setting rules. When you need certain rules for procedural generation you need to add these rules. If you have special cases you set more or different rules for these. –  Menno Gouw Mar 3 at 16:19
    
I'm not sure why you don't just use a generator that has a great reputation about it's distribution? (I think the Mersenne twister is not bad.) –  Alexandre Vaillancourt Mar 3 at 16:22
2  
I agree. The random generation itself is not the problem. Doing this can even break your random generator by making it predictable. Rule generation is the way to go. –  ashes999 Mar 3 at 17:25

4 Answers 4

up vote 8 down vote accepted

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.

share|improve this answer
    
Could you go a bit more in-depth about defining the distribution function? The rest should be pretty clear. –  API-Beast Mar 3 at 19:11
    
For example, if the current planets are at positions 0.1, 0.3 and 0.8, g(x) = (abs(x-0.1)*abs(x-0.3)*abs(x-0.8))^0.5, where "^" means exponentiation. (This is slightly differently written from the previous formula, but equivalent.) This distribution function looks roughly like the gif in your question and is not based on anything in particular. (Query string for WolframAlpha: "plot from 0 to 1 (abs(x-0.1)*abs(x-0.3)*abs(x-0.8))^0.5") –  yarr Mar 3 at 21:14
    
Wow, that function is pretty damn cool. Didn't know that a function like that is actually that simple :) Link for the lazy: bit.ly/1pWOZMJ –  API-Beast Mar 3 at 22:05

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.