Hex Grid Icosahedron

Problem Overview

Let's model the real world (literally). How would you make a reasonably spherical map for a simulation of the real world? In effect, this is a spherical finite-element simulation.

The use cases in this example are subtly different from those in the original GeographyExample. The biggest difference is that they are flexible -- if it is "too hard" to implement something exactly, we will settle for a reasonable compromise.

The use cases in this example are the same as in HexGridSphere, but subtly different from those in TriangleGridIcosahedron?. Both the hex grid and triangle grid solutions have similar errors, because the hex grid solutions are derived from the triangle grid solutions. The biggest differences are:

the hex grid problems require more than 3 sides per cell
the triangle grid problems insist every cell have the same number of neighbors.

Ever play "Civilization"? It is a wonderful game, but it's on a rectangular map. The north pole is as wide as the equator. We want a map that's spherical enough to allow ICBMs to change who can attack who by just going over a pole. We still want the map to be a grid, like the original game. That's the big UseCase. It inherits an untold number of use cases from "Civilization".

Some attainable goals:

The map is made of cells.
The user can navigate from cell to cell.
The neighbors of a cell are deterministic.
Given the location of a cell, you can determine how many neighbors it has, which cells those neighbors are, and where those neighbors are.
Each cell has equal resources for purposes of the game, except where the game chooses to award bonuses or penalties.
The cost (in time and resources) to move between neighboring cells is identical for purposes of the game, except where the game chooses to award bonuses or penalties.
All cells have 4 or more neighbors.
All cells have 10 or fewer neighbors.
There are no teleport points that jump to a point far away on the sphere.

Some goals to strive for, where coming close is good enough:

Nearly all cells have close to the same area as each other in the real world. (+/- 15% is considered very good.) This makes the "equal resources" rule plausible. The solution below is exactly equal-area, except that the areas of 12 cells are fudged.
Nearly all cells have an identical number of neighbors. The solution below achieves 6 neighbors for all but 12 cells. Those 12 cells have 5 neighbors.
The distances between neighboring cells is fairly uniform. (+/- 15% is considered very good.) This makes the "equal travel time" / "equal travel expense" rule plausible. The solution below achieves +5%/-9%.

See also HexGridSphere, which uses a simpler shape (an octahedron), but has worse distortions.

One solution:

Model the world as a truncated icosahedron.
Each face is broken up into hexagons.
Lay hexagons along the edges.
Place pentagons at the corners.
There are 12 pentagons and 2.5*(4^N) - 10 hexagons, where n is an integer.

Find points recursively

The centers of the hexagons (and pentagons) correspond to the points on a sphere found using the following recursive algorithm:

Divide the sphere into 20 equilateral triangles.
Each equilateral triangle is a spherical triangle, with 3 sides.
Find the midpoint of each side.
Draw a (possibly kinked) line connecting the adjacent midpoints. These division methods are illustrated below.
- Variation A: Don't kink the lines. Draw the lines along great circle routes.
- Variation B: Kink the lines, so that each of the 4 resulting shapes has an equal area. Each kinked line has 2 equal-length arcs of great circles, connected at the new midpoint.
Repeat Steps 3-4 until you have enough points.

Hexagonal Tiles

To make a map with hexagonal tiles, start by making a map with "triangular" tiles, using either variation A or variation B. Put the center of each hexagonal tile at a corner of six "triangular" tiles. Allocate one-third of the area of each "triangular" tile to each hexagon. So far, all of this can be done in your mind's-eye, or using pencil-and-paper. We do not need any code yet.

There will be 12 exceptional tiles: The original 12 corners will become pentagons, not hexagons.

There will wind up being 2.5*(4^N) - 10 hexagons, and 12 pentagons.

Tile sizes and neighbors

The simplest way of dealing with the equal-area problem is to ignore it -- assume that all tiles (whether hexagonal or pentagonal) have the same amount of resources.

For practical purposes, every tile is the same distance from each of its neighbors.

Differences between hexagons

When viewed on the truncated icosahedron, the hexagons are not "lopsided". (Although some of them straddle edges of the icosahedron, and so are rotated.)

When viewed on a sphere, the hexagons are lopsided -- most of them are not congruent to each other.

For purposes of building a Civ-like game, it is adequate to build the game on the truncated octahedron -- the flaws in the spherical model can be ignored. The truncated octahedron model satisfies the "polar orbital" and "Northwest passage" use cases.

Illustration of Variation A

 The Variation A splits up a triangle like this,
 where each point is the midpoint of a side,
 and each "straight" side is an arc of a great circle.

 This does not guarantee that the triangles will have equal areas.
 The outer triangle ABC was made in the previous iteration;
 the inner triangle XYZ is being created in this iteration.

 AX and XB are colinear (by construction).
 AY and YC are colinear (by construction).
 BZ and ZC are colinear (by construction).

 The midpoint of the new sides falls halfway along the great circle arc.
 For example, half-way between X and Y.


 . A___________________________X___________________________B
 . |   __,,--~~^`  | __,,--~~^`
 . | __,,--~~^`       |       __,,--~~^`
 ._Y,~~^`______________________Z,--~~^`
 . |   __,,--~~^`Variation A
 . | __,,--~~^`not kinked
 . C,~~^`not equal-area

 .

Illustration of Variation B

 Variation B splits up each shape like this.
 In this example, CYAXBZ was made in the previous iteration. 
 YpXqZr will be made in this iteration.

 AX and XB are great circle arcs, but are NOT colinear
 (except in the very first iteration). 
 Likewise, AY and YC are not necessarily colinear, 
 and BZ and ZC are not necessarily colinear.

 Choose Point p such that
 with pX being a great circle arc,
 and pY being another great circle arc,
 the area of the shape YAXp is exactly one-quarter
 of the area of the shape CYAXBZ.
 Choose points q and r similarly. 

 . A___________________________X___________________________B
 . |   __,,--~~^`  | __,,--~~^`
 . | __,,--~~p'       q       __,,--~~^`
 ._Y,~~^`________r_____________Z,--~~%`
 . |   __,,--~~^`Variation B
 . | __,,--~~^`kinked
 . C,~~^`equal-area

Arc-length of an icosahedron edge

The arc-length of an icosahedron edge equals the AngleBetweenDodecahedronFaces.

      = arccos(tan(18°)/tan(36°))
      ~ 63.435°
      ~  1.10715 rad

Number and spacing of tiles

 Let steps = the number of moves it takes to move from one pentagonal tile
             to a "nearby" pentagonal tile.
 Let hex area (var B) = area of each "hexagon", 
                        calculated using variation B,
                        in square radians.
 Let step space = distance between centers of the hexagons
                  along the shortest path between "nearby" pentagonal tiles,
                  in radians

 iter-                 tri-            pent-    hex area  step
 ation   N   steps   angles  hexagons  agons    (var B)   space    shape
  -1     0      0         5        _      0     pi * 1.6  1.11*2   sphere
   0     1      1        20        0     12     pi * 0.4  1.11     dodecahedron
   1     2      2        80       30     12     pi / 10   1.11/2
   2     3      4       320      150     12     pi / 40   1.11/4
   3     4      8      1280      630     12     pi /160   1.11/8
         5
         6
         7
         8
         9
   9    10    512   5242880  2621430     12    pi/655360  1.10715 / 512

 N - 1   N  (2^N)/2  5*4^N (4^N)*5/2-10  12   pi*1.6/4^N  1.10715*2/(2^N)

Area and spacing of flat, regular hexagons

 The distance between neighboring flat, regular hexagons is:
 distance = sqrt(3) * side

 The area of a flat, regular hexagon is:
 area = 6 * (1/2) * side * sqrt(3) / 2 * side
      = 3 * sqrt(3) / 2 * side^2
      =     sqrt(3) / 2 * 3 * side^2
      =     sqrt(3) / 2 * distance^2

 So that:
 distance^2 = 2 / sqrt(3) * area
 distance   = sqrt ( 2 / sqrt(3) * area )

 For the hex area (variation B), we therefore expect an average
 distance between neighboring hexagons
 (in the limit as N -> infinity, so that each hexagon is nearly flat):
 average distance = sqrt ( 2 / sqrt(3) * area )
                  = sqrt ( 2 / sqrt(3) * pi*1.6/4^N * rad^2 )
                  = sqrt ( 2 / sqrt(3) * pi*1.6) / 2^N * rad
                  = 2.409182 / 2^N * rad

Distortion along edges of icosahedron, using variation B

 In fact the step space is:
 step space       = arccos(tan(18°)/tan(36°))/2^N
                  = 1.10715*2/(2^N) * rad 
                  = 2.2143   / 2^N  * rad

Which means the step space is 8.1 % smaller than we expect based on the area of the "hexagons".

Which means that this row of hexagons is 8.8 % wider than we expect based on the area of the "hexagons".

Let s = expected hexagon side length, based on the area of the "hexagons". Based on the area of the "hexagons", we expect the distance between the center of a "hexagon" in this row and the center of a "hexagon" in an adjacent row to be

   sqrt( (1.5*s)^2 + (s*sqrt(3)/2)^2)
 = s*sqrt(  2.25   +      0.75  )
 = s* sqrt(3)

Assuming the "hexagons" are uniformly distorted, the distance between the center of a "hexagon" in this row and the center of a "hexagon" in an adjacent row is:

 = sqrt( (1.5 * 1.088*s)^2 + (sqrt(3)/2 * 0.9191*s)^2 )
 = s*sqrt( (1.63202)^2 + (0.79597)^2)
 = s*sqrt( (2.66348)^2 + (0.63357)^2)
 = s*sqrt(  3.29705  )
 = s*1.81578
 = s*1.73205*1.04834

This implies that the distance between the centers of this row of hexagons and the centers of the adjacent row of hexagons is 4.8 % greater than we expect based on the area of the "hexagons".

We will ignore the fact that each pentagon has five-sixths of the area of each hexagon. This affects just 12 tiles -- and can easily by compensated for, by stealing 2.8 % of the area of each adjacent hexagon.

Distortion at centers of icosahedron faces

AnswerMe: Does variation B create kinked or unkinked triangles at the centers of the icosahedron faces? (In the limit as N goes to infinity.)

If variation B creates unkinked triangles at the centers of the icosahedron faces, there will be no distortion of the hexagons there.

Known uses:

See http://www.raze.org/traveller/worldmap.pdf for an example of this - Traveller, an old ScienceFiction RolePlayingGame, has been using this system for mapping worlds for some time.

Alternative Patterns:

There is also the GordianKnot approach, which is to not use tiles; rather, the map is continuous (as in Harpoon). Of course, this makes most of the detailed mechanics of the game different, but the intent, and so the feel of the game, can be preserved.

Another option is to divide the sphere, but not necessarily into a regular array of similar pieces. For strategy games countries, duchies, and the like make great irregular pieces.

See also: HexGridSphere, GeographyExample, TriangleGridIcosahedron?, SphericalTrigonometry, AngleBetweenDodecahedronFaces