Arcane Game Lore

Gaming is not in the blood, it's in the dice!

Creating Star Maps – part 3

In this installment we start adding bells and whistles to the star map generation process I described in my earlier posts (part 1, part 2).  Specifically, drawing connections between star systems and labeling them with the distances.

It’s been a while since I posted on this particular topic as I simply haven’t had a chance to work on it.  Between work, family, school, and finishing up issue 14 of the Frontier Explorer, I have been completely swamped.  There is currently a lull and I’m taking advantage of it to work on some of my other projects, including this one.  So let’s dive in.

Goals

My goal for this part of the project (and for the project in general) is not to have a completely finished and perfect map at the end.  Rather to have something close to finished but editable that I could tweak into final form.  Get the heavy lifting out of the way and just have to tweak the details.  Up to this point, the final result did not need tweaking after the program generated it.  This one definitely does.

Part of the reason for that is that people have different ideas on how to connect star systems.  Should there only be a few connections?  Do you need connections at all?  Should there only be short ones? Do you allow the occasional long ones?  Do you have connections between all stars?  Only certain spectral types?  This particular aspect really depends on the setting you are going to use the map generator for.

Ideally it would be nice to have settings that the user could adjust to impact some of these things.  For now, I’ll be going with some that I choose in order to get the basics hammered out.  Improvements can come later.

The other reason is that there are just so may moving parts as you start adding in more details and labels that coding for every possible outcome is often sub optimal, especially if you are only going to use it a few times.  Looking at the results you can find and fix errors much faster than it would take to develop code to find all the edge cases.  As long as the result is easily editable (and I think SVG files definitely are) you just need to get close.

My Choice of Parameters

So what parameters did I select?  There were actually only two.

First.  I was only going to draw connections between systems that had stars with F, G, and K spectral types.  These are the stars most likely to have actual earth-like habitable planets and I definitely have a “realism” bent in most of what I do.  Plus this also limited the number of connections on the map as there are typically not an overwhelming number of these system (notice I said typically, see examples below).

Second. I was only going to draw connections there were less than 15 light years in length.  I like the idea that long jumps are hard and if you want to go long distances, you make a bunch of small hops.  It provides more strategic value to some systems as they might be the only way to get from one side of the map to the other or may control access to a cluster of stars, etc.  Plus it helps somewhat on keeping the map from being too cluttered with connections.  I actually started with a distance of 10 but that was not generating enough connections for my liking.  And it’s easier to remove unwanted connections than to add in needed ones.

Obviously all of this can be changed if desired and you can always add any additional connections desired (or remove ones you don’t want) after the initial map is generated to suit the game or star sector you want to have.

Algorithm

While you could do this in a single pass through the list of star systems, I chose to do it in two passes.

The single pass method would be to start with one star system, see if it has the right spectral type star (i.e. on of the ones I’ve designated as habitable) and if it does, compare it to every other star system to see if they are 1) within the desired distance and 2) have a habitable star.  If so draw the connection.

The option I chose was to first make a pass through all the systems and check for habitability.  If a system had a habitable star, I’d save it into a new list.  Then working with just the list of habitable systems I’d loop over all of them looking for systems that were within the correct distance and then draw the connections.

Not that it really matters because the number of systems we’re working with on these maps is fairly small, but it is overall more efficient to do it the second way.  (Warning: computer sciencey speak here, feel free to skip the rest of this paragraph if you’re not interested in computational complexity discussions) If we have N total systems and M habitable systems, the first method requires O(N2) habitability checks and O(N*M) distance checks.  The second method only requires O(N) habitability checks and O(M2) distance checks.  Since M << N, the second option is much faster.  In practice, it doesn’t really make a difference, the program returned as soon as I hit enter to run it.  Doing it the “slow” way may have taken a second instead of a fraction of a second.  This way was just easier to think about.

Once the decision was made to draw the connection, a line was drawn from the center of one system to the center of the other, the mid point of the line was computed, and the distance (in integer light years) was drawn at the midpoint, offset somewhat based on the slope of the line so that it wasn’t falling directly on the line itself.

That offset was what was giving me the most fits, and I’m still not completely happy with it.  There are still a few cases where the number is drawn too far from the line for my tastes.  I have some ideas of how to fix it but that can wait as the number of tweaks are usually small.

Some Examples

Before we go any farther, lets see some of the raw outputs from this algorithm.  (All of these images are included at half resolution since the site won’t accept the full sized files (plus they down load faster).  They are also included as PNG files although the program creates SVG files since mobile devices typically don’t have SVG renderers.) Comments on each map follow the images.

testMap-half

This first map shows a sector with a typical number of stars and connections. As you can see, there are a few stars relatively close together in the middle of the map that generated a bunch of nearby connections that are all overlapping and hard to read.  This is not surprising based on the algorithm used.  We’ll come back to this map later.

Star map with two clusters and only one star joining them

The next one shows two groups of systems with a single star connecting the two groups.  (I really like this one and may just use it for a game or story with a few edits.)  Just glancing at the map, you might wonder why the two blue (F) stars just above the single connecting star aren’t connected.  Looking closely, you see the star on the right is 12 ly below the plane of the map and the one on the left is 11 ly above it.  So the real distance between those two stars is 24 ly, well beyond the range limit for connections.  The system that is the single connection would have a huge strategic value as whoever controls it controls the flow of people, goods, and information between the two clusters.

Map with two clusters of stars with no connections between them

This one shows two small clusters of stars that are not connected at all.  The closest connection is the right most star of the left group and the top star of the right group at a distance of 16 ly.  In both of these last cases you, as the map maker, might want to make a long connection or a pair of shorter ones through one of the small M star systems in between.  Or maybe you want to keep them isolated.  Either way, this gives you some setting details that you can use to develop the story behind these systems.

Map with way too many connections to be readable

Here’s a final map that is just way too cluttered.  It’s perfectly usable but you’d probably want to do a lot of editing and connection removal and develop a story to go with why you can’t move willy-nilly between all the systems (or maybe why you can if you leave them all in).  This is one of those maps that had an unusually high number of habitable systems.  (Note that this image file is smaller than the others due to file size restrictions on the web site :( ).

Editing

As I said at the beginning, the generated maps were never intended to be the final versions and it was my intention that I would be editing them once they were done.  This is why they are generated as SVG files.  In that format, each star, each line, each number is just an object that I can move, delete, change, etc. as I wish.  Just fire up your favorite vector graphics editor (I use Inkscape) and get to work.

There are basically three main edits you might make:

  1. Deleting connections – You’ll almost always want to do this one as there tend to be several routes that are close or overlapping that you might want to delete or maybe you just decide to get rid of some of the longer connections.  In this case you just select the connection and delete it.  Since the connection and associated distance are grouped in the SVG file they move and delete together.
  2. Adding connections – In come cases you might want to add some longer connections or connections through other stars systems not used by the algorithm.  This to is fairly easy as you just draw the line, compute the distance, and add the text to the map.  You’ll have to play with the z-ordering but typically moving it all the way to the bottom and then up 2 should put you above the black background and the grid but behind the stars, which are drawn on top of all the connections.  (at some point I’ll go in and make the file have layers: at least one for the background and grid, one for the connections, and one for the stars)
  3. Moving text – As I said before, some of the distance labels fall a little too far from the lines for my liking and there are often times where the connection lines overlap the height coordinate for the star.  In both of these cases you’ll want to move the text slightly to make it look better (or be visible at all).  In these cases you just grab the text object (ungrouping it if necessary in your program, you don’t have to in Inkscape) and move it to its desired location.

Of course you can make any other edits you want at this point but that typically covers the major things you might want to do.  Here’s that first map again after I edited it to my liking.  I removed some of the longer connections in the middle of the map and moved some of the text around but didn’t add in any new connections on the map.

The original map with some of the connections removed and the text moved to improve readability

What’s Next?

Next up I’ll probably tackle a text output so you have the data on the systems the map represents.  Right now, it’s just a pretty picture but there is information there that you could use that the program can just create for you instead of you having to interpret it from the image.

Also, for those that are interested, here is the Python code for the current version of the program. (StarMapGen.zip – 7kB).  Just run the makeMap.py file to create a map.  It currently spews a bit of debugging information to the console and writes a sampleMap.svg file as output.  One of these days I’ll make a gitHub repository for it.  The code is in no way pretty or even necessarily organized optimally.  (I’m running up my technical debt to get it working.)

What do you think?  Do you like the distance connections or do they cause the map to be too cluttered?  What algorithms would you like to see implemented for making connections?  What other suggestions do you have?  Let me know in the comments below.


Categorised as: Game Aids | Game Design | Resources | World Building


6 Comments

  1. Tobias says:

    I definitely like what you have done so far. I write Python in my day job, would you be interested in patches?

  2. dagorym says:

    I used to write some Python for my day job as well when I worked at NASA. More C++ though. Now I’m a librarian.

    I’m open to patches if you want to contribute. I should really get it up on gitHub to make that easier.

  3. Tod says:

    GitHub would be great. One thing I’d like to be able to do would be to run the renderer with an existing list of stars (say for instance I wanted to generate a map of the region around the Sun, not just any arbitrary region). That would be handy. :)

    • dagorym says:

      That actually should be fairly easy as the rendering engine just takes a list of star system objects. Right now I just generate those randomly. It should be easy enough to write code that can read in actual stellar data, create the structure needed and pass that in to the map rendering engine.

  4. Sean says:

    Did you ever put the star map generator up on Github?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>