As I alluded to in my previous post, identifying the grid system I wanted to use was just part of the solution. In order to work effectively at this scale, I needed to have a way to concisely identify each cell, a method to quickly calculate the neighbors of a given cell, and a method to quickly calculate the position of a given cell.
The first step in any of the possible solutions is to remember that each hexagonal grid cell (and the twelve pentagonal cells) is generated by using points in a triangular mesh. Each point (or vertex) identifies an individual grid cell. The lines between these vertices (forming the faces of the triangles) connect them to the vertices which identify the adjacent grid cells. The following image illustrates this:
You may note that the triangular grid seems to “pop out” slightly above the cells. This is because my current rendering scheme draws the cells by computing each cell-vertex’s position as the average of the positions of the three surrounding triangle-vertices. Because of this, the sphere defined by the cells is slightly smaller than the sphere defined by the triangles. (The solution to this is simple: compute the average then normalize the length of the vector. But the extra computation is not worth doing at this point, and may never be.)
It’s also worth noting at this point that it’s particularly valuable to work with the triangular view of the world because most algorithms will only be interested in the cells and the connections between them, which the triangles represent wonderfully. Pretty much only the display code needs to know how to show the cells as actual hexagons.
If we take the triangular grid and flatten it, it becomes slightly easier to think about. The following image shows the flattened form of the depth-0 triangular grid (a regular icosahedron) and the flattened form of the depth-1 triangular grid (with each triangular face of the original icosahedron divided into four sub-faces). Note that when the grid is flattened, certain vertices are shown twice. In this image, I’ve chosen one position for each vertex as canonical, and drawn dotted lines connecting it to the other places the same vertex is shown.
Recall from the previous post that a grid of depth d has 10·4d + 2 cells (or triangular vertices). If you examine the image, the source of this formula becomes clear. For each of the original vertices except the north and south poles in the depth-0 grid, there are four vertices in the depth-1 grid. I’ve used colors to show this relationship.
This suggests a very obvious way to compute a unique integer for each cell. Number the icosahedron vertices 0–11, with 10 and 11 being the north and south poles, respectively. As you increase in depth, multiply the previous number by 4 and add 0–3 for the four child vertices (for the co-located child, the north-east child, the east child, and the south-east child, respectively.) Voila, problem solved. There exists a simple mapping between cells and integers.
Of course, it’s never quite that easy. I also needed an easy fast method of calculating the neighbors of each cell, and my work towards a solution to that problem led me to choose a different system.
Let me first describe the system that I’m actually using, then I will explain why it is superior for computing the list of adjacent cells. First, recall the “gray strip” in the first image I posted (showing the triangular grid on a sphere). That strip is equivalent to all of the children from putting two of the original icosahedral vertices together. For example, all of the yellow and all of the cyan nodes in the second image. If you squint carefully and maybe tilt your head a bit, you may also notice that the shape of that collection of nodes on the flattened layout is something like a rectangle.
Those five rectangular “strips” are the basis of the improved solution. The following image is a view of a single one of those five rectangular strips on a depth-2 grid laid out as a rectangle, with all of the edges shown along with adjacent cells in other strips.
Each cell is labeled with its strip (A–E), with a horizontal position i within the strip, and with a vertical position j within the strip (in addition to “NP” for the north pole and “SP” for the south pole.) The bottom right yellow cell “A30” has s = A, i = 3, and j = 0. The values of i for depth d range from 0 to 2d − 1, and the values of j range from 0 to 2d+1 − 1.
To calculate the integer for a given cell, we take s encoded in three bits, followed by i encoded in d bits, followed by j encoded in d + 1 bits. I’ve chosen to always represent the north and south poles as 0 and 1, respectively, so I then add 2 to the value from this formula.
On the face of it, this mapping is more complicated than the original recursive definition I described above. However, it turns out to be much much easier to work with when calculating adjacencies (and, luckily, positions).
To see why, notice first that all of the “internal” edges in the adjacency graph are very easy to compute—those for A25, for example, which can be had simply by adding or subtracting 1 from i and j. The remaining “special-case” edges are all along the border of the graph, and those fall into a handful of regular patterns. For example, in the “north-east” direction (labeled 2 in the image) from A07–A37, each cell is adjacent to a sister-cell on side “B”. In fact, there’s a simple formula we can use to compute the adjacency in direction 2 along that border: s’ = s + 1, i’ = 0, j’ = 7 - i. There are similar simple rules for all of the other borders.
With this representation of the cells as integers, it is very easy to determine if a cell is inside the rectangle or on a border, it is very easy to determine which border it is on, and it is very easy to calculate the numeric representation of the cells on the other side of that border. With the recursive base-4 representation, sadly, it’s not nearly so easy. (For example, in the base-4 representation, the cells on the border where j = 7 would be those cells in which every other bit of the integer representation was 1.)
So, given a cell position s, i, j, with the length of the short side n = 2d and the length of the long side m = 2d+1, you can calculate the adjacent cells with the following system of rules:
i < n-1 s, i+n, j  j < m-1 s, i+1, j+1  j < m-1 s, i, j+1  i > 0 s, i-1, j  j > 0 s, i-1, j-1  j > 0 s, i, j-1  i = 0 j < n s-1, n-1, n+j  j > 0 s-1, n-1, n-1+j  else j >= n s-1, m-j-1, m-1  j > n s-1, m-j, m-1  i = n-1 j < n s+1, n-j-1, 0  j = 0 SP  else j > 0 s+1, n-j, 0  j >= n s+1, 0, j-n  j < m-1 s+1, 0, 1+j-n  j = 0 s-1, n-1, n-1-i  i > 0 s-1, n-1, n-i  else if j = m-1 s+1, 0, m-1-i  i = 0 NP  else i > 0 s+1, 0, m-i 
The number in square brackets after each rule indicates in which direction that adjacent cell lies. Note that I explicitly chose the way I laid out my “rectangle” such that cells A00 and A04, which have only five adjacent cells, are missing a cell in direction 5. That way, each cell is adjacent to cells in directions 0–4, and a handful are missing a cell in the last direction 5.
Next time: Computing the physical locations of the cells.