Modeling the communications delay

[robject]

Originally posted by kaladorn:

The distance at Jump-X, where X is a specified number and includes provision for fueling along the way (no gas-giant-less desert systems!) would be far more useful, but also a much much more computationally intensive project. It could be simplified with some assumptions, but nothing will prevent dead-ending.... (except massive sized models and lots of cycles!).

Now *that's* a computer program.

I suspect this could be efficiently done with a genetic algorithm, with a DNA string length related to the distance of travel and max jump size. Hmmmm.

Heading (1-6)
Jump (1-N); 1 <= N <= 6

</font><blockquote>code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">generate a big batch of random routes.
until done
{
foreach route
{
viability = 1.
viability-- for each hex in route with no GG, wet, or ice world.
}
sort routes.
done if time-is-up or cycles-is-up or ?
save non-duplicate routes with viability 1.
remove the bottom 90% from route list.
modify the top 10% here and there
in order to refill the route list.
}
sort all viable routes.
save the top 10 or so.</pre>[/QUOTE]I suppose route generation is an algorithm unto itself, but it can be simplified by just selecting a random hex more-or-less heading toward the destination.

 

[kaladorn]

The little I know about genetic algorithms suggests this might be a problem they'd work to solve, but that they can be ugly to set up.

You could choose the 'random walk' approach to selecting your next destination (along a line of direction). I'd think perhaps using a chess-like look-ahead a few jumps might actually yield better results.

Still, you *could* get dead ended. But even then, your algorithm should allow backstepping to the last bifurcation and exploring options from there (repeat until you find a viable branch or all branches are explored).

 

[Anthony]

Distance at jump-X is actually a fairly simple problem, which is O(n^2) in distance. I solved it some time ago when I was writing trade route algorithms.

The hard part, however, involves efficient routing to multiple worlds; routes can be shared, since often the same data is going to multiple worlds.

 

[kaladorn]

Simple, yes. But en-squared order is not the happiest circumstance for large N.

That is to say, if I decide I want the most advantageous route from Terra to Regina, staying within the Imperium, respecting red zones, desert worlds with no gas giants, and political boundaries that are important (ie not going somewhere I'll get killed), that might just be en-squared plus a bit.
And that's a long darn distance with a large number of possible paths.

Of course, if I get the algorithm right and I'm willing to wait a while, the computer *will* eventually solve it.

 

[Anthony]

Originally posted by kaladorn:
Simple, yes. But en-squared order is not the happiest circumstance for large N.

N is not that large (a few thousand, or tens of thousand at worse), with a very limited constant term, and respecting red zones/etc actually makes it easier -- the time requirement is basically linear in the number of stars you can route through, so every star you eliminate the problem gets that much easier.

That is to say, if I decide I want the most advantageous route from Terra to Regina, staying within the Imperium, respecting red zones, desert worlds with no gas giants, and political boundaries that are important (ie not going somewhere I'll get killed), that might just be en-squared plus a bit.
And that's a long darn distance with a large number of possible paths.

My trade mapping software runs the routing algorithm thousands of times, though it currently limits paths to 199 parsecs because the longer distance stuff is just not worth keeping track of. Generating shortest routes from world X to every other world in the Imperium takes several seconds on a rather old linux box.

 

[FlightCommanderSolitude]

I'd agree that searching for paths is fairly straightforward, and doesn't require anything as exotic as a genetic algorithm. It's pretty much just a walk over a graph, the only complication being that your graph needs to have six dimensions to it eg J1 paths, J2 paths, ... J6 paths.

Follow-up to my previous question: I need a function that returns all of the hexes that are N hexes away from a given hex. Eg, for hex 0405 and distance 1, I want a list like (0404, 0505, 0506, 0406, 0306, 0305). Again, this is a deceptively tricky problem, and I'm wondering if any of you folks have already solved it.

 

[Anthony]

For some fairly atrocious code that may be useful, take a look at http://maps.travellercentral.com/nr.c

Someday I should look at some real compsci methods of solving this stuff; it's probably a variant on the travelling salesman problem, but I took very few formal CS classes.

 

[FlightCommanderSolitude]

Hrm, although interesting, that didn't quite cut it. I've currently got a function to give me all the hex locations one hex away from a given hex, but I did it by hardcoding the offsets, which is even lamer than it sounds because the offsets are different depending on whether it's an even or odd column. Instead of doing this for all the other jump numbers, I'd prefer a formula for comping up with the list. So, still looking, will post it here if I solve it.

Thanks for the link though!

 

[kaladorn]

Hmmm. If I understand what you want, you want to take a hex, with address xxxx and determine the addresses of all the hexes within y distance from that location.

What does such an algorithm have to consider?
- Do you want sector relative coords or subsector relative? (ie is Inthe 2410 of SM or 0810 of Regina)
- Do you want calculations to span sector boundaries?
- At the sector edges, there is a discontinuity in the numbering schemes (2440 is adjacent to 2401 of
the next sector)

I'll try to come up with something nice that works.

 

[Hal]

Originally, I asked the question about whether or not someone had a working algorithm for deteriming distance between hexes given start hex and end hex. Unfortunately, every example given to me of an algorithm given to me did NOT work. Ultimately, what I ended up "discovering" was a rather complex solution. It required that I break down each hex number into two parts (What I arbitrarily called X and Y components). Then I had to test to determine if the X component was odd or even for both source and destination hex, and odd/even for the Y part. Specifically, dividing a hex number by 100 to get the first two digits as X, and taking the remainder of that number as the Y component. I won't get into the full proceedure, but I will say this:

I tested the "easy" methods given to me by others and it did not work for every case I could imagine

I tested my method and it worked for every method

I wrote the code in visual basic. My intentions for writing this code were to produce a FAR TRADER based program that would generate cargo. It works after a fashion - until I realized that I should have written the code to generate ALL cargoes available at that current location rather than for source location and destination location.

Gonna have to go back to programming again one of these days.

Hal

 

[TheEngineer]

Hi Hal,

had similar hex grid problems when switching from rectangular coordinates to the hex grid for combat vector movement.

I wonder which weird mind invented hex grids anyway

If I may I would kindly ask to show Your HexDist code in order to proceed with other things.

Hope it will work with negativ hex coordinates as well...

Regards,

Mert

 

[kaladorn]

The true distance between any two points x1,y1 and x2,y2 in two-space is going to be

s = sqrt((delta x squared) + (delta y squared))
delta x is the separation in x
delta y is the separation in y

<This presumes my brain hasn't checked out>

That's just geometry.

To accompany this in a traveller hex-map situation, you need to know the coordinates (x, y) of the centers hexes in question, which you can derive from:
- the hex number
- a knowledge of the distance across a hex
- a reference point (for your axes, a 0,0 location)

Assume that your axes run nicely squared up to your hex grid, not with some rotation applied (since you are defining your axes, that's all good!).

 

[FlightCommanderSolitude]

Originally posted by kaladorn:
Hmmm. If I understand what you want, you want to take a hex, with address xxxx and determine the addresses of all the hexes within y distance from that location.

Exactly. BTW, I looked into this over the weekend and while I found many interesting properties of the problem, I was unable to derive a solution that would be any more elegant or efficient than just coming up with tables of offsets. Of course, I have a brain the size of a pea, so hopefully someone can do me better!

Originally posted by kaladorn:
What does such an algorithm have to consider?
- Do you want sector relative coords or subsector relative? (ie is Inthe 2410 of SM or 0810 of Regina)
- Do you want calculations to span sector boundaries?
- At the sector edges, there is a discontinuity in the numbering schemes (2440 is adjacent to 2401 of
the next sector)

Ug, thanks for pointing the sector boundary problem out, I hadn't looked into the problem that far. It would be nice to be able to solve for that as well. Localizing and globalizing hex numbers is easy enough.

Also, Hal, I didn't have any problems with the distance methods that robject posted. I think your solution is a restatement of his. What did you have problems with?

 

[Anthony]

Originally posted by Hal:
Originally, I asked the question about whether or not someone had a working algorithm for deteriming distance between hexes given start hex and end hex.

I did. It's used in the .c file I link to above. However, it sounds similar to yours.

 

[FlightCommanderSolitude]

Ok, so I finished the function for getting a list of hexes in the jump-neighborhood of a given hex. The hexes returned are not fixed if they are negative, they are just the raw hex locations. Presumably, a calling function could decide what to do with such locations, eg if they are outside of the sector, map them into another sector's coordinates.

As I mentioned, this uses a lookup table, and is implemented in Perl:

</font><blockquote>code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">sub neighborhood {
my $location = shift; # a hex location, eg '0101'
my $distance = shift; # a number between 1 and 6
$distance--;
my $inclusive = shift || undef; # if false, get all hexes at $distance
# if true, get all hexes within $distance

my %HEXOFFSET;
%HEXOFFSET = (
0 => [
[[ 0, 1], [ 0,-1], [ 1, 0], [-1, 0], [ 1, 1], [-1, 1]],

[[ 0, 2], [ 0,-2], [ 2, 0], [-2, 0], [ 2, 1], [-2, 1],
[ 2,-1], [-2,-1], [ 1,-1], [-1,-1], [ 1, 2], [-1, 2]],

[[ 0, 3], [ 0,-3], [ 3, 0], [-3, 0], [ 3, 1], [-3, 1],
[ 3,-1], [-3,-1], [ 2, 2], [-2, 2], [2, -2], [-2,-2],
[ 3, 2], [-3, 2], [ 1,-2], [-1,-2], [ 1, 3], [-1, 3]],

[[ 0, 4], [ 0,-4], [ 4, 0], [-4, 0], [ 4, 2], [-4, 2],
[ 4,-2], [-4,-2], [ 4, 1], [-4, 1], [ 4,-1], [-4,-1],
[ 2, 3], [-2, 3], [ 2,-3], [-2,-3], [ 3, 3], [-3, 3],
[ 3,-2], [-3,-2], [ 1, 4], [-1, 4], [ 1,-3], [-1,-3]],

[[ 0, 5], [ 0,-5], [ 5, 0], [-5, 0], [ 5, 2], [-5, 2],
[ 5,-2], [-5,-2], [ 5, 1], [-5, 1], [ 5,-1], [-5,-1],
[ 4, 3], [-4, 3], [ 4,-3], [-4,-3], [ 2, 4], [-2, 4],
[ 2,-4], [-2,-4], [ 5, 3], [-5, 3], [ 3, 4], [-3, 4],
[ 3,-3], [-3,-3], [ 1, 5], [-1, 5], [ 1,-4], [-1,-4]],

[[ 0, 6], [ 0,-6], [ 6, 0], [-6, 0], [ 6, 1], [-6, 1],
[ 6,-1], [-6,-1], [ 6, 2], [-6, 2], [ 6,-2], [-6,-2],
[ 6, 3], [-6, 3], [ 6,-3], [-6,-3], [ 4, 4], [-4, 4],
[ 4,-4], [-4,-4], [ 2, 5], [-2, 5], [ 2,-5], [-2,-5],
[ 1,-5], [-1,-5], [ 1, 6], [-1, 6], [ 3,-4], [-3,-4],
[ 3, 5], [-3, 5], [ 5,-3], [-5,-3], [ 5, 4], [-5, 4]],
],
1 => [
[[ 0, 1], [ 0,-1], [ 1, 0], [-1, 0], [ 1,-1], [-1,-1]],

[[ 0, 2], [ 0,-2], [ 2, 0], [-2, 0], [ 2, 1], [-2, 1],
[ 2,-1], [-2,-1], [ 1, 1], [-1, 1], [ 1,-2], [-1,-2]],

[[ 0, 3], [ 0,-3], [ 3, 0], [-3, 0], [ 3, 1], [-3, 1],
[ 3,-1], [-3,-1], [ 2, 2], [-2, 2], [2, -2], [-2,-2],
[ 3,-2], [-3,-2], [ 1, 2], [-1, 2], [ 1,-3], [-1,-3]],

[[ 0, 4], [ 0,-4], [ 4, 0], [-4, 0], [ 4, 2], [-4, 2],
[ 4,-2], [-4,-2], [ 4, 1], [-4, 1], [ 4,-1], [-4,-1],
[ 2, 3], [-2, 3], [ 2,-3], [-2,-3], [ 3,-3], [-3,-3],
[ 3, 2], [-3, 2], [ 1,-4], [-1,-4], [ 1, 3], [-1, 3]],

[[ 0, 5], [ 0,-5], [ 5, 0], [-5, 0], [ 5, 2], [-5, 2],
[ 5,-2], [-5,-2], [ 5, 1], [-5, 1], [ 5,-1], [-5,-1],
[ 4, 3], [-4, 3], [ 4,-3], [-4,-3], [ 2, 4], [-2, 4],
[ 2,-4], [-2,-4], [ 5,-3], [-5,-3], [ 3,-4], [-3,-4],
[ 3, 3], [-3, 3], [ 1,-5], [-1,-5], [ 1, 4], [-1, 4]],

[[ 0, 6], [ 0,-6], [ 6, 0], [-6, 0], [ 6, 1], [-6, 1],
[ 6,-1], [-6,-1], [ 6, 2], [-6, 2], [ 6,-2], [-6,-2],
[ 6, 3], [-6, 3], [ 6,-3], [-6,-3], [ 4, 4], [-4, 4],
[ 4,-4], [-4,-4], [ 2, 5], [-2, 5], [ 2,-5], [-2,-5],
[ 1, 5], [-1, 5], [ 1,-6], [-1,-6], [ 3, 4], [-3, 4],
[ 3,-5], [-3,-5], [ 5, 3], [-5, 3], [ 5,-4], [-5,-4]],
],
) unless scalar %HEXOFFSET;

my @neighbors;
my ($hx, $hy) = ($1, $2) if $location =~ /(\d\d)(\d\d)/;

foreach my $n (reverse (0 .. $distance)) {
my $ar = $HEXOFFSET{$hx % 2}[$n];
my $hex;

foreach (@$ar) {
push @neighbors, sprintf ("%02d%02d", ($hx + @$_[0]), ($hy + @$_[1]));
}

last unless $inclusive;
}

return @neighbors;
}</pre>[/QUOTE]

 

[kaladorn]

Just a thought:

In general, hex numbers can be generalized across the OTU wrt some reference point. If we treated someplace like core as the central sector (0,0) and treated any displacement away from it spinward as a negative and anti-spinward as positive, coreward as positive and rimward as negative (based on how we usually see the maps laid out), we'd end up with a scheme which locates every sector by a series of X,Y coordinates.

Thus, SM gets -4,1.

If we considered the all coordinates wrt to Reference (0140 in Core Sector), we would have an absolute hex coordinate formula which turned hex 0101 in the Spinward Marches into hex -128, +79.

The basics of this are (32 * -4) = -128 (4 sectors displaced) for the x and (40 * 1) + 39 = 79 (1 sector up plus the shift for reference being 0140 not 0101.

To come up with coords relative to another world in the SM (rather than hex 0101), you'd need to add any X difference between the 01 column and the planet's column and subtract the Y difference between the 01 row and the planet's row.

For instance, Inthe (2410 spinward marches) is then:
-128 + 24 = -104
+79 - 10 = 69

in absolute terms

So in other words:

Absolute hex coordinates wrt reference:

Xabs = 32 * sectorXshift + systemXlocation
Yabs = 40 * subsectorYshift - systemsYlocation

SectorXshift is the number of sectors spinward (neg) or anti-spinward (positive) wrt Core.
SectorYshift is the number of sectors coreward (pos) or rimward (neg) of Core.
The systemXlocation is the displacement in X wrt the 01 column in your sector.
The systemYlocation in the displacement in Y wrt the 01 row in your sector.

Thus Terra, using these formulas, would be:
Solomani Rim Sector: 0,-3
Terra's Sector Relative Coords: 1827

Xabs(Terra) = 32 * 0(sectorXshift) + 17(localXshift = 18 col - 01 col = 17) = 17
Yabs(Terra) = 40 * -3(sectorYshift) - 27 = -147

So, Terra, in absolute coords, is 17,-147.

I hope that came out moderately clear.

The data you need to calc abs hex location x,y for any hex is:
1. Where is the sector relative to core
2. The formulas above for Xabs and Yabs
3. How far from 0101 in your sector your system is.

 

[robject]

The hex-offset scheme is the Ring/Ray system exactly, except your reference point is Sylea instead of the galactic center (whatever that is).

 

[Hal]

Hi Mert and Guys,
For what it is worth, the coding I produced was rather "inelegant" in that it doesn't have any simplistic "formula" it is based off of. It is in visual basic, so I can send the actual coding for anyone who wants to see it. I am not sure how large the compiled program is outright - so if anyone is brave enough to want that file outright, I can make arrangements to either email it outright - or I can perhaps go to IRC and DCC it (I have cable modem if that helps).

What it does:

SH = start hex
EH = End hex

The program will "deduce" or generate the ID values of the surrounding hexes at a specified radius. In other words, if the program is checking for a match for the ending hex location in the 6th "ring" or radius out from SH, it is capable of generating all hex ID's that are precisely 6 hexes away from the SH. If any of those ID's generated = EH's ID, then the program exits and indicates that the distance is 6 hexes. I've further refined it so that rather than check *all* of the potential hexes within a ring, it only generates 1/3rd of the potential hex ID's that will contain the end hex location.

In any event - if anyone would like the code in Visual Basic, email me at

hal@buffnet.net

If you want a compiled version of the program, let me know and I will check to see how big it is. It will be larger than you expect because for some reason, Visual Basic will give it a large library of DLL's (I picked up Visual Basic Enterprise edition for a song - but never really learned how to use it properly as the documentation was poor - it is a NFR edition if anyone is curious).

 

[FlightCommanderSolitude]

I think the formula for ring/ray coordinates is:

</font><blockquote>code:</font><hr /><pre style="font-size:x-small; font-family: monospace;"> my $ray = 62832 + (32 * $sector_x) + $system_x;
my $ring = 10000 + (40 * $sector_y) + $system_y - 40;</pre>[/QUOTE]...where $sector_x and $sector_y are the sector offsets from Core sector (eg, Spinward Marches is -4, -1); and $system_x and $system_y are the x and y components of the sector-relative hex location of the system in question. It took me while to boil this out of the various library data entries, which weren't very clear, at least not to the Flight Commander's pea brain!

 

[robject]

Also, don't forget that Sylea is de facto Ray Zero...