10
\$\begingroup\$

Im trying to generate a star map.

My try would be:

  1. Have a width and height for the map.
  2. Place points (stars) randomly across the area of width and height.

A simple approach, but it has the problem of randomly placing stars extremely close to each other.

To solve this problem, one approach would be to have a minimum distance and when generating a star, you compare the distance from the new star to every generated star and if its below minimum distance, you generate a new one, but I dont know if thats efficient. Any tips?

\$\endgroup\$
7
  • 3
    \$\begingroup\$ There may be more efficient ways to do it, but why does it not work for you? Do you have issues with this implementation? Are you prematurely optimizing? \$\endgroup\$
    – Vaillancourt
    Commented Aug 23, 2016 at 19:27
  • \$\begingroup\$ What's the purpose of the star map? Is it a background, or more like a playing field? \$\endgroup\$
    – Erik
    Commented Aug 23, 2016 at 19:40
  • \$\begingroup\$ @AlexandreVaillancourt yea I dont know how many stars I want to generate yet and it feels like it is a very inefficient way. \$\endgroup\$ Commented Aug 23, 2016 at 19:47
  • \$\begingroup\$ @Erik not a background, stars you can interact with \$\endgroup\$ Commented Aug 23, 2016 at 19:48
  • \$\begingroup\$ And... will you do it a run-time or offline? \$\endgroup\$
    – Vaillancourt
    Commented Aug 23, 2016 at 19:49

3 Answers 3

16
\$\begingroup\$

A Poisson-Disk sampling distribution will allow you to select random points a minimum distance apart & Bridson's algorithm can efficiently solve the problem in O(n) - fast enough for real time provided your star count doesn't get too huge.

Bridson's algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. For instance, consider the following image:

enter image description here

When checking to see if the candidate blue dot is too close to existing dots, you don't need to check it against every existing dot. Instead you can restrict the search to the dots in the neighboring cells (which you can find quickly using a lookup table). Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. Herman Tulleken's Poisson Disk sampling article (includes source code) covers an adaptation for varying the minimum distance at different parts the image; basically like a dithering algorithm. Using perlin noise / simplex noise as shown in the article clouds might give a more natural looking star map. For example, I used the image on the left to generate the right:

enter image description here enter image description here

To do this, when considering a candidate point, I first check the value of input image, which yields a value from 0 to 1. I then scale this to my desired min & max distance between points; in this case I selected 5 & 20 pixels. So when placing a point in the dark regions, my stars can be as close as 5 pixels to each other & when placing stars in the light regions, they can be up to 20 pixels apart.

It's worth noting that Bridson's speed up doesn't exactly work with variable distance sampling because the output points aren't using a uniform minimum distance. However you can still use a the output grid to reduce the searching. A smaller the grid results in a quicker the search for nearest neighbors at the expense of increased memory for a larger lookup table.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The links are very nice. However, they could get lost over time. It might be even better to include more details here. \$\endgroup\$ Commented Aug 24, 2016 at 9:28
  • \$\begingroup\$ Added a bit more explanation & illustration to guard against that. \$\endgroup\$
    – Pikalek
    Commented Aug 24, 2016 at 17:55
1
\$\begingroup\$

One very naive but simple solution would be to simply always jump the "minimum" distance, and then append a random amount on top of that. This means stars will never get too buddy buddy, and you'll at least get a bit of deviation.

e.g

for (int x = 0; x < MAX_WIDTH; x+= MIN_SEPERATION_X)
{
  x += generateRandom();

  for (int y = 0; y < MAX_HEIGHT; y+= MIN_SEPERATION_Y)
  {
    y += generateRandom();

    if (x < MAX_WIDTH && y < MAX_HEIGHT)
    {
      image[x + y * width] = STAR;
    }
  }
}

(Inserting your favourite random number generation function)

\$\endgroup\$
4
  • \$\begingroup\$ But what if you hit another star there? (Also your stars should be in a tilted band if doing like this.) \$\endgroup\$ Commented Aug 24, 2016 at 9:26
  • 1
    \$\begingroup\$ Is it possible to hit another star? I'm assuming only one iteration over the whole image. Doesn't both numbers always changing by a min separation stop that? I hear stellar merges are pretty messy so I agree it's good to make sure they don't happen. Causing a supernova would be a very inconsiderate bug. \$\endgroup\$ Commented Aug 24, 2016 at 10:04
  • \$\begingroup\$ I meant that the min_separation is not guaranteed (cannot be with this algorithm) because you always add random numbers. At least make sure, the random numbers cannot be larger than min_separation. The guaranteed minimal distance is then min_separation - max(generate_Random). But it's not a really bad approach. +1 \$\endgroup\$ Commented Aug 24, 2016 at 11:01
  • \$\begingroup\$ This approach will tend to produce columns of stars in neat vertical lines, since you don't vary the x coordinate as y changes. This is unlikely to look random or natural for dense collections. \$\endgroup\$
    – DMGregory
    Commented Aug 24, 2016 at 11:59
0
\$\begingroup\$

If you know the X Y Z size of your play space you could pick a random spot in that space

and then do a SphereCast to check if there is anything too close already.

//pseudo code

SpawnStar(){
 Vector3 spot = new vector3(random(0,world size),random(0,world size,random(0,world size)

  while(true){
  SphereCast(spot, radius)
   if(hit something){
      spot = get new random spot
    }else{
     SpawnStar();
     brake;
    }
  } 
}

Problem with this is that it probably wont be very good for real time, however for pre generated it's fine and pretty quick.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Whatever a SphereCast is, isn't this exactly the solution which is mentioned in the question and regarded as inefficient? \$\endgroup\$ Commented Aug 24, 2016 at 9:25
  • 1
    \$\begingroup\$ @Trilarion docs.unity3d.com/ScriptReference/Physics.SphereCast.html \$\endgroup\$ Commented Aug 24, 2016 at 9:38
  • 1
    \$\begingroup\$ I think you mean OverlapSphere. SphereCast fires a sphere along a line, so it has a capsule-shaped detection footprint. \$\endgroup\$
    – DMGregory
    Commented Aug 24, 2016 at 12:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .