Galaxies

I'm working on the galaxy generation algorithms right now.  I did a bunch of work on the cluster, multi-cluster, and spiral algorithms back in summer '09, but they (1) were in just 2-D and (2) took waaaay too much memory and possibly too much time to generate.  Since I shifted the game to a 3-D star map, the memory required to generate a 3-D cluster or spiral galaxy using the old '09 algorithm would be more than most computers could handle.

Briefly, the old algorithm created a 2-D grid of numbers and assigned them integer values that acted as probability weightings.  Two number generators spit out a sequence of gaussian-distributed random values that were taken as the X and Y coordinates of a star system.  Once a star was placed on the map, the grid cells immediately adjacent to it had their weightings changed so that no other star could be placed next to it and so that stars a little further out had a lower chance of being placed--essentially, reducing the clustering of stars a bit and preventing overlaps.  Spiral galaxies just did this with a particular shape and then applied a 2-D rotation matrix, with the rotation amount scaled by the distance of the stars from the galactic center (giving a nice spiral shape).

You can probably see how this would take up a lot of memory if generating a galaxy with lots of stars--the grid could become huge if you wanted to place 10,000 stars on the map.  Additionally, the random number generators, by the end, were trying to put new stars into an already populated map and would have to start over every time they landed on or near an occupied area.

My solution:  For the cluster galaxies, I'm using a series of concentric spherical "shells" that expand outward from the galactic center, one light year (LY) of gamespace at a time.  The number of stars on the surface of each shell is dictated by a gaussian distribution, cut off at six standard deviations (sd).  The value of the distribution at each LY is computed, as is the total area under the curve (integrated out to 6 sd's) and these two numbers, combined with the total number of stars to be placed, produce the number of stars in a given shell.  The star locations are then calculated by computing random points on the surface of a unit sphere and then extending them out to the appropriate radius.

The only collision checking I need to do is with the current shell of stars that a given star is being placed within, which is rarely more than 100 and decreases over time.  This still might take up more CPU time than my previous algorithm, but it looks like it will take up MUCH less memory.  I'm a little worried that the shells might appear too regular, but I think the relatively small number of points per shell surface area and their random locations should prevent this.  I'll try to get some visualizations up and running soon and may finally have pictures to post!