XML and Save Games

I'm about ready to continue forward in developing the various game classes (planets, stars, etc.), but there is one last system that I definitely need to build before moving forward much--saving and loading the game state and game parameters.

I'm planning to hold as much data as possible in external files, allowing users to edit and modify as they wish.  I see three different types of data files:

1) Game parameters, such as galaxy sizes, weapons damage, or the max. number of planets allowed per system.

2) Save game data.

3) Application settings information, such as keyboard mappings, video settings, etc.

I'm currently using Java Enums for some of (1), have not even touched (2), and have a Settings object that I pass to the relevant systems for (3).  I plan to convert (1) and (2) entirely to XML, and probably create an XML file that contains (3) as well.

For (1) and (3) I can probably use either Java's native XML capabilities (likely going the DOM route), JAXB, or XPath for creating new, user-generated classes.  The latter two options would be exercised if the user (for example) added new technologies to the game by editing the tech tree XML file.  

For (2), I plan to use XStream, which looks like a very quick and powerful way to grab object data and store it in XML, and then also unpack XML data back into Java objects.  I test ran it the other night by saving just one StarSystem object--and it followed all the references in the Controller, Views, and Model for that system, creating a 1.2MB text file...  Upon review, it had followed references to Java Monkey Engine classes and ended up saving a good chunk of the graphics engine's underlying object data, none of which was necessary.  Oops.  I can write some conversion classes that will better determine what data should be saved.

So all this is what I'll be doing over the next couple weeks--in addition to just refreshing my memory on XML (worked with it for a month or two about 5 years ago!) and celebrating the new year!  I also got the new Deus Ex game for Christmas, so I might be a little slower than I'd like in getting to all this... :)

Minor update--Elliptical Galaxies and Collision Detection

1) Straightened out a few kinks in the collision detection algorithm.
2) Converted the bounding boxes for detecting collisions into bounding polygons, so custom galaxies of any shape can be aligned in a variety of ways and not "squared off" as the old bounding rectangle method I used would have it.
3) Implemented elliptical galaxies.
4) Implemented random galaxy rotations--most noticeable with the ellipticals.  Adds some variety to the layout.

In the picture below, the bright orange pixels are the bounding polygons for each galaxy--I turned them on in this run to observe.  There are two large elliptical galaxies, two large spirals, one medium spiral, one small spiral, and about four tiny ellipticals.  Note that not all ellipticals will look like footballs--I set their parameters to make them dramatically non-circular for testing reasons.

I'll maybe have one more post in the next day or two, then nothing until after Christmas.  Enjoy!

Multiple Galaxies

I can now place multiple galaxies in random, non-intersecting patterns.  Each galaxy has its own hex grid that references world coordinates--meaning, I can place the galaxies anywhere and their grids take on appropriate values, but I don't have to place any grid locations between the galaxies.  Saves quite a bit of space.  Later, I'm going to add the ability to create hex grid locations in empty space to allow for the possibility of new destinations being created out there.

Note that the 2-arm spirals below are actually barred spiral galaxies.

Star Locations Picked

I've finished the algorithm for randomly generating star locations within a galaxy.  A few pictures, again using stand-in graphics (the blue dots):

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.

Hex Grid Working

I've been re-tooling the galaxy generation algorithm to account for the existence of the hexgrid.  While doing that I've also been testing the amount of memory that a hex grid will consume and finally playing around with different lighting options, etc. in JME3.

I can now generate circular arrays of hexagons over 400 tiles wide and maintain a decent framerate.  The picture below is a sample grid that's about 100 tiles wide.

To keep performance acceptable, I've made the tiles all one object.  Additionally, as you move away from the tiles they'll disappear.  Note that they become a blue "haze" above at some distance away--that haze will be replaced by a gradual fade out as they recede into the distance.

I've estimated that a low density, 3,000 star spiral galaxy will require a circular gird approximately 400 tiles across, so I appear to be ok.  I'll try to get some more pictures together (maybe with a star or two) this weekend!

Update: Space geography

Almost two months since my last update, but I've been busy.  Still lots of work ahead though!

The star system layout code has been re-worked and made much, much more OO-like.  I had to go back and debug it and ended up not remembering how it worked, so breaking up what was a 2000+ line system design class into several smaller classes with self-contained methods and variables helped a lot.

I've also taken a crack at making spiral arms more interesting by adding arm branches that diverge from the main trunk, but so far the results are not very spectacular.  However, this effort lead me to realize a few things:

1) There is no reason to have the star layout in 3D, even relatively flat 3D.  Yes, it adds realism, but it also makes judging distances and moving ships much more complex.  I've decided to flatten out all my galaxies into a 2D plane.

2) By flattening into 2D, I can now much more easily implement some more interesting "space geography" (astrography?) stuff that I've wanted to do since starting.  Stars voids and clusters are just the beginning, and I'm keeping the full list secret for now :).

3) 2D also allows me to better organize the game space.  Rather than picking points out of the ether and working with undefined spaces between stars or other objects, I can now implement a grid system and bring some order to space.  I'm a little concerned about the amount of memory this will take up--some back-of-the-envelope math tells me that a 10,000 star game with 4 galaxies could require as much as 1,000,000 grid tiles, which would take from 30 - 50MB of memory for just the tiles.  Eek.  But a 10,000 star 1 galaxy game would probably need half that or less (as there would be no empty spaces between galaxies), so I have some options to reduce the overall burden on memory.

Ships would not be forced to travel along the grid (they can still move in straight lines any way they need to) but they would be forced to choose a grid tile as a destination--travel paths must always end at the center of a grid tile, which is where anything in that tile resides.

The main benefit of the grid is the ability to organize space and to pick out a region of space relative to other regions.

Star System Layout Complete

I now know why most space-based games don't try to include multi-star systems in anything approaching a realistic manner.  Whew.  The following star system types are now available:

Single
Binary center:  2 stars tightly orbit each other at system center with mutually shared planets.
Binary orbit:  2 stars orbiting each other further out, with planets around each individual star (or no planets, if they're in the "dead zone" of about 3 - 30AU which stops planet formation).
Trinary center:  3 stars tightly orbit each other at the system center, mutually shared planets.
Trinary, binary center, single orbiter:  2 stars together at the center of the system, with a single star orbiting farther out.  Planets potentially around each grouping.
Trinary all orbit:  3 stars, one at the system center, 2 more in their own, independent orbits.  Possibility of planets around each.
Quad center:  4 stars at the system center, mutually shared planets.
Quad binary center, binary orbit:  2 stars at system center, 2 stars orbiting each other further out.  Planets possible around each grouping.
Quad binary center, single orbit, single orbit:  2 stars at system center, then 2 independently orbiting stars further out.  Planets possible around each grouping.

Based on the system type, the masses of the stars present, their radii, and the orbital distances of the stars, I calculate approximate regions of stable planet orbits around each star/group.  If I wanted to do this accurately I'd use some sort of dynamical simulation, but that would be a bit crazy given that this is a computer game.  I have enough detail as is, so I fudged the calculations a bit.  For systems with just "center" stars, it sets the minimum stable distance at the largest center star's radius plus 0.05AU and the largest stable distance at 100AU (arbitrary, but approx. the maximum distance of Eris).

For systems with stars in separate orbits, it gets a bit more complicated and calculates the stable orbit zone around each star/group as a mass-weighted fraction of the distance from the star's surface to the zero-gravity point between each pair of stars.  I won't go into the details here, but I've been getting decent numbers out of this for multi-star systems.

In the process of setting this up, I noticed some errors in my star building routine that were creating nonsense values for the parameters of certain star types.  I had to go back to the source I took some of my equations from and discovered that his paper was full of typos!  That's the last time I trust something published in the Journal of Serbian Astronomy... probably should have seen that coming though :).  I've since fixed the star creation routine and have confirmed that all star parameters are within expected boundaries.

Now that I have my stable orbit regions, it's time to build the planets!  Gas giants are apparently key here, so they're going to be put in first and their characteristics will determine where/how many rocky/icy planets are created as well.

State Machine Up and Running

The game now launches in the Menu state and loads the corresponding bundle of Nifty GUI designs that take you through the various UI menus to set up a new game, load a game, set options, etc.  Upon loading/starting a game, the state machine:

1) initiates a shutDown() method in the current state (Menu) which de-registers all of its listeners from the event manager system
2) confirms shutDown() is complete
3) swaps to the Strategy state (the main game-playing state where you view the stars and everything else) and passes this state the game settings
4) runs a startUp() method for the Strategy state, which registers all of its listeners to the event manager if the state already exists or creates a new Strategy state (generates a new galaxy, stars, etc.).
5) sends an event that tells the elements of the Strategy state (stars, etc.) to enter their default views.
6) and then goes from there.

There's also a Combat state that remains to be implemented and which is only accessible via the Strategy state.

I've made a small modification to my event manager as well.  The normal system receives an event and broadcasts it to all the listeners registered for that event.  However, there are certain events for which there may be many listeners, only a few of which are affected.  For example, adding a new planet to a star system is a possible event in the game and is an action that all star systems listen for.  In a 3000 star game, the event manager would have dispatch this event to all 3000 of them so they can figure out if they're the one adding the star or not.

One way around this is to directly access the star that is getting the new planet, circumventing the event manager entirely.  But I'm trying to maintain very loose coupling between systems and this violates that rule and opens up the possibility for more problems down the road as the code gets more complex.

As an alternative, I've added in the ability to specify an optional target for an event message.  Every game object (physical--planets, stars, etc--and social--empires, religions, etc.) has a long int identifier associated with it, so an event may specify the identifier or a particular object.  The event manager will test for an identifier before doing anything and, if it finds one, will send the event directly to the correct target.  The tradeoff is maintaining an extra hashmap in the event manager class that links the identifier to an object, but the boost in performance will be worth it for these "many listener" events.  Adding stars to a new 3000 star galaxy went from taking 6 seconds to less than 1 second after this change.

Next up, I'm designing planets and other habitable objects.

Spiral Galaxies Done (for now)!

Spirals are done... enough.  Still have some tweaks that I want to implement, but I'll wait on those.  Here's a description of how I designed spiral galaxies in 3D:

I realized early on that I would have to generate the core and arms separately, as there's no single geometric shape that easily describes an entire spiral galaxy.  The core would be a disk that bulged a bit toward the center, while the arms could be described by half-ellipsoids--think of them as looking like footballs that are pulled to be longer and then cut in half.  One of those halves can roughly represent the volume of a galactic arm.

When you cut an ellipsoid in half, you get a flat "butt" to it.  In order to join this flat region to the side of the disk-shaped core, I decided to cut away at the sides of the core to transform it from a disk with rounded edges to a polygon-disk.  In other words, a spiral galaxy with 4 arms would have a square core (though it would still have height in the z-direction) and the flat sides of the square would be the locations where the flat butt of the arm ellipsoids would join.

But how do you cut away at the central disk to create the flat joins?  Answer:  Don't cut away, just build it that way in the first place.  Rather than fill in a disk using a disk point-picking method, fill in a series of triangles and rotate them to the appropriate angle.  Think of it this way--a hexagon can be broken into 6 triangles, a square into 4 triangles, and a larger triangle can be broken into 3 smaller triangles.  I used a triangle point picking method to create each "triangle sector" of the core.  In the end, I was left with the desired shape of either a big triangle (3 arms), a square (2 or 4 arms), or a hexagon (6 arms).

(Edit:  Forgot to mention that I also had to use a triangle interior detection algorithm when doing the triangle point picking, since the point picking actually puts the points in a quadrilateral and you have to determine which sector they are in.)

After that I just used the disk point picking method again to create each arm, multiplying the (x, y) coordinates for each point by the (a,b) dimensions of the arm ellipsoid.  Then I had to rotate the arm to align with the proper flat join on the core and translate it outward so it lined up perfectly.

I have some code in place to allow a single arm to have branches that split off and run for some length, but it was getting somewhat complicated to implement.  I might come back to it at some point, but for now I'm happy with just having singular, non-branching arms.

I recorded a couple videos of the new spirals.  My recording software can only capture at about 15 frames/second, so there's a bit of chop.

Videos:

3 Arm Spiral, 3000 Stars

4 Arm Spiral, 3000 Stars

6 Arm Spiral, 3000 Stars

Stars almost ready

Wow, the time just flies by.  I re-worked the elliptical galaxy algorithm to give them a better and more defined shape and have nearly finished implementing the Star class.  Next steps:

1) Create a visible elliptical galaxy full of stars.
2) Confirm that all star model values are within expected tolerances (i.e. my equations all give good numbers).
3) Create a visible spiral galaxy full of stars.
4) Create a bar spiral galaxy full of stars.
5) Create a uniform/irregular galaxy full of stars.
6) Enable multiple galaxies, with appropriate collision checking (will have to break out the math for this one...).
7) Implement some sort of depth culling so that stars farther away are not rendered but instead fall into a sort of galactic background.
8) Implement nebulae
9) Implement voids/clusters within galaxies
10) Develop planet/habitable object classes

I think that will keep me busy for a while!

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."

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!