Take the 2-minute tour ×
Role-playing Games Stack Exchange is a question and answer site for gamemasters and players of tabletop, paper-and-pencil role-playing games. It's 100% free, no registration required.

Are there any freely available documents for math regarding hex maps? I'm especially searching for hex maps of whole planets. How do such programs as "Traveller Heaven & Earth" calculate the various distances between hexes?

Perhaps there is some material on this topic in classical tabletop/boardgame stuff, but I never played such games and thus have no access to such material yet.

I'm targeting icosahedral maps of planets / worlds in particular.

I'm looking for distance calculations "as the crow flies" regardless of obstacles, as opposed to the length of the most direct valid path.

Any hints on this?

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

Amit Patel has a nice blog that has a section regarding hex maps. I especially like the Isometric cube coordinate system.

Regarding icosahedrons, consider each facet to be a triangular hex map where edge hexes(FJM, NLI and BCD) are shared between two facets and corner hexes (A, E and O) are actually pentagons common to all five facets at the vertex.

    O
   M N
  J K L
 F G H I
A B C D E

The regular approaches to hexagonal distance calculations work well with this kind of map. At the vertex pentagons, continuing towards any two hex(pent?) edges opposing the edge entered is equivalent.


Edit: That's the dual of a geodesic sphere

dual of geodesic sphere


Edit #2: Stumbled upon this icosahedral world map generator. Hope it helps

share|improve this answer
    
Ah, that's great! Exactly what I want, really like the programming part. –  Martin Dec 5 '11 at 13:35
add comment

It is all to do with graph theory. You can model your hexes as nodes in a graph. The arcs will just be of fixed length with a cost of travel depending on either hex "geography". From there on, a shortest path algorithm will give you want you want. The generic case is NP hard -- aka travelling salesman -- but there are some good approximations.

Edit: As "crow fly" would mean that you have a fixed cost for each arc. This may give you more than one optimal path as they will have the same cost of travel. As an example:

 A
B C
 D

The cost of the path ABD is the same as the cost of the path ACD.

share|improve this answer
add comment

If you're talking about large hexagonal maps on spheres, there is no clean way to do this, since you cannot perfectly cover a sphere in equally-sized hexagons. (Think about the irregular patterns on a soccer ball or golf ball.) The other methods mentioned here are good for grids and graphs, but if you're trying to simply calculate distances on a sphere you need to revert to great-circle distance. If you're attempting to cover the entire Earth in 5' hex squares, for example, convert each one to a latitude and longitude and use this method. (This might not be the scope of your problem at all, though.)

Note that Heaven & Earth approximates planets as an icosahedral projection (giant d20) of a hexagonal map, as seen here, and the other methods mentioned would work well in this case.


Additionally, there is an excellent (if slightly programmer-centric) article on the subject of hex grids here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.