February 13, 2011

More Galaxy/Universe Building

I realized that my cluster galaxy algorithm only lets me make roughly spherical galaxies--where's the fun in that?  I'm going to tweak it a bit to let me generate elliptical galaxies as well, following math here for a 2D ellipse, then creating a random (appropriately scaled) projection along the z-axis to add a 3rd dimension.  I'll probably have to collision check all the stars, so it might take a bit longer, but it's worth a shot.

Other than that, I've been hacking away at the universe creation routine.  This is the thing that makes the galaxy--and actually, it now makes multiple galaxies!  I figured that while a 10,000 star galaxy is unwieldy in 3D (issues with seeing into it, navigating around, etc.), 10 galaxies with 1,000 stars each could be quite manageable if they're separated enough.  I just need to figure out a good way to randomly arrange them--will work on that tomorrow if I have time after work.

Biggest annoyance today: the Java Vector3f class doesn't seem to have a rotate() method or anything like that.  Have to do it all "by hand."

February 4, 2011

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!