procedural generation - How would I go about generating a star map?

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?

Answer

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:

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:

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.