Ensuring that a randomly generated galaxy wont place stars inside one another?

Question

I'm attempting to build a game with a spiral galaxy design. In doing so I followed a short guide on making the rough layout of the galaxy.

My code works, but the "stars" (I'm bad with variable names, in this code "star" refers to the central star of a solar system) often clip into one another. Is there a way for me to ensure that no stars will intersect?

Code below is what I'm using to generate my galaxies.

    for(var i = 0; i < starCount; i++) {
    var distance : float = Random.Range(minDistance, maxDistance);
    distance = Mathf.Pow(distance, 2);

    // Choose an angle betweeen 0 and 2*PI
    var angle : float = Random.Range(0.0 , 1.0) * 2 * Mathf.PI;
    var armOffset : float = Random.Range(0.0,1.0) * armOffsetMax;

    armOffset = armOffset - armOffsetMax/2;
    armOffset = armOffset * (1/distance);

    var squaredArmOffset : float = Mathf.Pow(armOffset, 2);
    if(armOffset < 0) {
        squaredArmOffset = squaredArmOffset * -1;
    }
    armOffset = squaredArmOffset;

    var rotation : float = distance * rotationFactor;

    angle = Mathf.Round(angle/armSeparationDistance) * armSeparationDistance + armOffset + rotation;

    //Convert polar coordinates to 2D cartesian ones
    var starX : float = Mathf.Cos(angle) * distance;
    var starY : float = Mathf.Sin(angle) * distance;

    var randomOffsetX : float = Random.Range(0.0, 1.0) * randomOffsetXY;
    var randomOffsetY : float = Random.Range(0.0, 1.0) * randomOffsetXY;

    starX += randomOffsetX;
    starY += randomOffsetY;

    var newStar : Transform = Instantiate(star, Vector3(starX, starY), Quaternion.identity);
    newStar.transform.parent = center;
}

Answer 1

The only way to ensure that is to check previously generated stars coordinates, or make (some of) the variables semi-random, e.g. your angle and radius for next star would constantly grow (radius will reset for next angle of course) for a random value, thus ensuring that no intersection would occur.

Answer 2

You could use some kind of distribution algorithm, like grid-based distribution (overlay Grid, place one star randomly in each grid), cell-based Distribution (same as Grid, but not with squares, but with custom shaped cells) or use a given algorithm like poisson disk sampling.

------

Simple, fast and efficient, the grid-based approach is probably your way to go.

Simply overlay a grid, and generate one star in each grid-unit.

However, this is highly visible in large-scale projects. If your player can zoom out far enough, he will eventually see that the stars are distributed in a grid and you dont want him to see this, because it looks bad in a topdown-view (my opinion). If the player only sees a small portion of the galaxy or the galaxy as whole so the stars blur together, this should be no problem.

Bonus: You can prewrite your grid in an Image. If you take every pixel as a grid-unit, you can easily generate a whatever shaped galaxy simply by generating stars only in the white pixels. If generating several galaxys from the same Image, you get different outputs which share a common shape.

---

More complex with little gain, the cell-based approach has its uses. If the gridshape is to uniform for you, try grouping several grids into one cell, and generate only one star somewhere in this cell. This will break up the grid pattern and make it look a bit nicer.

However: This needs more space per star. Instead of utilizing every unit in the grid, you'll only use 1/2, 1/3 or less, depending on the size of your cells. Also creating images to generate from becomes more difficult, as you need more colors to seperate neighboring cells in your image. If going hardcore, you can do it with 4 Colors, even though more colors is better in this case to increase the usability of the image for humans.

Bonus: If you create small cells in the arms and large cells in the void between the arms of a galaxy, you can create small wanderers in the void, alone in the dark, housing tremendous treasures and deadly dangers. Just a plot hook.

Additional Info: Generating the cells from a regular grid is maybe the easiest, but not necessarily the best approach. But I believe this would lead to far here and would require a new question.

---

Best results, longest way. Algorithms like the Poisson Disk Sampling are advanced distribution algorithms which lead to far better results than the described ones, however require usually more time and/or memory. I will not go into detail about the exact implementation here as it is already described in detail in the link.

The Poisson Disk Sampling is not zhe only distribution algorithm, but the one I'm best familiar with. Googeling Disk Sampling should give hints about other algorithms.

---

TL; DR Follow the link and implement this.

Answer 3

Stars are typically separated by distances much greater than the size of a solar system. You could snap the coordinates of each star to some fraction of a light year, and ensure that your solar systems are no larger than that fraction. Keep a hash map of all star positions to ensure that no two stars share the same position.