Hex Grid Sphere

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 the same as in HexGridIcosahedron.

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.

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, for all but 6 cells.
Nearly all cells have an identical number of neighbors. The solution below achieves 6 neighbors for all but 6 cells. Those 6 cells have 4 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 +13%/-18%.

See also HexGridIcosahedron, which uses a more complicated shape to achieve better accuracy.

One solution:

Model the world as a truncated octahedron.
Each face is broken up into hexagons.
Lay hexagons along the edges.
Place squares at the corners.
There are 6 squares and 4^n - 4 hexagons, where n is an integer.

Find points recursively

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

Divide the sphere into 8 octants, using 3 great circles.
Each octant 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 6 exceptional tiles: The original 6 corners will become squares, not hexagons.

There will wind up being 4^n - 4 hexagons, and 6 squares.

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 square) have the same amount of resources.

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

Most hexagons have 6 neighbors: 1 to the north-east, 1 to the north-west, 1 to the east (more or less), 1 to the west (more or less), 1 to the south-east, and 1 to the south-west.

The hexagons due north of equatorial squares have 6 neighbors: 1 to the north, 1 to the (north of) east, 1 to the (north of) west, 1 to the south-east, 1 to the south, and 1 to the south-west.

The hexagons due south of equatorial squares have 6 neighbors: 1 to the south, 1 to the (south of) east, 1 to the (south of) west, 1 to the north-east, 1 to the north, and 1 to the north-west.

Each of the 4 equatorial squares has 4 neighbors: 1 to the north, 1 to the east, 1 to the west, and 1 to the south.

The north pole square has 4 neighbors, all to the south.

The south pole square has 4 neighbors, all to the north.

Efficiency

The hex-grid solution is much simpler than trying to calculate the locations and neighbors of almost-square tiles. That gets very ugly, very fast. It uses many floats, is hard to imagine how to project the map, and is slow (because it uses so many spherical trigonometric functions).

Whereas the hex-grid solution is amenable to addressing the tiles using integers. This is very fast, because it does NOT require any spherical trigonometric functions. In effect, the spherical world is projected onto a slightly truncated octahedron, and the tiles are located at natural spacings on the octahedron. This is similar to how the earth's oblate spheroid is projected onto a sphere in conventional cartography.

In a Civ-like game with an arbitrary world (i.e., not the map of a real planet), the hex-grid solution eliminates SphericalTrigonometry from the program.

In a Civ-like game where the world is based on a real planet (such as Earth), you do need some SphericalTrigonometry. When you are drawing the original map (that is, populating the terrain properties of the cells), you need to know the latitude and longitude of each point. Unfortunately, most of the nice straight rows of cells are not due east-west of each other -- you need to use the recursive algorithm described in the triangular variation (or the equal-area almost-triangular variation) to find the corners of the "triangles" (centers of the cells).

Differences between hexagons

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

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

Number and spacing of tiles

 Let steps = the number of moves it takes to move from the equator
             to the north pole.
 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 equator or prime meridian,
                  in radians

 iter-                 tri-                      hex area  step
 ation   N   steps   angles  hexagons  squares   (var B)   space   shape
  -1     0      0         2        1       0     pi *  4           sphere
   0     1      1         8        0       6     pi        pi/ 2   cube
   1     2      2        32       12       6     pi /  4   pi/ 4
   2     3      4       128       60       6     pi / 16   pi/ 8
   3     4      8       512      252       6     pi / 64   pi/16
         5
         6
         7
         8
         9
   9    10    512   2097152  1048572       6              pi/1024

 N - 1   N  2^(N-1)  2*4^N   4^N - 4       6    4*pi/4^N  pi/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) * 4*pi/4^N * rad^2 )
                  = sqrt ( 2 / sqrt(3) * 4*pi) / 2^N * rad
                  ~ 3.80925 / 2^N * rad

Distortion along edges of octahedron, using variation B

 In fact the step space is:
 step space       = pi/2^N  * rad

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

Which means that this row of hexagons is 21.25 % 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.2125*s)^2 + (sqrt(3)/2 * 0.825*s)^2 )
 = s*sqrt( (1.81875)^2 + (0.71447)^2)
 = s*sqrt(  3.81832  )
 = s*1.95405
 = s*1.73205*1.12817

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

We will ignore the fact that each square has two-thirds of the area of each hexagon. This affects just 6 tiles -- and can easily by compensated for, by stealing 7 % of the area of each adjacent hexagon.

Distortion at centers of octahedron faces

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

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

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.

It should also be noted that hexagonal grids have another advantage over square grids -- there's no diagonals. This means that you do not have to make a decision as to the mechanics of diagonals. In action-y games, you want diagonals to take 1.4 times as long (sqrt(2)) as straight lines, to be sure, but in strategy games this is unacceptable.

-- DanUznanski

A reasonable good solution to this problem on a square board would be this ZinmLanguage program:

 __________________________________
 |    |    |   |3->0|   |    |    |
 |____|____|___|____|___|____|____|
 |    |3->0| 2 | 2  | 2 |3->0|    |
 |____|____|___|____|___|____|____|
 |    | 2  | 1 | 1  | 1 | 2  |    |
 |____|____|___|____|___|____|____| 
 |3->0| 2  | 1 |*7 0| 1 | 2  |3->0|
 |____|____|___|____|___|____|____|
 |    | 2  | 1 | 1  | 1 | 2  |    | 
 |____|____|___|____|___|____|____|
 |    |3->0| 2 | 2  | 2 |3->0|    |
 |____|____|___|____|___|____|____| 
 |    |    |   |3->0|   |    |    |
 |____|____|___|____|___|____|____|

as long as pieces generally move at least three squares. -- JonGrover

Also, there are other kinds of grids than the truncated octahedron listed here that have hexagons and can map to the sphere: the truncated icosahedron and its variants (soccerball, buckyball C60 and C80), with 12 pentagons, and the truncated tetrahedron with 4 triangles. The one with pentagons is decidedly more spherical than the truncated octahedron.

I'm working on some analysis of the spherical world as described by these items right now... I'll probably get back to this topic tonight with a bit of research.

-- DanUznanski

Should this page be renamed to HexGridOctahedron??

See Also: GeographyExample, SphericalTrigonometry, HexGridIcosahedron, TriangleGridIcosahedron?, HexGridDisk

Note: Please do NOT ConvertSpacesToTabs on this page. It will mess up the formatting of the equations and illustrations.