gridTools

[Martin_Goliath]

Introduction

The gridTools Perl package is a collection of tools that can be used for generating hexagonal grids and making TOAW map "embryos".

The map generating process can be divided into three steps:
(1) Grid generation, where long/lat coordinates for a hexagonal grid is produced for the map region of your choice.
(2) Hex numbering, where TOAW-style (x,y)-coordinates are assigned to each hex.
(3) Map generation, in which land hexes are determined against a GIS database, and a starting point for a TOAW map in XML-format is constructed.

Details of each of these steps are described in subsequent posts. I have tried to be as objective as possible, describing both merits and draw-backs of the method. Posts will be edited to reflect new findings and clarify things.

If you find this could be useful for your upcoming scenario - please let me know what you would like to have. If time allows, I will produce a sample for you to use or discard. For those of you who would like to try it out for yourself, the rest of this post outlines what you need.

Obtaining gridTools

Acknowledgements:
The grid generation utilizes DGGRID, http://www.sou.edu/cs/sahr/dgg/, while some other algorithms use several tools of GMT, http://gmt.soest.hawaii.edu/, which is hereby acknowledged.
The method for further subdivision of a grid came about in a discussion with Bob Cross and Colin Wright (see post 10 - 23 below).

Disclaimer:
The package is provided freely "as is" - you use it at your own peril!

Download:
The gridTools zip-archive attached to this post contains the following files:

• README.txt : a text file basically containing this and associated posts.
• gridTools.pm : the gridTools Perl package
• generateGrid.pl : a Perl script that uses gridTools to generate a grid
• hexNumbering.pl : a Perl script that uses gridTools to assign TOAW (x,y) numbers to each hex in a grid generated by gridTools
• determinePlaces.pl : a Perl script that uses gridTools to assign TOAW (x,y) numbers to all places listed in a separate file. Distances between these places are also calculated
• calcDistances.pl : a Perl script that performs distance calculations
• toawMap.pl : a Perl script that uses gridTools to construct a TOAW map in XML-format from a grid numbered by gridTools
• input.pl : sample input file for gridTools with comments (Sicily @ 15 km/hex)
• test-places.inp : sample file with some placenames to be added to the map.

Dependencies:
In order to use the package, you need some additional software. They are all downloadable for free (links valid as of 2008-07-13):

• Obviously, you need to have a Perl interpreter installed. I use ActivePerl 5.10.0, which is available here: http://www.activestate.com/Products/activeperl/index.mhtml
• The grid generation uses DGGRID, which you can get here: http://www.sou.edu/cs/sahr/dgg/dggrid/dggrid.html (you want the MSDOS executable)
• The GMT generic mapping tools are available from http://gmt.soest.hawaii.edu/. Select "Download", and "GMT Windows", then download the required, as well as the two optional files.
• Finally, if you want to view PostScript grid plots that are optionally generated as a help for map planning, you will also need a PostScript viewer. GSView (built on GhostScript) is one choice, capable of exporting PostScript to PDF-format. Instructions on how to get GSView and GhostScript are available here: http://pages.cs.wisc.edu/~ghost/gsview/index.htm

[Martin_Goliath]

Grid Generation

The DGGRID program used for the grid generation constructs a so-called icosahedron-based hexagonal grid for the specified part of a globe. This grid is projected onto the globe, determining coordinates for hex centres and corners. As with all projections, there will be distortions between the mapand the reality. The particular projection used by DGGRID has some nice properties:

• The hexagons all have the same area, so all hexes represent equally large regions
• The distance between two adjacent hex centres is the same over the whole grid

There are draw-backs as well:

• An icosahedron-based grid of the whole earth will always contain twelve pentagons, equally spaced over the globe. This puts an upper limit on how large an area of the earth that can be covered by true hexagons. In practice, an area about 7000 km wide can always be covered by pure hexagons by moving the grid orientation appropriately. However, the largest possible TOAW-map with current limitations (300 x 300 hexes @ 50 km/hex) is larger than this.
• Since the grid is made up by of equal-size hexagons that cover a globe, the hex size cannot be freely specified. Instead, only specific hex sizes are available. By further subdividing the grid, the possibilities are quite numerous, but there might still be hex sizes that cannot be obtained.
• As a further comment on hex sizes, it is worth mentioning that distances between hexes on a hexagonal grid will depend on direction. A 7% discrepancy can be expected.
• As mentioned, the projected hexagons will in general be distorted. The subsequent hex numbering will still assume that they are symmetric, and it can not be ruled out that this will introduce undesirable distortions. I have not noticed any obvious deviations for the test cases I have performed so far.

The parameters needed for the grid generation are:

• The type and order of the grid. This specifies the hex size of the grid. A table of available hex sizes is appended to the sample input file input.pl.
• The grid orientation. Typically, you only have to change this when you need to get rid of pentagons in yur map region, and when you want to fine-tune the grid orientation.
• The map region of interest. Either you specify a "square" by giving the western and eastern longitude boundaries, together with the nortern and southern latitude boundaries. More general, you can specify any closed set of long/lat points, where the final point should be equal to the starting point.

Optionally, the grid generation process can produce a grid overlay on a map (the neccessary GIS data for the map is included with GMT). This plot can be useful for fine-tuning the grid orientation, etc.

Another option is to provide a file with long/lat coordinates as well as names for a number of place locations of interest. These will be added both to the grid plot and to the TOAW-map produced later on. Furthermore, a file containing a table of great-circle distances between all places within the map region can be requested. This can be useful when verifying that the distances on the map are reproduced correctly.

Example: Sicily @ 15 km/hex
Assuming that the necessary software packages (see previous post) have been downloaded and installed, you can do the grid generation for the provided Sicily example by double-clicking the file generateGrid.pl. (Be sure to check that the path specifications in input.pl coincides with the locations where you placed the various software packages on your system.) When the script is finished, a number of files has been created:

• hexes.dat : the long/lat coordinates of centres and corners for all hexes in the grid.
• hcentres.dat : long/lat for hexagon centres (this information is contained in hexes.dat, but can be useful to have in a file of its own).
• pcentres.dat : long/lat for hexagon centres (this file should be empty if you intend to proceed with the map making!)
• gridplot.ps : a plot of the grid (attached to this post)

[Martin_Goliath]

Hex numbering

When a grid has been generated, the next step is to assign TOAW (x,y)-coordinates to all hexes. TOAW has (0,0) in the upper-left corner, with the x-axis pointing to the right, and the y-axis pointing down. We are free to choose which of the six hex sides we want to coincide with the "down" direction given by the y-axis, see attached picture.

In principle, the numbering algorithm should work on any hex grid, not just one generated by DDGRID and gridTools, provided that a few formatting rules are obeyed by the data:

• The data should be given in the format used for the hexes.dat file.
• The coordinates of hex corners for a particular hex should be specified in counter-clockwise order.
• The coordinates of hex corners that are shared by two or more hexes should be identical. This is because the coordinate comparisons are done on strings, which is considerably faster in Perl than floating-point comparisons.

Example:
To continue the example in the previous post, double-clicking the file hexNumbering.pl will assign (x,y)-coordinates to the hexes in the grid. Next, double-clicking the file determinePlaces.pl will determine which hexes that correspond to the places listed in the file test-places.inp.
The following files will have been produced by the scripts:

• xy.dat : (x,y)-values for all hexes
• xyplaces.dat : (x,y)-values corresponding to given places
• distances.dat : a table of distances between given places. For this particular example, it looks like this:
  
  Great-circle distances between places within map region
  
  Messina - Palermo : 192.422 km, 13 hexes, 14.80 km/hex
  Messina - Pantelleria : 349.261 km, 22 hexes, 15.88 km/hex
  Messina - Vulcano : 56.2244 km, 3 hexes, 18.74 km/hex
  Palermo - Pantelleria : 193.216 km, 15 hexes, 12.88 km/hex
  Palermo - Vulcano : 146.745 km, 10 hexes, 14.67 km/hex
  Pantelleria - Vulcano : 320.863 km, 22 hexes, 14.58 km/hex
  
  Mean distance per hex: 15.26 +- 1.94 km/hex

[Martin_Goliath]

Map generation

Finally, it is time to construct the TOAW map. Each hex centre is compared against a GIS data base (provided together with GMT). If the hex centre is on land, the hex is considered to be a land hex. Otherwise, it is marked as water. Obviously, this is often a bit too crude: coastal cities may find themselves sitting in the brine. As stated, gridTools provides map "embryos" - a lot of map details have to be fine-tuned, not to mention adding all terrain features!

There are a few specifications available for the map generation:

• The terrain type given to all land hexes can be chosen
• Water hexes adjacent to land can be automatically set to Shallow water.
• If a file with placename locations is given, these names can be added to the correct map hexes
• The map can be cut at given x and/or y values
• The map can be offset by given amounts along the x- and y-axis. Note that several *.mml files can be combined if they are offset, as described by Bob Cross in another thread.

Example:
The final step in our example is performed by double-clicking toawMap.pl, which will produce the XML map file map.mml. In order to use the file in TOAW, open the scenario editor In the File menu, choose Load map (XML). If everything worked out, the result should look like the attached pic.

[ColinWright]

ORIGINAL: MarGol

...only specific hex sizes are available. For instance, you can have 11 km and 7.5 km hexes, but not the sizes in-between....

Now that's a little disappointing. If you mean what you say, then this program (or set of programs) cannot map at TOAW-available scales -- like 5 km per hex or 10 km per hex.

On the other hand, you go on to map Sicily at 15 km per hex, so perhaps I missed something. What TOAW scales can the program map at?

[Martin_Goliath]

ORIGINAL: ColinWright

Now that's a little disappointing. If you mean what you say, then this program (or set of programs) cannot map at TOAW-available scales -- like 5 km per hex or 10 km per hex.

The grid generation program is limited to specific hex sizes. In particular, in the interval from 1 to 100 km the following sizes are available: 1.2, 1.9, 2.0, 3.5, 3.8, 6.1, 7.5, 11, 15, 18, 30, 32, 55, 60, and 95 km. In summary, only the 15 km TOAW scale is exactly matched, and if you can accept a 10% discrepancy: 10 km (using 11 km), 20 (using 18), and 50 (using 55).

The size limitation should not be necessary when mapping a portion of the earth - it is only relevant when you want to cover the whole globe. However, the DGGRID software does not seem to allow for other sizes. I guess we have to wait for item 1.5 on the wish list (Free setting of hex size and turn interval) to be realized in order to be able to use the full potential of the method. In the meantime I might try to work out an alternate method on my own. I find the idea of using available GIS-tools for TOAW map generation quite appealing, since it offers ways to automatically get distances and place locations right from the outset.

[ColinWright]

ORIGINAL: MarGol


....I find the idea of using available GIS-tools for TOAW map generation quite appealing, since it offers ways to automatically get distances and place locations right from the outset.

...hear hear. I spent many happy hours (months?) slapping the British Isles around to get both a reasonably right shape and sufficiently accurate distances.

However, I'd rather not repeat the experience.

[desert]

ORIGINAL: ColinWright
 
..hear hear. I spent many happy hours (months?) slapping the British Isles around to get both a reasonably right shape and sufficiently accurate distances.

 
That's why I only make fantasy scenarios. [:D]

[ColinWright]

ORIGINAL: desert

ORIGINAL: ColinWright

..hear hear. I spent many happy hours (months?) slapping the British Isles around to get both a reasonably right shape and sufficiently accurate distances.

That's why I only make fantasy scenarios. [:D]

To tell the truth, I think I like map-making. I'm even ambivalent about the program we're discussing here. It'll take the challenge out of it...

[ColinWright]

ORIGINAL: MarGol

ORIGINAL: ColinWright

Now that's a little disappointing. If you mean what you say, then this program (or set of programs) cannot map at TOAW-available scales -- like 5 km per hex or 10 km per hex.

The grid generation program is limited to specific hex sizes. In particular, in the interval from 1 to 100 km the following sizes are available: 1.2, 1.9, 2.0, 3.5, 3.8, 6.1, 7.5, 11, 15, 18, 30, 32, 55, 60, and 95 km. In summary, only the 15 km TOAW scale is exactly matched, and if you can accept a 10% discrepancy: 10 km (using 11 km), 20 (using 18), and 50 (using 55).

The size limitation should not be necessary when mapping a portion of the earth - it is only relevant when you want to cover the whole globe. However, the DGGRID software does not seem to allow for other sizes. I guess we have to wait for item 1.5 on the wish list (Free setting of hex size and turn interval) to be realized in order to be able to use the full potential of the method. In the meantime I might try to work out an alternate method on my own. I find the idea of using available GIS-tools for TOAW map generation quite appealing, since it offers ways to automatically get distances and place locations right from the outset.

!

It occurs to me that if you look at the patterns hexagons make, a three-hexagon wide figure itself forms a hexagon.

It's turned 90 degrees from the direction of the original hexagon, but if one was willing to accept only the center hexagon of each such figure being precisely located, then in theory one could obtain any scale that was exactly a third of the above figures. That is, if one can map 7.5, 15, 30, and 60, it shouldn't be too hard to come up with a program that can map every third hex for 2.5 km, 5 km, 10 km, and 20 km. Together with the ability of the original program to map 15 km, that gives us all OPART values up to 20 km/hex.

[Curtis Lemay]

ORIGINAL: ColinWright
!

It occurs to me that if you look at the patterns hexagons make, a three-hexagon wide figure itself forms a hexagon.

It's turned 90 degrees from the direction of the original hexagon, but if one was willing to accept only the center hexagon of each such figure being precisely located, then in theory one could obtain any scale that was exactly a third of the above figures. That is, if one can map 7.5, 15, 30, and 60, it shouldn't be too hard to come up with a program that can map every third hex for 2.5 km, 5 km, 10 km, and 20 km. Together with the ability of the original program to map 15 km, that gives us all OPART values up to 20 km/hex.

I don't think you can actually fit that three-hex wide hexagon onto a hex grid. See the red hexes on the attached screenshot. They drift downward at an angle. Now you can fit them together as the blue hexes show. But that results in a doubling, not trippling of the hexes.

[ColinWright]

ORIGINAL: Curtis Lemay

ORIGINAL: ColinWright
!

It occurs to me that if you look at the patterns hexagons make, a three-hexagon wide figure itself forms a hexagon.

It's turned 90 degrees from the direction of the original hexagon, but if one was willing to accept only the center hexagon of each such figure being precisely located, then in theory one could obtain any scale that was exactly a third of the above figures. That is, if one can map 7.5, 15, 30, and 60, it shouldn't be too hard to come up with a program that can map every third hex for 2.5 km, 5 km, 10 km, and 20 km. Together with the ability of the original program to map 15 km, that gives us all OPART values up to 20 km/hex.

I don't think you can actually fit that three-hex wide hexagon onto a hex grid. See the red hexes on the attached screenshot. They drift downward at an angle. Now you can fit them together as the blue hexes show. But that results in a doubling, not trippling of the hexes.

Yeah...but.

What we're talking about here could be viewed as two programs. One that comes up with latitude and longitude figures for the 'super hexes' -- and one that translates these into latitude and longitude figures for every third actual hex.

What if the first program is looking at a psuedo-grid that is tilted ninety degrees from the OPART grid? This seems like it might overcome the problem you mention.

Anyway, I think the line of thought needs to be pursued to a definitive conclusion. The results of dividing by three are just too perfect to be dismissed.

[Curtis Lemay]

ORIGINAL: ColinWright
Yeah...but.

What we're talking about here could be viewed as two programs. One that comes up with latitude and longitude figures for the 'super hexes' -- and one that translates these into latitude and longitude figures for every third actual hex.

You can divide that hex up into seven hexes, each 1/3 the size of the parent hex. But when you move over to the next hex and do the same, those seven hexes don't fit together with the previous seven. And I don't see any way to make them do so. It's just geometry. The "sides" of that super hex made of those seven hexes is not a flat surface, like it's parent. It's zig-zagged, so that the next super hex can't fit to it like the parent hexes did.

[ColinWright]

ORIGINAL: Curtis Lemay

ORIGINAL: ColinWright
Yeah...but.

What we're talking about here could be viewed as two programs. One that comes up with latitude and longitude figures for the 'super hexes' -- and one that translates these into latitude and longitude figures for every third actual hex.

You can divide that hex up into seven hexes, each 1/3 the size of the parent hex. But when you move over to the next hex and do the same, those seven hexes don't fit together with the previous seven. And I don't see any way to make them do so. It's just geometry. The "sides" of that super hex made of those seven hexes is not a flat surface, like it's parent. It's zig-zagged, so that the next super hex can't fit to it like the parent hexes did.

On the one hand, I'm not sure this matters. On the other hand, I'm not sure it doesn't.

However, what we're -- or at least I -- are really interested in are valid periodic reference points. You see the 'superhexes' as having to move off on a diagonal if they are to perfectly fit. One could equally well see them as following a zig-zag line -- in which case the coordinates for the center of every other 'super hex' would still be valid.

I can go ahead and arrange the land and sea hexes of that little peninsula to my satisfaction without specific coordinates. What disturbs me is realizing either Istanbul must be 200 km too far to the west, Tunis 200 km too far to the east, or Cairo 400km too far to the south.

I may be flogging a dead horse here. Worse, I am trying to get others to flog it for me. However, I do think it should be flogged. Somehow dividing the available scales by three just yields results that are too tantalizing to be overlooked. It's like realizing there's a ten pound trout behind that boulder. Don't say there's no way to cast to it; figure out how to cast to it.

To abandon the metaphor and return to the point, if what I have noticed can somehow be exploited, we will have a way of laying out a generally accurate hex grid for any OPART scale under 25 km per hex, rotated in any direction we please.

[Curtis Lemay]

Just one more point on this. Note that the "super hex" consists of seven hexes. To actually create a valid 1/3 size hexgrid using it, it would need to consist of nine hexes. Even if the super hexes could be fit together (which they can't) they wouldn't create enough hexes.

[ColinWright]

ORIGINAL: Curtis Lemay

Just one more point on this. Note that the "super hex" consists of seven hexes. To actually create a valid 1/3 size hexgrid using it, it would need to consist of nine hexes. Even if the super hexes could be fit together (which they can't) they wouldn't create enough hexes.

[Father Colin sighs and shakes his head]

Once again, my son, you are closing your eyes to the Light. Look at your own sample: the blue hexes. If you go along either a vertical or a diagonal row, every third hex is the center of a super hex. I'm not convinced that it matters if some territory is left uncovered by the superhexes. It may be enough that their centers coincide with the center of every third actual hex: wouldn't this permit a program that would accurately give the latitude and longitude for every third hex on the actual map?

[Curtis Lemay]

ORIGINAL: ColinWright
Once again, my son, you are closing your eyes to the Light. Look at your own sample: the blue hexes. If you go along either a vertical or a diagonal row, every third hex is the center of a super hex.

Only in an alternate universe. Look again at the blue hexes. It's every other hex, not every third. As I said, the blue hex pattern could work - but it only results in a doubling of the number of hexes, not a trippling.

[ColinWright]

ORIGINAL: Curtis Lemay

ORIGINAL: ColinWright
Once again, my son, you are closing your eyes to the Light. Look at your own sample: the blue hexes. If you go along either a vertical or a diagonal row, every third hex is the center of a super hex.

Only in an alternate universe. Look again at the blue hexes. It's every other hex, not every third. As I said, the blue hex pattern could work - but it only results in a doubling of the number of hexes, not a trippling.

I am looking at the blue hexes. If I count vertically, every third hex is the center of a super hex. If I count diagonally, every third hex is the center of a super hex. It is true that if one proceeds horizontally, only one row of hexes lies between each center of a super hex.

If anything's to be made of this, it's probably best to look at hex centers without worrying about actual coverage. I remain fascinated by the fact that if we can only divide the values in this program by three, we obtain an almost complete list of TOAW values. What happens if every third hex center is mapped -- without worrying about whether the hexagons actually fit together on a TOAW field?

[Curtis Lemay]

ORIGINAL: ColinWright
I am looking at the blue hexes. If I count vertically, every third hex is the center of a super hex. If I count diagonally, every third hex is the center of a super hex. It is true that if one proceeds horizontally, only one row of hexes lies between each center of a super hex.

The blue grid I drew shows how you can halve the hex width, resulting in about 4x the number of hexes (count for yourself). You seem to be envisioning a different arrangement of the red hexes. Something like the yellow hexes in the attached. But they don't form a hexgrid. That super hex simply can't be arranged to fit together in a hexgrid pattern without the overlapping shown in with the blue hexes. It's a geometric impossibility.

[ColinWright]

ORIGINAL: Curtis Lemay

ORIGINAL: ColinWright
I am looking at the blue hexes. If I count vertically, every third hex is the center of a super hex. If I count diagonally, every third hex is the center of a super hex. It is true that if one proceeds horizontally, only one row of hexes lies between each center of a super hex.

The blue grid I drew shows how you can halve the hex width, resulting in about 4x the number of hexes (count for yourself). You seem to be envisioning a different arrangement of the red hexes. Something like the yellow hexes in the attached. But they don't form a hexgrid. That super hex simply can't be arranged to fit together in a hexgrid pattern without the overlapping shown in with the blue hexes. It's a geometric impossibility.

I think if you look at your own picture, you'll see that the yellow hexes do lie in a regular pattern, and that every group of seven yellow hexes does form a larger hexagon. More to the point, I'll go out on a limb here and bet that if you continue this pattern over a larger area, the 'superhexes' form a grid themselves.

That's all we need. Regularly spaced points of reference in a hexagonal field that can be rotated. It's irrelevant if there are unfilled interstices between the super hexes, since we won't actually be mapping on the superhexes. The superhexes would merely serve to establish accurate check points once every three hexes.

Put it this way. The point is to come up with a program that can give us accurate coordinates for every third point in the final hexagonal field -- and to do so regardless of how the field is rotated. I'm suspecting this can indeed do this.