How do I generate solar systems for a 2d universe map, but still look random

Question

I need to generate 64 systems separated into 16 sectors, each with 4 systems. Each system must have another system within 10 units in it's own sector, but no closer than 3. One system in a sector must have a non-sector system within 20 units, but no closer than 8. When I made a formula that satisfies these requirements, I end up with a very visible grouping of 16 sectors in a box formation with very little variety. Probably because I want it output into an array so I can track distances, etc.

I'd do a random generation, where it just places a system on a grid and then makes sure it doesn't conflict with a rule, and then find a way to group them, but it just seems beyond me right now. I wouldn't be sure how to check for inability to place another system... I'm probably looking at the problem from the wrong angle.

Any help?

Each dot is a system, the grey background is just a box to make it temporarily easier to see.

Answer 1

Okay, my two cents:

In your problem, I would try with a heavily modified Poisson-Disk-Sampling.
This method will first Poisson-Sample a Sector, and, after sampling enough Sectors, will sample a universe. This means the algorithm runs in two phases. This may be costintensive!

Some thoughts to it. Consider a Sector being a disk with radius sec, and a System a disk with radius sys.

---

---

How big have the radii to be too fullfill your criterias?

sys has to be at least 1.5. This way, if two disks are placed next to each other, the center-points of the two disks are 3.0 appart, your minimum distance. Additionally, sys may not be larger than 5.0, otherwise Systems would be more than 10.0 apart.
So when generating your disks, you can evenly give them a sys of 1.5 and allow gaps, or assign a randomvalue in the range of 1.5 to 5.0 to the discs. In the second case a newly placed disc should always touch at least one already existing disc to keep the Sector small.

---

sec is a bit more difficult to compute. What is the (approximate) minimal radius? Well, the minimal radius is achieved when all for systems in the sector are placed in a square with sys being 1.5 for each System. This means that the minimal sec is the diagonale between two Systems + a safety margin around the outermost Systems.
I happenend to draw a picture of this in paint:
I rounded a bit and came to the conclusion that the smallest possible sec is ≈6.0. This is because the light-blue-lines count full, the diagonale (dark red) only counts half (as it goes through the center).
The computation of the maximum sec proved to be very difficult, so I will only make assumptions here (though detailed ones in my opinion).

First: When we leave your second rule out, the maximum sec is 4 + 10 + 10 + 10 + 4 = 38 This is your solution when you place all four Systems in one line. THIS IS OBVIOUSLY NOT THE DESIRED SOLUTION, as you could not guarantee that if you placed a similar Sector next to it, any System would have a non-Sector-System in range. We can however make an assumption (which is just that, it does not have to be true). We can assume that the Systems are more or less evenly distributed. This means that if a System covers 50% of anothers Sectors Area, it will most likely have also a System from the other Sector in Range. Time to Math!

a*a + b*b = c*c
a = sec
b = sec + sec + (sec-4)
c = 20

sec^2 + (3*sec - 4)^2 = 20^2    ==>    sec ≈ 7.5

As you can see, to nearly guarantee all conditions your sec has to be in the range of 6.0 and 7.5. Pretty small Sectors, huh? If you weaken the conditions, your sectors will grow in size, but so will the average spacing between Non-Sector-Systems. Your call.

One note. This also limits the distance of a System from the Sector-Midpoint. Satisfying all conditions, a System is between 2.0 and 3.5 units away from the Midpoint. Use this in your calculations!

---

---

To recap:

sys is in the range of 2.0 and 3.5
sec is in the range of 6.0 and 7.5

I must admit, I actually never generated a star field with this method, only draw a lot of circles on a lot of paper and it looked nice and stuff. The actual result can (and probably will) be ... interesting. You will have to play alot with sys and sec to produce nice looking results, but I hope I could help you.

Answer 2

I think the main problem is that you are generating your sectors too closely together, so that according to your criteria, sectors too close will be discarded, thus leaving those sectors that are just far enough apart. This results in a tight packing, which would be a hexagonal grid if you use Euclidean distance, or a square grid if you use Manhattan. Is that what's happening here?

Instead, try generating your sectors really far apart, and pulling them together until they are close enough together. Note that if you overdo this, you'll end up with long chains or very sparse tree-like structures. If the results are too sparse to your liking, you can try adding a criterion for maximum universe size, so that you keep pulling the farther ones together.

Iterative algorithms are great for such problems; I recommend trying a force-directed algorithm.

Answer 3

I'm probably looking at the problem from the wrong angle.

Yes, you are. You are confusing "uniform" with "random". People intuitively think that random means "more or less equal in all space". That is wrong, because that is uniform. Truly random (or pseudorandom) tends to form clusters of points close together or very far away. Here is a picture illustrating what I mean.

Image taken from here.

By the way in that image you also have your answer. You may want to take a look at Sobol Sequences, and play with them around your requirements. Or, if you really want random distributions, you will need to accept some points very close or very far away from each other.