December 10, 2011

Detailed Spiral Galaxy Shapes Complete

I know I promised some pictures with stars in them in my last post, but they're not here yet--don't worry, they're coming though!  Since my last update I've been integrating the hex grid locations into my game.  This has ended up being a bit more complicated than expected due to the sheer number of them.

I encountered two performance bottlenecks:

(1) Generating the hex locations
(2) Determining which locations are in which sector of the galaxy.

The algorithm for (1) runs in O(n^3), which would be fine if my hex grid was only about 50x50 tiles (2,500 tile area).  Unfortunately, the grid can be as large as 300x300 (90,000 area) so the generation was taking anywhere up to about half a minute.  The solution was to auto-generate a large array of locations and save them and their distances from the center point of the map (0,0) to a text file.  The text file can then be read in during any galaxy generation, with the read stopping at a specified distance (so the whole file isn't read every time).  The process now takes ~0.5 seconds for the largest galaxies, though the text file is about 8 MB.  I could probably put it in a .zip file to decrease that size.

(2) was a bit more difficult until I discovered that Java AWT could create polygons from (x,y) coordinates and test if points were within them very quickly.  It takes about 3 seconds to test 75,000 points and determine which sector of the galaxy they are in.  My only complaint is that the test can only use integers, so there are some rounding errors that create a handful of points that should be in a sector but are not.  If the test used floating point numbers there'd be no problem, but I'd guess it wouldn't be so fast...

On top of (1) and (2) I've had to fix a number of small errors with the positioning, rotation, and spiral skewing of the various branches that come off the main arms of the galaxy.  The pictures below show locations in the main body of the galaxy (green) and those outside the galaxy (red).  The red locations will actually host some scattered stars, as they form the galactic halo.  The center red hole shouldn't be there--one of my sectors isn't showing up for some reason.  My apologies in advance to those who are red/green colorblind--I'll think of a better color combo if I post something like this again.

There are 2, 3, 4, and 6 arm spiral galaxies.  Shown above are a 3-arm and a 4-arm.  Remember, these pictures are just for testing and the solid colors are actually about 90,000 individual points--the shots are just very zoomed out.

No comments:

Post a Comment