3
\$\begingroup\$

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?

system map for space game

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Random and strict placement requirements don't go together. Either relax your requirements or relax the requirement for randomness. I think this is a bit too broad of a question, as this is more of a "doesn't look good enough" type question. These types of questions are subjective and don't have correct answers. \$\endgroup\$ – MichaelHouse Aug 31 '14 at 14:59
  • \$\begingroup\$ Possible related to this question + my answer. The question tries to ensure that no stars (aka systems) are placed in each other, but the answers should be convertible to your question. \$\endgroup\$ – J_F_B_M Aug 31 '14 at 15:38
  • \$\begingroup\$ Some screenshots would really help to visualize the problem. \$\endgroup\$ – Philipp Aug 31 '14 at 18:58
  • \$\begingroup\$ @Larethian Yeah, that might work... I'll have to do a bit of thinking on it. I wasn't thinking about doing it like that, but it 's worth a shot. \$\endgroup\$ – Nogusielkt Sep 1 '14 at 19:08
  • \$\begingroup\$ @byte56 Taking a second look at your comment, I realize that the formula I originally used is even more strict than my requirements and that's probably why it looks so bad. It was basically requiring 2 to be within 3-10 \$\endgroup\$ – Nogusielkt Sep 3 '14 at 0:41
3
\$\begingroup\$

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:
Smallest possible Sector. Who reads these tooltips anyway? 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. Pictures title on my computer is: 38 is too big. Otherwise I would have no idea what this picture would mean 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

Surprise, another senseless description. I needed over 5 minutes for the green circle. And the center is actually a bit right of the red dot.

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hmmm... that might work. If I generate a sector and then pull it close enough to another sector to meet my requirements, I think it'll look a lot better. \$\endgroup\$ – Nogusielkt Sep 1 '14 at 19:01
1
\$\begingroup\$

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.

enter image description here 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.

\$\endgroup\$
  • \$\begingroup\$ The psuedorandom sequence looks fine, I'd just like to filter out the extremes on both ends (dots too close and too far away)... I'd be fine with whatever is left. Which... I might be able to do it like that. \$\endgroup\$ – Nogusielkt Sep 1 '14 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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