Algorithm for calculating jump distances

[forthekill]

Does anyone already have a good algorithm for calculating optimum jump routes or jump distances between two worlds in a sector?

Before I tackle this problem I'd like to know if anyone already has, or at least has tried. No use duplicating work, especially since it is no small task.

I took a look at nroute.c, but trying to figure out what that code is doing is close to futile.

 

[robject]

Yes, I've got that. So does Joshua Bell. I wonder if I can dig it up...

 

[forthekill]

Awesome. Thanks.

 

[inexorabletash]

I have an implementation of the A* pathfinding algorithm for Traveller's hex coordinate space here:

http://travellermap.com/tmp/pathfind.htm

That's just a demo page, not a utility; you'll have to dig in to get at the implementation. The page generates pseudorandom sectors (using a "seed" at top left) then computes a jump route between two hexes (defaulting to 0101 to 3240) for a given jump rating (default 1).

Note that all worlds are rated equal. It would be easy to modify the algorithm to e.g. filter out worlds that aren't good refueling candidates (no spaceport/no water). Adding a fitness function for worlds (e.g. trade rating, etc) and adjusting the route accordingly is possible, but more difficult; with the A* algorithm you end up weighing the cost of a trip, not the destination.

 

[robject]

No no, I think he just wants this sort of function:

my $parsecs = distance from $thisWorld to $thatWorld;

Here it is in pseudo-Perl-C-JavaScript-whatever:

int distance( $from, $to )
{
   my $a1 = $from.row + int( $from.col / 2 );
   my $a2 = $to.row + int( $to.col / 2 );

   my $d1 = abs( $a1 - $a2 );
   my $d2 = abs( $col1 - $col2 );
   my $d3 = abs( ($a1 - $col1) - ( $a2 - $col2 ) );

   # return the largest value from the three options
   return $d1 if $d1 > $d2 > $d3; 
   return $d2 if $d2 > $d1 > $d3;
   return $d3; # last man standing
}

 

[forthekill]

Well initially I thought I only need what robject specified, but looking at what I am trying to do, I may need what Joshua presented as well.

I am trying to code the Trade Route generation rules from GURPS Far Trader in Javascript, and I need to calculate the Distance Modifier.

It calls for the distance between two worlds, but the text indicates that distance should be calculated by jump routes between the worlds, which should "generally be jump-4 along X-boat routes and jump-2 elsewhere" which is another way of saying "there is no damn way you can program this, and if you can you will hate yourself at the end".

At the very least, I could use Joshua's code to get the jump-2 distance and be done with it for now, and perhaps tackle tracking X-boat routes and using them in the calculation (probably never).

At the end of the day I would like something to generate the routes automatically, and then adjust them as I see fit post gen, instead of coming up with them manually for a whole damn sector.

Regardless, a simple calculator to give me pure distance would be helpful as well.

 

[robject]

Use Joshua's A* algorithm. Modify, rinse, and repeat.

Between every world pair, calculate all possible routes, retaining the shortest route found so far.

If the world at the current leg of the route under consideration is on the xboat route, include worlds 4 parsecs away that are also on the xboat route. Always include all worlds 2 parsecs away.

Do it brute force, but later you can prudently add in some paring logic as it occurs to you.

 

[forthekill]

Here is the Javascript for robject's pseudocode:

function distance(world1, world2){
	var a1 = world1.row + Math.floor(world1.col / 2, 10);
	var a2 = world2.row + Math.floor(world2.col / 2, 10);
	
	var d1 = Math.abs(a1 - a2);
	var d2 = Math.abs(world1.col - world2.col);
	var d3 = Math.abs((a1 - world1.col) - (a2 - world2.col));
	
	if ((d1 > d2) && (d1 > d3)){ return d1; }
	if ((d2 > d1) && (d2 > d3)){ return d2; }
	return d3;
}

 

[inexorabletash]

The hex distance function in JS was buried in my code too.

 

[forthekill]

Yeah, I found that this afternoon.

I also started playing with the jump path code and I have to say it's pretty sweet. I pulled out the part that does the path calc and and modified it to make it more modular. You still pass it the startHex, endHex, and jumpLength, as you had it, but I added passing in the map itself.

It of course then returns a path, if any, and I can then just calculate the path length by counting the number of hexes in the path object.

I'm also in the process of writing a function to populate the map from existing data, rather than as it is randomly generated, which will probably just get incorporated into the sec file reading code.

 

[inexorabletash]

For SEC parsing, dig into the code in travellermap.com/sector.htm

 

[robject]

I detect the beginnings of a JavaScript library.

 

[BillDowns]

For SEC parsing, dig into the code in travellermap.com/sector.htm

I wold suggest developing an XML schema that also wraps the .sec format. That way you can provide either the .sec record or just the individual elements from a new app.

 

[forthekill]

Here is the sector reading/generation part my experiment so far:

http://frontiers.forthekill.com/travGen/genSec.htm

Much of the JS code is from Joshua, but I split out the functions into a more modular setup, and am working to make sure they can easily talk to each other (like matching up variable names in the sector generation and sector parsing code) and be easily called from other JS.

It's just a work in progress so far, and I still have a lot of commenting, clean-up, and stuff to implement.

I've also got the base trade route generation code for a world and world pair done, but I still have to do:

- Loop through a sector and record all the pairings and relevant trade info.
- Output the trade route info to a common internal and output format (MSEC?)

I still will need to do:

- Border generator
- Map renderer
- Route renderer (generic to handle X-boat, trade, whatever routes)

to screen and to PDF.

By the way Joshua, thank you for your pointers and your very easy to follow code! And that sector.htm page produces really awesome results. I had never seen that output before on your site.

 

[inexorabletash]

You're welcome. Most of the code is intended to be examples, rather than finished tools.

I have not tackled client-side rendering yet, so you're on your own for that! I would suggest implementing an abstraction layer so the same code can output to SVG, Canvas, or PDF. My server-side code uses PDFSharp to render to PDF or GDI+.

I'm happy to share any of my server code, but it is not terribly interesting. The coordinate space transforms are probably the most challenging part.

 

[forthekill]

So I'm at the point where I have the trade gen finished, but man does it take forever for a decently populated sector.

I am no good at profiling but what little I can see is that it is the route calculation (which I borrowed from Joshua) that is taking all the time, but I don't have much idea on how to speed it up significantly, if that's even possible.

Otherwise it seems to work great. I still need to take the output from the trade gen and do something meaningful with it.

My next project is to create some Javascript to draw the blank sector, worlds, names/text, and routes to the screen, hopefully in a layered fashion. Time to learn Canvas! Thankfully I work with someone who has become somewhat of a Canvas expert so I have someone to go to with any serious questions.

Check it out here: http://frontiers.forthekill.com/travGen/genSec.htm

If you load a sector be prepared to wait more than a few minutes for the gen to finish fully. It's more quickly demonstrated using the Generate button with a small Density.

 

[forthekill]

Basic hex map in Javascript using Canvas.

http://frontiers.forthekill.com/travGen/hexmap.htm

 

[forthekill]

Basic hex map in Javascript using Canvas.

http://frontiers.forthekill.com/travGen/hexmap.htm

It now does worlds and names.

I'm working on getting the hex numbers, UWP, and the worlds colored by type, like Universe does.

 

[robject]

Nice work so far!

 

[inexorabletash]

Yep, great work! Keep going - only a few hundred more features to go! Ping me if you need any advice. The two things I'd advise going after sooner rather than later are (1) some sort of styling abstraction, and (2) coordinate transforms.

(The days where TravellerMap.com should rely on server-side rendering are numbered. Map sites in general are moving towards sending vector data down to the browser to render using Canvas or SVG.)