How do I handle the math of hex maps?

Question

I'm having trouble calculating distances on hex-mapped worlds. The math, even at the regional scale, is difficult.

But I'm also interested in distances at the world-scale. 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.

How do such programs as "Traveller Heaven & Earth" calculate the various distances between hexes, particularly at the planet-scale (with those odd pentagons getting into the path)? 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.

Any hints on this?

Answer 1

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.

---

Here is the dual of a geodesic sphere

---

Also, please take a look at this icosahedral world map generator. Hope it helps

Answer 2

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.

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.

Answer 3

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.