Modeling the communications delay
- Thread starter The Oz
- Start date
My cut at the 'find the neighbouring hexes' problem
Now, I've only set it to support ranges up to six. And it doesn't validate if you've entered valid coordinates (you could enter 4040 for instance, and it'd probably do something wrong). I haven't put that last check in.
It took me a fair bit of arsing around, giving up, going off, doing some analysis, coming back, developing some alternate code from the analysis, bug checking, fixing, and then testing in all the boundary cases I could think of.
I believe it is now, as they say, ready for prime-time.
Now, if I mated it to a 'reader' for the sector files (which goes back to my previous 'why aren't the formats documented anywhere?' point), I could find out which of these hexes actually had planets in them.
One good byproduct of my analysis: I now know all the geometric stuff like finding the coordinates of the vertices of a hex given the coordinates of the center and geometric distances between hex centers, etc.
Now, I've only set it to support ranges up to six. And it doesn't validate if you've entered valid coordinates (you could enter 4040 for instance, and it'd probably do something wrong). I haven't put that last check in.
It took me a fair bit of arsing around, giving up, going off, doing some analysis, coming back, developing some alternate code from the analysis, bug checking, fixing, and then testing in all the boundary cases I could think of.
I believe it is now, as they say, ready for prime-time.
Now, if I mated it to a 'reader' for the sector files (which goes back to my previous 'why aren't the formats documented anywhere?' point), I could find out which of these hexes actually had planets in them.
One good byproduct of my analysis: I now know all the geometric stuff like finding the coordinates of the vertices of a hex given the coordinates of the center and geometric distances between hex centers, etc.
TheEngineer
SOC-14 1K
Hi,
regarding the hex grid calculation stuff...
Well, heading 3 is indeed east and not west
quote:
--------------------------------------------------------------------------------
Are you restricting yourself to 1-12 headings? Why not use a 360 bearing system?
--------------------------------------------------------------------------------
I thought it would be more useful as a gaming aid when using a more abstract
heading system. But perhaps you´re right and I will switch to full 360 degrees
at least "internally".
quote:
--------------------------------------------------------------------------------
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?
--------------------------------------------------------------------------------
You're right. The system is a bit mixed...
Right now I think, that I just have to write an additional AddHexVector function for getting
correct hex grid coordinates. I will give it a try.
quote:
--------------------------------------------------------------------------------
One good byproduct of my analysis: I now know all the geometric stuff like finding the coordinates of the vertices of a hex given the coordinates of the center and geometric distances between hex centers, etc.
--------------------------------------------------------------------------------
Would you provide some code snippets ?
Regarding the possible book 6 project:
Isn't that alread done in H&E ?
Regards,
Mert
regarding the hex grid calculation stuff...
Well, heading 3 is indeed east and not west
quote:
--------------------------------------------------------------------------------
Are you restricting yourself to 1-12 headings? Why not use a 360 bearing system?
--------------------------------------------------------------------------------
I thought it would be more useful as a gaming aid when using a more abstract
heading system. But perhaps you´re right and I will switch to full 360 degrees
at least "internally".
quote:
--------------------------------------------------------------------------------
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?
--------------------------------------------------------------------------------
You're right. The system is a bit mixed...
Right now I think, that I just have to write an additional AddHexVector function for getting
correct hex grid coordinates. I will give it a try.
quote:
--------------------------------------------------------------------------------
One good byproduct of my analysis: I now know all the geometric stuff like finding the coordinates of the vertices of a hex given the coordinates of the center and geometric distances between hex centers, etc.
--------------------------------------------------------------------------------
Would you provide some code snippets ?
Regarding the possible book 6 project:
Isn't that alread done in H&E ?
Regards,
Mert
There is software which parses UWP data, and Heaven & Earth may currently do that. However, I don't know if H&E provides a module or package I can incorporate into my own schemes, and I'm not aware of the output format of H&E data. I've seen the database data on their webpage ( I think ), and am suitably impressed, so perhaps this is already done?
FlightCommanderSolitude
SOC-13
I'm already about 95% done with such a project, but the remaining 5% is a killer, and I suspect I'll need to start over (again) with a still more rational model. I tend to write code in "drafts", ie write it once to figure out where the real problems are, then rewrite it differently to more elegantly solve those problems.
I'll let you know however when I have something ready for other eyeballs!
Were you able to find a formula, or did you use a table?
FlightCommanderSolitude
SOC-13
Indeed it wasn't, that was a cut-n-paste tragedy on my part. I meant to direct that to kaladorn .
It does...whence my laboriously-cobbled tables back on page three! It would be nicer to know a forumula to derive the locations, although the lookup table might be faster.
Their are probably many ways to approach the problem, but my algorithm, in simple (I will clean up the code and post a link) was:
Knowing that the range in x will be from your (start_hex - range_specified) to (start_hex + range_specified) and that range in Y at its maximum (in the center) was 2 * spec_range + 1, and drops off by one in either direction, I had the algorithm generate the range of possible addresses.
Bugaboos:
- Rounding of PHP fractional values. (such as when you have a range of 3, indicating a +1.5 and -1.5 modification to generate the Y range, sometimes leading to it generating 4 systems or the whole shebang being offset one)
- The original hex matters (odd/even)
- The relationship between the original hex and the current hex matters (are they both odd or even, is one odd, the other even?)
- In boundary conditions, you have to be able to generate the right addresses (so 0140, 3240, 0101 and 3201 are great test addresses)
I did not use a table, this is done programmatically. There are actually 8 different cases of interest and I have them modelled.
I'll clean up and comment the code and get it linked.
Knowing that the range in x will be from your (start_hex - range_specified) to (start_hex + range_specified) and that range in Y at its maximum (in the center) was 2 * spec_range + 1, and drops off by one in either direction, I had the algorithm generate the range of possible addresses.
Bugaboos:
- Rounding of PHP fractional values. (such as when you have a range of 3, indicating a +1.5 and -1.5 modification to generate the Y range, sometimes leading to it generating 4 systems or the whole shebang being offset one)
- The original hex matters (odd/even)
- The relationship between the original hex and the current hex matters (are they both odd or even, is one odd, the other even?)
- In boundary conditions, you have to be able to generate the right addresses (so 0140, 3240, 0101 and 3201 are great test addresses)
I did not use a table, this is done programmatically. There are actually 8 different cases of interest and I have them modelled.
I'll clean up and comment the code and get it linked.
FlightCommanderSolitude
SOC-13
Cool, I'd be interested in comparing it speedwise to the table method. I tested your page against my code (slightly modified to handle boundaries), using a number of different hex locations, and came up with the same result sets, which is good.
TheEngineer
SOC-14 1K
HI,
just try this one.
Based on the distance function mhd (already posted) its a quite - hmmmm - simple approach, but works well.
It does not need supercomputing resources, too
Public Sub GetHexes(basex,basey,Distance)
For cx = basex - Distamce To basex + Distance
For cy = basey - Distance To basey + Distance
If mhd(basex, basey, cx, cy) = Distance Then
' Display hex coordinates
Text1.Text = Text1.Text & cx & ":" & cy & vbCrLf
End If
Next cy
Next cx
End function
Regards,
Mert
just try this one.
Based on the distance function mhd (already posted) its a quite - hmmmm - simple approach, but works well.
It does not need supercomputing resources, too
Public Sub GetHexes(basex,basey,Distance)
For cx = basex - Distamce To basex + Distance
For cy = basey - Distance To basey + Distance
If mhd(basex, basey, cx, cy) = Distance Then
' Display hex coordinates
Text1.Text = Text1.Text & cx & ":" & cy & vbCrLf
End If
Next cy
Next cx
End function
Regards,
Mert
1. I coded in PHP. Not sure what that means speedwise. I get the impression some operations may not be as fast as one would like (I do a number of modulo ops and I have no idea how fast they are). Still, it works quick enough. And I don't know enough PHP to know if my *code* is good, not to mention the underlying algorithms, which can be a separate issue.
2. Mert, the only inelegance (IMO) of your method, which I contemplated, is that it will evaluate if hexes are 'fair game' even for ones that are not (it seems to check all of those in a 'box' if I read it right, including some of them that will fail the distance check). My method only produces valid hexes. Doesn't mean it will be faster, but it struck me that I shouldn't be checking invalid ones. If you use a large radius (say 10-15), you may find you check a lot of invalid hexes.
3. My method will, barring limits in PHP I'm not aware of, extend to N hexes radius. I limit at six for practical test cases, but I can probably do 200. It'll just take some time.
4. The table method would fail if R>40 I'd imagine (maybe not) - in that it could span two sectors. I think my method (have not tried anything so insane) may well work for any arbitrary length, given the compute resources, and I suspect it might scale, barring PHP issues, gracefully.
2. Mert, the only inelegance (IMO) of your method, which I contemplated, is that it will evaluate if hexes are 'fair game' even for ones that are not (it seems to check all of those in a 'box' if I read it right, including some of them that will fail the distance check). My method only produces valid hexes. Doesn't mean it will be faster, but it struck me that I shouldn't be checking invalid ones. If you use a large radius (say 10-15), you may find you check a lot of invalid hexes.
3. My method will, barring limits in PHP I'm not aware of, extend to N hexes radius. I limit at six for practical test cases, but I can probably do 200. It'll just take some time.
4. The table method would fail if R>40 I'd imagine (maybe not) - in that it could span two sectors. I think my method (have not tried anything so insane) may well work for any arbitrary length, given the compute resources, and I suspect it might scale, barring PHP issues, gracefully.
TheEngineer
SOC-14 1K
Hi Thomas,
its not elegant at all...its just a brute force attack
But works under all conditions.
To analyse speed of the code would be interesting.
Perhaps up to some distance limit the calculation of valid hexes consumes more "cycles" than the brute force way does ?
I am just thinking of a method combination :
Define one hex with the correct distance and then find adjected hexes with the same distance again and again......
Regards,
Mert
its not elegant at all...its just a brute force attack
But works under all conditions.
To analyse speed of the code would be interesting.
Perhaps up to some distance limit the calculation of valid hexes consumes more "cycles" than the brute force way does ?
I am just thinking of a method combination :
Define one hex with the correct distance and then find adjected hexes with the same distance again and again......
Regards,
Mert
There is also an interesting possibility related to the geometry of the situation. If I can calculate the six vertices of the larger hexagon my 'radius' will create, I can immediately *infer* all of the hexes in between these six points, and then all the hexes they contain. I haven't tried this approach, but you can do it manually on paper.
I'm not sure performance matters (Except to the little optimizer in all engineering geeks). When are we going to use this? Maybe for trade calculations? Maybe for J-6 maps? Maybe for some indications of where a ship could jump? The last two are gonna be 6 hex radius limited. The former one will probably have (based on your economic model) some place at which the values of even the best trade routes drop to insignificance. I'd have to get someone with GT:FT to try to tell me what a reasonable value here is..... how far can a trade route extend before being not worthy of notice?
These will be the limiting boundaries of practical uses of this type of nearby hex coord calculation, and I think any of our methods are acceptable, given that.
The only other case I can see is defining a map around a given hex, but then you probably just want to figure a max and min x and max and min y and draw the systems inside that rectangle. So no need for as much fancy dancy math.
Can you see a reason you'd want to use this for distances over 8 or 10 hexes? (I'm assuming that's where trade drops off the map in GT:FT).
So speed probably doesn't matter as any of ours solutions work here. I just liked mine because it didn't involve a distance calculation for each hex and then failing some of them.
I'm not sure performance matters (Except to the little optimizer in all engineering geeks). When are we going to use this? Maybe for trade calculations? Maybe for J-6 maps? Maybe for some indications of where a ship could jump? The last two are gonna be 6 hex radius limited. The former one will probably have (based on your economic model) some place at which the values of even the best trade routes drop to insignificance. I'd have to get someone with GT:FT to try to tell me what a reasonable value here is..... how far can a trade route extend before being not worthy of notice?
These will be the limiting boundaries of practical uses of this type of nearby hex coord calculation, and I think any of our methods are acceptable, given that.
The only other case I can see is defining a map around a given hex, but then you probably just want to figure a max and min x and max and min y and draw the systems inside that rectangle. So no need for as much fancy dancy math.
Can you see a reason you'd want to use this for distances over 8 or 10 hexes? (I'm assuming that's where trade drops off the map in GT:FT).
So speed probably doesn't matter as any of ours solutions work here. I just liked mine because it didn't involve a distance calculation for each hex and then failing some of them.
In using Far Trader's tables, and the following asumptions - the answer for your question about how far one needs to go to generate trade routes is:
Givens: World Trade Numbers are based on the planet's pop value halved.
Assumptions: Modified Trade values of 7+ generate enough cargo per week to fill 50 to 100 dtons of volume or more with 7 being the lowest possible to generate 50 to 100 dtons
Two A population worlds will generate a value 7 trade route up to 59 hexes away.
two worlds, class A population and class 9 population will generate a trade route up to 29
hexes away.
Two worlds either of class A and class 8 population *OR* class 9 and class 9 population will generate a trade route up to 19 hexes away.
As you can see, you need to think somewhat larger view here.
For what it is worth? Lets say you have a Far Trader ship - free trader J2 ship. Lets further stipulate that the trade route is 58 hexes away, for a total of 29 jumps. Further assume that the ship is carrying 50 dtons of freight the whole distance and is being paid 650 Crimps per parsec per dton of freight. That ship will have earned at the end of its journey - 1.885 MegaCrimps.
*note: Crimp is Credit Imperial
FlightCommanderSolitude
SOC-13
Great idea!
The only time the efficiency of this function would matter (to me) is when generating the graph of systems reachable from other systems. Eg, if I want to generate routes from Regina to Kinorb, I need to know all the potential legs of the journey, which is where this function comes in.
Assuming HAL is right, we're looking at an outer bound of 60. (Was that 'worst case' situation?)
In the other case, travel routes, I think this is *not* repeat *not* the approach to take. It is a very compute intensive solution to this problem. You may use it to find all points within "ship jump number" of a point along the way, but that still limits to six.
I *really* would not do this for trying to figure the route from A to B, using large radii.
Two reasons:
1. A lot of wasted computing (the direction you take is somewhat directional, this algorithm is omnidirectional)
2. You may find it necessary to visit planets outside the larger hex thus defined (in odd situations).
There are other approaches to the 'best route A to B' problem and I think this would only at best be a minor component of that far larger problem.
In the other case, travel routes, I think this is *not* repeat *not* the approach to take. It is a very compute intensive solution to this problem. You may use it to find all points within "ship jump number" of a point along the way, but that still limits to six.
I *really* would not do this for trying to figure the route from A to B, using large radii.
Two reasons:
1. A lot of wasted computing (the direction you take is somewhat directional, this algorithm is omnidirectional)
2. You may find it necessary to visit planets outside the larger hex thus defined (in odd situations).
There are other approaches to the 'best route A to B' problem and I think this would only at best be a minor component of that far larger problem.
FlightCommanderSolitude
SOC-13
To find a route from A to B, you first need to find a way to get from A to somewhere else that might be B. To get to that somewhere else, you need to know hexes that are JN-reachable from A, whence the need for the JN neighborhood function.
In other words, I'd like to calculate all the routes from every system to other systems within a single jump of JN. In other words, a road map. I only need to do that once, but it would nice if the function were speedy.
Once I have that it's a somewhat straighforward process to find the shortest path from any origin to any destination. I've been looking into so-called single-source shortest path or SSSP graph algorithms, in particular the Dijkstra algorithm, which seems to do a pretty good job.
It may be preferable to actually calculate the JN-reachable systems on an as-needed basis, in which case the pathfinding algorithm would be slowed down by overhead, but the up-front cost of invoking it would be gone.
There are also some problems I haven't shoe-horned into the algorithm yet, like:
1. How to limit possible paths to a certain jump number;
2. How to limit possible paths due to absence of refuelling facilities at a system;
3. How to force the algorithm to find a path through one or more intermediate systems (although I think this is a case of just running the algorithm multiple times, eg to go from A to C via B, find the SSSP from A to B and then the one from B to C).
