Modeling the communications delay

[FlightCommanderSolitude]

But, according to this library data page :

By convention, the concentric ring passing through Reference (Core / Core 2118) is labelled the 10,000th ring, and is used as a baseline. Similarly, the ray of latitude extending from the centre of the galaxy through Reference is designated as the first ray.

Although there appears to be some confusion over where, exactly, Reference is. When I look here it's at Core 0140, which is the value I used. Capital/Sylea is at 2118, not Reference. Uh...confused, please help!

In any case, does anybody have any interesting thoughts about pathfinding algorithms? I'm a reasonably proficient coder, but these tweaky compsci problems were never my forte. After noodling around with the problem there appear to be some gotchas that didn't jump out at first glance.

For example, you'd ideally want a list of all routes available to a J(N) vessel from System A to System Z, presumably passing through only those systems that have refueling facilities. With J1 this works out OK; with J2 it poses some interesting challenges. And with J6 the result is just about every possible route on your map, which is probably not that useful.

So, perhaps what would be more useful is a routine to find the shortest path (ie with the fewest jumps) from System A to System Z, optionally passing through Systems B and C, or System D.

Back to the original topic: to model the communications delay, you'd first need to find the nearest xboat links at both the head and tail; I guess the referee would have to decide how much time would pass for a message to get picked up by the xboat network, depending on the importance of the message etc. Then you could use the above algorithm to find the shortest path from head to tail, but you'd use a pruned version of the astrographic data where only xboat links were included. Then you'd multiply the number of jumps in the resulting path by one week or so to find the amount of time the message took to get somewhere.

I haven't looked into the xboat routes but I imagine that xboat route times differ significantly, or at least interestingly, between some equidistant points. Eg, the amount of time it takes for a message to reach Capital from Regina might be much less than for a message to reach Capital from Podunk, even if Regina and Podunk were equidistant hexwise from Capital. The ideal situation here would be to have a map that visually showed a message's "reach" at successive weeks.

Sorry if I'm boring everyone to tears.

 

[kaladorn]

I think the 'J-N route from X to Y' problem is a moderately complex one to get all factors in place and end up with good (efficient) answers.

As for where Reference is, I used Ned Utzig's page. I'm fairly certain it's not where the quote you throw out is (that being Sylea!). I think 0140 is where it is. That's the assumption I made.

One interesting distinction between my Imperio-centric version and the Core-centric version - mine makes the axes correspond to how you hold your usual SM or Charted Space maps. That is, up is int he positive (coreward) direction. Judging by the coords assigned to SM in the other system (-4, -1), it reverses this.

I think, therefore, that an Imperio-centric system, though offensive to other sophonts

undoubtedly makes game-sense since our maps are all printed and labelled in such a way as to make coreward as a positive direction sensible.

 

[FlightCommanderSolitude]

Originally posted by kaladorn:
As for where Reference is, I used Ned Utzig's page. I'm fairly certain it's not where the quote you throw out is (that being Sylea!). I think 0140 is where it is. That's the assumption I made.

Exactly. I myself used the Utzig site to find Reference, and I pointed out that the library data entry pointed to Sylea instead of Reference, although I think it means Reference. Interestingly, the library data on this site refers to "Reference/Capital". It would be uh nice if we could find a definition of the ring/ray coordinate system that was both canonical and correct!

Your point about the direction of the axes is understood, although I think it makes sense that the numbers get bigger going out from the core. But the ring/ray thing is already kind of silly (do we really need the huge numbers?), if they really wanted an Imperium-centric system they'd just do offsets from Sylea or something!

 

[kaladorn]

Maybe the location of Capital/Sylea/Reference (coords for each, are they the same?, etc) could be good material for an Ask Avery.

 

[robject]

Hey! Those are good questions. I hadn't thought about Reference vs. Capital. I seem to recall that Reference isn't Capital, and of course Capital is Sylea. I'll have to look up the Library Data in The Traveller Book to see what it says.

I'd say the world name would be easier to correct than the ring/ray numbers; that is, if Ring/Ray is numbered from 0140 Core, then the reference is Reference, not Sylea.

That *is* a good Ask Avery question.

 

[FlightCommanderSolitude]

I checked my copy of Supp8 last night and it reads pretty much the same as the library data on this site, ie "Reference/Capital" is the origin, and it does not provide coordinates.

Using Reference as the uh reference makes sense for a couple of reasons, namely the name and the fact that it's in the bottom left corner of the Core sector.

Capital is Sylea, at 2118 Core. Reference is at 0140.

BTW, was a canonical version of the Core sector ever published? I'm looking at all of the mapping sites and wondering where they get all that stuff.

 

[kaladorn]

More than likely, TNS articles have provided coordinates (possibly multiple sets) and canon may have seen multiple versions of that sector (similar to when they wrote-over Ley Sector and Glimmerift Reaches).

I'd think the 'lower corner' makes for easy galactographic sense, but the 'capital' might make for political sense.... (which do you suspect would win?)

It'd just mean a slightly different transform, that's all.

 

[robject]

There are uncanonical maps of Core (the one in the T4 rulebook is WAY different). I think there's a megatraveller sector map for Core, isn't there?

 

[kaladorn]

I think some of the subsectors of Core were mapped (including probably Capital's subsector). Don't know if the whole sector was.

 

[robject]

I do have a sector map of Core, I think from HIWG, but I've no idea if it's "canonical". At this point, it almost doesn't matter, since the Star Salad maketh my eyes glaze over after a couple subsectors worth...

 

[Hal]

Originally posted by FlightCommanderSolitude:
</font><blockquote>quote:</font><hr />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? </font>[/QUOTE]Hello FlightCommanderSolitude,
I neglected to answer your question earlier, so I apologize now for getting to it now.
What I found to be the case was that under *most* circumstances, the formulas worked at giving me the correct answer. But there were specific instances where they did not exactly work. In general, they would give me the correct answer some 90% of the time, but there was *always* an instance where it got the answer wrong by a value of 1 hex.
The thing to test is as follows:

Break the hex id into X and Y components where X is the first two number, Y is the last two numbers.

SH = Start hex
EH = End Hex

X=even, Y = Even SH, X=even, Y = Even EH
X=even, Y=Odd SH, X=even, Y=even EH
X=Odd, Y = Even SH, X=even, Y= even EH
X=Odd, Y = Odd SH, X=even, Y= Even EH

Keep on going through ALL of the possible permutations as above, and you will find that the formulaeic method doesn't exactly work with all cases. At least, that was what I found to be the case when someone sent me a "formula" they thought should work. For those who are good with Excel - the excel spreadsheet can be "programmed" to demonstrate the validity of a formula or not.

Hal

 

[kaladorn]

Could you please provide an example of incorrect results?

 

[TheEngineer]

Hi,

this is some evil VB code, in fact a slightly adapted/modified version of the code presented by robject(?) few posts ago.

I use this one in the space combat software and it behaves well (so far..) in any combination (odd, even, positiv, negative hex values).

Public Function mhd(x1 As Long, y1 As Long, x2 As Long, y2 As Long) As Long
Dim dx As Double
Dim dy As Double
dx = Abs(x2 - x1)
dy = (y2 - y1)
If x1 Mod 2 = 0 Then dy = (dy - 0.5)
If x2 Mod 2 = 0 Then dy = (dy + 0.5)
dy = Abs(dy)
If dx > (2 * dy) Then
mhd = dx
Else
mhd = dx / 2 + dy
End If
End Function


regards,

Mert

 

[kaladorn]

Mert, you write code like an engineer....

 

[Hal]

Originally posted by TheEngineer:

Public Function mhd(x1 As Long, y1 As Long, x2 As Long, y2 As Long) As Long
Dim dx As Double
Dim dy As Double
dx = Abs(x2 - x1)
dy = (y2 - y1)
If x1 Mod 2 = 0 Then dy = (dy - 0.5)
If x2 Mod 2 = 0 Then dy = (dy + 0.5)
dy = Abs(dy)
If dx > (2 * dy) Then
mhd = dx
Else
mhd = dx / 2 + dy
End If
End Function


regards,

Mert

Mert?
I just typed in your code into excel and tested it. I happened to have my THE SPINWARD MARCHES CAMPAIGN with me at work. Thus far, it has proven to be accurate!
I did note one interesting thing in your code that I hadn't done (based on memory) - I didn't modify results based on BOTH the X's of start hex and end hex *at the same time*. That may have been why it didn't work based on someone else's suggestion. I am EMBARASSED that your few lines of code are likely to be about 3 to 5% in volume the amount of coding I had to use to create my own solution! In this case - I am very thankful to give this section of VB coding a shot. THANK you.

humbly yours,
Hal

 

[TheEngineer]

Hi,

as I mentioned before its mainly robjects code...but at least its the condensed version of any code after a few cycles of optimizing.
I did so with my original code and finally ended here, too.
The most important point is to use the symetric nature of the hex grid.

The dx = abs(x2-x1) uses the symetry and flips left (negative) part to the right.
The two if-lines adjust the symetric y value origin according to the odd/even nature of a hex column.
The the symetry is used again dy = abs(dy) and negative y value are flipped to the positives.

The calculation itself is performed here
If dx > (2 * dy) Then
mhd = dx
Else
mhd = dx / 2 + dy
End If
and is quite simple

But though this one works I still have trouble in adjusting vector movement algorithms to hex environment....

@Hal: Fix your computer, so we can code some trade stuff

Regards,

Mert

 

[kaladorn]

Mert,

What's causing you grief in the vector adaption to hexes?

Many board games have done this, so I guess I can't quite see what your problem is, exactly...?

 

[TheEngineer]

Hi Thomas,

problem is, that I cannot use some of my "normal" vector calculations.
Interally I work with a heading system from 1 to 12 (3 is "west", 6 is "south" etc).
Here I can set vectors in the "polar" way simply by specifing a heading/direction and a length.
A function then returns x/y values of vector.
This works when dealing with a "normal" geometric system, but is difficult in the hex grid because of the damned y-shift in odd/even rows.
After a vector addition of old pos + movement vector it sometimes results in future ship positions that are geometricaly [speed-value] units away from the old pos, but 1 unit less or more in the hex grid system.
As a workaround I checked the distance using the hex dist function, and modified the target hex coordinates in an appropriate way.
Thats not very elegant and I dont like it.

I guess, I will have to write some suitable mapping function from "normal" system to hex grid.....

What I would not like to do is to adapt the complete internal heading system with one fitting to hex grids only.

I will work out the problematic "use cases" and post it to the software solutions..

Regards,

Mert

 

[kaladorn]

Originally posted by TheEngineer:
Interally I work with a heading system from 1 to 12 (3 is "west", 6 is "south" etc).

3 is *West?*

Now that's different.

Here I can set vectors in the "polar" way simply by specifing a heading/direction and a length.

Are you restricting yourself to 1-12 headings? Why not use a 360 bearing system?

A function then returns x/y values of vector.
This works when dealing with a "normal" geometric system, but is difficult in the hex grid because of the damned y-shift in odd/even rows.

I've been attempting the posited problem in PHP.... ARGH! (I keep thinking I have it, then go test a boundary case and it breaks down.... partly I think because PHP rounds 0.5 to 1 and 1.5 to 1 - allegedly 'proper' rounding)

I've chosen PHP so the results can eventually be available to all.

Of course, I hadn't taken the 'convert all to universal coords then back' approach. That may be an alternative project.

After a vector addition of old pos + movement vector it sometimes results in future ship positions that are geometricaly [speed-value] units away from the old pos, but 1 unit less or more in the hex grid system.

This ought to be a solvable problem.

As a workaround I checked the distance using the hex dist function, and modified the target hex coordinates in an appropriate way.
Thats not very elegant and I dont like it.

You're probably doing your hex-math as 'hexes'. That is to say, you aren't using a geometric system with the actual vectors, determining a 2 space coordinate, then figuring out which hex that would actually be in. That would make them match up identically, I'd think. Or am I wrong?

I guess, I will have to write some suitable mapping function from "normal" system to hex grid.....

What I would not like to do is to adapt the complete internal heading system with one fitting to hex grids only.

No, don't do that. I agree that's not a wonderful thing.

 

[robject]

Hey, Flight Commander man, perhaps we should put our Perl together and come up with a Book 6 extended star system generation program -- one specifically designed to take official sector data and churn out full system details in some format that is extremely easy for Perl to re-read in.

Then, to the back-end of that, we can attach a filter that churns out data in whatever format people like (such as some version of Traveller XML).

I've got a lovely Perl module that parses UWPs from standard and slightly non-standard sector formats.