Global Grids, Part 2: Indexing the grid
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.