Using the Route Finder in chView2

Our first attempt at a route between Sol and 61 Cygni...

Our first attempt at a route between Sol and 61 Cygni…

The Route Finder Report has always been one of my favorite tools in chView2. Even with the distance links displayed, it can be very hard visually to ascertain a good route between two stars in a three dimensional display. Route Finder makes that considerably easier. The recent addition of a textual report describing the legs of the route with actual leg distances and total distance travelled has made it even more convenient and useful to me.

The purpose of Route Finder is to find the shortest path between two stars consisting of a number of legs, each of which begin and end at an existing astronomical object and are of some limited length. This is the model of Traveller’s Jump Drive, which is capable of 1, 2, 3, 4, 5, or 6 parsec jumps between stars(although in some versions jumps beginning or terminating in deep space may or may not be allowed), my own version of the Alcubierre Warp Drive in FTL mode and apparently C.J. Cherryh’s choice of FTL drive(I don’t recall the exact parameters of that drive, or the name of it, but I do remember that it was restricted to travel along specific routes). This involves a percolation model of interstellar travel where the allowed route between two points may be quite convoluted and considerably longer than the direct path seems to indicate. If the length of the longest allowed leg is less than some critical percolation value, there could even be objects on the map that are mutually unreachable.

One feature, in fact, that I’d like to see added to chView2, eventually, is a tool to determine that smallest critical leg size limit such that all objects on the map are reachable from all others. Because the maps are necessarily smaller than the total extent of the galaxy, it may be a necessary to limit the, “No Orphans,” requirement to some extent smaller than the entire map, as actual routes may exist between objects near the edge that pass through objects that aren’t represented on the map.

Links tab in Preferences window...

Links tab in Preferences window…

With all that in mind, let’s look at how one uses the Route Finder Report.

This requires some set up. First open the Links tab in the Preferences(View>Preferences…:Links tab). Make sure that Show Links and Show Numbers options are both checked, if not click any checkbox without a checkmark to select the option. Now select the numbered textbox at the very bottom middle of the window right above the “OK” button. This is the maximum allowable link between two stars. In my

own science fictional universe the maximum distance that the Warp Drive can travel between two stars is about nine light years, so I enter “9.0”. That sets the maximum leg length that the Route Finder uses. Now we select the two objects between which we wish to travel. Simply click on the first object to select it, then, while holding down the shift key on your keyboard, click on the other end of your desired route. The order of selection

Our first attempt at a route between Sol and 61 Cygni...

Our first attempt at a route between Sol and 61 Cygni…

doesn’t matter as the route can be considered symmetrical. For the example, I will select Sol and 61 Cygni A in my localSpace.chv.xml map. With the two termini of your route selected, simply go to the Report menu and select the Route Finder item. From that we get the Route Finder Report shown to the left.

What we see on the report is a route that leaves Sol, passes through BL Ceti, SO 0253+1652, GX Andromedae, Kruger 60, Gliese 725 and Ross 248, ending finally, about 50.9 light years later at 61 Cygni. How cool

The route on the map. Along with everything else...

The route on the map. Along with everything else…

is that? The trouble is, as anyone who’s ever wondered about the sanity of their GPS knows, this kind of algorithm doesn’t always find the absolute best route. So, just as a sanity check, let’s have a look at the route on the map(image to the right).

As you can see from the figure, even with the stars nicely picked out and even with the termini circled, it isn’t necessarily easy to see the route among all the clutter of a densely-packed starmap. ChView2 is capable of helping with that. First go the menu and select View>Show only selected. This

A better view of the route. A key principle of cartography is to show only the useful information.

A better view of the route. A key principle of cartography is to show only the useful information.

will show all of the objects that were selected by the Route Finder and remove extraneous objects from the view. This is only temporary, after you’re done examining the route you can select View>Show All to return the view to normal. In order to maximize the clarity of the view, I also rotated the view orientation a bit. This, much clearer view of the route is shown to the left.

On visual examination, that clump of linked stars at the upper right end of the map is a bad sign. The algorithm is usually pretty reliable, but sometimes it breaks, and this may be one of those times. Looking at the report again, we see that from GX Andromedae the route snakes through Kruger 60 all the way out to Gliese 725 and then way back to Ross 248 before finally ending up at 61 Cygni. In this case, the roughly seven lightyears of the direct route from GX Andromedae is obviously shorter than 4.9 lightyears to Kruger 60, then over six out to Gliese 725, then over eight lightyears back to Ross 248 and then another over five and a half lightyears out again to 61 Cygni. Yeah, that ain’t right. This is instructive, though, both to what a bad route looks like and how to fix it.

First let’s find the route from GX Andromedae to 61 Cygni. That’s a direct route and

The last bit of the route. Much better.

The last bit of the route. Much better.

about seven light years as shown to the right. Not bad at all…

Now we use Route Finder to calculate the route from Sol to GX Andromedae. Whoa! All over the place and with a distance of over a hundred light years. That’s ugly bad.

I’m not sure what’s going wrong here. If I ever figure it out, I’ll try fixing it. The best way to fix this will be to use the route to GX Andromedae that was calculated as part of the route from Sol to 61 Cygni and use a calculator to figure out the distance.

The stars of the best route hand-selected.

The stars of the best route hand-selected.

Sol <-> BL Ceti (8.73 LY), BL Ceti <-> SO 0253+1652 (8.03 LY), SO 0253+1652(8.79 LY) for a total of about 25.55 LY. Now our last check gave us a direct route from GX Andromedae to 61 Cygni of about 7.08 LY. Adding those together, we get a total distance of about 32.635 LY. The resulting route is shown in the image above and to the left. After a bit of jiggering with Open Office, I was able to create the following official-looking Route Finder table.Final-Route-fixed

I really need to get rid of circled-R symbol. For some reason, I thought it was cute, now it just seems kind of stupid…

Again, if I can ever figure out what’s gone wrong here, I’ll try to fix it, but I’m still mystified. I’d certainly welcome advice. It seems to happen less frequently with smaller maps and a lot with larger maps, and as shown in the example, it’ll work fine over some parts of the route and blow up even worse over others. The code is zipped into the jar file if anyone would like a look…

I hope this has been useful, and I would love some help with this,
The Astrographer

Advertisements
This entry was posted in Mapping, Science Fiction, World Building and tagged , , , , . Bookmark the permalink.

2 Responses to Using the Route Finder in chView2

  1. jjaquinta says:

    The critical distance for connectivity is, I think, something like 7.46 light years. I did write something to calculate that, but I never migrated it to code. Once you know the number, well, you know the number. I didn’t think anyone would want to run it more than once. 🙂
    If my memory serves me correct, the route finding algorithm kind of goes like this:
    Pass 1: find a route. For the given start, get all stars within range. Skip any that we’ve already been to. Rank them according to how close they are to the destination star. (If one is the destination star, link to it and we’re done.) Create a link to the top of the list, and recurse this step from there. If that reports it gets to the star, we’re done. If not, we try the second on the list. If none of them get us there, we report this is a dead end.
    Pass 2: optimize the list. For every trio of stars in the list, A-B-C, find all stars that are within range of A, and all the stars that are in range of C. Check each star that is in both of those lists. If A-new-C is shorter than A-B-C, use that instead.
    This is, indeed, not guaranteed to get the best route. But algorithms that are take exponential time. Usually this gets us pretty close. If you find regular problems, you might do a pass 3 that looks at quartets of stars and tries to replace them with triplets.

  2. Astrographer says:

    I would think the critical connectivity distance would vary with the point density. For instance a Hiparcos map might have a smaller critical distance than a Gliese 1 map, which would probably, in turn have a shorter critical distance than a map of nebulae or galaxies.

    Anyway, I don’t know how much utility that would have to most folks, but I’m playing with ideas on how to make a sort of interstellar GIS. If I went completely nuts, I’d have integration with GRASS or SAGA for planetary maps. This is all pretty ambitious stuff for the distant future.

    7.46 light years seems pretty short. I know the creators of 2300AD went with 7.7 light years and ended up with a lot of orphan stars. “You can’t get there from here.” They were using the, by now rather outmoded, Gliese 1 map, so the situation with Hiparcos and all those brown dwarfs might be a bit better. I also wonder if our definition of critical distance might be slightly different? I’m looking for the shortest distance such that every point on the map is reachable from every other point. A critical distance of 7.46 light years makes me think you were looking for the shortest distance so that every point had at least one other point within range. That can still lead to a lot of separate mutually unreachable clusters.

    The pathfinder algorithm you describe pretty well matches what I could figure out from the code. It seems to me that if I could figure out some way to detect those clumps of interconnected stars, I could use that property to refine the route. This is worth thinking about… Since, in my experience, the route usually gets wonky towards one or the other end of the route, it might be worth making a pass that looks at each object starting at the end of the route to see if it directly links to another object in the route then check the total distance. It might not be the absolutely shortest route, but it should be less obviously wrong… This would be in linear time I think, but only over objects in the tentative route. That would be about as effective as the manual method described here, but it would be automated and could be applied to a modified civilization growth routine I’d like to get working.

    Perfection is the enemy of good enough, but I think if I can get it off the ground, it might be worth looking in to as the example above shaved nearly a third off the total distance. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s