- 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.

- 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%.*

- 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.

- 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.

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 .

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

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

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

In fact the step space is: step space = pi/2^N * radWhich 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.12817This 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.

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

View edit of February 8, 2004 or FindPage with title or text search