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.

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  [3]
    j < m-1        s,      i+1,    j+1  [2]
  j < m-1          s,        i,    j+1  [1]
  i > 0            s,      i-1,      j  [0]
    j > 0          s,      i-1,    j-1  [5]
  j > 0            s,        i,    j-1  [4]

  i = 0
    j < n          s-1,    n-1,    n+j  [0]
      j > 0        s-1,    n-1,  n-1+j  [5]
    else j >= n    s-1,  m-j-1,    m-1  [0]
      j > n        s-1,    m-j,    m-1  [5]

  i = n-1
    j < n          s+1,  n-j-1,      0  [2]
      j = 0        SP                   [3]
      else j > 0   s+1,    n-j,      0  [3]
    j >= n         s+1,      0,    j-n  [3]
      j < m-1      s+1,      0,  1+j-n  [2]

  j = 0            s-1,    n-1,  n-1-i  [4]
    i > 0          s-1,    n-1,    n-i  [5]
  else if j = m-1  s+1,      0,  m-1-i  [2]
    i = 0          NP                   [1]
    else i > 0     s+1,      0,    m-i  [1]

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.

2 comments:

his leniency said...

(GWJ Pirate Bob here)

On indexing cells into a 2d grid, so far I haven't really viewed it as important honestly. Each cell contains a list of neighbors, yes, but beyond that it's not as critical I think. I looked up neighbors simply by going through the indices of my subdivided icosahedron mesh. Each cell knows it's center point, so distances for pathfinding to another cell can be computed by the angle between their centers. Directions, N, S, E, W, can be found with converting the center to polar coordinates and then latitude/longitude.

J. Prevost said...

Hmm. Could you go into more detail? In the context of storing information about individual cells, would you then be storing locations as a mapping between (lat × lon [× elevation]) and the information about the cell?

Part of why I wanted to go to integral indexes is simplifying that mapping. If I can distill each cell ID on a 2D grid of depth 22 to a 48-bit number (22 bits by 23 bits for each strip, and three bits to identify the strip), then I can identify cells in a 3D spherical shell as a single 64-bit number allowing for 16 bits of depth (so: approximately the surface of the Earth to an elevation difference of slightly less than that between the peak of Everest and the depths of the Marianas Trench).

In practice any single game is going to use only a very very tiny portion of the available space in the shell, but having the shell represented so clearly still allows for super simple indexable storage of information about individual cells. In particular, when I was reading around I was unable to find any very simple structures for mapping locations to data *dynamically*. The most likely suspect seems like a quadtree, simply because although it is not balanced, changes to its contents do not require structural changes to the geometry represented (like a kd-tree). However, with integral indices I can build a fast sparse array implementation tailored for 64-bit indices instead.

Some simplifications to my location-computing code may make your suggestion simpler to work with, however. (I'm still working on that, although work has prevented me from spending too much time on it. Hence my not posting further details about that, yet.)

Post a Comment