November 11, 2011

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.

September 18, 2011

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.

September 12, 2011

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.

July 16, 2011

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

May 13, 2011

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!

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!

December 31, 2010

Hooray!

I've managed to get a colored square to appear on the screen, then make it change color by left-clicking the mouse.  Sounds pretty boring, doesn't it?

But this means that the following subsystems work:

3D rendering
Input manager
Game event handling
Basic GUI interface system

First the 3D engine and input manager (keyboard presses, mouse clicks, etc.) are loaded.  (Note:  I'm skipping many other subsystems that all come with the Java Monkey Engine [JME]--but these are the important ones).  Then the event manager is loaded and all basic game events are registered with it.  I currently have just one event for testing... :).  Next, the GUI state manager is loaded, which in turn creates the "Main Menu" state and the "Second Menu" states.  Main Menu contains a blue colored square on the screen while Second Menu contains a green square.  The Main Menu registers the action of left clicking the mouse with the input manager, then registers the GUI state manager as a listener for the click event.  The GUI state manager is told how to handle any messages coming into it and knows that the event should signal it to swap out the Main Menu for the Second Menu, thus changing the square from blue to green.

What this means is when the application is started, a black background appears with just a blue square in the lower left.  When the mouse is clicked, the "Main Menu" state sends a message to the input manager saying that a left-click occurred.  The input manager then sends a message to the game event manager, which the event manager then processes and sends to the GUI state manager.  The GUI state manager sees this message and swaps the Main Menu for the Second Menu, thus turning the blue square green.

Phew.  Sounds like a lot, but this loose coupling enables each system (input, events, GUI) to function independently and not worry about referencing and hooking into all the others.  It'll save a lot of time and effort when the game gets big and complex!

December 5, 2010

Kick-off

Hello everyone!  This blog has been created to keep any interested people updated on my progress in designing and coding the game Dark Matter.  This game is a turn-based strategy game set in space, similar in some ways to the Master of Orion, Galactic Civilizations, or Space Empires franchises.  I intend for the game's mechanics to differ somewhat from these mainstream games, though I'm not going to reveal exactly how until I've made much more progress coding.  Please also note that Dark Matter is a working title only and the real game's name will be different (since there is already an actual PC game named Dark Matter!).

I've been designing this game for several years now in an on-again off-again fashion and have come to the point where I need to get serious about coding it.  Designing on paper can only get me so far and the whole exercise starts to feel circular after the fourth revision of my tech tree...

I have a programming background, but its unfortunately in scientific/numerical methods and analysis--Matlab and C.  This means that I've had to teach myself object-oriented programming over the past few years.  I think I'm at a point where I can start coding Dark Matter now.  I'm going to write the game in Java using the Eclipse IDE and will probably use Java Monkey Engine 3 as an underlying engine for the game, with additional coding and game design help from Mike McShaffry's "Game Coding Complete, 3rd Edition."