When I generated a procedural galaxy, I wanted to make sure no two stars were too close to each other but that the grid was non-obvious. This algorithm lets you have trillions of stars if you want, and a basically infinitely sized galaxy, since it only generates stuff near the player but always generates the same stuff each time--way better on your memory use, especially since you can go ahead and make each system take up megs of RAM if you want. There's basically no setup time either...it's all free. I arranged the stars like this:
1) Define the absolute minimum distance apart you want stars to be and halve that number. If this is 2 light years, then make the galaxy up of 1ly x 1ly x 1ly sectors. (I use 3 dimensions, you can use 2.) Define a viewing area M; the player can see anything within the M x M x M sectors that they are centered in. Define an interference zone I; some calculations will be performed for stars within M+I of the player's location, because it impacts stars that are within distance I from each other. Maybe you'll call M 500ly and I 50ly.
2) Define a function that takes x,y,z in the range -(M+I)..(M+I) and returns the chance for a potential star in that sector, independent of other nearby stars. (Modify that function for distance from the galactic core, position along arms, etc.) For each sector near the player, run that function once, in a specific order--left to right, top to bottom, forward to back. If it returns true, then position the potential star randomly in that sector using a uniform distribution.
3) Define a function that takes a distance R from other stars within a maximum distance I, and returns the % chance that it will interfere with star generation. Take your potential star within M, and test it only against the upper-left-forward quadrant within distance I of that star, rolling that function for the distance R to each potential star in that area. If any of these interference rolls fail, then your potential star is not an actual star. Do not display it to the player. If none of them fail, then your potential star is promoted to an actual star.
These steps allow you to only calculate stars in a small range around the player, while letting them roam freely around the galaxy. Importantly, stars will appear to be distributed in a completely analogue fashion; your 1ly x 1ly x 1ly grid will be completely invisible. And of course, they can leave an area, come back, and see the exact same stuff that was there when they left. (Anything they change will need to be written to disk of course.) It's also very fast. You can calculate characteristics for each star after step 3.
If you want larger-scale features--dust clouds, regions with a lot of young stars, etc--run this algorithm on two passes. First generate the big features on a massive scale, then when you generate the stars, have them search for them in all directions instead of just one quadrant. And yeah, all this stuff is really useful for showing a map to the player--a small map for nearby stars, and a big one for large scale phenomena.
Remember to consider star populations! You should consider a probability function that takes star location as input, and returns what population it's in (I or II). Yes, you'll end up with regions of really awful crummy densely packed dead pop II stars. And yes that's kind of cool.
Supposedly, binary stars outnumber non-binaries. But I'd recommend calculating their 'type' after step 3, instead of doing any collapsing tricks. MUCH easier to change later, and this algorithm is totally awesome if I do say so myself and depends on it. And of course when you get closer to the system, close enough to scan it, just use the star's location as the random number seed to generate its contents.
Author
Topic: System Generation for a sci-fi rougelike (Read 775 times)